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.
