196b781eef85b7ce609fd12234cc1f39

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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 !

0f8ba0cdebc6938f4cd0601aeef21621

jes5199

April 6, 2008, April 06, 2008 00:19, permalink

No rating. Login to rate!

slightly faster, caches more data

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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

Your refactoring





Format Copy from initial code

or Cancel