[QUIZ] Numeric Maze (#60)

ruby-talk
61

Here it is, my solution. From mathematical and algorithmic point of
view, you won't find anything new.

Kero, this is really the quickest solution so far, passing my little
test suite. Before you, Ryan Sobol, was the leader, clocking in at 2.376
secs with #60.20 on the Quiz list. Your #60.22, clocks in at 1.972
seconds, a decrease by 17%.

I'm challenging every quizzer: There is more to fetch!

You don't say? You do 868056 -> 651040 in 76 seconds. I broke my program off
after 15 minutes. I can not accept the title of fastest solution.

However, I need 21 seconds for 868056 -> 27 so I would assume that searching
for prefixes, or the approach from two sides has lots of potential.

By refactoring Kero's code, I was able to squeeze the execution time to
0.37 seconds, that's another 80%.

Did you do other things than eliminating method calls?

I'm not submitting this code, as I'm sure there are more improvements to
be done.

If you did other things, I'd be interested to see it, still. My mail address
is mangled,
  "kero@chello.single-dot.nl".split(/\./).values_at(0,2).join(".")

Thanks.

62

Christer Nilsson wrote:

Simon wrote:

Hello dear quizzers,

could someone please confirm (or disprove) that this i correct?

my subproblem solution to (868056,651040) gave the same result as your, in 76 secs.

I investigated the ideas suggested by Ilmari and Greg, but found that there is no way of knowing if the result is optimal. The result are impressing, but misses often trivial cases. It seems as hard to patch the non optimal solution as it is to solve it normally.

Are you using a different approach?

Christer

Oops, sorry i kind of 'lost' this thread..

My approach isn't that different but a little bit more optimized.
I use strings instead of hashs (or arrays like you do) to store the
information (and i only store which operation leads us there, ?X is
an empty field, ?M - multiply, ?D - divide, ?A - add, ?S - sub). I
need ?S (Sub 2) because search is done from both sides.

Well, here it is, it solves the the subproblem in 0.062s.

···

---------------------------------------------------------------------

require 'set'

def find_path from, to
   pathf = ''.ljust([from + 2, to + 2].max * 2, 'X')
   pathb = pathf.dup
   pathf[from] = ?F
   pathb[to] = ?F

   forward, backward, newbees = [from], [to],

   loop do
     forward.each do |n|
       pathf[newbees.push(n + 2).last] = ?S if pathf[n+2] == ?X
       pathf[newbees.push(n + n).last] = ?D if pathf[n+n] == ?X
       pathf[newbees.push(n / 2).last] = ?M if (n%2) == 0 && pathf[n/2] == ?X
     end
     forward, newbees = newbees,
     forward.each {|n|return pathf, pathb, n if pathb[n] != ?X}

     backward.each do |n|
       pathb[newbees.push(n - 2).last] = ?A if n > 1 && pathb[n-2] == ?X
       pathb[newbees.push(n + n).last] = ?D if pathb[n+n] == ?X
       pathb[newbees.push(n / 2).last] = ?M if (n % 2) == 0 && pathb[n/2] == ?X
     end
     backward, newbees = newbees,
     backward.each {|n|return pathf, pathb, n if pathf[n] != ?X}
   end
end

def solve from, to
   return nil if from < 0 || to <= 0
   return [from] if from == to
   pathf, pathb, n = find_path(from, to)

   result = [n]
   [pathf, pathb].each do |path|
     loop do
       case path[result.last]
         when ?A then result << result.last + 2
         when ?S then result << result.last - 2
         when ?D then result << result.last / 2
         when ?M then result << result.last * 2
         else break
       end
     end
     result.reverse!
   end
   result.reverse
end

from, to = (ARGV.shift || 868056).to_i, (ARGV.shift || 651040).to_i

t = Time.now
p solve(from, to)
puts "Time: #{Time.now - t}"

---------------------------------------------------------------------

cheers

Simon

63

On 12/30/05, Christer Nilsson

If start equals target, zero steps are needed.

Wouldn't that be a 'times 1' transformation? I don't see that in the list.

···

--
Jim Freeze

64

Jim Freeze wrote:
>> solve(1, 1) # => [1]
>

Only positive integers are allowed.

That means you can't divide odd numbers with two (operation halve)

Ok, I'll change the example
(2,2) #=> [2,4,2] or [2,1,2]

···

On 12/30/05, Christer Nilsson <janchrister.nilsson@gmail.com> wrote:

--
Jim Freeze

65

On 12/30/05, James Edward Gray II

> You have a set of three operations:
>
> double
> halve (Odd numbers cannot be halved.)
> add_two

I think it makes it interesting if the ending point is derived from a
transformation on the previous integer. More math like. So, I would suggest
we either have:

  double
  halve (evens only)
  add_two
  times_one

so we can get (1,1) #=> [1,1]

or, we use the original tranformations to get:

  (1,1) #=> [1,2,1]

Seems less hand wavy than having the final value magically appear without
being tranformed from a previous step.

$0.02

···

--
Jim Freeze

66

Kero wrote:

I have a generic solution which is perfectly happy with negative numbers
(and Bignums) which is unlikely to be the fastest solution at all. Now
you
allow others to use even more optimizations!

Kero,

You are perfectly right, I should have stated clearly in the Quiz
description, that the domain is positive integers.

There is no reason to include zero or negative numbers. The number of
possible mazes is still infinity squared!

Enjoy!

Christer Nilsson

···

--
Posted via http://www.ruby-forum.com/\.

67

It happened to me too. Took me at least a minute to figure out _my_ problem. :slight_smile:

--Steve

···

On Dec 31, 2005, at 10:10 AM, Gavin Kistner wrote:

I know, I read "one" as "1" the first time also :slight_smile:

68

Thanks Christer...

I'll fix that one. My search was far from exhaustive. :slight_smile:

--Steve

···

On Dec 31, 2005, at 9:47 AM, Christer Nilsson wrote:

Steve, there seem to be at least one difference:

<[300, 302, 304, 152, ... , 2, 1]> expected but was
<[300, 150, 152, ... , 2, 1]>.

69

I'm using a Dual 2 Ghz G5, so the hardware is at least *some* of the difference.

James Edward Gray II

···

On Dec 31, 2005, at 12:26 PM, Jim Menard wrote:

Damn. I got it down from 7 minutes to 18 seconds on a 667 MHz PPC, but
it looks like I have a bit more work to do.

70

solve(222, 9999)
result:
Total time taken in seconds: 56.0
[222, 224, 226, 228, 230, 232, 234, 236, 238, 240, 242, 244, 246, 248,
250, 252, 254, 256, 258, 260, 262, 264, 266, 268, 270, 272, 274, 276,
278, 280, 282, 284, 286, 288, 290, 292, 294, 296, 298, 300, 302, 304,
306, 308, 310, 312, 624, 1248, 2496, 2498, 4996, 4998, 9996, 9998,
19996, 19998, 9999]

Is this last one correct? I get for this for (222, 9999) --
[222, 224, 112, 56, 28, 14, 16, 18, 36, 38, 76, 78, 156, 312, 624, 1248,
2496, 2498, 4996, 4998, 9996, 19992, 19994, 9997, 9999]

Maurice

71

Gavin Kistner:

James Edward Gray II:

You can't get a negative, unless you start with one.

He meant "You can't get a negative, unless you start with a negative" and
not "You can't get a negative, unless you start with 1".

Now I got it. Thank you! :slight_smile:

Malte

72

I think I've improved upon this test code a bit. I found this one to
be a bit brittle, as it will fail solutions with unanticipated paths
of the same or smaller length. I lost some of the metadata in the
switch, as Steve has the different solutions ordered by type (i.e.
primes, powers of two, etc).

Looks great Peter. I posted a note about and link to your improved version on my [original post][1].

I'm just pounding away at this test case code because my mathematician
buddy is busy at the moment. This is quite the nontrivial problem...

Exactly why I created my own test cases. :slight_smile:

--Steve

[1]: http://swaits.com/articles/2005/12/31/ruby-quiz-60-test-cases

···

On Dec 31, 2005, at 4:24 PM, Peter Burns wrote:

73

#!/usr/bin/env ruby

···

#
# Ruby Quiz #60, Numeric Maze
# http://www.rubyquiz.com/quiz60.html
#
# You have a starting point and a target, say 2 and 9.
# You have a set of three operations:
# double, halve (odd numbers cannot be halved), add_two.
#
# Problem: Move from the starting point to the target,
# minimizing the number of operations.
# Examples:
# solve(2,9) # => [2,4,8,16,18,9]
# solve(9,2) # => [9,18,20,10,12,6,8,4,2]
#
#
# This solution builds a tree with each node having up to
# three subnodes, one for each operation. It builds the
# tree one level at a time and checks for a solution before
# proceeding down to the next level. This brute force
# approach performs much better after adding an optimization
# suggested by Dominik Bathon: track what numbers have been
# visited and do not build subnodes for previously visited
# numbers.
#

module NumericMaze

  class Node
    attr_accessor :parent, :value, :children

    def initialize(parent, value)
      @parent = parent
      @value = value
      @children = {}
    end

    def double
      @children[:double] = Node.new(self, @value * 2)
    end

    def halve
      return :halve_failed if @value % 2 != 0
      @children[:halve] = Node.new(self, @value / 2)
    end

    def add_two
      @children[:add_two] = Node.new(self, @value + 2)
    end

  end

  def NumericMaze.solve(start, target)
    # Initialize node arrays with root node
    node_arrays = []
    node_arrays[0] = []
    node_arrays[0] << Node.new(:root, start)
    # Initialize hash of visited numbers; do not
    # visit a number twice (thanks to Dominik Bathon)
    visited_numbers = {}
    # Check for a solution at each level
    level = 0
    while true
      # Examine nodes at this level and
      # build subnodes when appropriate
      node_arrays[level+1] = []
      node_arrays[level].each do |node|
        # Skip if method "halve" failed
        next if node == :halve_failed
        # Skip if this number has been tried already
        next if visited_numbers[node.value]
        visited_numbers[node.value] = true
        # Has a solution been found? If yes,
        # print it and exit
        if node.value == target
          # Build array of values used
          # (from bottom up)
          value_array = []
          node_ptr = node
          while true
            break if node_ptr.parent == :root
            value_array << node_ptr.value
            node_ptr = node_ptr.parent
          end
          # Display answer and exit
          p [start] + value_array.reverse
          exit
        end
        # Collect new results at this level
        node_arrays[level+1] << node.double
        node_arrays[level+1] << node.halve
        node_arrays[level+1] << node.add_two
      end
      level += 1
    end
  end

end

########################################

if ARGV.length != 2
  puts "Usage: #{$0} <start> <target>"
  exit
end

NumericMaze.solve(ARGV[0].to_i, ARGV[1].to_i)

--
Posted via http://www.ruby-forum.com/.

74

I guess we're allowed to submit solutions now...

Yes, 48 hours have passed sent the quiz was sent in

here's my first ever ruby quiz solution

Awesome. Thanks for joining the fun!

(these quizzes are a great idea, btw):

Thanks. I truly hope people find them helpful.

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.

Hey, that's clever. Thanks for sharing.

James Edward Gray II

···

On Jan 1, 2006, at 11:01 AM, Maurice Codik wrote:

75

Maurice,

I just noticed that your solution can't find the path between two odd numbers.

- Mark

···

On 1/1/06, Maurice Codik <maurice.codik@gmail.com> wrote:

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

76

My first quiz, as well.

Simple optimizations of don't-double-after-halving (and vice versa) and
pruning.

I enjoy the aesthetic feel of moving through one long queue. Not too
fast on the large cases though. :slight_smile:

The use of detect is a bit ungainly, but it still seemed like the
appropriate function.

dave

···

----
#!/usr/bin/ruby

class Array
  def uniquepush(num)
    self.push(num) if (self.assoc(num[0]) == nil)
  end
end

def interpret(val, solution)
  returnval = "[" + val.to_s
  solution[1].each{|step|
    val = val/2 if (step == 0)
    val = val+2 if (step == 1)
    val = val*2 if (step == 2)
    returnval += "," + val.to_s
  }
  returnval += "]"
end

def solve(initial, target)
  queue = [[initial, Array.new]]
  solution = queue.detect{|step|
    if (step[0] == target)
      true
    else
      queue.uniquepush([step[0]/2, step[1].clone().push(0)]) if (step[0]
% 2 == 0 && step[1].last != 2)
      queue.uniquepush([step[0]+2, step[1].clone().push(1)])
      queue.uniquepush([step[0]*2, step[1].clone().push(2)]) if
(step[1].last != 0)
      false
    end
  }
  interpret(initial, solution)
end

puts solve(ARGV[0].to_i, ARGV[1].to_i)

77

Hi all,

hereby my first solution for the ruby quiz and my first real world ruby
program. :slight_smile:

So all comments about my ruby-coding-style are very welcome(especially how
you think about using the throw catch statement).

The program itself runs two depth first searches in parallel one from the
start number and one from the end number looking for the middle number in the
end-result.
When found, the two paths to get to this middle number form the end-result.

It is possible to use the same method to calculate both pathways by using
negative numbers for the path from the end-point.

···

--
Hope you like it,

  Steven <steven.aerts@gmail.com>

--
class NumericMaze
  def solve (from, to)
    return [from] if from == to
    
    @done = {from => :from, -to => :to}
    @todo = [from, -to]
    
    catch :found do
      while true
        t = @todo.shift
        
        addEdge(2*t, t)
        addEdge(t+2, t) if (t <- 2) || (0 <= t)
        addEdge(t/2,t) if t.modulo(2) == 0
      end
    end
    return @result
  end
  
  def addEdge(new, from)
    return if @done[new] != nil
   
    @done[new] = from
    
    if @done[-new] then #path found
      @result = calcPath(new.abs)
      throw :found
    end
    
    @todo.push new
  end
  
  def calcPath(middle)
    pathway = [middle]
  
    t = middle
    pathway.unshift(t) until (t = @done[t]) == :from
    
    t = -middle
    pathway.push(-t) until (t = @done[t]) == :to

    return pathway
  end
end

78

It's great to see so many new faces. Welcome everyone!

James Edward Gray II

···

On Jan 1, 2006, at 11:01 AM, Maurice Codik wrote:

here's my first ever ruby quiz solution

On Jan 1, 2006, at 2:41 PM, Dave Lewis wrote:

My first quiz, as well.

On Jan 1, 2006, at 3:39 PM, Justin Bishop wrote:

I'm another newbie to the ruby-quiz.

On Jan 1, 2006, at 4:14 PM, Pablo Hoch wrote:

Btw, I'm new to ruby quiz, too. :slight_smile:

On Jan 1, 2006, at 4:20 PM, Steven Aerts wrote:

hereby my first solution for the ruby quiz and my first real world ruby program. :slight_smile:

79

Here's my solution. Short, sweet, and slow. One benefit of this
method is that it's easily adaptable to new operations.

-Nathan

$ops = [:double, :halve, :add_two]

def solve(start, finish)
  solve_recur($ops, [[]], start, finish)
end

def solve_recur(ops, op_arrays, start, finish)
  op_arrays.each do |op_array|
    if (is_solution?(op_array, start, finish))
      return print_solution(op_array, start)
    end
  end
  new_op_arrays = multiply_ops(ops, op_arrays)
  solve_recur(ops, new_op_arrays, start, finish)
end

def multiply_ops(ops, op_arrays)
  result = []
  ops.each do |op|
    op_arrays.each do |op_array|
      result << (op_array.clone << op)
    end
  end
  result
end

def is_solution?(op_array, start, finish)
  current = start
  op_array.each do |op|
    return false if op == :halve && current.is_odd?
    current = current.send(op)
  end
  current == finish
end

def print_solution(op_array, start)
  solution = op_array.inject([start]) do |acc, op|
    acc << acc.last.send(op)
  end
  puts solution.inspect
end

class Integer

  def double
    self * 2
  end

  def halve
    raise "unable to halve #{self}" if self.is_odd?
    self / 2
  end

  def add_two
    self + 2
  end
  
  def is_odd?
    self % 2 != 0
  end

end

80

Kero wrote:

I can not accept the title of fastest solution.

I think there are a lot of winners here. Your code executed fastest for
one problem. It's quite difficult to filter out a single winner. A lot
of different problems has to be defined. So, the person owning the
problem formulation privilege, has all the power. One remedy for this
would be to let every participant suggest one problem (start and target)
each. Then every solver has to solve all suggested problems, and the
solvers will get a score according to their rank for each individual
problem. That's a lot to administer. A cut off time has to be decided,
say one second. And then we have the problem with "dirty" integers, some
solutions leave after execution. Should the clean up time be included?

"Dirty" Integer: By attaching data to the Integer objects, like "parent"
and "queue", Arrays can be avoided. But the next call to "solve" will be
affected, if the Integers are not clean. See Quiz#60.20, line 2.

As I submitted this Quiz, I wouldn't like to be part af that contest.

Did you do other things than eliminating method calls?

Inline code only account for an improvement of 7%, so the answer is yes.

If you did other things, I'd be interested to see it, still.

I've sent the code to James. Eventually it will published in his
wrap-up. If not, it will be submitted to the ML.

However, I need 21 seconds for 868056 -> 27 so I would assume that
searching for prefixes, or the approach from two sides has lots of potential.

Agreed, searching from two sides could probably gain a lot. If we have a
distance from start to target of 10, with an average branching factor of
2, the workload should be proportional to 1024. Starting from both
sides, the workload should be something like 32 + 32 = 64, with a
potential of being 16 times faster. I haven't even tried this approach,
yet.

Christer

···

--
Posted via http://www.ruby-forum.com/\.