[QUIZ] Numeric Maze (#60)

[Christer Nilsson]

$ 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

 

[Phil Tomson]

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

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

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

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

Kero,

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

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

Enjoy!

Christer Nilsson

 

[James Edward Gray II]

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

$ 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 Gray II

 

[Malte Milatz]

James Edward Gray II:

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

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

Malte

 

[Christer Nilsson]

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

 

[James Edward Gray II]

James Edward Gray II:

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

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

James Edward Gray II

 

[Gavin Kistner]

James Edward Gray II:

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

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

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

 

[Stephen Waits]

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

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

$ 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 Gray 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 Menard, (e-mail address removed), (e-mail address removed)
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 Edward Gray 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.

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

James Edward Gray II

 

[Kenji Sihan]

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

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

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

------=_Part_17758_20672011.1136066911459--

 

[Malte Milatz]

Gavin Kistner:

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

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

 

[James Edward Gray II]

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

 

[Stephen Waits]

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

 

[Wilson Bilkovich]

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

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

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

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 ~