# Forum: Ruby Numeric Maze (#60)

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
on 2005-12-30 15:40
```The three rules of Ruby Q.:

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 Q. by submitting ideas as often as you can:

http://www.rubyquiz.com/

3.  Enjoy!

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

by Christer N.

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

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]```
on 2005-12-30 22:21
```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 2005-12-30 22:39
```On Dec 30, 2005, at 2:18 PM, J. Ryan S. wrote:

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

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 G. II```
on 2005-12-30 22:57
```J. Ryan S. 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 ~

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 N.```
on 2005-12-30 22:57
```On Sat, Dec 31, 2005 at 05:36:58AM +0900, James Edward G. II wrote:
> On Dec 30, 2005, at 2:18 PM, J. Ryan S. wrote:
>
> >Are negative numbers and zero allowed to be a starting point or  target?
>
> 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.

Heh, I couldn't figure out how to get a negative number using double,
halve,
and add_two from the number 1.  Then I realized the problem wasn't with
my
math, but with my English :-)

That, or I'm really confused.
Jeff```
on 2005-12-30 23:06
```Jeffrey D. wrote:
> Heh, I couldn't figure out how to get a negative number using double,
> halve,
> and add_two from the number 1.

You are correct Jeffrey, see the matrix in my last reply. Starting with
a positive number, you can only reach positive numbers.

This quiz should be interesting enough, using only positive numbers, as
any positive number can be reached from any positive number.

Christer N.```
on 2005-12-30 23:06
```On Dec 30, 2005, at 2:57 PM, Christer N. wrote:

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

Works for me.  Let's do that.

James Edward G. II```
on 2005-12-31 00:19
```On Dec 30, 2005, at 8:37 AM, Ruby Q. wrote:

> The three rules of Ruby Q.:
>
> 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.  :)  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 2005-12-31 00:28
```On Dec 30, 2005, at 4:17 PM, J. Ryan S. wrote:

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

Then people can counter post if they think they have a better

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

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

James Edward G. II```
on 2005-12-31 01:06
```J. Ryan S. 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 N.```
on 2005-12-31 01:40
```On 12/30/05, Christer N. <removed_email_address@domain.invalid> wrote:
>
> J. Ryan S. wrote:
> > Would it be appropriate to post my potential answers (not code) to
> > this question?
>
> Some examples:
>
> solve(1, 1)  # => [1]

Is this a degenerate case? If to go from a to b in (a,b) through
transformation x,y or z, wouldn't there be two possible shortest
solutions:

[1,2,1]
[1,0.5,1]```
on 2005-12-31 01:46
```On Dec 30, 2005, at 23:37, Jim F. wrote:

>
> Is this a degenerate case? If to go from a to b in (a,b) through
> transformation x,y or z, wouldn't there be two possible shortest
> solutions:
>
>   [1,2,1]
>   [1,0.5,1]

(It's specified that you can't halve odd numbers)

m.s.```
on 2005-12-31 01:48
```Jim F. wrote:
>> solve(1, 1)  # => [1]
>
>
> Is this a degenerate case? If to go from a to b in (a,b) through
> transformation x,y or z, wouldn't there be two possible shortest
> solutions:
>
>   [1,2,1]
>   [1,0.5,1]

Only positive integers are allowed.
That means you can't divide odd numbers with two (operation halve)

If start equals target, zero steps are needed.

Christer N.```
on 2005-12-31 01:52
```J. Ryan S. schrieb:

> this question?  For example,
>
> ~ 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

It took 20-30min :D

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

But thinking about a no BF solution makes my head hurt :(
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 2005-12-31 02:07
```Robert R. wrote:
> J. Ryan S. schrieb:
>
>> this question?  For example,
>>
>> ~ 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
>
> It took 20-30min :D
>
> 1->15 : 2000021, took about .5s
>
> But thinking about a no BF solution makes my head hurt :(
> 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.

Robert, your solution is correct. There may be different solutions with
the same number of steps.

[22, 24, 26, 28, 30, 60, 62, 124, 248, 496, 498, 996, 1992, 1994, 997,
999]
[22, 11, 13, 15, 30, ...]

I agree, it shouldn't take so long time. Try shaving off one magnitude.

Christer```
on 2005-12-31 02:28
```On 12/30/05, Christer N.

> If start equals target, zero steps are needed.

Wouldn't that be a 'times 1'  transformation? I don't see that in the
list.```
on 2005-12-31 02:31
```On 12/30/05, Christer N. <removed_email_address@domain.invalid> wrote:
>
> Jim F. 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 2005-12-31 02:59
```On Dec 30, 2005, at 5:37 PM, Jim F. wrote:

>
> Is this a degenerate case? If to go from a to b in (a,b) through
> transformation x,y or z, wouldn't there be two possible shortest
> solutions:
>
>   [1,2,1]
>   [1,0.5,1]

Hmm, let's go back to the quiz and see if we can find an answer:

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

> You have a set of three operations:
>
> 	double
> 	halve    (Odd numbers cannot be halved.)
>
> Problem: Move from the starting point to the target, minimizing the
> number of
> operations.

The key phrase seems to be "minimizing the number of operations".  I
don't think we can get any smaller than zero and I don't see anything
disallowing it, so I imagine it's fine.

Just my opinion on an obviously debatable topic.

James Edward G. II```
on 2005-12-31 03:08
```On 12/30/05, James Edward G. II

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

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)
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```
on 2005-12-31 03:36
```Jim F. wrote:
> we either have:
>
>   double
>   halve (evens only)
>   times_one
>
> so we can get (1,1) #=> [1,1]
>
> or, we use the original tranformations to get:
>
>   (1,1) #=> [1,2,1]

My suggestion is:

consider the original transformations having cost one. The new
operation, times_one, will have cost zero. Find the minimum cost
transforming a to b.

Hmm, this is getting interesting...

Christer```
on 2005-12-31 03:56
```On 12/30/05, Christer N. <removed_email_address@domain.invalid> wrote:
>
>
> My suggestion is:
>
> consider the original transformations having cost one. The new
> operation, times_one, will have cost zero. Find the minimum cost
> transforming a to b.
>
> Hmm, this is getting interesting...

:)

\$    xform
--   ---------
0    times_one
2    times_two
4    times_one_half```
on 2005-12-31 04:06
```Jim F. wrote:
> \$    xform
> --   ---------
> 0    times_one
> 2    times_two
> 4    times_one_half

Jim, you have just defined Quiz #60B !

The original Quiz #60A looks like this:

\$    xform
--   ---------
0    times_one
1    times_two
1    halve

Feel free to submit to none, one or both !

Christer```
on 2005-12-31 13:39
```>> 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.
>
> Works for me.  Let's do that.

Bah!

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!

But given the table, I suppose I should add some code to prevent
infinite
loops from the "no" entries of the table above. ah, well.

Bye,
Kero.```
on 2005-12-31 13:48
```In article <removed_email_address@domain.invalid>,
>>
>> Some examples:
>>
>> solve(1, 1)  # =3D> [1]
>
>
>Is this a degenerate case? If to go from a to b in (a,b) through
>transformation x,y or z, wouldn't there be two possible shortest solutions:
>
>  [1,2,1]
>  [1,0.5,1]

But you can't halve an odd number (from the original rules).

Phil```
on 2005-12-31 14:34
```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 N.```
on 2005-12-31 19:01
```On Dec 30, 2005, at 2:27 PM, James Edward G. II wrote:

> On Dec 30, 2005, at 4:17 PM, J. Ryan S. wrote:
>
>> Would it be appropriate to post my potential answers (not code) to
>> this question?  For example,
>

Since that's about all I'm going to be able to do on this quiz, here
are some of my test cases.  I'm pretty confident in the shorter
solutions, but have less confidence in the longer ones.  These were
all discovered via stochastic search.

I hope this won't qualify as "code", as mentioned above - since the
idea is that everyone may test their solutions against this, the fact
that it's already coded as test cases seems naturally acceptable to me.

I'm very much looking forward to the solutions on this one!

For now, I've posted them on http://swaits.com/

--Steve```
on 2005-12-31 19:08
```On Dec 30, 2005, at 5:51 PM, Robert R. wrote:

>
> It took 20-30min :D

\$ time ruby numeric_maze.rb 22 999
22, 24, 26, 28, 30, 60, 62, 124, 248, 496, 498, 996, 1992, 1994, 997,
999

real    0m0.635s
user    0m0.381s
sys     0m0.252s

;)

James Edward G. II```
on 2005-12-31 19:46
```Stephen W. wrote:
>
> Since that's about all I'm going to be able to do on this quiz, here
> are some of my test cases.  I'm pretty confident in the shorter
> solutions, but have less confidence in the longer ones.  These were
> all discovered via stochastic search.
>
> I hope this won't qualify as "code", as mentioned above - since the
> idea is that everyone may test their solutions against this, the fact
> that it's already coded as test cases seems naturally acceptable to me.
>
> I'm very much looking forward to the solutions on this one!
>
> For now, I've posted them on http://swaits.com/
>
> --Steve

Steve, there seem to be at least one difference:

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

Christer```
on 2005-12-31 19:50
```James Edward G. II:

Doesn't 2 / 2 == 1 evaluate as true?

Malte```
on 2005-12-31 19:53
```On Dec 31, 2005, at 11:47 AM, Malte M. wrote:

> James Edward G. II:
>
> Doesn't 2 / 2 == 1 evaluate as true?

Yes, but how does that get you a negative number?

James Edward G. II```
on 2005-12-31 20:11
```On Dec 31, 2005, at 10:47 AM, Malte M. wrote:
> James Edward G. II:
>
> Doesn't 2 / 2 == 1 evaluate as true?

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

I know, I read "one" as "1" the first time also :)```
on 2005-12-31 20:20
```On Dec 31, 2005, at 10:10 AM, Gavin K. wrote:

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

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

--Steve```
on 2005-12-31 20:23
```On Dec 31, 2005, at 9:47 AM, Christer N. wrote:

> Steve, there seem to be at least one difference:
>
> <[300, 302, 304, 152, ... , 2, 1]> expected but was
> <[300, 150, 152,      ... , 2, 1]>.

Thanks Christer...

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

--Steve```
on 2005-12-31 20:29
```On 12/31/05, James Edward G. II <removed_email_address@domain.invalid> wrote:
> > 1 - halve
> sys     0m0.252s
>
> ;)
>
> James Edward G. II

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.

Jim
--
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```
on 2005-12-31 21:20
```On Dec 31, 2005, at 12:26 PM, Jim M. 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.

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

James Edward G. II```
on 2005-12-31 22:23
```James G. wrote:
> On Dec 30, 2005, at 5:51 PM, Robert R. wrote:
>
>>
>> It took 20-30min :D
>
> \$ time ruby numeric_maze.rb 22 999
> 22, 24, 26, 28, 30, 60, 62, 124, 248, 496, 498, 996, 1992, 1994, 997,
> 999
>
> real    0m0.635s
> user    0m0.381s
> sys     0m0.252s
>
> ;)
>
> James Edward G. II

Very new Rubyist here. :)

solve(22, 999)
result:
Total time taken in seconds: 0.782
[22, 24, 26, 28, 30, 60, 62, 124, 248, 496, 498, 996, 998, 1996, 1998,
999]

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]

AMD Athlon 1400, 1.6 GHz```
on 2006-01-01 00:09
```>
> 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```
on 2006-01-01 00:24
```Gavin K.:
>> James Edward G. II:
> 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!  :-)

Malte```
on 2006-01-01 01:14
```Maurice Codik wrote:
>>
>> 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

Yea I think it is correct. I thought I had a shortcut in my algorithm,
which excluded solutions like that one. My solution for (222, 9999) is
slightly different though:
[222, 224, 112, 56, 28, 14, 16, 18, 36, 38, 76, 78, 156, 312, 624, 1248,
496, 2498, 4996, 4998, 9996, 9998, 19996, 19998, 9999]
in +- 38 seconds```
on 2006-01-01 02:24
```On 12/31/05, Stephen W. <removed_email_address@domain.invalid> wrote:
>
> For now, I've posted them on http://swaits.com/
>
> --Steve

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

http://rafb.net/paste/results/qwhnUg32.nln.html

Any feedback is, of course, appreciated.

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...```
on 2006-01-01 02:39
```On Dec 31, 2005, at 4:08 PM, Maurice Codik wrote:

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

My code dies a horrible death on this one.  <laughs>  I think I get a
right answer, but the wait was embarrassing:

\$ time ruby numeric_maze.rb 222 9999
222, 224, 112, 56, 58, 29, 31, 33, 35, 37, 39, 78, 156, 312, 624,
1248, 2496, 2498, 4996, 4998, 9996, 19992, 19994, 9997, 9999

real    96m13.978s
user    49m27.502s
sys     46m22.817s

Guess I need more than my one optimization now.  <laughs>

James Edward G. II```
on 2006-01-01 03:09
```On Dec 31, 2005, at 4:24 PM, Peter B. wrote:

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

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

--Steve

[1]: http://swaits.com/articles/2005/12/31/ruby-quiz-60...```
on 2006-01-01 06:00
```On 12/31/05, Stephen W. <removed_email_address@domain.invalid> wrote:
> 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.  :)
>
> --Steve
>
> [1]: http://swaits.com/articles/2005/12/31/ruby-quiz-60...
>

I'd just like to chime in to say that this quiz is killing me.  The
difference between 'code to solve the problem' and 'code that finishes
running, you know, sometime today' is big.```
on 2006-01-01 06:42
```On Dec 31, 2005, at 10:59 PM, Wilson B. wrote:

>>
>> --Steve
>>
>> [1]: http://swaits.com/articles/2005/12/31/ruby-quiz-60...
>>
>
> I'd just like to chime in to say that this quiz is killing me.  The
> difference between 'code to solve the problem' and 'code that finishes
> running, you know, sometime today' is big.

Don't worry, you're not alone.  :)

I'm very anxious to see the code that the rest of you have come up
with.  It's been a long time since my brain worked over a problem
like this.  :)

~ ryan ~```
on 2006-01-01 07:13
```On Sun, 01 Jan 2006 04:59:32 +0100, Wilson B.
wrote:

>>
>
> I'd just like to chime in to say that this quiz is killing me.  The
> difference between 'code to solve the problem' and 'code that finishes
> running, you know, sometime today' is big.

\$ time ruby num_maze.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.768s
user    0m1.725s
sys     0m0.022s

;-)

===== SPOILER WARNING =====

The following might be considered a spoiler, if you want to solve the
quiz

Some tips:

Try to abstract the problem: You are in a numeric maze, you have two or
three ways to go next, you want to find the _shortest path_ to the
target.
You don't want to visit the same number twice on your path.

It is not necessary to find some specific strategy/algorithm for this
special case, so don't concentrate to much on the "mathematical
problem".

There were similar quizzes in the past, check out their solutions.```
on 2006-01-01 11:25
```On 1/1/06, Dominik B. <removed_email_address@domain.invalid> wrote:
> ;-)
I wrote a heuristic solver by abusing the properties of the
mathematical problem. It doesn't find the shortest transformation
sequence but runs pretty fast.

\$ time ruby numpuz.rb 150128850109293 8591982807778218492

[150128850109293, 300257700218586, 300257700218588, 150128850109294,
150128850109296, 75064425054648, 37532212527324, 18766106263662,
18766106263664, 9383053131832, 4691526565916, 2345763282958,
2345763282960, 1172881641480, 586440820740, 293220410370,
293220410372, 146610205186, 146610205188, 73305102594, 73305102596,
36652551298, 36652551300, 18326275650, 18326275652, 9163137826,
9163137828, 4581568914, 4581568916, 2290784458, 2290784460,
1145392230, 1145392232, 572696116, 286348058, 286348060, 143174030,
143174032, 71587016, 35793508, 17896754, 17896756, 8948378, 8948380,
4474190, 4474192, 2237096, 1118548, 559274, 559276, 279638, 279640,
139820, 69910, 69912, 34956, 17478, 17480, 8740, 4370, 4372, 2186,
2188, 1094, 1096, 548, 274, 276, 138, 140, 70, 72, 36, 18, 20, 10, 12,
14, 28, 56, 58, 116, 118, 236, 238, 476, 952, 1904, 1906, 3812, 3814,
7628, 7630, 15260, 15262, 30524, 61048, 122096, 122098, 244196,
244198, 488396, 976792, 976794, 1953588, 1953590, 3907180, 7814360,
7814362, 15628724, 31257448, 31257450, 62514900, 62514902, 125029804,
250059608, 250059610, 500119220, 1000238440, 1000238442, 2000476884,
2000476886, 4000953772, 4000953774, 8001907548, 16003815096,
16003815098, 32007630196, 32007630198, 64015260396, 128030520792,
256061041584, 256061041586, 512122083172, 1024244166344,
1024244166346, 2048488332692, 2048488332694, 4096976665388,
4096976665390, 8193953330780, 8193953330782, 16387906661564,
32775813323128, 65551626646256, 131103253292512, 131103253292514,
262206506585028, 524413013170056, 1048826026340112, 1048826026340114,
2097652052680228, 4195304105360456, 4195304105360458,
8390608210720916, 16781216421441832, 33562432842883664,
67124865685767328, 67124865685767330, 134249731371534660,
134249731371534662, 268499462743069324, 268499462743069326,
536998925486138652, 536998925486138654, 1073997850972277308,
1073997850972277310, 2147995701944554620, 2147995701944554622,
4295991403889109244, 4295991403889109246, 8591982807778218492]

real    0m0.037s
user    0m0.029s
sys     0m0.008s

Anyone want to provide the shortest solution to that? ;-)```
on 2006-01-01 13:34
```Ilmari H. wrote:
> I wrote a heuristic solver by abusing the properties of the
> mathematical problem. It doesn't find the shortest transformation
> sequence but runs pretty fast.
>
> \$ time ruby numpuz.rb 150128850109293 8591982807778218492
>
> [150128850109293, 300257700218586, 300257700218588, 150128850109294,
> 150128850109296, 75064425054648, 37532212527324, 18766106263662,
> 18766106263664, 9383053131832, 4691526565916, 2345763282958,
> 2345763282960, 1172881641480, 586440820740, 293220410370,
> 293220410372, 146610205186, 146610205188, 73305102594, 73305102596,
> 36652551298, 36652551300, 18326275650, 18326275652, 9163137826,
> 9163137828, 4581568914, 4581568916, 2290784458, 2290784460,
> 1145392230, 1145392232, 572696116, 286348058, 286348060, 143174030,
> 143174032, 71587016, 35793508, 17896754, 17896756, 8948378, 8948380,
> 4474190, 4474192, 2237096, 1118548, 559274, 559276, 279638, 279640,
> 139820, 69910, 69912, 34956, 17478, 17480, 8740, 4370, 4372, 2186,
> 2188, 1094, 1096, 548, 274, 276, 138, 140, 70, 72, 36, 18, 20, 10, 12,
> 14, 28, 56, 58, 116, 118, 236, 238, 476, 952, 1904, 1906, 3812, 3814,
> 7628, 7630, 15260, 15262, 30524, 61048, 122096, 122098, 244196,
> 244198, 488396, 976792, 976794, 1953588, 1953590, 3907180, 7814360,
> 7814362, 15628724, 31257448, 31257450, 62514900, 62514902, 125029804,
> 250059608, 250059610, 500119220, 1000238440, 1000238442, 2000476884,
> 2000476886, 4000953772, 4000953774, 8001907548, 16003815096,
> 16003815098, 32007630196, 32007630198, 64015260396, 128030520792,
> 256061041584, 256061041586, 512122083172, 1024244166344,
> 1024244166346, 2048488332692, 2048488332694, 4096976665388,
> 4096976665390, 8193953330780, 8193953330782, 16387906661564,
> 32775813323128, 65551626646256, 131103253292512, 131103253292514,
> 262206506585028, 524413013170056, 1048826026340112, 1048826026340114,
> 2097652052680228, 4195304105360456, 4195304105360458,
> 8390608210720916, 16781216421441832, 33562432842883664,
> 67124865685767328, 67124865685767330, 134249731371534660,
> 134249731371534662, 268499462743069324, 268499462743069326,
> 536998925486138652, 536998925486138654, 1073997850972277308,
> 1073997850972277310, 2147995701944554620, 2147995701944554622,
> 4295991403889109244, 4295991403889109246, 8591982807778218492]
>
> real    0m0.037s
> user    0m0.029s
> sys     0m0.008s
>
> Anyone want to provide the shortest solution to that? ;-)

Beautiful!

So many bignums, so few cycles...

Would be interesting to see your heuristic solution applied to something
human, like 222->999.

I think we have to rephrase

> Anyone want to provide the shortest solution to that? ;-)

to

Anyone want to provide   a shorter  solution to that?

Christer```
on 2006-01-01 14:19
```Christer N. wrote:

Ilmari H. wrote:
>> ..., 8740, 4370, 4372, 2186,
>> 2188, 1094, 1096, 548, 274, 276, 138, 140, 70, 72, 36, 18, 20, 10, 12,
>> 14, 28, 56, 58, 116, 118, 236, 238, 476, 952, 1904, 1906, 3812, 3814,
>> 7628, 7630, ...

I can confirm that the four digit subproblem 8740 -> 7630 is solved
optimally.

Is it possible that the complete problem is solved optimally?

Christer```
on 2006-01-01 14:26
```> Ilmari H. wrote:

The Five digit subproblem is solved optimally.

Christer```
on 2006-01-01 14:31
```I'm still doing this in far too much of a brute force sort of method.
I think tomorrow I'll work more towards optimizing with some sneaky
math.  One advantage of brute force is that, if you do it right, you
can be sure that you're getting a shortest path.  I've found a couple
of shorter paths from Steve's, but I can't deal at all with his bigger
test cases.

Current progress:

~/Documents/Projects/ruby_quiz peter\$ ruby 60.rb
Started
.......E......E.E.E.E......
Better solution found:
[300, 150, 152, 76, 38, 40, 20, 10, 12, 6, 8, 4, 2]
[300, 150, 152, 76, 38, 40, 20, 10, 12, 14, 16, 8, 4, 2]
......E......E.................E.E...................E..................E....................E...................E...................
Better solution found:
[900, 450, 452, 226, 228, 114, 116, 58, 60, 30, 32, 16, 8]
[900, 902, 904, 452, 226, 228, 114, 116, 58, 60, 30, 32, 16, 8]
....................E...............................................................................................................EEEEEEEEE.EEEEEEEEEE.EEEEEEEEEE.EEEEEEEEEE..EEEEEEEEEE.EEEEEEEEEE.EEEEEEEEEE.EEEEEEEEEE.EEEEEEEEEE.EEEEEEEEEE.E................................................................................
Finished in 434.789958 seconds.

1) Error:
test_case_104(TestNumericMaze):
RuntimeError: Too Slow

[snip...]

483 tests, 738 assertions, 0 failures, 114 errors

I'm having my solve method throw an error when it is taking too long
to evaluate to more easily distinguish giving an invalid result from
just taking too long.

Slightly updated test suite:
http://rafb.net/paste/results/SKaTxv60.nln.html```
on 2006-01-01 14:44
```Christer N. wrote:
> Christer N. wrote:
>
> Ilmari H. wrote:
>>> ..., 8740, 4370, 4372, 2186,
>>> 2188, 1094, 1096, 548, 274, 276, 138, 140, 70, 72, 36, 18, 20, 10, 12,
>>> 14, 28, 56, 58, 116, 118, 236, 238, 476, 952, 1904, 1906, 3812, 3814,
>>> 7628, 7630, ...
>
> I can confirm that the four digit subproblem 8740 -> 7630 is solved
> optimally.
>
> Is it possible that the complete problem is solved optimally?
>
> Christer

17478, 17480, 8740, 4370, 4372, 2186,
> 2188, 1094, 1096, 548, 274, 276, 138, 140, 70, 72, 36, 18, 20, 10, 12,
> 14, 28, 56, 58, 116, 118, 236, 238, 476, 952, 1904, 1906, 3812, 3814,
> 7628, 7630, 15260, 15262, 30524, 61048

I think this is optimal as well.```
on 2006-01-01 17:14
```On Sun, Jan 01, 2006 at 06:23:08PM +0900, Ilmari H. wrote:
} On 1/1/06, Dominik B. <removed_email_address@domain.invalid> wrote:
} >
} > \$ time ruby num_maze.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.768s
} > user    0m1.725s
} > sys     0m0.022s
} >
} > ;-)
}
} I wrote a heuristic solver by abusing the properties of the
} mathematical problem. It doesn't find the shortest transformation
} sequence but runs pretty fast.
}
} \$ time ruby numpuz.rb 150128850109293 8591982807778218492
[...]
} real    0m0.037s
} user    0m0.029s
} sys     0m0.008s
}
} Anyone want to provide the shortest solution to that? ;-)

Whatever you're doing, I'm doing much the same thing. I get the
identical
solution in almost identically the same time (note: Dual G4 800):

real    0m0.037s
user    0m0.028s
sys     0m0.009s

I wouldn't call my solver heuristic, though. There is exactly one
heuristic
optimization. Other than that it is pretty much a straight analysis of
the
problem, with a nasty cleanup at the end to remove path loops.

By the way, I can't get to
http://swaits.com/articles/2005/12/31/ruby-quiz-60... at the
moment. It seems to be down. Would anyone like to post some canonical
test
cases to the list?

--Greg```
on 2006-01-01 17:48
```On Dec 30, 2005, at 7:37 AM, Ruby Q. 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.

James Edward G. 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

#
# 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(", ")```
on 2006-01-01 18:03
```On 1/1/06, Christer N. <removed_email_address@domain.invalid> wrote:
> Would be interesting to see your heuristic solution applied to something
> human, like 222->999.

Ok, here's a couple. They tend to be a step or two worse than optimal,
the worst case performance I've run into yet is 4x longer path (with
255 -> 257.)

ruby numpuz.rb 22 999
[22, 24, 12, 14, 28, 30, 60, 62, 124, 248, 496, 498, 996, 998, 1996,
1998, 999]

ruby numpuz.rb 222 999
[222, 224, 112, 56, 28, 30, 60, 62, 124, 248, 496, 498, 996, 998,
1996, 1998, 999]

ruby numpuz.rb 222 9999
[222, 224, 112, 56, 28, 14, 16, 18, 36, 38, 76, 78, 156, 312, 624,
1248, 2496, 2498, 4996, 4998, 9996, 9998, 19996, 19998, 9999]

ruby numpuz.rb 22222 99999
[22222, 22224, 11112, 5556, 2778, 2780, 1390, 1392, 696, 348, 174,
176, 88, 44, 22, 24, 48, 96, 192, 194, 388, 390, 780, 1560, 1562,
3124, 6248, 12496, 12498, 24996, 24998, 49996, 49998, 99996, 99998,
199996, 199998, 99999]```
on 2006-01-01 18:06
```On Jan 1, 2006, at 15:47, James Edward G. II wrote:

> On Dec 30, 2005, at 7:37 AM, Ruby Q. 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.

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 2006-01-01 18:10
```On Jan 1, 2006, at 8:04 AM, Matthew S. 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```
on 2006-01-01 18:28
```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```
on 2006-01-01 18:34
```My solution is not optimal nor fast.. but different than the other
solutions so far.

--
Simon S.

def solve(a, b)
t = "h#{b}"
t = "h#{b*=2}" + t while b < a
s = "#{a}d#{a*2}"
a *= 2;b *= 2
s += "a#{a+=2}" while a < b
s += t
loop do
l = s.length
s.gsub!(/(\d+)d\d+a\d+a/) { "#{\$1}a#{\$1.to_i + 2}d" }
s.gsub!(/4a6a8/, '4d8')
s.gsub!(/(\D|^)(\d+)(?:\D\d+)+\D\2(\D|\$)/) {\$1 + \$2 + \$3}
break if s.length == l
end
s.scan(/\d+/).map{|i|i.to_i}
end```
on 2006-01-01 19:00
```On 12/30/05, Ruby Q. <removed_email_address@domain.invalid> wrote:
>
> 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]
>
>

# The problem can be thought of in binary.
# (Which also happens to make solving by hand easy.)
#
# 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 = :/
# 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 :/
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 :/
a.last / 2
when :+
a.last + 2
end
}
a
end

if __FILE__ == \$0
p(nsrch(*ARGV.map{|n| n.to_i}))
end```
on 2006-01-01 19:03
```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 = [lambda { |x,state| (state != :halve) ? [x*2, :double] : nil },
#
double
lambda { |x,state| (x.modulo(2).zero? and state != :double) ?
[x/2, :halve] : nil }, #halve
lambda { |x,state| [x+2, :initial]}] # add_two

def solver(from, to)

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

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

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

retval
end

# cant use hash default proc memoization since i dont want to memoize on
the

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

key = [from, to, maxdepth]

if not @memo.has_key? key
@memo[key] = 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 = ARROWS.map { |f| f.call(from, state) }.compact

if next_steps.assoc(to)
[from, to]
else
# havent found it yet, recur
kids = 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 = kids.sort_by { |x| x.length }.first
[from, *best]
end
end
end

list = [ [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 2006-01-01 19:21
```#!/usr/bin/env ruby
#
# Ruby Q. #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 B.: 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

@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 B.)
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
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
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)```
on 2006-01-01 19:24
```On 1/1/06, Christer N. <removed_email_address@domain.invalid> wrote:
>
> Is it possible that the complete problem is solved optimally?
>
> Christer

It's possible, but I don't know.```
on 2006-01-01 19:42
```On Jan 1, 2006, at 11:01 AM, Maurice Codik wrote:

> 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 G. II```
on 2006-01-01 20:30
```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]

while(toqueue.length>0 && fromqueue.length>0)
fromnode = fromqueue.shift
tonode = toqueue.shift
if(toedges[fromnode] || fromnode==to) then
break
elsif(fromedges[tonode] || tonode==from) then
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

chain = []
while(fromedges[currnode] != :start)
chain.unshift currnode if currnode != to
currnode = fromedges[currnode]
end
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)```
on 2006-01-01 20:39
```I've posted my solution, along with a few words about my approach, at
<http://www.io.com/~jimm/rubyquiz/quiz60/>.

Jim
--
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```
on 2006-01-01 21:12
```Maurice,

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

- Mark```
on 2006-01-01 21:54
```Mark: could you explain what you mean? these were outputs from that
prog:

solve(3,1233):
[3, 6, 8, 16, 18, 36, 38, 76, 152, 154, 308, 616, 1232, 2464, 2466,
1233]
solve(1,25):
[1, 3, 6, 12, 24, 48, 50, 25]

looks like it finds them just fine... or do u mean that these arent the
optimal paths?

James: Now that I think about it, your optimization and mine are almost
equivalent, I think-- I'm fairly certain that the only way to get to a
number that you've been to already is by using consecutive pairs of
double/half.. since the add_two operation isn't invertable in this quiz.

Maurice```
on 2006-01-01 22:07
`Nevermind, a copy and paste error on my part!`
on 2006-01-01 22:28
```On 2005-12-31, James Edward G. II <removed_email_address@domain.invalid> wrote:
> On Dec 31, 2005, at 12:26 PM, Jim M. 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.
>
> I'm using a Dual 2 Ghz G5, so the hardware is at least *some* of the
> difference.

With one simple optimisation (no pruning), on a 700 MHz Duron:

kero@chmeee:~/pub/ruby/quiz\$ time ruby 60-num_maze.rb 22 999
real    0m0.772s
user    0m0.588s
sys     0m0.076s

But I'm not sure I want to run 8740 7630
let alone 150128850109293 8591982807778218492```
on 2006-01-01 22:43
```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. :)

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)```
on 2006-01-01 23:19
```On Jan 1, 2006, at 19:54, Maurice Codik wrote:

> James: Now that I think about it, your optimization and mine are
> almost
> equivalent, I think-- I'm fairly certain that the only way to get to a
> number that you've been to already is by using consecutive pairs of
> double/half.. since the add_two operation isn't invertable in this
> quiz.
>
> Maurice

OK, so this sort of counter-example is pretty trivial, but the +2 can
be composed to be equivalent to the double operation starting from
even numbers, so the double/halve optimisation doesn't necessarily
eliminate re-visiting a number in a path (but strikes me that it
would do in the overwhelming majority of cases).

4,  6,  8,  4
+2  +2  /2
| *2 |

You could heuristicise (neologisms are a New Year's resolution of
mine) your way out of this by limiting chains of +2 but, there also
exist other more complicated composite operations which are
equivalent to doubling, but aren't as easy to optimise away:

6,  3,  5,  10,  12,  6 oops!
/2  +2  *2   +2   /2
| *2          |

14,  7,  9,  11,  22,  24,  26,  28,  14 oops!
/2  +2  +2   *2   +2   +2   +2   /2
| *2                         |

For both these sorts of exceptions, though, you'd need more and more
instances of +2 in the double-equivalent sequence as the initial
number becomes higher and higher, so I don't expect this will cause
any particular pain in a practical implementation.

matt.```
on 2006-01-01 23:40
```I'm another newbie to the ruby-quiz.  This is a dirt-simple BFS. it
takes 8 seconds on my machine to do solve(22,999); i make sure no path
hits upon a number a previous path had ever hit upon, and i discovered
it'd run slightly faster by simply checking to see if my path is
halving right after doubling or doubling right after halving, and
*then* checking the entire list of numbers passed. (hope that made
sense)

i had toyed around with other optimizations but none seemed elegant
and time-saving enough to be worth it. what i was hoping for was a
nice way to identify when certain paths are careening insanely
off-path and clearly won't be the correct answer...i have yet to see
the solution that can do things like solve(222,9999) in
milliseconds...i am anxiously awaiting one...or did i miss it?

here is mine:
--------------------------------
def solve(start, finish)
paths = [[start, start+2], [start, start*2]];
paths.push([start, start/2]) if (start%2 == 0);
allNum = paths.flatten.uniq;
loop {
newP = Array.new();
paths.each{ |path|
curN = path.last;
unless(allNum.include?(curN+2))
return path.push(curN+2) if (curN+2 == finish);
allNum.push(curN+2);
newP.push(path.clone.push(curN+2));
end
unless (allNum.include?(curN*2))
return path.push(curN*2) if (curN*2 == finish);
allNum.push(curN*2);
newP.push(path.clone.push(curN*2));
end
if (curN%2 == 0 and not allNum.include?(curN/2))
return path.push(curN/2) if (curN/2 == finish);
allNum.push(curN/2);
newP.push(path.clone.push(curN/2));
end
}
paths = newP;
}
end```
on 2006-01-02 00:14
```Here's my solution. It uses the A* algorithm and the priority queue
stuff
from quiz #44. Btw, I'm new to ruby quiz, too. :)

Pablo

---

#!/usr/bin/ruby

INF = 1.0/0.0
LOG2 = Math.log(2)

# The priority queue is taken from Ruby Q. #44 (by Levin A.).
class PriorityQueue
def initialize
@storage = Hash.new { |hash, key| hash[key] = [] }
end

def push(data, priority)
@storage[priority] << data
end

def next
return nil if @storage.empty?
key, val = *@storage.min
result = val.shift
@storage.delete(key) if val.empty?
return result
end
end

def solve(a, b)
return nil if a < 0 || b < 1
q = PriorityQueue.new
cost = Hash.new{INF}
parent = {}

q.push a, 0
cost[a] = 0

logb = Math.log(b)

while n = q.next
break if n == b

sub = []
sub << n*2
sub << n/2 if n%2 == 0
sub << n+2

sub.each do |s|
# Number of operations from a to s
c = cost[n] + 1

next if cost[s] <= c
cost[s] = c
parent[s] = n

# h = estimated min. number of operations required from s to b
x = (s > 0) ? s : 1   # log(0) = error
# This computes the number of *2 or /2 operations needed
# to go from s to b
h = ((logb-Math.log(x))/LOG2).abs.floor
q.push s, c + h
end
end

# Build the path backwards
path, n = [b], b
while n = parent[n]
path << n
end
path.reverse
end

if __FILE__ == \$0
if ARGV.length == 2
steps = solve(ARGV[0].to_i, ARGV[1].to_i)
puts "#{steps.inspect} (#{steps.length})"
else
puts "Usage: #{\$0} <from> <to>"
end
end```
on 2006-01-02 00:20
```> 1248, 2496, 2498, 4996, 4998, 9996, 19992, 19994, 9997, 9999
>
> real    96m13.978s
> user    49m27.502s
> sys     46m22.817s
>
> Guess I need more than my one optimization now.  <laughs>

I stopped at 222 -> 4998 which took 43 seconds. Each next step will take
a rough factor 3, so I'll end up near 3 hours. Oops...

First pruning... Slices running time to less than 0.2 seconds *wheee*
and to
9999 in slightly more than 0.2 seconds (which proves I got rid of that
nasty
exponential thing).```
on 2006-01-02 00:20
```Hi all,

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

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,

--
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(t+2, t) if (t <- 2) || (0 <= t)
end
end
return @result
end

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```
on 2006-01-02 00:38
```In article <removed_email_address@domain.invalid>,
>> examples people have been throwing around, but it's pretty simple.
>
>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?

I kept thinking that a recursive solution would be the easiest way to
go, but
I quickly found that even some of the most trival testcases overwhelmed
the
stack :-(  (not too surprising, I guess, given the size of the search
space).

If I have time to get it done I'll post my non-recursive version (that
is
unfortuneately becoming quite bloated, I think).

Phil```
on 2006-01-02 00:47
```Ilmari H. 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 [x] + down(x*2) if x.modulo(2)==1
return [x] + down(x/2) if x.modulo(4)==0
[x] + down(x-2)
end

def up(x)
return [] if x==0
return [1] if x==1
return [2,1] if x==2
return [x] + up(x*2) if x.modulo(2)==1
return [x] + up(x/2) if x.modulo(4)==0
[x] + 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```
on 2006-01-02 01:05
```> [snip...]
>
> 483 tests, 738 assertions, 0 failures, 114 errors
>
> I'm having my solve method throw an error when it is taking too long
> to evaluate to more easily distinguish giving an invalid result from
> just taking too long.
>
> Slightly updated test suite: http://rafb.net/paste/results/SKaTxv60.nln.html

So very sorry...

http://rafb.net/paste/results/bsHQO336.html```
on 2006-01-02 01:11
```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"```
on 2006-01-02 01:26
```On Jan 1, 2006, at 4:37 PM, Phil T. wrote:

> I kept thinking that a recursive solution would be the easiest way
> to go, but
> I quickly found that even some of the most trival testcases
> overwhelmed the
> stack :-(  (not too surprising, I guess, given the size of the
> search space).

This seems odd to me.  Wouldn't a recursive breadth-first (or even
iterative depth-first) only ever recurse as deep as there are numbers
in the solution?  Everything we've seen so far should be well within
solvable that way, unless I'm missing something obvious here...

James Edward G. II```
on 2006-01-02 01:35
```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 B. 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. :)

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

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

James Edward G. II```
on 2006-01-02 01:39
```On Jan 1, 2006, at 4:20 PM, Steven Aerts wrote:

> (especially how
> you think about using the throw catch statement).

Looking good so far.  Here's some general comments:

1.  We usually do variable and method names in "snake_case" style and
class names in "CamelCase" (as you had them).
2.  Most of us write infinite loops in Ruby as loop do ... end.

These are just style nitpicks of course though, so don't take them
too seriously.  ;)

James Edward G. II```
on 2006-01-02 01:45
```In article

> i had toyed around with other optimizations but none seemed elegant
> and time-saving enough to be worth it. what i was hoping for was a
> nice way to identify when certain paths are careening insanely
> off-path and clearly won't be the correct answer...i have yet to see
> the solution that can do things like solve(222,9999) in
> milliseconds...i am anxiously awaiting one...or did i miss it?

I think one should look at the mathematical side of the problem first.
Here are some starting ideas:

- write both the starting and the target number in binary
- notice that the three operators do the following:
- add a zero to the right = left shift the number one position
- remove a zero from the right = right shift the number one position
- flip a bit in the one-but-rightmost position, possibly changing
consecutive ones to zeroes to the left of this bit

Only the first operation can possibly increase the number of zeroes in
the number (always by one).

Only the second one can change the parity of the number.

Only the last one can possibly change the number of ones in the number
(either increasing it by one, or decreasing it by possibly arbitrary
amounts)

Looking at the example (222,9999), I see the following:
222 = 0x00DE =           1101 1110   (2 zeroes, 6 ones)
9999 = 0x270F =   10 0111 0000 1111   (5 zeroes, 8 ones)

From this, we can see that we must do at least 3 left shifts (to obtain
the five zeroes), at least one right shift (to change parity), and at
least one '+2' (to change the number of ones)

Looking at it in a different way: we must get a '1' in position 14 from
the right. That '1' can only come from position 13, using either the
'*2' or the '+2' (with sufficient overflows) operations.

There is no '1' in position 13. To get one there, we need one at
position 12, etc.

In the end to get a '1' in position 14 is by moving the one in position
8 there, using a combination of at least six '*2' or '+2' operations.
If we do that using '*2' only, the '1' in position 7 would move to
position 13. We do not want a '1' there, so we should use '+2' at least
once.

I think logic like this will lead to a better understanding of the
problem, and possibly to more efficient solutions.

For instance: I would guess that many of the optimal solutions are
rather dull, ending in a series of ('*2') or ('+2', '*2') operations to
shift in zero and one bits, followed by a single '/2' if the target
value is odd (WARNING: this is just a hunch; I may be completely wrong
here)

Reinder```
on 2006-01-02 02:12
```This is my first Ruby quiz. I was hoping to have the whole thing done
by the end of the first 48 hours, but I kept getting hung up on edge
cases.
I did figure out the binary approach on my own, though.

On Mon, Jan 02, 2006 at 08:42:56AM +0900, Reinder V. wrote:
[...]
} I think one should look at the mathematical side of the problem first.
} Here are some starting ideas:
}
} - write both the starting and the target number in binary
} - notice that the three operators do the following:
}   - add a zero to the right = left shift the number one position
}   - remove a zero from the right = right shift the number one position
}   - flip a bit in the one-but-rightmost position, possibly changing
}     consecutive ones to zeroes to the left of this bit
[...]
} I think logic like this will lead to a better understanding of the
} problem, and possibly to more efficient solutions.

This is exactly what I started from. My solution involves no search
algorithm. It is entirely rule-based, including two optimization rules
which could be called heuristic. (My code is at the end of this
message.)
The optimization rules are that two adds are cheaper than (and equal to)
half-half-add-double-double. I'm pretty sure the results are guaranteed
to
be optimal, too.

} For instance: I would guess that many of the optimal solutions are
} rather dull, ending in a series of ('*2') or ('+2', '*2') operations
to
} shift in zero and one bits, followed by a single '/2' if the target
} value is odd (WARNING: this is just a hunch; I may be completely wrong
} here)

Yeah, that's what I'm seeing. Take a look at some results (code below
the
line of ####):

% ruby test60.rb 2 9
[2, 4, 8, 16, 18, 9]

Ops = 5: dddah

real	0m0.022s
user	0m0.017s
sys	0m0.006s

% ruby test60.rb 9 2
[9, 18, 20, 10, 12, 6, 8, 4, 2]

Ops = 8: dahahahh

real	0m0.023s
user	0m0.017s
sys	0m0.008s

% ruby test60.rb 999 222
[999, 1998, 2000, 1000, 500, 250, 252, 126, 63, 65, 67, 69, 71, 142,
144, 72, 36, 38, 19, 21, 23, 25, 27, 54, 108, 110, 220, 222]

real	0m0.023s
user	0m0.018s
sys	0m0.005s

% ruby test60.rb 222 999
[222, 224, 112, 114, 116, 118, 120, 122, 124, 248, 496, 498, 996, 998,
1996, 1998, 999]

real	0m0.022s
user	0m0.015s
sys	0m0.007s

% ruby test60.rb 32 48
[32, 16, 18, 20, 22, 24, 48]

real	0m0.021s
user	0m0.013s
sys	0m0.008s

% ruby test60.rb 48 32
[48, 24, 26, 28, 30, 32]

Ops = 5: haaaa

real	0m0.022s
user	0m0.014s
sys	0m0.008s

% ruby test60.rb 150128850109293 8591982807778218492
[150128850109293, 300257700218586, 300257700218588, 150128850109294,
150128850109296, 75064425054648, 37532212527324, 18766106263662,
18766106263664, 9383053131832, 4691526565916, 2345763282958,
2345763282960, 1172881641480, 586440820740, 293220410370, 293220410372,
146610205186, 146610205188, 73305102594, 73305102596, 36652551298,
36652551300, 18326275650, 18326275652, 9163137826, 9163137828,
4581568914, 4581568916, 2290784458, 2290784460, 1145392230, 1145392232,
572696116, 286348058, 286348060, 143174030, 143174032, 71587016,
35793508, 17896754, 17896756, 8948378, 8948380, 4474190, 4474192,
2237096, 1118548, 559274, 559276, 279638, 279640, 139820, 69910, 69912,
34956, 17478, 17480, 8740, 4370, 4372, 2186, 2188, 1094, 1096, 548, 274,
276, 138, 140, 70, 72, 36, 18, 20, 22, 24, 26, 28, 56, 58, 116, 118,
236, 238, 476, 952, 1904, 1906, 3812, 3814, 7628, 7630, 15260, 15262,
30524, 61048, 122096, 122098, 244196, 244198, 488396, 976792, 976794,
1953588, 1953590, 3907180, 7814360, 7814362, 15628724, 31257448,
31257450, 62514900, 62514902, 125029804, 250059608, 250059610,
500119220, 1000238440, 1000238442, 2000476884, 2000476886, 4000953772,
4000953774, 8001907548, 16003815096, 16003815098, 32007630196,
32007630198, 64015260396, 128030520792, 256061041584, 256061041586,
512122083172, 1024244166344, 1024244166346, 2048488332692,
2048488332694, 4096976665388, 4096976665390, 8193953330780,
8193953330782, 16387906661564, 32775813323128, 65551626646256,
131103253292512, 131103253292514, 262206506585028, 524413013170056,
1048826026340112, 1048826026340114, 2097652052680228, 4195304105360456,
4195304105360458, 8390608210720916, 16781216421441832,
33562432842883664, 67124865685767328, 67124865685767330,
134249731371534660, 134249731371534662, 268499462743069324,
268499462743069326, 536998925486138652, 536998925486138654,
1073997850972277308, 1073997850972277310, 2147995701944554620,
2147995701944554622, 4295991403889109244, 4295991403889109246,
8591982807778218492]

Ops = 171:

real	0m0.039s
user	0m0.032s
sys	0m0.007s

% ruby test60.rb 8591982807778218492 150128850109293
[8591982807778218492, 4295991403889109246, 4295991403889109248,
2147995701944554624, 1073997850972277312, 536998925486138656,
268499462743069328, 134249731371534664, 67124865685767332,
33562432842883666, 33562432842883668, 16781216421441834,
16781216421441836, 8390608210720918, 8390608210720920, 4195304105360460,
2097652052680230, 2097652052680232, 1048826026340116, 524413013170058,
524413013170060, 262206506585030, 262206506585032, 131103253292516,
65551626646258, 65551626646260, 32775813323130, 32775813323132,
16387906661566, 16387906661568, 8193953330784, 4096976665392,
2048488332696, 1024244166348, 512122083174, 512122083176, 256061041588,
128030520794, 128030520796, 64015260398, 64015260400, 32007630200,
16003815100, 8001907550, 8001907552, 4000953776, 2000476888, 1000238444,
500119222, 500119224, 250059612, 125029806, 125029808, 62514904,
31257452, 15628726, 15628728, 7814364, 3907182, 3907184, 1953592,
976796, 488398, 488400, 244200, 122100, 61050, 61052, 30526, 30528,
15264, 7632, 3816, 1908, 954, 956, 478, 480, 240, 120, 60, 30, 32, 34,
36, 38, 40, 42, 44, 46, 48, 50, 25, 27, 29, 31, 33, 66, 68, 136, 272,
544, 546, 1092, 2184, 4368, 8736, 8738, 17476, 34952, 34954, 69908,
139816, 139818, 279636, 559272, 1118544, 1118546, 2237092, 2237094,
4474188, 8948376, 17896752, 35793504, 35793506, 71587012, 71587014,
143174028, 286348056, 572696112, 572696114, 1145392228, 2290784456,
4581568912, 9163137824, 18326275648, 36652551296, 73305102592,
146610205184, 293220410368, 586440820736, 586440820738, 1172881641476,
1172881641478, 2345763282956, 4691526565912, 4691526565914,
9383053131828, 9383053131830, 18766106263660, 37532212527320,
37532212527322, 75064425054644, 75064425054646, 150128850109292,
300257700218584, 300257700218586, 150128850109293]

Ops = 157:

real	0m0.039s
user	0m0.030s
sys	0m0.010s

(All times on a dual G4 800.)

##### test60.rb
################################################################

require '60'
include NumericMazeSolver

src = ARGV[0].to_i
dst = ARGV[1].to_i

solution, ops = Solver.new(src, dst).solve
p solution
puts "\nOps = #{solution.length-1}: #{ops}"

##### 60.rb
####################################################################

module NumericMazeSolver

module BitHelpers

def bit_len(num)
return num.to_s(2).length
end

end

class NumericPath

def initialize(s)
@result = [s]
@ops = ''
end

def reset(s = nil)
@result.slice!(1, @result.length)
@result[0] = s if s
@ops = ''
end

def cur
@result.last
end

def src
@result.first
end

@result << (cur + 2)
@ops << 'a'
#p @result
end

def double
@result << (cur << 1)
@ops << 'd'
#p @result
end

def halve
c = cur
fail "Trying to halve an odd number: #{c}" unless (c % 2) == 0
c >>= 1
@result << c
@ops << 'h'
#p @result
end

double
halve
end

end

class Solver
include BitHelpers

def validate(src, dst)
fail "We only deal with integers." unless
(dst.kind_of? Integer) && (src.kind_of? Integer)
fail "Not dealing with negative numbers" if
(dst<0) || (src<0)
fail "Can't get to zero from a positive number." if
(dst==0) && (src>0)
end

def initialize(src, dst)
validate(src, dst)
@dst = dst
@dst_bit_len = bit_len(@dst)
@result = NumericPath.new(src)
end

def shifted_diff
tmpsrc = @result.cur
tmpdst = @dst
src_bit_len = bit_len(tmpsrc)
shift = src_bit_len - @dst_bit_len
if shift < 0
tmpsrc >>= shift #really a left shift, since shift is negative
else
tmpdst <<= shift
end
xor_not_sub = tmpdst < tmpsrc
diff = xor_not_sub ? (tmpdst ^ tmpsrc) : (tmpdst - tmpsrc)
top_matched = bit_len(tmpdst) - bit_len(diff)
return [ diff, shift, top_matched, src_bit_len ]
end

def solve
@result.reset
while @result.cur != @dst
diff, shift, top_matched, src_bit_len = shifted_diff
dist_from_top = src_bit_len - top_matched
#       p @result.result
#       puts "src  = #{@result.cur.to_s(2)}"
#       puts "dst  = #{@dst.to_s(2)}"
#       puts "diff = #{diff.to_s(2)}\n"
#       puts "dist = #{dist_from_top}\n"
if diff==0
while shift > 0
@result.halve
shift -= 1
end
while shift < 0
@result.double
shift += 1
end
elsif dist_from_top > 5
# getting there
try_to_halve(@result.cur)
elsif dist_from_top == 5
# one away!
# do this now in case we'd have to double-add-halve
# unnecessarily later
bit = 1 << (2 + shift + top_matched)
if (diff&bit) != 0
end
@result.halve
elsif dist_from_top == 4
if shift > 0
try_to_halve(@result.cur)
else
end
elsif dist_from_top == 3
if shift > 0
try_to_halve(@result.cur)
else
end
elsif dist_from_top == 2
else
@result.double
end
end
return [ @result.result, @result.ops ]
end

private

def try_to_halve(cur)
if ((cur&1) != 0)
# odd, so we can't halve yet
@result.double
elsif ((cur&2) != 0)
# won't be able to halve again
else
@result.halve
end
end

end

end

# vim:ts=2 sw=2 expandtab foldmethod=syntax foldcolumn=5
################################################################################

} Reinder
--Greg```
on 2006-01-02 03:04
```Gregory S. wrote:
> This is my first Ruby quiz. I was hoping to have the whole thing done
> by the end of the first 48 hours, but I kept getting hung up on edge
> cases.
> I did figure out the binary approach on my own, though.
>

Gregory, this is an amazing solution! However I got a failure trying
some arbitrarily selected src and dst values:

\$ ruby test60.rb 4934939 39329291
./60.rb:47:in `halve': Trying to halve an odd number: 49 (RuntimeError)
from ./60.rb:127:in `solve'
from test60.rb:7```
on 2006-01-02 03:18
```Kenneth C. wrote:
> Gregory S. wrote:
>> This is my first Ruby quiz. I was hoping to have the whole thing done
>> by the end of the first 48 hours, but I kept getting hung up on edge
>> cases.
>> I did figure out the binary approach on my own, though.
>>
>
> Gregory, this is an amazing solution! However I got a failure trying
> some arbitrarily selected src and dst values:
>
> \$ ruby test60.rb 4934939 39329291
> ./60.rb:47:in `halve': Trying to halve an odd number: 49 (RuntimeError)
>         from ./60.rb:127:in `solve'
>         from test60.rb:7

Another case with smaller numbers:

\$ ruby test60.rb 49 64
./60.rb:47:in `halve': Trying to halve an odd number: 49 (RuntimeError)
from ./60.rb:127:in `solve'
from test60.rb:7```
on 2006-01-02 04:04
```> 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 use
@@max = [(source + 2) * 2, target * 2].max
which matches your roof almost exactly (The small assymetry is due to
the
missing sub2 operator, naturally.). The speedup is huge, as you can see
in some other posting of mine. I'm not entirely certain about the
optimality
property, but look at the following example:

13, 15, 30, 32, 16, 8  # what I thought of myself, pushing through the
roof
13, 26, 28, 14, 16, 8  # what the program found, not going through the
roof

Where the point is that an odd number either +1 or +3 can always be
halved
twice, and there is no point in adding two first (though maybe in
between).

I'm even thinking
[source*2+2, target*2].max
could be the roof, but hey, what's 2 more or less.

Ah well, this is not my field of expertise. Somebody can shed more light
on
this?

Bye,
Kero.```
on 2006-01-02 04:25
```Hey everyone,

Like so many people before me, this is my first Ruby Q. that I am
letting out to the world.

The interesting thing about my solution is that I managed to come up
with most of the previously mentioned optimizations for the BFS type of
solution and I came up with one more that has not yet been mentioned.
The value I use for deciding when to stop processing nodes because they
are too far from the max value is 3*max(start,end).  I saw that someone
used 2*max+4, so potentially my code could be improved by using that

The optimization that I have that I haven't seen anyone else use is
always starting with the maximum value and going to the smaller value.
This allows a lot of branches to be killed early because the value gets
too high.  Obviously, switching the start and end value means I need to
do num - 2 instead of num + 2 and also reverse the results.

Here is the money test on my 1.80 Ghz Pentium M:

solve_maze(222, 9999) = [222, 224, 112, 56, 28, 30, 32, 34, 36, 38, 76,
78, 156,
312, 624, 1248, 2496, 2498, 4996, 4998, 9996, 19992, 19994, 9997,
9999]
Length: 25
Tree size: 3608
0.120000   0.000000   0.120000 (  0.120000)

Sincerely,

Chris Parker
---------------------------------------------------------------------------------------------------------------------------------
require 'benchmark'

class Integer
def odd?
return self % 2 == 1
end

def even?
return !odd?
end
end

#Aliases for more quene like syntax
class Array

alias deq shift

alias enq <<

end

#Node class that knows both its children and parent
#Also, takes an intial value and a function to perform on that value
#When retrieving value from a node, the action is performed on the
value the first time
#All subsequent calls to value returns the return value of the first
time action was called with value
class Node

def initialize(value, action, parent=nil)
@value = value
@action = action
@children = []
@parent = parent
@done_action = false
end

#find the path to the root node from the current node
def get_path_to_root
if(parent == nil)
return [value]
end
parent.get_path_to_root<<value
end

def tree_size
#remember that if there are no children, aka this is a leaf node,
this returns 1, the initial value of result
return children.inject(1){|result,child| result + child.tree_size }
end

def value
if(!@done_action)
@done_action = true
return @value = @action.call(@value)
end
return @value
end

#print tree in a stringified array format
def tree_as_array
print "%d" % value
print "[" if children.length != 0
children.each_with_index{|child, index| child.tree_as_array; print
", " if index != children.length - 1}
print "]" if children.length != 0
end

end

#Solves the numeric maze with a bunch of optimizations
#Optimizations:
#(1) if parent action was halve, no child should be double
#(2) if parent action was double, no child should halve
#(3) if value of current node is greater than 3 times the
max(start_num, end_num), don't double or add 2
#(4) if value of current node has already been found, stop processing
this node
#(5) start_num should always be >= end_num.  This is an optimization
because of (3).
#    It kills many branches early, reducing the number of nodes in the
tree.  This is done
#    without breaking anything by making add_two be subtract_two and
the results be reversed if start and end are switched.
def solve_maze(start_num, end_num)
reverse_solution = start_num < end_num
if reverse_solution
add_two = lambda{ |int| int-2 }
start_num,end_num = end_num,start_num
else
add_two = lambda{ |int| int+2 }
end
double = lambda{ |int| int*2 }
halve = lambda{ |int| int/2 }
no_action = lambda{ |int| int } #special case for the start number
root = Node.new(start_num, no_action)
#keep track of numbers found to prevent repeat work
hash = {}
#the queue for the BFS
q = [root]
#start_num is always larger than end_num, numbers larger than this
are unlikely to be in
#an optimal solution
big_val = start_num*3
while q.length != 0
node = q.deq
val = node.value
if val == end_num
solution = node.get_path_to_root
solution.reverse! if reverse_solution
return [solution, root.tree_size()]
end
if !hash.has_key?(val)
node.children << Node.new(val, add_two, node) if val.abs <
big_val
node.children << Node.new(val,double,node) if node.action !=
halve && val.abs < big_val
node.children << Node.new(val,halve,node) if val.even? &&
node.action != double
node.children.each{|kid| q.enq(kid)}
hash[val] = true
end
end
end

if ARGV.length.odd? && !ARGV.length.zero?
print "Should be an even number of arguments in the format of
start_num end_num [start_num end_num] ...\n"
exit
end

puts Benchmark.measure{
ARGV.each_index do |index|
if index.odd?
next
else
start_num = ARGV[index].to_i
end_num = ARGV[index + 1].to_i
result = solve_maze(start_num, end_num)
print "solve_maze(",start_num, ", ",end_num,") =
",result[0].inspect,
"\nLength: ",result[0].length,
"\nTree size: ",result[1],"\n"
end
end
}```
on 2006-01-02 04:52
```On Mon, Jan 02, 2006 at 10:19:00AM +0900, Kenneth C. wrote:
} Kenneth C. wrote:
} > Gregory S. wrote:
} >> This is my first Ruby quiz. I was hoping to have the whole thing
done
} >> by the end of the first 48 hours, but I kept getting hung up on
edge
} >> cases.
} >> I did figure out the binary approach on my own, though.
} >>
} >
} > Gregory, this is an amazing solution! However I got a failure trying
} > some arbitrarily selected src and dst values:
} >
} > \$ ruby test60.rb 4934939 39329291
} > ./60.rb:47:in `halve': Trying to halve an odd number: 49
(RuntimeError)
} >         from ./60.rb:127:in `solve'
} >         from test60.rb:7
}
} Another case with smaller numbers:
}
} \$ ruby test60.rb 49 64
} ./60.rb:47:in `halve': Trying to halve an odd number: 49
(RuntimeError)
}         from ./60.rb:127:in `solve'
}         from test60.rb:7

Ratzafratz. I'll look into it. Did I mention running into problems with
edge cases? Oy. Thanks for the test cases.

--Greg```
on 2006-01-02 07:37
```On 1/2/06, Gregory S. <removed_email_address@domain.invalid> wrote:
> I'm pretty sure the results are guaranteed to
> be optimal, too.
>

\$ ruby test60.rb 255 257
[255, 510, 512, 514, 257]

Ops = 4: daah

Same problem I ran into :)```
on 2006-01-02 07:55
```On 1/2/06, Christer N. <removed_email_address@domain.invalid> wrote:
> > # 1000000010 >> 1
>                   <--  <--  <--
>     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 toyed with writing a optimize-function, which would take the
midstate list and find patterns that are known to be suboptimal. One
pattern to look for would be going from odd number to another, where
the distance is even and less than 32, which is the point where the

The optimizer iterates from start of path, and then for each number,
find from end of path the farthest matching number, replace the ops
between with optimized version.

E.g. for [255, 510, 512, 514, 257], start from 255, then iterate
remaining numbers from end to start, 257 matches, so replace the ops
between with +2 to get [255, 257].

Other patterns? Hmm, dunno. 12 -> 11 is suboptimal, 14 -> 13 too, both
demonstrating a faster solution that would be divide to odd, add 2s to
match. I hypothesize that this only happens with small numbers, where
the divide-to-odd + add 2s is less ops.

[14, 16, 8, 4, 6, 12, 24, 26, 13] -> [14, 7, 9, 11, 13]

(This is also weird in that Gregory's solver gives a one step shorter
solution: [14, 16, 8, 10, 12, 24, 26, 13])

Food for thought,

Ilmari```
on 2006-01-02 09:26
```Here's my (first) solution (ever) for quiz #60.

I also choose a breadth-first search algorithm because I'm probably
going to need a decent searching algorithm in the near future.  To
maximize reusability, I implemented 6 methods in the Integer class
that abstract the problem-specific logic out of the searching
algorithm.  When I use a different 'node' class, I will also need to
include the Comparable mix-in and define the <=> method for the
Array.max method on line #40.

The running time for the algorithm is O(N), where N is the number of
integers the algorithm 'visits'.  To limit the number of visited
mentioned: removing consecutive double/halves and removing adjacent
values greater than a maximum.

\$ time ./quiz.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    0m2.098s
user    0m1.868s
sys     0m0.091s

Not faster than Dominik's, but still pretty fast.  Perhaps my 1.33
Ghz G4 and 768 MB of RAM is holding my back?  :)

Although this is one of many BFS algorithms posted, I'd really
appreciate some feedback on my implementation.  Especially in regards
to potential speed ups, missed opportunities for ruby idioms, and

~ ryan ~

#!/usr/bin/env ruby

class Integer

def odd?
self % 2 != 0
end

# optimized to remove consecutive double/halves and remove
adjacent values greater than a maximum
list = []
list << self * 2 unless @parent == self * 2  or self * 2 > maximum
list << self / 2 unless self.odd? or @parent == self / 2
list << self + 2 unless self + 2 > maximum
list || []
end

def visit!(parent = nil)
@discovered = true
@parent = parent
@distance = parent ? parent.distance + 1 : 0
end

def path_from(start)
if self == start
[start]
else
if @parent == nil
raise "no path from #{start} to #{self} exists"
else
@parent.path_from(start) << self
end
end
end
end

def solve(start, target)
return [start] if start == target
roof = [start, target].max * 2 + 2
start.visit!
queue = [start]
queue.each do |vertex|
unless child.discovered
child.visit!(vertex)
return target.path_from(start) if target == child
queue.push(child)
end
end
end
end

# Run this code only when the file is the main program
if \$0 == __FILE__
# Parse arguments (authored by James Edward G. II)
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) }

p solve(start, finish)
end```
on 2006-01-02 18:25
```On Sun, 01 Jan 2006 19:27:56 +0100, <removed_email_address@domain.invalid>
wrote:

> For this quiz I took what I made for the word chain quiz and modified
> it a bit.

I did that, too ;-)

My solution uses unidirectional BFS (like many others). The NumericMaze
class is generic, meaning that it can also work with other ops, so
naturally it doesn't have any optimizations for this special problem. I
only limit the search space in the "if \$0 == __FILE__" part.

Dominik

class NumericMaze

OP_DOUBLE = lambda { |x| x * 2 }
OP_HALVE = lambda { |x| x % 2 == 0 ? x / 2 : nil }
OP_ADD_TWO = lambda { |x| x + 2 }

# ops is an array of lambdas, each lambda returns a next step for a
given
# number, or nil if no next step is possible for the given number
def initialize(ops = [OP_DOUBLE, OP_HALVE, OP_ADD_TWO])
@ops = ops
end

def solve(start, target, max_num = nil)
# build chain with simple breadth first search
current = [start]
return current if start == target
pre = { start => nil } # will contain the predecessors
catch(:done) do
until current.empty?
next_step = []
current.each do |num|
@ops.each do |op|
unless (step_num = op[num]).nil?
# have we seen this number before?
unless pre.has_key?(step_num) ||
(max_num && step_num > max_num)
pre[step_num] = num
throw(:done) if step_num == target
next_step << step_num
end
end
end
end
current = next_step
end
return nil # no chain found
end
# build the chain (in reverse order)
chain = [target]
chain << target while target = pre[target]
chain.reverse
end

end

if \$0 == __FILE__
a, b, = *ARGV.map { |str| Integer(str) }
p NumericMaze.new.solve(a, b, [a, b].max.abs * 3)
end```
on 2006-01-02 18:28
```On Mon, 02 Jan 2006 08:25:08 +0100, J. Ryan S.
wrote:

> G4 and 768 MB of RAM is holding my back?  :)
It actually is faster than my version:

\$ time ruby ryan_org.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.197s
user    0m1.138s
sys     0m0.026s

(Pentium M 1.5)

> Although this is one of many BFS algorithms posted, I'd really
> appreciate some feedback on my implementation.  Especially in regards to
> potential speed ups, missed opportunities for ruby idioms, and

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

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

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. But it has one big downside: solve only works once, because
Fixnums are immediate values:

\$ irb -r ryan
irb(main):001:0> solve 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]
irb(main):002:0> solve 22222, 99999
=> [22222]

Dominik```
on 2006-01-02 19:08
```On Jan 2, 2006, at 11:24 AM, Dominik B. wrote:

> On Mon, 02 Jan 2006 08:25:08 +0100, J. Ryan S.
>
> It actually is faster than my version:

Oh nice.  :)

>      self % 2 != 0
> @@ -40,7 +38,7 @@
> distance, which is unused.
>
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 ~```
on 2006-01-02 19:29
```I didn't like having the roof calculation done inside the solve
method.  So here is my revised algorithm, including Dominik's
suggestions and a new roof class method for Integer.

#!/usr/bin/env ruby

class Integer

@@roof = 1.0/0.0

def self.roof(*args)
@@roof = args.max * 2 + 2 || @@roof
end

def odd?
self % 2 != 0
end

# optimized to remove consecutive double/halves and remove
adjacent values greater than a maximum
list = []
list << self * 2 unless @parent == self * 2  or self * 2 > @@roof
list << self / 2 unless self.odd? or @parent == self / 2
list << self + 2 unless self + 2 > @@roof
list
end

def visit!(parent = nil)
@parent = parent
end

def path_from(start)
if self == start
[start]
else
if @parent == nil
raise "no path from #{start} to #{self} exists"
else
@parent.path_from(start) << self
end
end
end
end

def solve(start, target)
return [start] if start == target
Integer.roof(start, target)
start.visit!
queue = [start]
queue.each do |vertex|
unless child.parent
child.visit!(vertex)
return target.path_from(start) if target == child
queue.push(child)
end
end
end
end

# Run this code only when the file is the main program
if \$0 == __FILE__
# Parse arguments (authored by James Edward G. II)
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) }

p solve(start, finish)
end

~ ryan ~```
on 2006-01-02 21:54
```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

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```
on 2006-01-02 23:14
```Here it is, my solution. From mathematical and algorithmic point of
view,
you won't find anything new. However:

- One of the few times that class variables come in handy: I put the
halve/double operations into Integer and then decided to make the
do-all
method Integer.solve_num_maze but the steps are done in
Integer#handle_num_maze

- Both optimizations are done in the method #enqueue

(orig
from swaits.com, unaccessible; not updated) included:
http://members.chello.nl/k.vangelder/ruby/quiz/

The code itself:

class Integer
def even?
self[0] == 0
end

def odd?
self[0] == 1
end

def halve
self / 2  if self.even?
end

def double
self * 2
end

def sub2
self - 2
end

Step = Struct.new(:dist, :next)

def self.source; @@source; end
def self.route; @@route; end
def self.queue; @@queue; end

def source; @@source; end
def route; @@route; end
def queue; @@queue; end

def self.solve_num_maze(source, target)
raise ArgumentError.new("Can't solve from >=0 to <0")  if target < 0
and source >= 0
raise ArgumentError.new("Can't solve from >0 to 0")  if target <= 0
and source > 0
@@source = source
@@route = {}
@@queue = []
@@max = [(source + 2) * 2, target * 2].max
# @@max = [source, target].max << 2  # and other attempts
queue << target
route[target] = Step.new(0, nil)
while (job = queue.shift) != source
job.handle_num_maze
end

result = [source]
step = source
while step != target
step = route[step].next
result << step
end
result
end

def enqueue(job)
# optimization 1, do not go through pending searches when
effectively done
queue.clear  if job == source

# optimization 2, do not look for solutions where it is not
necessary
queue << job  if job <= @@max
end

def handle_num_maze
if route[double].nil? or route[self].dist + 1 < route[double].dist
route[double] = Step.new(route[self].dist+1, self)
enqueue double
end
# mind the extra check on existence of #halve
if halve and (route[halve].nil? or route[self].dist + 1 <
route[halve].dist)
route[halve] = Step.new(route[self].dist+1, self)
enqueue halve
end
if route[sub2].nil? or route[self].dist + 1 < route[sub2].dist
route[sub2] = Step.new(route[self].dist+1, self)
enqueue sub2
end
end
end

p Integer.solve_num_maze(ARGV[0].to_i, ARGV[1].to_i)```
on 2006-01-02 23:54
```Hello dear quizzers,

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

[222222222, 222222224, 111111112, 55555556, 27777778, 27777780,
13888890, 13888892, 6944446, 6944448, 3472224, 1736112, 868056, 434028,
217014, 217016, 108508, 54254, 54256, 27128, 13564, 6782, 6784, 3392,
1696, 848, 424, 212, 106, 108, 54, 27, 29, 31, 33, 35, 37, 39, 78, 156,
158, 316, 632, 634, 1268, 1270, 2540, 2542, 5084, 5086, 10172, 20344,
40688, 40690, 81380, 162760, 325520, 651040, 1302080, 1302082, 2604164,
2604166, 5208332, 10416664, 10416666, 20833332, 41666664, 41666666,
83333332, 166666664, 166666666, 333333332, 666666664, 666666666,
333333333]

75 items

Time: 62.015s

There seems to be more potential in the brute force attack than i
thought possible.

cheers

Simon```
on 2006-01-03 00:00
```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

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

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

~ (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```
on 2006-01-03 00:57
```Thanks for the testcases,

i just found a shorter one for (700, 1)

[700, 350, 352, 176, 88, 44, 22, 24, 12, 6, 8, 4, 2, 1]

and a different one for

test_minus_one_two_three_five_and_ten(TestNumericMaze) [quiz60.rb:448]:
<[159, 318, 320, 160, 80, 40, 20, 10, 5, 7, 9, 18, 36, 72, 74, 76, 78,
156, 158]> expected but was
<[159, 318, 320, 160, 80, 40, 20, 10, 12, 14, 16, 18, 36, 38, 76, 78,
156, 158]>.

cheers

Simon```
on 2006-01-03 01:13
```I always learn something from Ruby Q.! Use of a ceiling (as presented
by many quizzers) greatly speeds up my solution and makes its
performance competitive with the non-binary solutions. This change took
only two lines of code.

- Ken

#!/usr/bin/env ruby
#
# Ruby Q. #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 two optimizations
# suggested by Dominik B. and others: track what numbers
# have been visited and do not build subnodes for previously
# visited numbers; and use a ceiling to disregard numbers
# large enough that they will not be needed in the solution.
#

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

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

end

def NumericMaze.solve(start, target)
ceiling = [start, target].max*2+2
# 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 B.)
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 number exceeds ceiling
next if node.value > ceiling
# 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
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
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)```
on 2006-01-03 02:16
```On Jan 2, 2006, at 2:57 PM, Simon Kröger wrote:

> Thanks for the testcases,

You're welcome.  Thanks for trying them.

--Steve```
on 2006-01-03 02:20
```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```
on 2006-01-03 02:39
```removed_email_address@domain.invalid wrote:
> 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 ;-)

42,

you seem to produce a non optimal solution:

[222, 224, 112, 56, 58, 60, 62, 124, 248, 496, 498, 996, 998, 1996,
1998, 999]
expected but was
[222, 111, 113, 115, 117, 119, 121, 123, 246, 248, 496, 498, 996, 1992,
1994, 997, 999]

Christer```
on 2006-01-03 03:47
```On Monday 02 January 2006 15:57, Simon KrÃ¶ger wrote:
> and a different one for
> test_minus_one_two_three_five_and_ten(TestNumericMaze) [quiz60.rb:448]:
> <[159, 318, 320, 160, 80, 40, 20, 10, 5, 7, 9, 18, 36, 72, 74, 76, 78,
> 156, 158]> expected but was
> <[159, 318, 320, 160, 80, 40, 20, 10, 12, 14, 16, 18, 36, 38, 76, 78,
> 156, 158]>.

(BTW, the second on there *is* shorter. =)```
on 2006-01-03 07:15
```Ok, It's a day late, but I've got my solution.  I've also updated the
test suite I submitted earlier with some shorter solutions.  All it
assumes is that you have a method solve that takes two whole numbers
(some tests use 0 as a starting point) that returns a list of numbers
representing the path.  I found it useful for testing and
benchmarking.  http://rafb.net/paste/results/zoPwZL59.html

Initially I tried a blind breath first search, which worked pretty
well, but there were a lot of values in my test suite that took an
obscene amount of time to run.  Today I decided to switch over to an
A* search, which improved things a lot.  My heuristic
(abs(log_base(2,a) - log_base(2,b))) is based on the idea that (except
for 0 and 1) multiplying/dividing by two is the fastest way of moving
toward the goal number.  I apologize if that didn't make any sense.

Anyway, assuming I implimented it correctly, and my heuristic is
optimistic (the latter claim I'm moderately sure of) this should
return the shortest path.  http://rafb.net/paste/results/exPug998.html

I'd be interested in seeing other's benchmarks on this suite.

~/Documents/Projects/ruby_quiz peter\$ ruby 60.rb
Started
.....................................................................................................
.....................................................................................................
.....................................................................................................
.....................................................................................................
...............................................................................
Finished in 90.666885 seconds.

483 tests, 966 assertions, 0 failures, 0 errors

[On a iBook G4, 512 meg ram]```
on 2006-01-03 15:01
```Kero wrote:
> 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 S., 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!

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

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

This is my test suite:

solve(2,9), [2,4,8,16,18,9]
solve(22,99).size, 8
solve(222,999).size, 16
solve(2222,9999).size, 25
solve(22222,99999).size, 36

Christer N.```
on 2006-01-03 18:00
```On Jan 3, 2006, at 8:01 AM, Christer N. wrote:

> Before you, Ryan S., 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%.

Nuts.  :)

Kudos, Kero!

~ ryan ~```
on 2006-01-03 21:15
```removed_email_address@domain.invalid wrote:
> 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 ;-)

now without :* but much shorter..

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 = []
@ops << lambda {|x| x - 2 if x > 1 }
@ops << lambda {|x| x * 2 if x.odd? or @goal < @start }
@ops << lambda {|x| x / 2 if x.even? }
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
while current = @queue.shift
temp_goal, steps = *current

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

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

@ops.each do |op|
if (new_goal = op.call temp_goal)
@queue << [new_goal, new_steps]
end
end
end
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

# for the testcases
def solve(a, b)
Solver.solve(a,b)
end```
on 2006-01-03 22:20
```removed_email_address@domain.invalid wrote:
>
> now without :* but much shorter..
>

Still doesn't solve (222,999) correctly. One step too much.

222 224 112  56  58  60  62 124 248 496 498 996  998 1996 1998 999
expected but was
222 111 113 115 117 119 121 123 246 248 496 498 996 1992 1994  997 999

Christer```
on 2006-01-04 00:58
```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

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|
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)```
on 2006-01-04 01:45
```Here's my solution.
It's a bi-directional depth-first search. I'm not sure anyone else did
that.
It's reasonably fast for small numbers, but takes 25 secs to do
22222->99999

It also solves Quiz60B, if you adjust the costs. use 22->34 for an
example where the different costs affect the solution.

----
class NumericMazeSolver
#the allowable operations - changing the order changes the solution
#this order favors smaller numbers
#create a hash mapping operations to their inverse.
ANTIOP=OPS[:FWD].zip(OPS[:REV]).inject({}){|h,s|h[s[0]]=s[1];h[s[1]]=s[0];h}

#change this line to solve Quiz60B

def initialize(noisy=false)
@noisy = noisy
end

# a Trail holds a set of operations
class Trail
def initialize direction, value=nil, path=[], cost = nil
@dir =direction
@path = path
@path.push value if value
@cost = if cost && value
cost + calc_cost(value)
else
path.inject(0){|sum,op| c=calc_cost(op); sum+=c if c; sum}
end
end

def grow operation
return Trail.new(@dir,operation,@path.dup,@cost)
end
def inspect
s=@path.inject("\$#{@cost}:"){|s,v| s+"#{v}->"}
s[0..-3]
end
def invert
Trail.new(@dir, nil, @path.reverse.map{|v| ANTIOP[v] || v},@cost)
end
def calc_cost operation
@dir == :FWD ? COST[operation] : COST[ANTIOP[operation]]
end
end

#the operations
def double a
return a*2
end
def halve a
return a/2 if a%2==0
end
return a+2
end
def sub2 a
return a-2
end

#store the cheapest trail to each number in the solution hash
def expand(val)
trail = @sset[val]
OPS[trail.dir ].each do |op|
result= self.send(op,val)
if result
newpath = trail.grow(op)
if (foundpath = @sset[result] )
if foundpath.dir != newpath.dir
cost = foundpath.cost+newpath.cost
@match= [newpath,result, cost] if (!@match || (cost <
@match.last))
elsif foundpath.cost > newpath.cost
@sset[result] = newpath
end
else
@sset[result] = newpath
if (!@match || (newpath.cost+@depth) < @match.last)
@newvals.push(result)  #only check if total cost can be
less than match cost
end
end
end
end
end

def solve(start,target)
return nil if start<0 || target < 1
return [start] if start==target
@sset = {start=>Trail.new(:FWD,start) ,
target=>Trail.new(:REV,target) }
@newvals=[start,target]
solution = nil
@match=nil
@depth=0
while true do
val = @newvals.shift
break if !val
expand(val)
@depth+=1
end
trail, matchnum = solution
trail, matchnum = @match
if trail.dir == :FWD
first,last = trail,@sset[matchnum].invert
else
first,last = @sset[matchnum],trail.invert
end
#    p first,last
get_solution(first,last)
end

def get_solution(first,last)
puts "SOLUTION = " + first.inspect + "->" + last.inspect  if @noisy
p = first.path + last.path
s=[p.shift]
p.each{ |v| s << self.send(v,s[-1]) unless v.is_a? Integer}
s
end

end

if __FILE__ == \$0
start, goal, is_noisy = ARGV[0].to_i, ARGV[1].to_i, ARGV[2]!=nil
puts "usage: @\$0 start goal [noisy]" unless start && goal
p NumericMazeSolver.new(is_noisy).solve(start, goal)
end```
on 2006-01-04 07:13
```Here's my solution.  Short, sweet, and slow.  One benefit of this
method is that it's easily adaptable to new operations.

-Nathan

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

self + 2
end

def is_odd?
self % 2 != 0
end

end```
on 2006-01-04 14:30
```>> 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 S., 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
is mangled,

Thanks.```
on 2006-01-04 17:50
```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```
on 2006-01-04 19:12
```Thanks for your "general comments".

it
much faster.

Steven

class NumericMaze
def solve (from, to)
return [from] if from == to

@done = {from => :from, -to => :to}
@todo = [from, -to]
@max = [from*2+2, to*2].max

catch :found do
loop do
t = @todo.shift

add_edge(t+2, t) if (t <- 2) || (0 <= t)
end
end
return @result
end

return unless @done[new] == nil
return if new > @max

@done[new] = from

if @done[-new] then #path found
@result = calc_path(new.abs)
throw :found
end

@todo.push new
end

def calc_path(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```
on 2006-01-04 19:13
```On Jan 4, 2006, at 9:50 AM, Christer N. wrote:

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

It's no secret.  ;)  Here's the code:

On Jan 3, 2006, at 12:29 PM, NILSSON Christer wrote:
>
>
> def solve number,target
>   @@route[source] = nil
>   def even?
>
>
> target < 0 and source >= 0
>       job.handle_num_maze
>
>   def handle_num_maze
>     if route[sub2].nil? or route[self].dist + 1 < route[sub2].dist
>     t solve(   22,   99).size, 8
>     t solve(  222,  999).size, 16
>     t solve( 2222, 9999).size, 25
>     t solve(22222,99999).size, 36
>     t solve(99999,22222).size, 42
>     t solve( 9999, 2222).size, 33
>     t solve(  999,  222).size, 23
>     t solve(   99,   22).size, 13
>     t solve(    9,    2).size, 9
James Edward G. II```
on 2006-01-04 19:13
```Yup, my solution is really slow. I made a minor change which reduces
the search space a little (and avoids things such as double followed by
halve, and v-v).  Still rather slow, but I didn't expect it to be fast.

class Integer
def even?
self & 1 == 0
end

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

def solve(a, b)
known = []

i = 0
steps = [[a]]
known << a

until steps[i].include?(b)
i += 1
steps[i] = []
steps[i-1].each do |x|
x.maze_adj.each { |y| steps[i] << y unless known.include?(y) }
end
known.concat steps[i]
end

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

# Examples
p solve(9, 2)
p solve(2, 9)
p solve(22, 99)
p solve(222, 999)```
on 2006-01-04 19:14
```Christer N. wrote:
> 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```
on 2006-01-04 23:35
```I took a look into bi-directional search, and it's really a rewarding
technique. I predicted a 16-fold performance increase, but it was 12.
I'm storing the result of both searches in a common array. To keep the
two solutions separated I use the sign. When the other side, there is a
connection, between the two growing trees.

I really tried to find something more clever than Simon's solutions, but
had to give up. Kudos to Simon!

Thanks to everybody, it's been really nice to follow everybody's
efforts!

Christer

Timings:

t solve(      2,      9).size, 6    #1
t solve(     22,     99).size, 8    #2
t solve(    222,    999).size, 16   #3
t solve(   2222,   9999).size, 25   #4
t solve(  22222,  99999).size, 36   #5
t solve( 222222, 999999).size, 47   #6
t solve(2222222,9999999).size, 58   #7
t solve(9999999,2222222).size, 61   #7
t solve( 999999, 222222).size, 51   #6
t solve(  99999,  22222).size, 42   #5
t solve(   9999,   2222).size, 33   #4
t solve(    999,    222).size, 23   #3
t solve(     99,     22).size, 13   #2
t solve(      9,      2).size, 9    #1

Each test consists of two problems.

Test 7:
Simon     1.833 secs
Christer  3.425 secs

Test 6:
Simon     0.321 secs
Christer  0.551 secs
Ryan     37     secs

Test 5:
Simon     0.11  secs
Christer  0.15  secs
Ryan      4.597 secs
Tristan   7.18  secs
Kenneth  13.93  secs
Zed      14.241 secs
Kero     70.6   secs

Test 4:
Chris     2.614 secs

Test 2:
James     0.12  secs

def solve start, target
return [start] if start == target
@max = 2 + 2 * [start,target].max
@back = []
@back[start] = start
@back[target] = -target
q1 = [start]
q2 = [target]
loop do
q1 = solve_level(q1, 1)
q2 = solve_level(q2, -1)
end
end

def path(number)
nr = abs(@back[number])
[number] + (nr == number ? [] : path(nr))
end

def solve_level(queue, sign)
@queue = []
@sign = sign
queue.each do |number|
store number, number * 2
store number, number + 2 * sign
store number, number / 2 if number[0] == 0
end
@queue
end

def store number, result
return if result > @max
return if result <= 0
if @back[result].nil? then
@queue.unshift result
@back[result] = number * @sign
else
if sign(@back[result]) == -@sign then
end
end
end

def abs(x) x > 0 ? x : -x end
def sign(x) x > 0 ? 1 : -1 end```
on 2006-01-05 15:45
```There is a small time fraction possible to squeeze out from Simon's
solution.
These lines, by Simon, are trying to detect if contact has been made, in
the bi-directional search:

forward.each {|n|return pathf, pathb, n if pathb[n] != ?X}
backward.each {|n|return pathf, pathb, n if pathf[n] != ?X}

If pathf and pathb are merged into one string, this check be done
without iteration. To be able to do that we must distinguish between
numbers reached by going forward and numbers reached by going backwards.
This can be done by using lower and upper case letters:

Forward character set:
?f starting number
?d divide
?m multiply

Backward character set:
?F target number
?S subtract 2
?D divide
?M multiply

?X unreached number

Result:

t solve(22222222,99999999).size, 58   #8
t solve(99999999,22222222).size, 61   #8
Christer   5.108 secs
Simon      6.175 secs

The code is ugly, please turn down the light:

# one common string
# use letters for operations

def solve start, target
return [start] if start == target
@MAX = 1 + 2 + 2 * [start,target].max

op = ''.ljust(@MAX, 'X')
op[start] = ?f
op[target] = ?F

q1 = [start]
q2 = [target]
loop do
q1 = solve1(q1,op)
q2 = solve2(q2,op)
end
end

def path(n,op)
case op[n]
when ?A,?a: [n] + path(n-2,op)
when ?D,?d: [n] + path(n*2,op)
when ?S,?s: [n] + path(n+2,op)
when ?M,?m: [n] + path(n/2,op)
when ?F,?f: [n]
end
end

def solve1(queue,op)
q = []
queue.each do |n|

#   store1 ?m, n, n * 2 if n+n<=@MAX
result = n + n
if result <= @MAX then
if op[result]==?X then
q.push result
op[result] = ?m
else
@ready = n, result if op[result] < ?a
end
end

#   store1 ?a, n, n + 2 if n+2<=@MAX
result = n + 2
if result <= @MAX then
if op[result]==?X then
q.push result
op[result] = ?a
else
@ready = n, result if op[result] < ?a
end
end

#   store1 ?d, n, n / 2 if n.modulo(2) == 0
if n.modulo(2) == 0 then
result = n / 2
if op[result]==?X then
q.push result
op[result] = ?d
else
@ready = n, result if op[result] < ?a
end
end

end
q
end

def solve2(queue,op)
q = []
queue.each do |n|

#   store2 ?M, n, n * 2 if n+n<=@MAX
result = n + n
if result <= @MAX then
if op[result]==?X then
q.push result
op[result] = ?M
else
@ready = n, result if op[result] >= ?a
end
end

#   store2 ?S, n, n - 2 if n>2
result = n - 2
if result >= 1 then
if op[result]==?X then
q.push result
op[result] = ?S
else
@ready = n, result if op[result] >= ?a
end
end

#   store2 ?D, n, n / 2 if n.modulo(2) == 0
if n.modulo(2) == 0 then
result = n / 2
if op[result]==?X then
q.push result
op[result] = ?D
else
@ready = n, result if op[result] >= ?a
end
end

end
q
end

#def store1 op, number, result
#if result.op.nil? then
#@queue.push result
#result.op = op
#else
#@ready = number, result if result.op < ?a
#end
#end

#def store2 op, number, result
#if result.op.nil? then
#@queue.push result
#result.op = op
#else
#@ready = result, number if result.op >= ?a
#end
#end```
on 2006-01-06 20:51
```Ruby Q. schrieb:

>
>
>
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.
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
```On Jan 6, 2006, at 12:49 PM, Robert R. wrote: