“Before you speak, listen. Before you write, think. Before you spend, earn. Before you invest, investigate. Before you criticize, wait. Before you pray, forgive. Before you quit, try. Before you retire, save. Before you die, give.”

Thursday, April 7, 2011

Problem 14 Collatz Ruby vs. Java

Finally after joining the Euler club I have solved the Collatz problem. As it turns out this problem cannot be proven mathematically .. and some mathematicians went nuts trying to prove it.
For me it is intuitively simple .. you divide more than you multiply and that's that.
Anyway I have spent almost 3h on this problem 20m writing a solution in Ruby and ... 2h 30m running it.
On my home machine I have a Ruby 1.8.7 on Windows 7 environment and my computer a Core i7 860 8GB RAM machine (good enough I would say). I gave up at around 1 AM while it was half done.
Here is the code.

def chain_collatz(n,cache)
chain_length=1
puts "-> #{n}"
if n==1
return chain_length

else
if cache[n]!=nil
puts "cache_hit"
chain_length+=cache[n]
return chain_length
end

if n%2==0
n=n/2
else
n=3*n+1
end

chain_length+=chain_collatz(n,cache)
cache[n]=chain_length
return chain_length
end


end

#puts chain_collatz(10100,cache)
#puts "cache"
#puts cache.keys
cache=Hash.new
def get_number(n,cache)
max_chain_length=1
vnumber=13
max_number=1
for i in 13..n
chain_length=chain_collatz(i,cache)
max_number=i if chain_length>max_chain_length
max_chain_length = chain_length if chain_length > max_chain_length

number=i
puts "Done with number #{number}"
end

return max_number
end

puts get_number 1000000,cache


After a lot of pain it ran and gave the correct result. Found it only this morning.
After having the problem solved I rewrote it in Java to see whether I could have it any faster:
The result?

import java.util.HashMap;
import java.util.Map;

public class Collatz {
public static void main(String args[]) {
Map m = new HashMap();
Collatz collatz = new Collatz();
long startTime =System.currentTimeMillis();
System.out.println(collatz.getMaxCollatzTo(1000000l, m));
long endTime =System.currentTimeMillis();
System.out.println (" Execution took" +(endTime-startTime) +" milisseconds");



}

public Long chainCollatz(Long number, Map map) {
Long chainLength = 1l;
if (number == 1) {
return 1l;
} else {
if (map.containsKey(number)) {
// System.out.println("Cache hit" + number);
chainLength += map.get(number);
return chainLength;
}
if (number % 2 == 0) {
number = number / 2;
} else {
number = 3 * number + 1;
}
chainLength += chainCollatz(number, map);
map.put(number, chainLength);
return chainLength;
}

}

public Long getMaxCollatzTo(Long number, Map map) {
Long maxChainLength = 1l;
Long maxChainForNumber = 1l;
for (Long i = 13l; i < number; i++) {
Long chainLength = chainCollatz(i, map);
if (chainLength > maxChainLength) {
maxChainLength = chainLength;
maxChainForNumber = i;
}
// System.out.println("Done with "+i);
}
return maxChainForNumber;
}

}


The Java code took only 50 seconds to run.

Anyway puzzled by this I started optimizing the code in both Ruby and Java .. removing all but essential console outputs.
Finally I got to test it on a Linux OS with similar processing power (Ruby implementation in Windows really sucks I think).
Final result.
Ruby 1.8.7 11.7 seconds
Java 6(1.6.0.22) 1.471 seconds
Tested also with ruby 1.9 and got it down to 3 seconds .
This puts Java on top of my list for Project Euler problems and makes me question the ability of Ruby to run unoptimized code.

But still for prototyping it's great.