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.
James G. (Guest)
on 2005-12-30 15:40
(Received via mailing list)
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.)
	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]
J. Ryan S. (Guest)
on 2005-12-30 22:21
(Received via mailing list)
Are negative numbers and zero allowed to be a starting point or
target?  I'm assuming no, but I'd like a confirmation.

~ ryan ~
James G. (Guest)
on 2005-12-30 22:39
(Received via mailing list)
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
Christer N. (Guest)
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 ~

I made a quick analysis:

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

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

Christer N.
Jeffrey D. (Guest)
on 2005-12-30 22:57
(Received via mailing list)
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
Christer N. (Guest)
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.
James G. (Guest)
on 2005-12-30 23:06
(Received via mailing list)
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
J. Ryan S. (Guest)
on 2005-12-31 00:19
(Received via mailing list)
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.
James G. (Guest)
on 2005-12-31 00:28
(Received via mailing list)
On Dec 30, 2005, at 4:17 PM, J. Ryan S. wrote:

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

Absolutely.  Please do.

Then people can counter post if they think they have a better
answer...  ;)

> 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
Christer N. (Guest)
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.
Jim F. (Guest)
on 2005-12-31 01:40
(Received via mailing list)
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]
Matthew S. (Guest)
on 2005-12-31 01:46
(Received via mailing list)
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.
Christer N. (Guest)
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.
Robert R. (Guest)
on 2005-12-31 01:52
(Received via mailing list)
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
2 - add_two

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.
Christer N. (Guest)
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
> 2 - add_two
>
> 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
Jim F. (Guest)
on 2005-12-31 02:28
(Received via mailing list)
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.
Jim F. (Guest)
on 2005-12-31 02:31
(Received via mailing list)
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]
James G. (Guest)
on 2005-12-31 02:59
(Received via mailing list)
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.)
> 	add_two
>
> 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
Jim F. (Guest)
on 2005-12-31 03:08
(Received via mailing list)
On 12/30/05, James Edward G. II

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


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

  double
  halve (evens only)
  add_two
  times_one

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

or, we use the original tranformations to get:

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

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

$0.02
Christer N. (Guest)
on 2005-12-31 03:36
Jim F. wrote:
> we either have:
>
>   double
>   halve (evens only)
>   add_two
>   times_one
>
> so we can get (1,1) #=> [1,1]
>
> or, we use the original tranformations to get:
>
>   (1,1) #=> [1,2,1]

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
Jim F. (Guest)
on 2005-12-31 03:56
(Received via mailing list)
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
1    add_two
2    times_two
4    times_one_half
Christer N. (Guest)
on 2005-12-31 04:06
Jim F. wrote:
> $    xform
> --   ---------
> 0    times_one
> 1    add_two
> 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    add_two
1    times_two
1    halve

Feel free to submit to none, one or both !

Christer
Kero (Guest)
on 2005-12-31 13:39
(Received via mailing list)
>> 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.
unknown (Guest)
on 2005-12-31 13:48
(Received via mailing list)
In article <removed_email_address@domain.invalid>,
Jim F.  <removed_email_address@domain.invalid> wrote:
>>
>> 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
Christer N. (Guest)
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.
Stephen W. (Guest)
on 2005-12-31 19:01
(Received via mailing list)
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,
>
> Absolutely.  Please do.

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
James G. (Guest)
on 2005-12-31 19:08
(Received via mailing list)
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
Christer N. (Guest)
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
Malte M. (Guest)
on 2005-12-31 19:50
(Received via mailing list)
James Edward G. II:
> You can't get a negative, unless you start with one.

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

Malte
James G. (Guest)
on 2005-12-31 19:53
(Received via mailing list)
On Dec 31, 2005, at 11:47 AM, Malte M. wrote:

> James Edward G. II:
>> You can't get a negative, unless you start with one.
>
> Doesn't 2 / 2 == 1 evaluate as true?

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

James Edward G. II
Gavin K. (Guest)
on 2005-12-31 20:11
(Received via mailing list)
On Dec 31, 2005, at 10:47 AM, Malte M. wrote:
> James Edward G. II:
>> You can't get a negative, unless you start with one.
>
> 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 :)
Stephen W. (Guest)
on 2005-12-31 20:20
(Received via mailing list)
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
Stephen W. (Guest)
on 2005-12-31 20:23
(Received via mailing list)
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
Jim M. (Guest)
on 2005-12-31 20:29
(Received via mailing list)
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
--
Jim M., removed_email_address@domain.invalid, 
removed_email_address@domain.invalid
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
James G. (Guest)
on 2005-12-31 21:20
(Received via mailing list)
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
Kenji S. (Guest)
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
Maurice Codik (Guest)
on 2006-01-01 00:09
(Received via mailing list)
>
> 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
Malte M. (Guest)
on 2006-01-01 00:24
(Received via mailing list)
Gavin K.:
>> James Edward G. II:
>>> You can't get a negative, unless you start with one.
> He meant "You can't get a negative, unless you start with a negative" and
> not "You can't get a negative, unless you start with 1".

Now I got it. Thank you!  :-)

Malte
Kenji S. (Guest)
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
Peter B. (Guest)
on 2006-01-01 02:24
(Received via mailing list)
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...
James G. (Guest)
on 2006-01-01 02:39
(Received via mailing list)
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
Stephen W. (Guest)
on 2006-01-01 03:09
(Received via mailing list)
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).

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

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

Exactly why I created my own test cases.  :)

--Steve

[1]: http://swaits.com/articles/2005/12/31/ruby-quiz-60...
Wilson B. (Guest)
on 2006-01-01 06:00
(Received via mailing list)
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.
J. Ryan S. (Guest)
on 2006-01-01 06:42
(Received via mailing list)
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 ~
Dominik B. (Guest)
on 2006-01-01 07:13
(Received via mailing list)
On Sun, 01 Jan 2006 04:59:32 +0100, Wilson B. 
<removed_email_address@domain.invalid>
wrote:

>> Looks great Peter.  I posted a note about and link to your improved
>>
>
> 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
completely on your own don't read it!

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.
Ilmari H. (Guest)
on 2006-01-01 11:25
(Received via mailing list)
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? ;-)
Christer N. (Guest)
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
Christer N. (Guest)
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
Christer N. (Guest)
on 2006-01-01 14:26
> Ilmari H. wrote:

The Five digit subproblem is solved optimally.

Christer
Peter B. (Guest)
on 2006-01-01 14:31
(Received via mailing list)
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
Loaded suite 60
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
Kenji S. (Guest)
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.
Gregory S. (Guest)
on 2006-01-01 17:14
(Received via mailing list)
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
James G. (Guest)
on 2006-01-01 17:48
(Received via mailing list)
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(", ")
Ilmari H. (Guest)
on 2006-01-01 18:03
(Received via mailing list)
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]
Matthew S. (Guest)
on 2006-01-01 18:06
(Received via mailing list)
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.
Stephen W. (Guest)
on 2006-01-01 18:10
(Received via mailing list)
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
ToRA (Guest)
on 2006-01-01 18:28
(Received via mailing list)
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
Simon S. (Guest)
on 2006-01-01 18:34
(Received via mailing list)
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
Ilmari H. (Guest)
on 2006-01-01 19:00
(Received via mailing list)
On 12/30/05, Ruby Q. <removed_email_address@domain.invalid> wrote:
>         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]
>
>

# 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
Maurice Codik (Guest)
on 2006-01-01 19:03
(Received via mailing list)
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
Kenneth C. (Guest)
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

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

  end

  def NumericMaze.solve(start, target)
    # Initialize node arrays with root node
    node_arrays = []
    node_arrays[0] = []
    node_arrays[0] << Node.new(:root, start)
    # Initialize hash of visited numbers; do not
    # visit a number twice (thanks to Dominik 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
          # Display answer and exit
          p [start] + value_array.reverse
          exit
        end
        # Collect new results at this level
        node_arrays[level+1] << node.double
        node_arrays[level+1] << node.halve
        node_arrays[level+1] << node.add_two
      end
      level += 1
    end
  end

end

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

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

NumericMaze.solve(ARGV[0].to_i, ARGV[1].to_i)
Ilmari H. (Guest)
on 2006-01-01 19:24
(Received via mailing list)
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.
James G. (Guest)
on 2006-01-01 19:42
(Received via mailing list)
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
Jay A. (Guest)
on 2006-01-01 20:30
(Received via mailing list)
For this quiz I took what I made for the word chain quiz and modified
it a bit. It uses a bi-directional breadth first search. I didn't allow
negative numbers at all just to make it simple for me.

-----Horndude77

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

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

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

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

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

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

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

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

from, to = ARGV[0].to_i, ARGV[1].to_i
if from < 1 || to < 1 then
    puts "inputs must be positive"
    exit
end
p solve(from, to)
Jim M. (Guest)
on 2006-01-01 20:39
(Received via mailing list)
I've posted my solution, along with a few words about my approach, at
<http://www.io.com/~jimm/rubyquiz/quiz60/>.

Jim
--
Jim M., removed_email_address@domain.invalid, 
removed_email_address@domain.invalid
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
Mark (Guest)
on 2006-01-01 21:12
(Received via mailing list)
Maurice,

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

- Mark
Maurice Codik (Guest)
on 2006-01-01 21:54
(Received via mailing list)
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
Mark (Guest)
on 2006-01-01 22:07
(Received via mailing list)
Nevermind, a copy and paste error on my part!
Kero (Guest)
on 2006-01-01 22:28
(Received via mailing list)
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
[snip answer]
real    0m0.772s
user    0m0.588s
sys     0m0.076s

But I'm not sure I want to run 8740 7630
let alone 150128850109293 8591982807778218492
Dave Lewis (Guest)
on 2006-01-01 22:43
(Received via mailing list)
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)
Matthew S. (Guest)
on 2006-01-01 23:19
(Received via mailing list)
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.
Justin B. (Guest)
on 2006-01-01 23:40
(Received via mailing list)
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
Pablo Hoch (Guest)
on 2006-01-02 00:14
(Received via mailing list)
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

      # Discard this path if we already have a better/equal one
      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
Kero (Guest)
on 2006-01-02 00:20
(Received via mailing list)
> 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).
Steven Aerts (Guest)
on 2006-01-02 00:20
(Received via mailing list)
Hi all,

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

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

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

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

	Steven  <removed_email_address@domain.invalid>

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

		@done = {from => :from, -to => :to}
		@todo = [from, -to]

		catch :found do
			while true
				t = @todo.shift

				addEdge(2*t, t)
				addEdge(t+2, t) if (t <- 2) || (0 <= t)
				addEdge(t/2,t) if t.modulo(2) == 0
			end
		end
		return @result
	end

	def addEdge(new, from)
		return if @done[new] != nil

		@done[new] = from

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

		@todo.push new
	end

	def calcPath(middle)
		pathway = [middle]

		t = middle
		pathway.unshift(t) until (t = @done[t]) == :from

		t = -middle
		pathway.push(-t) until (t = @done[t]) == :to

		return pathway
	end
end
unknown (Guest)
on 2006-01-02 00:38
(Received via mailing list)
In article <removed_email_address@domain.invalid>,
Matthew S.  <removed_email_address@domain.invalid> wrote:
>> 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
Christer N. (Guest)
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
Kero (Guest)
on 2006-01-02 01:05
(Received via mailing list)
> [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
=?ISO-8859-1?Q?Simon_Kr=F6ger?= (Guest)
on 2006-01-02 01:11
(Received via mailing list)
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"
James G. (Guest)
on 2006-01-02 01:26
(Received via mailing list)
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
James G. (Guest)
on 2006-01-02 01:35
(Received via mailing list)
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
James G. (Guest)
on 2006-01-02 01:39
(Received via mailing list)
On Jan 1, 2006, at 4:20 PM, Steven Aerts wrote:

> So all comments about my ruby-coding-style are very welcome
> (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
Reinder V. (Guest)
on 2006-01-02 01:45
(Received via mailing list)
In article
<removed_email_address@domain.invalid>,
 Justin B. <removed_email_address@domain.invalid> wrote:

> 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
Gregory S. (Guest)
on 2006-01-02 02:12
(Received via mailing list)
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-add-double, and four 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]

Ops = 27: dahhhahhaaaadahhahaaaaddada

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]

Ops = 16: ahaaaaaaddadadah

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

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

Ops = 6: haaaad

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

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

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
    attr_reader :result, :ops

    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

    def add_two
      @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

    def add_one
      double
      add_two
      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
            @result.add_two
          end
          @result.halve
        elsif dist_from_top == 4
          if shift > 0
            try_to_halve(@result.cur)
          else
            4.times { @result.add_two }
          end
        elsif dist_from_top == 3
          if shift > 0
            try_to_halve(@result.cur)
          else
            2.times { @result.add_two }
          end
        elsif dist_from_top == 2
          @result.add_two
        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
        @result.add_two
      elsif ((cur&2) != 0)
        # won't be able to halve again
        @result.add_two
      else
        @result.halve
      end
    end

  end

end

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

} Reinder
--Greg
Kenneth C. (Guest)
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
Kenneth C. (Guest)
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
Kero (Guest)
on 2006-01-02 04:04
(Received via mailing list)
> 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.
Chris Parker (Guest)
on 2006-01-02 04:25
(Received via mailing list)
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
instead.

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
  attr_reader :action, :children, :parent

  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
}
Gregory S. (Guest)
on 2006-01-02 04:52
(Received via mailing list)
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
Ilmari H. (Guest)
on 2006-01-02 07:37
(Received via mailing list)
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 :)
Ilmari H. (Guest)
on 2006-01-02 07:55
(Received via mailing list)
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
multiply, add, divide, etc starts being less ops than add 2.

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
J. Ryan S. (Guest)
on 2006-01-02 09:26
(Received via mailing list)
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
integers, I added a few of the clever optimizations already
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
additional optimizations to the adjacency_list method.

~ ryan ~

#!/usr/bin/env ruby

class Integer
   attr_reader :distance, :discovered

   def odd?
     self % 2 != 0
   end

   # optimized to remove consecutive double/halves and remove
adjacent values greater than a maximum
   def adjacency_list(maximum = Infinity)
     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|
     vertex.adjacency_list(roof).each do |child|
       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
Dominik B. (Guest)
on 2006-01-02 18:25
(Received via mailing list)
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
Dominik B. (Guest)
on 2006-01-02 18:28
(Received via mailing list)
On Mon, 02 Jan 2006 08:25:08 +0100, J. Ryan S. 
<removed_email_address@domain.invalid>
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
> additional optimizations to the adjacency_list method.

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
-  attr_reader :distance, :discovered
+  attr_reader :parent

    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|
      vertex.adjacency_list(roof).each do |child|
-      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
J. Ryan S. (Guest)
on 2006-01-02 19:08
(Received via mailing list)
On Jan 2, 2006, at 11:24 AM, Dominik B. wrote:

> On Mon, 02 Jan 2006 08:25:08 +0100, J. Ryan S.
> <removed_email_address@domain.invalid> wrote:
>
> 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 ~
J. Ryan S. (Guest)
on 2006-01-02 19:29
(Received via mailing list)
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
   attr_reader :parent

   @@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
   def adjacency_list
     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|
     vertex.adjacency_list.each do |child|
       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 ~
(Guest)
on 2006-01-02 21:54
(Received via mailing list)
okay here's my shot at the quiz, it's quite large for such a simple
problem, but i couldn't resist to use
:* in my code ;-)

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

        def odd?
                not even?
        end
end

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

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

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

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

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

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

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

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

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

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

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

        def makes_sense?
                false
        end
end

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

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

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

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

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

        def makes_sense?(temp_goal)
                temp_goal > 1
        end
end

# for the testcases
def solve(a, b)
        Solver.solve(a,b)
end
Kero (Guest)
on 2006-01-02 23:14
(Received via mailing list)
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

My permanent URL has header, license anouncement and large testsuite
(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

  # add inverse for add_two (we're doing DynProg)
  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)
=?ISO-8859-1?Q?Simon_Kr=F6ger?= (Guest)
on 2006-01-02 23:54
(Received via mailing list)
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
Zed L. (Guest)
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
Word Ladder:

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
for already existing values.

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

real    0m2.280s
user    0m2.105s
sys     0m0.017s
~ (301) time ./numeric_maze5.rb 22222 99999
[22222, 22224, 11112, 5556, 2778, 2780, 1390, 1392, 696, 348, 174, 87,
89, 91, 93, 95, 97, 194, 388, 390, 780, 1560, 1562, 3124, 6248, 12496,
12498, 24996, 24998, 49996, 49998, 99996, 99998, 199996, 199998, 99999]

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


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

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

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

x = 1
while x = 1 - x: # cycle between 0 and 1 in infinite loop
  next_nodes = []
  tree[x].each {|node| # for each node in current level
    [node[:num]*2,
     node[:num]%2 == 0 ? node[:num]/2 : 0,
     x.zero? ? node[:num] + 2 : node[:num] - 2].uniq.select {|n|
       n > 0 and !node_index[x].key?(n)}.each {|newnum|
       # if we have a path to this result in the other tree, we're done
       success(x, node, node_index[1-x][newnum]) if
node_index[1-x].key?(newnum) # only way out of the loop
       next_nodes << node_index[x][newnum] = { :num => newnum, :parent
=> node } # build the next level
    }
  }
  tree[x] = next_nodes
end
=?ISO-8859-1?Q?Simon_Kr=F6ger?= (Guest)
on 2006-01-03 00:57
(Received via mailing list)
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
Kenneth C. (Guest)
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

    def add_two
      @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
          # Display answer and exit
          p [start] + value_array.reverse
          exit
        end
        # Collect new results at this level
        node_arrays[level+1] << node.double
        node_arrays[level+1] << node.halve
        node_arrays[level+1] << node.add_two
      end
      level += 1
    end
  end

end

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

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

NumericMaze.solve(ARGV[0].to_i, ARGV[1].to_i)
Stephen W. (Guest)
on 2006-01-03 02:16
(Received via mailing list)
On Jan 2, 2006, at 2:57 PM, Simon Kröger wrote:

> Thanks for the testcases,

You're welcome.  Thanks for trying them.

--Steve
Christer N. (Guest)
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
Christer N. (Guest)
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]

(17 steps instead of 16)

Christer
Wesley J. Landaker (Guest)
on 2006-01-03 03:47
(Received via mailing list)
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. =)
Peter B. (Guest)
on 2006-01-03 07:15
(Received via mailing list)
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
Loaded suite 60
Started
.....................................................................................................
.....................................................................................................
.....................................................................................................
.....................................................................................................
...............................................................................
Finished in 90.666885 seconds.

483 tests, 966 assertions, 0 failures, 0 errors

[On a iBook G4, 512 meg ram]
Christer N. (Guest)
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.
J. Ryan S. (Guest)
on 2006-01-03 18:00
(Received via mailing list)
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 ~
(Guest)
on 2006-01-03 21:15
(Received via mailing list)
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
Christer N. (Guest)
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
Matthew D Moss (Guest)
on 2006-01-04 00:58
(Received via mailing list)
Here is my solution, very much a derivative of my solution to the
Knight's Travails quiz (#27). It will return a shortest solution
(chosen at random if there are more than one). It will always find a
shortest solution, though not necessarily fast. (I haven't tried timing
this.)



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

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


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

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

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

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


# Examples
p solve(2, 9)
p solve(9, 2)
Adam S. (Guest)
on 2006-01-04 01:45
(Received via mailing list)
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.

-Adam
----
class NumericMazeSolver
  #the allowable operations - changing the order changes the solution
  #this order favors smaller numbers
  OPS = {:FWD=>[:halve, :add2,:double],:REV=>[:double, :sub2,:halve]}
  #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
  #COST = {:halve=>1, :add2=>1, :double=>1,:sub2=>1}
  COST = {:halve=>4, :add2=>1, :double=>2,:sub2=>1}

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

  # a Trail holds a set of operations
  class Trail
    attr_reader :path,:dir,:cost
    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
  def add2 a
    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
Nathan (Guest)
on 2006-01-04 07:13
(Received via mailing list)
Here's my solution.  Short, sweet, and slow.  One benefit of this
method is that it's easily adaptable to new operations.

-Nathan


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

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

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

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

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

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

class Integer

  def double
    self * 2
  end

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

  def add_two
    self + 2
  end

  def is_odd?
    self % 2 != 0
  end

end
Kero (Guest)
on 2006-01-04 14:30
(Received via mailing list)
>> 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
address
is mangled,
  "removed_email_address@domain.invalid".split(/\./).values_at(0,2).join(".")

Thanks.
Christer N. (Guest)
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
Steven Aerts (Guest)
on 2006-01-04 19:12
(Received via mailing list)
Thanks for your "general comments".

I made a little adjustment to the algortihm (added  ceiling) which makes
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(2*t, t)
				add_edge(t+2, t) if (t <- 2) || (0 <= t)
				add_edge(t/2,t) if t.modulo(2) == 0
			end
		end
		return @result
	end

	def add_edge(new, from)
		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
James G. (Guest)
on 2006-01-04 19:13
(Received via mailing list)
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
unknown (Guest)
on 2006-01-04 19:13
(Received via mailing list)
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

   def maze_adj
      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)
=?UTF-8?B?U2ltb24gS3LDtmdlcg==?= (Guest)
on 2006-01-04 19:14
(Received via mailing list)
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
Christer N. (Guest)
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
  @ready = nil
  q1 = [start]
  q2 = [target]
  loop do
    q1 = solve_level(q1, 1)
    break if @ready
    q2 = solve_level(q2, -1)
    break if @ready
  end
  path(@ready[1]).reverse + path(@ready[0])
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
    break if @ready
  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
      @ready = number, result
    end
  end
end

def abs(x) x > 0 ? x : -x end
def sign(x) x > 0 ? 1 : -1 end
Christer N. (Guest)
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
 ?a add 2
 ?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:

# store operations instead.
# 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

  @ready = nil
  q1 = [start]
  q2 = [target]
  loop do
    q1 = solve1(q1,op)
    break if @ready
    q2 = solve2(q2,op)
    break if @ready
  end
  path(@ready[0],op).reverse + path(@ready[1],op)
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

    break if @ready
  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

    break if @ready
  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
Robert R. (Guest)
on 2006-01-06 20:51
(Received via mailing list)
Ruby Q. schrieb:

>
>	add_two
>
>
This was really a nice riddle.
I learned much about understanding and implementing a BFS algo.
Thank you for that.

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

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

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

-
With kind regards from Duesseldorf, Germany
Robert "Mr. Overheadman" Retzbach
James G. (Guest)
on 2006-01-06 21:00
(Received via mailing list)
On Jan 6, 2006, at 12:49 PM, Robert R. wrote:

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

Sorry, crazy day.  It's up now.

James Edward G. II
This topic is locked and can not be replied to.