From: Maurice Codik <maurice.codik@...>
Date: 2006-01-02T02:01:20+09:00
Subject: Re: [SOLUTION] Numeric Maze (#60)

------=_Part_3102_4389072.1136134866960
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

I guess we're allowed to submit solutions now... here's my first ever ruby
quiz solution (these quizzes are a great idea, btw):

It's is an iterated-depth DFS w/ memoization written in a functional style
for fun.

It exploits the fact that the optimal path through the maze will never have
consecutive double/halves, which reduces the avg branching factor of the
search tree to ~2. Keeping track of this state makes the code a little
uglier, but faster on the longer searches.

Maurice

#! /usr/bin/ruby

# These return the next number &  state
ARROWS =3D [lambda { |x,state| (state !=3D :halve) ? [x*2, :double] : nil }=
, #
double
          lambda { |x,state| (x.modulo(2).zero? and state !=3D :double) ?
[x/2, :halve] : nil }, #halve
          lambda { |x,state| [x+2, :initial]}] # add_two

def solver(from, to)

  # constraining depth on a DFS
  retval =3D nil
  depth =3D 1
  @memo =3D nil

  # special case
  return [from] if from =3D=3D to

  while (retval.nil?)
    retval =3D memo_solver(from, to, depth)
    depth +=3D 1
  end

  retval
end

# cant use hash default proc memoization since i dont want to memoize on th=
e

# state parameter, only on the first 3
def memo_solver(from, to, maxdepth, state=3D:initial)
  @memo ||=3D Hash.new

  key =3D [from, to, maxdepth]

  if not @memo.has_key? key
    @memo[key] =3D iter_solver(from, to, maxdepth, state)
    @memo[key]
  else
    @memo[key]
  end
end

def iter_solver(from, to, maxdepth, state)
  return nil if maxdepth.zero?

  # generate next numbers in our graph
  next_steps =3D ARROWS.map { |f| f.call(from, state) }.compact

  if next_steps.assoc(to)
    [from, to]
  else
    # havent found it yet, recur
    kids =3D next_steps.map { |x,s| memo_solver(x, to, maxdepth-1, s)
}.compact

    if kids.length.zero?
      nil
    else
      # found something further down the tree.. return the shortest list up
      best =3D kids.sort_by { |x| x.length }.first
      [from, *best]
    end
  end
end

list =3D [ [1,1], [1,2], [2,9], [9,2], [2, 1234], [1,25], [12,11], [17,1],
        [22, 999], [2, 9999], [222, 9999] ]

require 'benchmark'

list.each do |i|
  puts Benchmark.measure {
    p solver(*i)
  }
end

On 1/1/06, Stephen Waits <steve@waits.net> wrote:
>
>
> On Jan 1, 2006, at 8:04 AM, Matthew Smillie wrote:
>
> > but the first thing that struck me when reading the problem was
> > "dynamic programming" - did anyone take this route and hence give
> > me a bit of satisfaction that my instincts were right?
>
> I had the same thought, then decided it doesn't fit.  But too, I'm
> interested in watching these solutions.
>
> I have a feeling they'll be based on exhaustive searches with a pinch
> of pruning and a dash of optimization.
>
> --Steve
>
>
>

------=_Part_3102_4389072.1136134866960--