require 'benchmark'
def euler_chain_size(start)
length = 0
while start > 1
start = start%2 == 0 ? start/2 : 3*start+1
length += 1
if @chains.has_key?(start)
length += @chains[start]
break
end
end
length
end
@chains = {}
max_chain_size = 0
max_chain_start = 1
Benchmark.bm do |x|
x.report do
1.upto(1000000) do |i|
chain_size = euler_chain_size(i)
@chains[i] = chain_size
if chain_size > max_chain_size
max_chain_size = chain_size
max_chain_start = i
end
end
end
puts "(#{max_chain_start}, #{max_chain_size})"
end
Refactorings
No refactoring yet !
jes5199
April 6, 2008, April 06, 2008 00:19, permalink
No rating.
Login to rate!
slightly faster, caches more data
require 'benchmark'
def operation(n)
return n%2 == 0 ? n/2 : 3*n+1
end
def recursive(hash, n)
hash[n] or hash[n] = 1 + recursive(hash, operation(n) )
end
chains = {}
max_chain_size = 0
max_chain_start = 1
Benchmark.bm do |x|
x.report do
chains[1] = 1
2.upto(1000000) do |i|
chain_size = recursive(chains, i)
if chain_size > max_chain_size
max_chain_size = chain_size
max_chain_start = i
end
end
end
puts "(#{max_chain_start}, #{max_chain_size})"
end
tyranarchy.myopenid.com
July 24, 2008, July 24, 2008 07:50, permalink
No rating.
Login to rate!
From the euler forums
array = []
(1..1_000_000).each do |x|
sum = 0
while x != 1
sum += 1
if x % 2 == 0
x = x / 2
else
x = (3 * x) + 1
end
end
array << sum
end
puts array.index(array.max) + 1
The problem description is here: http://projecteuler.net/index.php?section=problems&id=14
My interest was sparked by: http://diditwith.net/2008/04/03/ApplesAndOranges.aspx