[QUIZ] Numeric Maze (#60)

ruby-talk
1

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

···

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Christer Nilsson

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]

2

Are negative numbers and zero allowed to be a starting point or target? I'm assuming no, but I'd like a confirmation.

~ ryan ~

···

On Dec 30, 2005, at 8:37 AM, Ruby Quiz wrote:

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Christer Nilsson

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]

3

Would it be appropriate to post my potential answers (not code) to this question? For example,

solve(1,1) # => ???
solve(1,2) # => ???
...
solve(1,25) # => ???

This is the first Number Theory exercise I've done in a while and I'm not 100% confident I can test my algorithm against my the solutions I come up with by hand. :slight_smile: It would be nice to have a small subset of publicly agreed test cases.

~ ryan ~

PS- I'm new here and I hope I'm not over overstepping the rules.

···

On Dec 30, 2005, at 8:37 AM, Ruby Quiz wrote:

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

4

Here's my simple breadth-first search with a single optimization (described in comments). It's not at all fast enough for the big examples people have been throwing around, but it's pretty simple.

James Edward Gray II

#!/usr/local/bin/ruby -w

# Parse arguments.
unless ARGV.size == 2 and ARGV.all? { |n| n =~ /\A[1-9]\d*\Z/ }
   puts "Usage: #{File.basename($0)} START_NUMBER FINISH_NUMBER"
   puts " Both number arguments must be positive integers."
   exit
end
start, finish = ARGV.map { |n| Integer(n) }

# Simple helper methods for determining if divide-by-two operation is allowed.
class Integer
   def even?
     self % 2 == 0
   end
end

···

On Dec 30, 2005, at 7:37 AM, Ruby Quiz wrote:

Problem: Move from the starting point to the target, minimizing the number of
operations.

#
# A breadth-first search with a single optimization: All numbers are marked as
# "seen" when they are calculated, then all future calculations resulting in an
# already seen number cause the entire path to be abandoned. (We've seen it
# before in equal or less steps, so there's no need to use the alternate/longer
# path).
#
def solve( start, finish )
   return [start] if start == finish

   seen = {start => true}
   paths = [[start]]

   until paths.first.last == finish
     path = paths.shift

     new_paths = [path.dup << path.last * 2, path.dup << path.last + 2]
     new_paths << (path.dup << path.last / 2) if path.last.even?

     new_paths.each do |new_path|
       unless seen[new_path.last]
         paths << new_path
         seen[new_path.last] = true
       end
     end
   end

   paths.shift
end

# Run program.
puts solve(start, finish).join(", ")

5

# The problem can be thought of in binary.
# (Which also happens to make solving by hand easy.)

···

On 12/30/05, Ruby Quiz <james@grayproductions.net> wrote:

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Christer Nilsson

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]

#
# i * 2 = i << 1
# i / 2 = i >> 1, only applicable if i[0] == 0
# i + 2 = i + 0b10
#
# Let's solve 22 -> 99.
# Mark the numbers in binary: 22 = 10110, 99 = 1100011
#
# Now start making the binary digits of 22 into 99's,
# progress one digit at a time:
#
# 10110
# first 1 matches but second 0 should be 1, let's add 2
# 10110 + 10 => 11000
# ok, first five match (11000, 1100011)
# shift so that we can turn the sixth into 1
# 11000 << 1 => 110000
# 110000 << 1 => 1100000
# now add two to make 6th digit match
# 1100000 + 10 => 1100010
# shift and add to make 7th digit match
# 1100010 << 1 => 11000100
# 11000100 + 10 => 11000110
# ok, all first digits match, divide to make length right
# 11000110 >> 1 => 1100011
#
# Problems appear when trying to make 255 into 257:
# 11111111 -> 100000001
#
# The shortest way is by adding 2.
# But the algorithm below fails at that and goes the long way:
# 11111111 << 1
# 111111110 + 2
# 1000000000 + 2
# 1000000010 >> 1
# 100000001
#
def nsrch(s,g)
  orig_s = s
  ss = s.to_s 2
  gs = g.to_s 2
  ops =
  bits = gs.split(//)
  i = 0
  # Go through all bits of g.
  # If there are ones in the trailing part of ss, we
  # must get rid of them (Otherwise: 1001 -> 100, all digits match,
  # jump out of loop, make length equal by >>. Oops, it was an odd
  # number we just halved. So must check for ones.)
  while i < bits.size or ss[bits.size..-1].include? ?1
    b = bits[i]
    op = nil
    n = 0
    while ss[i,1] != b
      # Add zeroes to right to make length right and
      # to get the rightmost bit into an editable state.
      if ss.size < i+2 or s[0] == 1
        op = :*
      # Delete zeroes from right to make length right.
      elsif ss.size > i+2 and (s[0] == 0 and s[1] == 0)
        op = :confused:
      # Add 2 if length is ok and there are no zeroes to take out.
      # We are here because the second right-most bit is wrong.
      # Adding 2 flips it. It may also flip every bit we've just
      # went through, invalidating the invariant and thus we reset
      # the bit counter.
      else
        op = :+
        i = 0
      end
      ops << op
      s = case op
          when :+
            s + 2
          when :*
            s << 1
          when :confused:
            s >> 1
          end
      ss = s.to_s 2
      break if op == :+ # invariant may be bad,
                        # must check before continuing
    end
    i += 1 unless op == :+
  end
  # take out extra zeroes on right
  r = s >> (ss.size-gs.size)
  ops.push *[:/]*(ss.size-gs.size)
  # and collect middle states using done ops
  a = [orig_s]
  ops.each{|op|
    a << case op
    when :*
      a.last * 2
    when :confused:
      a.last / 2
    when :+
      a.last + 2
    end
  }
  a
end

if __FILE__ == $0
  p(nsrch(*ARGV.map{|n| n.to_i}))
end

6

For this quiz I took what I made for the word chain quiz and modified
it a bit. It uses a bi-directional breadth first search. I didn't allow
negative numbers at all just to make it simple for me.

-----Horndude77

def solve(from, to)
    return [from] if from == to
    ops = []
    ops << lambda {|n| n*2}
    ops << lambda {|n| n/2 if n%2 == 0}
    ops << lambda {|n| n+2}

    invops = []
    invops << lambda {|n| n/2 if n%2 == 0}
    invops << lambda {|n| n*2}
    invops << lambda {|n| n-2}

    fromedges = {from => :start}
    toedges = {to => :start}
    fromqueue = [from]
    toqueue = [to]
    linknode = nil

    while(toqueue.length>0 && fromqueue.length>0)
        fromnode = fromqueue.shift
        tonode = toqueue.shift
        if(toedges[fromnode] || fromnode==to) then
            linknode = fromnode
            break
        elsif(fromedges[tonode] || tonode==from) then
            linknode = tonode
            break
        end

        ops.each do |o|
            val = o.call(fromnode)
            if(val && !fromedges[val] && val > 0) then
                fromedges[val] = fromnode
                fromqueue << val
            end
        end

        invops.each do |o|
            val = o.call(tonode)
            if(val && !toedges[val] && val > 0) then
                toedges[val] = tonode
                toqueue << val
            end
        end
    end

    return [] if(linknode == nil)
    chain = []
    currnode = linknode
    while(fromedges[currnode] != :start)
        chain.unshift currnode if currnode != to
        currnode = fromedges[currnode]
    end
    currnode = toedges[linknode]
    while(toedges[currnode] != :start && currnode != :start)
        chain << currnode
        currnode = toedges[currnode]
    end
    return [from]+chain+[to]
end

if ARGV.length != 2 then
    puts "usage: #{$0} <from> <to>"
    exit
end

from, to = ARGV[0].to_i, ARGV[1].to_i
if from < 1 || to < 1 then
    puts "inputs must be positive"
    exit
end
p solve(from, to)

7

I've posted my solution, along with a few words about my approach, at
<http://www.io.com/~jimm/rubyquiz/quiz60/>.

Jim

···

--
Jim Menard, jim.menard@gmail.com, jimm@io.com
http://www.io.com/~jimm
"Generics in Java are an apology for having collections of Objects, and are
somewhat like the puritan's suspicion that someone, somewhere, might be
enjoying themselves."
    -- Steven T Abell in comp.lang.smalltalk

8

Ok, my solution. It keeps track of all reached numbers *and* how it gets there in a hash (path). When the target is in the hash we simply have to go backwards and remember the values we pass on the way.

It does the 222 -> 9999 in 6.2s on my 2GHz+something system.
(should be easy to do a search from both sides, but no time [yet])

cheers

Simon

···

----------------------------------------------------------------
from, to = ARGV.shift || 222, ARGV.shift || 9999
t = Time.now

path = {from => :found}
while not path.include? to
   path.keys.each do |n|
     path[n + 2] = :add unless path.include?(n + 2)
     path[n * 2] = :mul unless path.include?(n * 2)
     path[n / 2] = :div unless (n % 2) != 0 || path.include?(n / 2)
   end
end

result = [to]
loop do
   case path[result.last]
     when :add then result << result.last - 2
     when :mul then result << result.last / 2
     when :div then result << result.last * 2
     else break
   end
end

p result.reverse
puts "Time: #{Time.now - t}s"
----------------------------------------------------------------

9

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

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? :slight_smile:
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 = :confused:
        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

10

Kinda ugly, but pretty fast. Breadth first search alternating from each
end. It's the same basic algorithm I used for a Perl Quiz of the Week
Word Ladder:

http://perl.plover.com/~alias/list.cgi?mss:99:200409:dlfkjbmmdljnajmfagki

Instead of CPAN's Tree::Simple, I'm using unidirectional (nodes can find
their parents, but not their children) n-ary trees implemented in
hashes. I don't explicitly implement the don't-double-then-halve
optimization, but I get it as a side-effect of my use of node_index to
index all values already in the tree so I can avoid creating new nodes
for already existing values.

~ (300) time ./numeric_maze5.rb 8740 7630
[8740, 4370, 4372, 2186, 2188, 1094, 1096, 548, 274, 276, 138, 140, 70,
72, 36, 38, 19, 21, 23, 25, 27, 29, 58, 116, 118, 236, 238, 476, 952,
1904, 1906, 3812, 3814, 7628, 7630]

real 0m2.280s
user 0m2.105s
sys 0m0.017s
~ (301) time ./numeric_maze5.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, 99998, 199996, 199998, 99999]

real 0m2.966s
user 0m2.796s
sys 0m0.016s

def success(x, node1, node2)
  node1, node2 = node2, node1 unless x.zero?
  p chain(node1).reverse + chain(node2)
  exit
end

def chain(node)
  (result ||= []) << node[:num] and node = node[:parent] until node.nil?
  result
end

tree = []
node_index = []
ARGV.each { |x|
  root = {:num => x.to_i, :parent => nil}
  tree << [root]
  node_index << { root[:num] => root }
}

x = 1
while x = 1 - x: # cycle between 0 and 1 in infinite loop
  next_nodes = []
  tree[x].each {|node| # for each node in current level
    [node[:num]*2,
     node[:num]%2 == 0 ? node[:num]/2 : 0,
     x.zero? ? node[:num] + 2 : node[:num] - 2].uniq.select {|n|
       n > 0 and !node_index[x].key?(n)}.each {|newnum|
       # if we have a path to this result in the other tree, we're done
       success(x, node, node_index[1-x][newnum]) if
node_index[1-x].key?(newnum) # only way out of the loop
       next_nodes << node_index[x][newnum] = { :num => newnum, :parent
=> node } # build the next level
    }
  }
  tree[x] = next_nodes
end

···

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

11

Here is my solution, very much a derivative of my solution to the
Knight's Travails quiz (#27). It will return a shortest solution
(chosen at random if there are more than one). It will always find a
shortest solution, though not necessarily fast. (I haven't tried timing
this.)

# Helper methods
class Integer
   def even?
      self & 1 == 0
   end

   def maze_adj
      if even?
         [self + 2, self * 2, self / 2]
      else
         [self + 2, self * 2]
      end
   end
end

def solve(a, b)
   i = 0
   steps = [[a]]

   # steps[i] contains all the numbers reachable in i steps
   until steps[i].include?(b)
      i += 1
      steps[i] = []
      steps[i-1].each do |x|
         steps[i].concat x.maze_adj
      end
   end

   # path is built in reverse order, finding a legal previous
   # number according to "adjacency" rules
   i -= 1
   path = [b]
   i.downto(0) do |k|
      s = steps[k].find_all { |x| x.maze_adj.include? path.last }
      path << s.sort_by { rand }.first
   end

   # path was built in reverse order, so reverse to get the final path
   path.reverse
end

# Examples
p solve(2, 9)
p solve(9, 2)

12

Ruby Quiz schrieb:

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Christer Nilsson

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 was really a nice riddle.
I learned much about understanding and implementing a BFS algo.
Thank you for that.

But I waited for the new riddle to appear :\
I guess I have to wait another few days.
But please don't say 'Tomorrow\'s quiz is about..' and similar.
Well I was bored today :>

I get an 403, when I try to touch /quiz61.html from rubyquiz.com
Maybe it's is correct that I get that response, maybe not.

Don't let us wait too long for that dice riddle :>

···

-
With kind regards from Duesseldorf, Germany
Robert "Mr. Overheadman" Retzbach

13

Zero seems fine as a starting number. You can always add_two.

You can't get a negative, unless you start with one. If you do, other negative targets and even a target of 0, seem fine. Some numbers would be impossible to reach though.

I think allowing them is fine. Let's just add that you're program won't be fed a start and end that have no solution (at least by me). Sound fair?

James Edward Gray II

···

On Dec 30, 2005, at 2:18 PM, J. Ryan Sobol wrote:

Are negative numbers and zero allowed to be a starting point or target?

14

J. Ryan Sobol wrote:

Are negative numbers and zero allowed to be a starting point or
target? I'm assuming no, but I'd like a confirmation.

~ ryan ~

I made a quick analysis:

   target
   - 0 +
- ok ok ok
0 no ok ok
+ no no ok
start

but, to make it simpler: let the domain be positive integers.
It all depends on the operators used.
With the proposed operators, it is possible to go from any positive
number to any positive number.

Christer Nilsson

···

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

15

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

Would it be appropriate to post my potential answers (not code) to this question? For example,

solve(1,1) # => ???
solve(1,2) # => ???
...
solve(1,25) # => ???

Absolutely. Please do.

Then people can counter post if they think they have a better answer... :wink:

PS- I'm new here and I hope I'm not over overstepping the rules.

Welcome to Ruby Quiz, Ryan. And no worries, you are doing just fine.

James Edward Gray II

···

On Dec 30, 2005, at 4:17 PM, J. Ryan Sobol wrote:

On Dec 30, 2005, at 8:37 AM, Ruby Quiz wrote:

16

J. Ryan Sobol wrote:

Would it be appropriate to post my potential answers (not code) to
this question?

Some examples:

solve(1, 1) # => [1]
solve(1, 2) # => [1, 2]
solve(1, 25) # => [1, 3, 6, 12, 24, 48, 50, 25]
solve(12, 11)# => [12, 14, 7, 9, 11]
solve(2, 9) # => [2, 4, 8, 16, 18, 9]
solve(9, 2) # => [9, 18, 20, 10, 12, 6, 8, 4, 2]
solve(17, 1) # => [17, 34, 36, 18, 20, 10, 12, 6, 8, 4, 2, 1]

There may exist equivalent paths, of the same length.

Christer Nilsson

···

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

17

J. Ryan Sobol schrieb:

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

Would it be appropriate to post my potential answers (not code) to this question? For example,

solve(1,1) # => ???
solve(1,2) # => ???
...
solve(1,25) # => ???

This is the first Number Theory exercise I've done in a while and I'm not 100% confident I can test my algorithm against my the solutions I come up with by hand. :slight_smile: It would be nice to have a small subset of publicly agreed test cases.

~ ryan ~

PS- I'm new here and I hope I'm not over overstepping the rules.

Hello.
I really enjoyed this puzzle, but my brain and my cpu are burning.

In a german ruby channel we used the example 22->999.
My really slow brute force algo came up with
122002000200212

0 - double
1 - halve
2 - add_two

It took 20-30min :smiley:

1->15 : 2000021, took about .5s

But thinking about a no BF solution makes my head hurt :frowning:
I have created some algos but they all don't find the shortest way.

I also have to mention that there are often more than 1 'shortest' ways.

I exspect the best of you!
Good luck.

···

On Dec 30, 2005, at 8:37 AM, Ruby Quiz wrote:

18

OK, so I didn't have time to code it up and see for sure, what with some transatlantic travel and New Year's and all that stuff, 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?

m.s.

···

On Jan 1, 2006, at 15:47, James Edward Gray II wrote:

On Dec 30, 2005, at 7:37 AM, Ruby Quiz wrote:

Problem: Move from the starting point to the target, minimizing the number of
operations.

Here's my simple breadth-first search with a single optimization (described in comments). It's not at all fast enough for the big examples people have been throwing around, but it's pretty simple.

19

Hey,

My solution's similar in style [breadth first, don't duplicate search],
though I've also roof-limited it so it can't explore the search space
above 2*[max(target,start)] + 4 which provides a fair speed up for e.g.
222, 9999. I'm not sure if that loses the optimality property though.
I can't get to the swaits.com test suite, but the other one my solver
finds smaller solutions for.

Regards,

Tris

···

----
require 'set'

class MazeSolver

  def solve start, finish
    visited = Set.new

    tul, tll = if start > finish
                 [(start << 1) + 4, nil]
               else
                  [(finish << 1) + 4, nil]
               end

    solve_it [[start]], finish, visited, tul, tll
  end

  def solve_it lpos, target, visited, tul, tll
    n = []
    lpos.each do |vs|
      v = vs.last
      next if tul and v > tul
      next if tll and v < tll

      return vs if v == target

      d = v << 1 # double
      h = v >> 1 unless (v & 1) == 1 # half
      p2 = v + 2 # plus 2

      n << (vs.clone << d) if visited.add? d
      n << (vs.clone << h) if h and visited.add? h
      n << (vs.clone << p2) if visited.add? p2
    end

    return solve_it(n, target, visited,tul, tll)
  end
end

if __FILE__ == $0
  puts MazeSolver.new.solve(ARGV[0].to_i, ARGV[1].to_i).join(" ")
end
--------

20

Ilmari Heikkinen wrote:

#
# Problems appear when trying to make 255 into 257:
# 11111111 -> 100000001
#
# The shortest way is by adding 2.
# But the algorithm below fails at that and goes the long way:
# 11111111 << 1
# 111111110 + 2
# 1000000000 + 2
# 1000000010 >> 1
# 100000001
#

Ilmari, I tried to replicate your solution, before seeing it, and
strangely run into exactly the same behaviour. The code is not complete,
but the idea is to go downwards to 1 with both numbers. I'm using the
complement of +2, -2 for the target number.

      t up(255), [255, 510, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1]
                  --> --> --v
                  <-- <-- <--
    t down(257), [257, 514, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1]

Having these two sequences, I find the largest common number, in this
case 512. This gives me the non optimal solution [255,510,512,514,257],
which is exactly the same as yours. I'm not sure if identifying
shortcuts afterwards, will find the shortest path, though, in all cases.
(Finding 255 + 2 = 257, is easy, but what about finding 255 -> 259 if
257 is missing.)

I tried the six digit subproblem of your big problem, and it worked out
perfectly optimal. So I was surprised 255 -> 257 behaved so bad.

Christer

def down(x)
  return if x==0
  return [1] if x==1
  return [2,1] if x==2
  return + down(x*2) if x.modulo(2)==1
  return + down(x/2) if x.modulo(4)==0
   + down(x-2)
end

def up(x)
  return if x==0
  return [1] if x==1
  return [2,1] if x==2
  return + up(x*2) if x.modulo(2)==1
  return + up(x/2) if x.modulo(4)==0
   + up(x+2)
end

require 'test/unit'
class TestIlmari < Test::Unit::TestCase
  def t (actual, expect)
    assert_equal expect, actual
  end
  def test_all
    t up(255), [255, 510, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1]
    t down(257), [257, 514, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1]
    #t up(72), [72,36,18,20,10,12,6,8,4,2,1]
    #t down(28), [28,14,12,6,4,2,1]
    #t up(150128850109293).size,82
    #t down(8591982807778218492).size, 100
  end
end

···

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