From: "J. Ryan Sobol" <ryansobol@...>
Date: 2006-01-03T02:06:11+09:00
Subject: Re: [SOLUTION] Numeric Maze (#60)


On Jan 2, 2006, at 11:24 AM, Dominik Bathon wrote:

> On Mon, 02 Jan 2006 08:25:08 +0100, J. Ryan Sobol  
> <ryansobol@gmail.com> wrote:
>
> It actually is faster than my version:

Oh nice.  :)

> 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
>

Seems like the biggest performance gain is obtained by removing the  
ternary operation when setting @distance in the visit! method.   
Although it wasn't necessary to solve this problem, I included  
@distance calculations because they are (or at least seem to be)  
intrinsic to searching algorithms.  I should have caught this before  
posting my solution.  :)

> 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.

The biggest performance gain comes from the optimization that removes  
adjacent values greater than a maximum.  It takes the infinite search  
space of integer values and reduces it to a linear search space.   
Kudos on the math wizards who originally posted that suggestion.

> But it has one big downside: solve only works once, because Fixnums  
> are immediate values:

Good observation!  Unfortunately, this problem has an infinite search  
space of integer values.  With a finite search space, the algorithm  
can loop through and reset each vertex or node before starting.  And  
the best part is the running time for the BFS algorithm with this  
technique remains linear.  In the general case, it is O(V + E), where  
V is the number of vertices and E is the number of edges in the  
finite graph.  (In my algorithm, N, which is the number of integers  
visited, is the same as E.)

~ ryan ~