# lonelywolf 's den

“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=1puts "-> #{n}"if n==1 return chain_lengthelse 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_lengthendend#puts chain_collatz(10100,cache)#puts "cache"#puts cache.keyscache=Hash.newdef get_number(n,cache)max_chain_length=1vnumber=13max_number=1for 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}"endreturn max_numberendputs 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.