From: "0x002A@..." <0x002A@...>
Date: 2006-01-03T04:53:00+09:00
Subject: Re: Numeric Maze (#60)

okay here's my shot at the quiz, it's quite large for such a simple
problem, but i couldn't resist to use
:* in my code ;-)

class Integer
        def even?
                self % 2 == 0
        end

        def odd?
                not even?
        end
end

# solves rubyquiz #60
class Solver
        def initialize(start, goal)
                @start, @goal = start, goal
                @visited = {}
                @queue = [[@goal, []]]
                @ops = []
                [AddTwo, Double, Halve].each {|op| @ops <<
op.new(@start, @goal) }
        end

        # are we there yet?
        def done_with?(temp_goal)
                @start == temp_goal
        end

        # transforms the carried steps into a valid solution
        def solution(steps)
                steps.reverse.unshift @start
        end

        # does all the work
        def solve
                # there should be a better way to recover the steps
than carrying them
                # around in the search tree (depth first search for
example?)
                while current = @queue.shift
                        temp_goal, steps = *current # parallel
assignment in conditionals won't work

                        return solution(steps) if done_with? temp_goal
                        next if @visited[temp_goal] # been there, done
that

                        #puts "#{@start} -> #{@goal}: testing
#{temp_goal}, steps so far: #{steps.join(" ")}"
                        #gets

                        @visited[temp_goal] = true
                        new_steps = steps + [temp_goal]

                        @ops.each do |op|
                                @queue << [op.apply(temp_goal),
new_steps] if op.makes_sense? temp_goal
                        end
                end
                # my guess is, that there's always a solution. any
proof?
                raise "no solution found"
        end

        # creates a new solver and attempts to solve(a,b)
        def self.solve(a,b)
                new(a,b).solve
        end
end

# Applies a method with the argument 2
# maybe too much OO? :-)
class TwoOperation
        def initialize(start, goal)
                @start, @goal = start, goal
        end

        def apply(temp_goal)
                temp_goal.send(@meth, 2)
        end

        def makes_sense?
                false
        end
end

# inverse of double
class Double < TwoOperation
        def initialize(start, goal)
                super
                @meth = :/
        end

        def makes_sense?(temp_goal)
                temp_goal.even?
        end
end

# inverse of halve
class Halve < TwoOperation
        def initialize(start, goal)
                super
                @meth = :* # heh a kissing smiley, ruby is soo cute
        end

        def makes_sense?(temp_goal)
                # was (@goal < @start and temp_goal.even?) or (not
temp_goal.even?)
                temp_goal.odd? or @goal < @start
        end
end

# inverse of add_two
class AddTwo < TwoOperation
        def initialize(start, goal)
                super
                @meth = :-
        end

        def makes_sense?(temp_goal)
                temp_goal > 1
        end
end

# for the testcases
def solve(a, b)
        Solver.solve(a,b)
end