From: Dominik Bathon <dbatml@...>
Date: 2006-01-03T01:24:44+09:00
Subject: Re: [SOLUTION] Numeric Maze (#60)

On Mon, 02 Jan 2006 08:25:08 +0100, J. Ryan Sobol <ryansobol@gmail.com>  
wrote:

> $ time ./quiz.rb 22222 99999
> [22222, 22224, 11112, 5556, 2778, 2780, 1390, 1392, 696, 348, 174, 87,  
> 89, 91, 93, 95, 97, 194, 388, 390, 780, 1560, 1562, 3124, 6248, 12496,  
> 12498, 24996, 24998, 49996, 49998, 99996, 199992, 199994, 99997, 99999]
>
> real    0m2.098s
> user    0m1.868s
> sys     0m0.091s
>
> Not faster than Dominik's, but still pretty fast.  Perhaps my 1.33 Ghz  
> G4 and 768 MB of RAM is holding my back?  :)

It actually is faster than my version:

$ time ruby ryan_org.rb 22222 99999
[22222, 22224, 11112, 5556, 2778, 2780, 1390, 1392, 696, 348, 174, 87, 89,  
91, 93, 95, 97, 194, 388, 390, 780, 1560, 1562, 3124, 6248, 12496, 12498,  
24996, 24998, 49996, 49998, 99996, 199992, 199994, 99997, 99999]

real    0m1.197s
user    0m1.138s
sys     0m0.026s

(Pentium M 1.5)

> Although this is one of many BFS algorithms posted, I'd really  
> appreciate some feedback on my implementation.  Especially in regards to  
> potential speed ups, missed opportunities for ruby idioms, and  
> additional optimizations to the adjacency_list method.

Here is a patch that speeds it up a bit:

--- ryan_org.rb 2006-01-02 16:47:20.000000000 +0100
+++ ryan.rb     2006-01-02 16:47:16.000000000 +0100
@@ -1,5 +1,5 @@
  class Integer
-  attr_reader :distance, :discovered
+  attr_reader :parent

    def odd?
      self % 2 != 0
@@ -15,9 +15,7 @@
    end

    def visit!(parent = nil)
-    @discovered = true
      @parent = parent
-    @distance = parent ? parent.distance + 1 : 0
    end

    def path_from(start)
@@ -40,7 +38,7 @@
    queue = [start]
    queue.each do |vertex|
      vertex.adjacency_list(roof).each do |child|
-      unless child.discovered
+      unless child.parent
          child.visit!(vertex)
          return target.path_from(start) if target == child
          queue.push(child)

It basically avoids some instance variable sets and removes distance,  
which is unused.

$ time ruby ryan.rb 22222 99999
[22222, 22224, 11112, 5556, 2778, 2780, 1390, 1392, 696, 348, 174, 87, 89,  
91, 93, 95, 97, 194, 388, 390, 780, 1560, 1562, 3124, 6248, 12496, 12498,  
24996, 24998, 49996, 49998, 99996, 199992, 199994, 99997, 99999]

real    0m1.031s
user    0m0.963s
sys     0m0.020s

I think it is an interesting idea to avoid using a hash, by storing the  
parent info in an instance variable of the Fixnums and it seems to be  
quite fast. But it has one big downside: solve only works once, because  
Fixnums are immediate values:

$ irb -r ryan
irb(main):001:0> solve 22222, 99999
=> [22222, 22224, 11112, 5556, 2778, 2780, 1390, 1392, 696, 348, 174, 87,  
89, 91, 93, 95, 97, 194, 388, 390, 780, 1560, 1562, 3124, 6248, 12496,  
12498, 24996, 24998, 49996, 49998, 99996, 199992, 199994, 99997, 99999]
irb(main):002:0> solve 22222, 99999
=> [22222]

Dominik