From: Brian Adkins <lojicdotcom@...>
Date: 2007-09-11T10:10:06+09:00
Subject: Re: Solving the Zurg puzzle in Ruby

I was curious about efficiencies, so to stress the program a bit more,
I added two more 'toys':

:foo => 30, :bar => 35

With the additional toys, my original program took 32.2s, adding the
blocks/yields to avoid too much precomputation only brought it down to
31.9s. I tested Paul's original program and it took 116s.

None of the programs find a solution since I left the time at 60, and
none are pruning, so they compute the whole candidate space. I
wouldn't expect a ~4x difference between the solutions. If anyone has
insight from the code or profile output below, I would appreciate it.

Here's my profile output (top 10):

  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
 16.94     6.27      6.27    11015     0.57     2.02  Range#each
 16.32    12.31      6.04    10230     0.59     1.12
Object#execute_move
 12.75    17.03      4.72    21245     0.22     1.33
Object#combinations
 11.05    21.12      4.09    31477     0.13     6.94  Array#each
  7.92    24.05      2.93    98813     0.03     0.03  Hash#[]
  6.73    26.54      2.49    10231     0.24    23.35  Object#play_game
  5.81    28.69      2.15    15334     0.14     0.19  Array#collect
  4.22    30.25      1.56     5911     0.26    39.85
Object#each_state
  2.86    31.31      1.06    36579     0.03     0.03  Fixnum#-
  2.59    32.27      0.96    36220     0.03     0.03  Array#+

Here's Paul's profile output (top 10):

  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
 20.65    14.90     14.90    50276     0.30    15.62  Array#each
 11.99    23.55      8.65    30240     0.29     1.08  Move#cost
  8.08    29.38      5.83    30870     0.19     0.30  Struct#hash
  7.89    35.07      5.69    30240     0.19     0.38  Array#collect
  5.68    39.17      4.10    47520     0.09     0.12  Kernel.send
  4.88    42.69      3.52    30240     0.12     0.17  Symbol#to_proc
  4.60    46.01      3.32    92610     0.04     0.04  Kernel.hash
  4.34    49.14      3.13    30240     0.10     0.21  Enumerable.max
  3.85    51.92      2.78    10231     0.27    51.66
SearchProblem#step
  3.27    54.28      2.36     5911     0.40    81.93
State#each_successor