class ScalaReversible(max:Int){

import java.lang.Character._

lazy val numReversible = (11 to max).filter(reversible(_)).size

private

def reverse(n:Int)=n + parseInt(n.toString.reverse)

def allOdd(n:Int) = n.toString.map(digit(_,10)).forall(_ % 2 == 1)

def reversible(n:Int) = allOdd(reverse(n))

}

## Wednesday, May 20, 2009

### JavaOne Talk: Scala Reversible Numbers

### JavaOne Talk: Python Reversible Numbers

class PyReversible(object):

__slots__ = ['max','numReversible']

def __init__(self, max):

self.max = max

self.numReversible = self.countReversible()

def countReversible(self):

return len([i for i in xrange(11,self.max+1) if self.reversible(i)])

def allOdd(self,n):

for ch in str(n):

if int(ch) % 2 != 1:

return False

return True

def reverse(self,n):

return n + int(str(n)[::-1])

def reversible(self,n):

return self.allOdd(self.reverse(n))

### JavaOne Talk: Ruby Reversible Numbers

class RubyReversible

def initialize(max)

@max = max

@numReversible = nil

end

def allOdd(n)

digits = n.to_s.split(//)

digits.length == digits.map{|c| c.to_i}.select{|i|

i % 2 == 1}.length

end

def reverse(n)

n + n.to_s.reverse.to_i

end

def reversible(n)

allOdd(reverse(n))

end

def countReversible()

@numReversible ||= (11..@max).select{|i|

reversible(i)}.length

@numReversible

end

end

### JavaOne Talk: Groovy Reversible Numbers

public class GroovyReversible {

final Integer max

final Integer numReversible = 0

public GroovyReversible(max){

this.max = max

this.numReversible = this.countReversible()

}

def countReversible(){

numReversible ?: (11..max).findAll{reversible(it)}.size()

}

def reversible(n){

allOdd(reverse(n))

}

def allOdd(n){

n.toString().toList().collect {it.toInteger()}.every{it % 2 == 1}

}

def reverse(n){

n + n.toString().toList().reverse().join().toInteger()

}

}

### JavaOne Talk: Reversible Numbers

public class Reversible {

final int max;

final int numReversible;

public Reversible(int max){

this.max = max;

this.numReversible = this.countReversible();

}

private int countReversible(){

if (numReversible > 0){

return numReversible;

}

int cnt = 0;

for (int i=11;i<=max;i++){

if (reversible(i)) {

cnt++;

}

}

return cnt;

}

private boolean reversible(int n){

return allOdd(reverse(n));

}

private boolean allOdd(int n){

while (n > 0){

int remainder = n % 2;

if (remainder == 0) return false;

n = n / 10;

}

return true;

}

private int reverse(Integer n){

char[] digits = n.toString().toCharArray();

char[] rev = new char[digits.length];

for (int i=digits.length-1;i>=0;i--){

rev[i] = digits[digits.length -i-1];

}

return n + Integer.parseInt(String.valueOf(rev));

}

}

### JavaOne Talk: Scala Word Sort

class ScalaWordSort(fileName:String){

lazy val sortedWords = {

Source.fromFile(dataFile).getLines.foreach(_.split(" ").foreach(words ::= _))

words.sort(_.toLowerCase < _.toLowerCase)

}

private

val dataFile = new File(fileName)

var words:List[String] = Nil

}

### JavaOne Talk: Python Word Sort

class PyWordSort(object):

def __init__(self, fileName):

print "init " + fileName

self.dataFile = open(fileName)

self.words = []

def sortedWords(self):

if len(self.words) == 0:

for line in self.dataFile:

for word in line.split():

self.words.append(word)

self.words.sort(lambda w,w1: cmp(w.lower(), w1.lower()))

return self.words

### JavaOne Talk: Ruby Word Sort

class RubyWordSort

def initialize(fileName)

@dataFile = File.new(fileName)

@words = Array.new

end

def sortedWorts

if (@words.length == 0)

@dataFile.each_line{ |line| line.split(' ').each{ |word| @words << word}}

@words = @words.sort{ |w,w1| w.upcase <=> w1.upcase }

end

@words

end

end

### JavaOne Talk: Groovy Word Sort

public class GroovyWordSort {

File dataFile

List words = []

public GroovyWordSort(fileName){

dataFile = new File(fileName)

}

def sortedWords(){

if (!words){

dataFile.eachLine{it.tokenize().each {words.add(it) }}

words = words.sort{w,w1 -> w.toLowerCase() <=> w1.toLowerCase()}

}

words

}

}

### JavaOne Talk: Word Sort

import java.io.*;

import java.util.*;

public class WordSort {

private final File dataFile;

private final List<String> words;

public WordSort(String fileName){

dataFile = new File(fileName);

words = new ArrayList<String>();

}

public List<String> getSortedWords(){

if (words.size() > 0){

return words;

}

try {

BufferedReader reader = new BufferedReader(new FileReader(dataFile));

try{

String line;

while ( (line = reader.readLine()) != null){

for (String string : line.split(" ")){

words.add(string);

}

}

} finally {

reader.close();

}

Collections.sort(words, new Comparator<String>(){

public int compare(String s, String s1) {

return s.toLowerCase().compareTo(s1.toLowerCase());

}

});

return words;

} catch (IOException e) {

throw new RuntimeException(e);

}

}

}

## Monday, May 18, 2009

### JavaOne Talk: Fan Prime Sieve

Note: This solution is courtesy of Mr. Fan himself, Brian Frank. Thanks Brian!

class Primes {

Int[] primes := Int[,]

Int size

new make(Int n) {

size = n

primes.capacity = n

init

}

private Void init() {

i := 2

max := calcSize

nums := Bool[,]

nums.fill(true, max)

while (i < max && primes.size < size) {

p := i

if (nums[i])

{

primes.add(p)

j := 2*p;

while (j < max - p) {

nums[j] = false

j += p;

}

}

i += 1;

}

}

Int last() { primes.last }

private Int calcSize() {

max := 2

while ((max.toFloat/max.toFloat.log).toInt < size && max < 0x7fff_ffff && max > 0) {

max *=2; // memory inefficient, but fast

}

return max;

}

}

## Saturday, May 09, 2009

### JavaOne Talk: Scala Prime Sieve

import java.lang.Integer._

import java.lang.Math._

import scala.collection.mutable.ArrayBuffer

class ScalaPrimes(val size:Int){

val primes = new ArrayBuffer[Int]

var cnt = 0

init

def last = primes(primes.size - 1)

private

def init {

var i = 2

val max = calcSize

val nums = new ArrayBuffer[Boolean]

for (i<-0 until max) nums += true

while (i < max && cnt < size){

val p = i

if (nums(i)){

primes += p

cnt += 1

(p until max/p).foreach((j) => nums.update(p*j,false))

}

i += 1

}

}

def calcSize = {

var max = 2

while ( (max/log(max)) < size && max < MAX_VALUE && max > 0) {

max *= 2

}

max

}

}

### JavaOne Talk: Python Prime Sieve

from math import log

import sys

class PyPrimes(object):

__slots__ = ['cnt','primes','size']

def __init__(self,n):

self.primes = n*[0]

self.cnt = 0

self.size = n

i = 2

max = self.calcSize()

nums = max*[True]

while i < max and self.cnt < self.size:

p = i

if nums[i]:

self.primes[self.cnt] = p

self.cnt += 1

for j in xrange(p, max/p):

nums[p*j] = False

i+= 1

def calcSize(self):

max = 2

while max/log(max) < self.size:

max = max *2 # this makes the sieve too big, but fast

return max

def last(self):

return self.primes[self.cnt - 1]

## Tuesday, May 05, 2009

### JavaOne Talk: Ruby Prime Sieve

class RubyPrimes

attr_accessor :cnt, :primes

def initialize(n)

@primes = Array.new(n,0)

@cnt = 0

i = 2

max = calcSize

nums = Array.new(max,true)

while (i < max && @cnt < @primes.length)

p = i

if (nums[i])

@primes[@cnt] = p

@cnt += 1

(p .. (max/p)).each{ |j| nums[p*j] = false }

end

i += 1

end

end

def calcSize

max = 2

max = max * 2 while ( max/Math.log(max) < @primes.length)

max

end

def last

@primes[@cnt -1]

end

end

### JavaOne Talk: Groovy Prime Sieve

public class GroovyPrimes {

int cnt = 0

final def primes = []

final int size

public GroovyPrimes(int n){

size = n

init()

}

int last() {

primes[cnt-1]

}

private void init(){

int i = 2

int max = calcSize()

def nums = [true]*max

while (i < max && primes.size() < size) {

int p = i

if (nums[i]) {

primes << p

(p..(max/p)).each{ j-> if (p*j < max) nums[p*j] = false}

}

i += 1

}

}

private int calcSize(){

int max = 2

while ((max / Math.log(max)) < size &&

max < Integer.MAX_VALUE && max > 0) {

max *= 2

}

max

}

}

### JavaOne Talk: Being Less Efficient

import java.util.List;

import java.util.ArrayList;

public class Primes {

final private List<Integer> primes;

private final int size;

public Primes(int n){

size = n;

primes = new ArrayList<Integer>(n);

init();

}

private void init(){

int i=2;

int max = calcSize();

List<Boolean> nums =

new ArrayList<Boolean>(max);

for (int j=0;j<max;j++){

nums.add(true);

}

while (i < max && primes.size() < size){

int p = i;

if (nums.get(i)){

primes.add(p);

int j = 2*p;

while (j < max - p){

nums.set(j,false);

j += p;

}

}

i += 1;

}

}

public int last(){

return primes.get(primes.size()-1);

}

private int calcSize(){

int max = 2;

while ((max/Math.log(max)) < size &&

max < Integer.MAX_VALUE && max > 0){

max *=2;

}

return max;

}

}

## Sunday, May 03, 2009

### JavaOne Talk: Prime Sieve

I am not too interested in significantly different ways to solve these problems. For example, the first algorithm is a prime sieve. So I would not be interested in somebody letting me know that there are other ways to generate primes besides a sieve. However, I am interested in finding mistakes in my implementations. I will not claim to be an expert in any of these languages -- in fact I have been learning two of the languages, Fan and Clojure, specifically for this talk -- so there is a good chance that I did screw something up. Even in the languages that I'd like to think I am pretty good at (including Java), I figure there is always a good chance of me doing something screwy there too. So without further ado, here is my prime sieve in Java.

import java.util.Arrays;

// calculates the first n primes

public class Primes {

final private int[] primes;

private int cnt = 0;

public Primes(int n){

primes = new int[n];

init();

}

private void init(){

int i=2;

int max = calcSize();

boolean[] nums = new boolean[max];

Arrays.fill(nums, true);

while (i < max && cnt < primes.length){

int p = i;

if (nums[i]){

// add it to the list of primes

primes[cnt++] = p;

int j = 2*p;

// remove all the multiples of the prime

while (j < max - p){

nums[j] = false;

j += p;

}

}

i += 1;

}

}

public int last(){

return primes[cnt-1];

}

// calculates number of integers needed to find n primes

private int calcSize(){

int max = 2;

while ((max/Math.log(max)) < primes.length && max < Integer.MAX_VALUE && max > 0){

max *=2; // memory inefficient, but fast

}

return max;

}

}

Subscribe to:
Posts (Atom)