The three rules of Ruby Quiz: 1. Please do not post any solutions or spoiler discussion for this quiz until 48 hours have passed from the time on this message. 2. Support Ruby Quiz by submitting ideas as often as you can: http://www.rubyquiz.com/ 3. Enjoy! -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= by Christer Nilsson You have a starting point and a target, say 2 and 9. You have a set of three operations: double halve (Odd numbers cannot be halved.) add_two Problem: Move from the starting point to the target, minimizing the number of operations. Examples: solve(2,9) # => [2,4,8,16,18,9] solve(9,2) # => [9,18,20,10,12,6,8,4,2]

on 2005-12-30 14:40

on 2005-12-30 21:21

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

on 2005-12-30 21:39

On Dec 30, 2005, at 2:18 PM, J. Ryan Sobol wrote: > Are negative numbers and zero allowed to be a starting point or > target? Zero seems fine as a starting number. You can always add_two. You can't get a negative, unless you start with one. If you do, other negative targets and even a target of 0, seem fine. Some numbers would be impossible to reach though. I think allowing them is fine. Let's just add that you're program won't be fed a start and end that have no solution (at least by me). Sound fair? James Edward Gray II

on 2005-12-30 21:57

J. Ryan Sobol wrote: > Are negative numbers and zero allowed to be a starting point or > target? I'm assuming no, but I'd like a confirmation. > > ~ ryan ~ I made a quick analysis: target - 0 + - ok ok ok 0 no ok ok + no no ok start but, to make it simpler: let the domain be positive integers. It all depends on the operators used. With the proposed operators, it is possible to go from any positive number to any positive number. Christer Nilsson

on 2005-12-30 21:57

On Sat, Dec 31, 2005 at 05:36:58AM +0900, James Edward Gray II wrote: > On Dec 30, 2005, at 2:18 PM, J. Ryan Sobol wrote: > > >Are negative numbers and zero allowed to be a starting point or target? > > Zero seems fine as a starting number. You can always add_two. > > You can't get a negative, unless you start with one. If you do, other > negative targets and even a target of 0, seem fine. Some numbers would be > impossible to reach though. Heh, I couldn't figure out how to get a negative number using double, halve, and add_two from the number 1. Then I realized the problem wasn't with my math, but with my English :-) That, or I'm really confused. Jeff

on 2005-12-30 22:06

Jeffrey Dik 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 Nilsson

on 2005-12-30 22:06

On Dec 30, 2005, at 2:57 PM, Christer Nilsson 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 Gray II

on 2005-12-30 23:19

On Dec 30, 2005, at 8:37 AM, Ruby Quiz wrote: > The three rules of Ruby Quiz: > > 1. Please do not post any solutions or spoiler discussion for this > quiz until > 48 hours have passed from the time on this message. Would it be appropriate to post my potential answers (not code) to this question? For example, solve(1,1) # => ??? solve(1,2) # => ??? ... solve(1,25) # => ??? This is the first Number Theory exercise I've done in a while and I'm not 100% confident I can test my algorithm against my the solutions I come up with by hand. :) It would be nice to have a small subset of publicly agreed test cases. ~ ryan ~ PS- I'm new here and I hope I'm not over overstepping the rules.

on 2005-12-30 23:28

On Dec 30, 2005, at 4:17 PM, J. Ryan Sobol 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 Quiz, Ryan. And no worries, you are doing just fine. James Edward Gray II

on 2005-12-31 00:06

J. Ryan Sobol wrote: > Would it be appropriate to post my potential answers (not code) to > this question? Some examples: solve(1, 1) # => [1] solve(1, 2) # => [1, 2] solve(1, 25) # => [1, 3, 6, 12, 24, 48, 50, 25] solve(12, 11)# => [12, 14, 7, 9, 11] solve(2, 9) # => [2, 4, 8, 16, 18, 9] solve(9, 2) # => [9, 18, 20, 10, 12, 6, 8, 4, 2] solve(17, 1) # => [17, 34, 36, 18, 20, 10, 12, 6, 8, 4, 2, 1] There may exist equivalent paths, of the same length. Christer Nilsson

on 2005-12-31 00:40

On 12/30/05, Christer Nilsson <janchrister.nilsson@gmail.com> wrote: > > J. Ryan Sobol wrote: > > Would it be appropriate to post my potential answers (not code) to > > this question? > > Some examples: > > solve(1, 1) # => [1] Is this a degenerate case? If to go from a to b in (a,b) through transformation x,y or z, wouldn't there be two possible shortest solutions: [1,2,1] [1,0.5,1]

on 2005-12-31 00:46

On Dec 30, 2005, at 23:37, Jim Freeze wrote: > > Is this a degenerate case? If to go from a to b in (a,b) through > transformation x,y or z, wouldn't there be two possible shortest > solutions: > > [1,2,1] > [1,0.5,1] (It's specified that you can't halve odd numbers) m.s.

on 2005-12-31 00:48

Jim Freeze 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 Nilsson

on 2005-12-31 00:52

J. Ryan Sobol 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.

on 2005-12-31 01:07

Robert Retzbach wrote: > J. Ryan Sobol 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

on 2005-12-31 01:28

```
On 12/30/05, Christer Nilsson
> If start equals target, zero steps are needed.
Wouldn't that be a 'times 1' transformation? I don't see that in the
list.
```

on 2005-12-31 01:31

On 12/30/05, Christer Nilsson <janchrister.nilsson@gmail.com> wrote: > > Jim Freeze wrote: > >> solve(1, 1) # => [1] > > > Only positive integers are allowed. > That means you can't divide odd numbers with two (operation halve) Ok, I'll change the example (2,2) #=> [2,4,2] or [2,1,2]

on 2005-12-31 01:59

On Dec 30, 2005, at 5:37 PM, Jim Freeze 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 Quiz 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 Gray II

on 2005-12-31 02:08

On 12/30/05, James Edward Gray II > > You have a set of three operations: > > > > double > > halve (Odd numbers cannot be halved.) > > add_two I think it makes it interesting if the ending point is derived from a transformation on the previous integer. More math like. So, I would suggest we either have: double halve (evens only) add_two times_one so we can get (1,1) #=> [1,1] or, we use the original tranformations to get: (1,1) #=> [1,2,1] Seems less hand wavy than having the final value magically appear without being tranformed from a previous step. $0.02

on 2005-12-31 02:36

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

on 2005-12-31 02:56

On 12/30/05, Christer Nilsson <janchrister.nilsson@gmail.com> 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

on 2005-12-31 03:06

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

on 2005-12-31 12:39

>> start >> >> but, to make it simpler: let the domain be positive integers. >> It all depends on the operators used. >> With the proposed operators, it is possible to go from any positive >> number to any positive number. > > Works for me. Let's do that. Bah! I have a generic solution which is perfectly happy with negative numbers (and Bignums) which is unlikely to be the fastest solution at all. Now you allow others to use even more optimizations! But given the table, I suppose I should add some code to prevent infinite loops from the "no" entries of the table above. ah, well. Bye, Kero.

on 2005-12-31 12:48

In article <5cd596d60512301537ydd6f53anf9cf2c9129fb5367@mail.gmail.com>, Jim Freeze <jim@freeze.org> 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

on 2005-12-31 13: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 Nilsson

on 2005-12-31 18:01

On Dec 30, 2005, at 2:27 PM, James Edward Gray II wrote: > On Dec 30, 2005, at 4:17 PM, J. Ryan Sobol 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

on 2005-12-31 18:08

On Dec 30, 2005, at 5:51 PM, Robert Retzbach 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 Gray II

on 2005-12-31 18:46

Stephen Waits wrote: > > Since that's about all I'm going to be able to do on this quiz, here > are some of my test cases. I'm pretty confident in the shorter > solutions, but have less confidence in the longer ones. These were > all discovered via stochastic search. > > I hope this won't qualify as "code", as mentioned above - since the > idea is that everyone may test their solutions against this, the fact > that it's already coded as test cases seems naturally acceptable to me. > > I'm very much looking forward to the solutions on this one! > > For now, I've posted them on http://swaits.com/ > > --Steve Steve, there seem to be at least one difference: <[300, 302, 304, 152, ... , 2, 1]> expected but was <[300, 150, 152, ... , 2, 1]>. Christer

on 2005-12-31 18:50

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

on 2005-12-31 18:53

On Dec 31, 2005, at 11:47 AM, Malte Milatz wrote: > James Edward Gray 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 Gray II

on 2005-12-31 19:11

On Dec 31, 2005, at 10:47 AM, Malte Milatz wrote: > James Edward Gray 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 :)

on 2005-12-31 19:20

```
On Dec 31, 2005, at 10:10 AM, Gavin Kistner wrote:
> I know, I read "one" as "1" the first time also :)
It happened to me too. Took me at least a minute to figure out _my_
problem. :)
--Steve
```

on 2005-12-31 19:23

On Dec 31, 2005, at 9:47 AM, Christer Nilsson wrote: > Steve, there seem to be at least one difference: > > <[300, 302, 304, 152, ... , 2, 1]> expected but was > <[300, 150, 152, ... , 2, 1]>. Thanks Christer... I'll fix that one. My search was far from exhaustive. :) --Steve

on 2005-12-31 19:29

On 12/31/05, James Edward Gray II <james@grayproductions.net> wrote: > > 1 - halve > 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, jim.menard@gmail.com, jimm@io.com http://www.io.com/~jimm "Generics in Java are an apology for having collections of Objects, and are somewhat like the puritan's suspicion that someone, somewhere, might be enjoying themselves." -- Steven T Abell in comp.lang.smalltalk

on 2005-12-31 20:20

On Dec 31, 2005, at 12:26 PM, Jim Menard wrote: > Damn. I got it down from 7 minutes to 18 seconds on a 667 MHz PPC, but > it looks like I have a bit more work to do. I'm using a Dual 2 Ghz G5, so the hardware is at least *some* of the difference. James Edward Gray II

on 2005-12-31 21:23

James Gray wrote: > On Dec 30, 2005, at 5:51 PM, Robert Retzbach 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 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

on 2005-12-31 23:09

> > solve(222, 9999) > result: > Total time taken in seconds: 56.0 > [222, 224, 226, 228, 230, 232, 234, 236, 238, 240, 242, 244, 246, 248, > 250, 252, 254, 256, 258, 260, 262, 264, 266, 268, 270, 272, 274, 276, > 278, 280, 282, 284, 286, 288, 290, 292, 294, 296, 298, 300, 302, 304, > 306, 308, 310, 312, 624, 1248, 2496, 2498, 4996, 4998, 9996, 9998, > 19996, 19998, 9999] Is this last one correct? I get for this for (222, 9999) -- [222, 224, 112, 56, 28, 14, 16, 18, 36, 38, 76, 78, 156, 312, 624, 1248, 2496, 2498, 4996, 4998, 9996, 19992, 19994, 9997, 9999] Maurice

on 2005-12-31 23:24

Gavin Kistner: >> James Edward Gray II: >>> You can't get a negative, unless you start with one. > He meant "You can't get a negative, unless you start with a negative" and > not "You can't get a negative, unless you start with 1". Now I got it. Thank you! :-) Malte

on 2006-01-01 00:14

Maurice Codik wrote: >> >> solve(222, 9999) >> result: >> Total time taken in seconds: 56.0 >> [222, 224, 226, 228, 230, 232, 234, 236, 238, 240, 242, 244, 246, 248, >> 250, 252, 254, 256, 258, 260, 262, 264, 266, 268, 270, 272, 274, 276, >> 278, 280, 282, 284, 286, 288, 290, 292, 294, 296, 298, 300, 302, 304, >> 306, 308, 310, 312, 624, 1248, 2496, 2498, 4996, 4998, 9996, 9998, >> 19996, 19998, 9999] > > > Is this last one correct? I get for this for (222, 9999) -- > [222, 224, 112, 56, 28, 14, 16, 18, 36, 38, 76, 78, 156, 312, 624, 1248, > 2496, 2498, 4996, 4998, 9996, 19992, 19994, 9997, 9999] > > Maurice Yea I think it is correct. I thought I had a shortcut in my algorithm, which excluded solutions like that one. My solution for (222, 9999) is slightly different though: [222, 224, 112, 56, 28, 14, 16, 18, 36, 38, 76, 78, 156, 312, 624, 1248, 496, 2498, 4996, 4998, 9996, 9998, 19996, 19998, 9999] in +- 38 seconds

on 2006-01-01 01:24

On 12/31/05, Stephen Waits <steve@waits.net> wrote: > > For now, I've posted them on http://swaits.com/ > > --Steve I think I've improved upon this test code a bit. I found this one to be a bit brittle, as it will fail solutions with unanticipated paths of the same or smaller length. I lost some of the metadata in the switch, as Steve has the different solutions ordered by type (i.e. primes, powers of two, etc). http://rafb.net/paste/results/qwhnUg32.nln.html Any feedback is, of course, appreciated. I'm just pounding away at this test case code because my mathematician buddy is busy at the moment. This is quite the nontrivial problem...

on 2006-01-01 01:39

On Dec 31, 2005, at 4:08 PM, Maurice Codik wrote: > I get for this for (222, 9999) -- > [222, 224, 112, 56, 28, 14, 16, 18, 36, 38, 76, 78, 156, 312, 624, > 1248, > 2496, 2498, 4996, 4998, 9996, 19992, 19994, 9997, 9999] My code dies a horrible death on this one. <laughs> I think I get a right answer, but the wait was embarrassing: $ time ruby numeric_maze.rb 222 9999 222, 224, 112, 56, 58, 29, 31, 33, 35, 37, 39, 78, 156, 312, 624, 1248, 2496, 2498, 4996, 4998, 9996, 19992, 19994, 9997, 9999 real 96m13.978s user 49m27.502s sys 46m22.817s Guess I need more than my one optimization now. <laughs> James Edward Gray II

on 2006-01-01 02:09

On Dec 31, 2005, at 4:24 PM, Peter Burns 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...

on 2006-01-01 05:00

On 12/31/05, Stephen Waits <steve@waits.net> wrote: > version on my [original post][1]. > > > I'm just pounding away at this test case code because my mathematician > > buddy is busy at the moment. This is quite the nontrivial problem... > > Exactly why I created my own test cases. :) > > --Steve > > [1]: http://swaits.com/articles/2005/12/31/ruby-quiz-60... > I'd just like to chime in to say that this quiz is killing me. The difference between 'code to solve the problem' and 'code that finishes running, you know, sometime today' is big.

on 2006-01-01 05:42

On Dec 31, 2005, at 10:59 PM, Wilson Bilkovich wrote: >> >> --Steve >> >> [1]: http://swaits.com/articles/2005/12/31/ruby-quiz-60... >> > > I'd just like to chime in to say that this quiz is killing me. The > difference between 'code to solve the problem' and 'code that finishes > running, you know, sometime today' is big. Don't worry, you're not alone. :) I'm very anxious to see the code that the rest of you have come up with. It's been a long time since my brain worked over a problem like this. :) ~ ryan ~

on 2006-01-01 06:13

On Sun, 01 Jan 2006 04:59:32 +0100, Wilson Bilkovich <wilsonb@gmail.com> 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.

on 2006-01-01 10:25

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

on 2006-01-01 12:34

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

on 2006-01-01 13:19

Christer Nilsson wrote: Ilmari Heikkinen wrote: >> ..., 8740, 4370, 4372, 2186, >> 2188, 1094, 1096, 548, 274, 276, 138, 140, 70, 72, 36, 18, 20, 10, 12, >> 14, 28, 56, 58, 116, 118, 236, 238, 476, 952, 1904, 1906, 3812, 3814, >> 7628, 7630, ... I can confirm that the four digit subproblem 8740 -> 7630 is solved optimally. Is it possible that the complete problem is solved optimally? Christer

on 2006-01-01 13:26

```
> Ilmari Heikkinen wrote:
The Five digit subproblem is solved optimally.
Christer
```

on 2006-01-01 13:31

I'm still doing this in far too much of a brute force sort of method. I think tomorrow I'll work more towards optimizing with some sneaky math. One advantage of brute force is that, if you do it right, you can be sure that you're getting a shortest path. I've found a couple of shorter paths from Steve's, but I can't deal at all with his bigger test cases. Current progress: ~/Documents/Projects/ruby_quiz peter$ ruby 60.rb 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

on 2006-01-01 13:44

Christer Nilsson wrote: > Christer Nilsson wrote: > > Ilmari Heikkinen wrote: >>> ..., 8740, 4370, 4372, 2186, >>> 2188, 1094, 1096, 548, 274, 276, 138, 140, 70, 72, 36, 18, 20, 10, 12, >>> 14, 28, 56, 58, 116, 118, 236, 238, 476, 952, 1904, 1906, 3812, 3814, >>> 7628, 7630, ... > > I can confirm that the four digit subproblem 8740 -> 7630 is solved > optimally. > > Is it possible that the complete problem is solved optimally? > > Christer 17478, 17480, 8740, 4370, 4372, 2186, > 2188, 1094, 1096, 548, 274, 276, 138, 140, 70, 72, 36, 18, 20, 10, 12, > 14, 28, 56, 58, 116, 118, 236, 238, 476, 952, 1904, 1906, 3812, 3814, > 7628, 7630, 15260, 15262, 30524, 61048 I think this is optimal as well.

on 2006-01-01 16:14

On Sun, Jan 01, 2006 at 06:23:08PM +0900, Ilmari Heikkinen wrote: } On 1/1/06, Dominik Bathon <dbatml@gmx.de> wrote: } > } > $ time ruby num_maze.rb 22222 99999 } > [22222, 22224, 11112, 5556, 2778, 2780, 1390, 1392, 696, 348, 174, 87, 89, } > 91, 93, 95, 97, 194, 388, 390, 780, 1560, 1562, 3124, 6248, 12496, 12498, } > 24996, 24998, 49996, 49998, 99996, 199992, 199994, 99997, 99999] } > } > real 0m1.768s } > user 0m1.725s } > sys 0m0.022s } > } > ;-) } } I wrote a heuristic solver by abusing the properties of the } mathematical problem. It doesn't find the shortest transformation } sequence but runs pretty fast. } } $ time ruby numpuz.rb 150128850109293 8591982807778218492 [...] } real 0m0.037s } user 0m0.029s } sys 0m0.008s } } Anyone want to provide the shortest solution to that? ;-) Whatever you're doing, I'm doing much the same thing. I get the identical solution in almost identically the same time (note: Dual G4 800): real 0m0.037s user 0m0.028s sys 0m0.009s I wouldn't call my solver heuristic, though. There is exactly one heuristic optimization. Other than that it is pretty much a straight analysis of the problem, with a nasty cleanup at the end to remove path loops. By the way, I can't get to http://swaits.com/articles/2005/12/31/ruby-quiz-60... at the moment. It seems to be down. Would anyone like to post some canonical test cases to the list? --Greg

on 2006-01-01 16:48

On Dec 30, 2005, at 7:37 AM, Ruby Quiz wrote: > Problem: Move from the starting point to the target, minimizing the > number of > operations. Here's my simple breadth-first search with a single optimization (described in comments). It's not at all fast enough for the big examples people have been throwing around, but it's pretty simple. James Edward Gray II #!/usr/local/bin/ruby -w # Parse arguments. unless ARGV.size == 2 and ARGV.all? { |n| n =~ /\A[1-9]\d*\Z/ } puts "Usage: #{File.basename($0)} START_NUMBER FINISH_NUMBER" puts " Both number arguments must be positive integers." exit end start, finish = ARGV.map { |n| Integer(n) } # Simple helper methods for determining if divide-by-two operation is allowed. class Integer def even? self % 2 == 0 end end # # A breadth-first search with a single optimization: All numbers are marked as # "seen" when they are calculated, then all future calculations resulting in an # already seen number cause the entire path to be abandoned. (We've seen it # before in equal or less steps, so there's no need to use the alternate/longer # path). # def solve( start, finish ) return [start] if start == finish seen = {start => true} paths = [[start]] until paths.first.last == finish path = paths.shift new_paths = [path.dup << path.last * 2, path.dup << path.last + 2] new_paths << (path.dup << path.last / 2) if path.last.even? new_paths.each do |new_path| unless seen[new_path.last] paths << new_path seen[new_path.last] = true end end end paths.shift end # Run program. puts solve(start, finish).join(", ")

on 2006-01-01 17:03

On 1/1/06, Christer Nilsson <janchrister.nilsson@gmail.com> wrote: > Would be interesting to see your heuristic solution applied to something > human, like 222->999. Ok, here's a couple. They tend to be a step or two worse than optimal, the worst case performance I've run into yet is 4x longer path (with 255 -> 257.) ruby numpuz.rb 22 999 [22, 24, 12, 14, 28, 30, 60, 62, 124, 248, 496, 498, 996, 998, 1996, 1998, 999] ruby numpuz.rb 222 999 [222, 224, 112, 56, 28, 30, 60, 62, 124, 248, 496, 498, 996, 998, 1996, 1998, 999] ruby numpuz.rb 222 9999 [222, 224, 112, 56, 28, 14, 16, 18, 36, 38, 76, 78, 156, 312, 624, 1248, 2496, 2498, 4996, 4998, 9996, 9998, 19996, 19998, 9999] ruby numpuz.rb 22222 99999 [22222, 22224, 11112, 5556, 2778, 2780, 1390, 1392, 696, 348, 174, 176, 88, 44, 22, 24, 48, 96, 192, 194, 388, 390, 780, 1560, 1562, 3124, 6248, 12496, 12498, 24996, 24998, 49996, 49998, 99996, 99998, 199996, 199998, 99999]

on 2006-01-01 17:06

On Jan 1, 2006, at 15:47, James Edward Gray II wrote: > On Dec 30, 2005, at 7:37 AM, Ruby Quiz wrote: > >> Problem: Move from the starting point to the target, minimizing >> the number of >> operations. > > Here's my simple breadth-first search with a single optimization > (described in comments). It's not at all fast enough for the big > examples people have been throwing around, but it's pretty simple. OK, so I didn't have time to code it up and see for sure, what with some transatlantic travel and New Year's and all that stuff, but the first thing that struck me when reading the problem was "dynamic programming" - did anyone take this route and hence give me a bit of satisfaction that my instincts were right? m.s.

on 2006-01-01 17:10

On Jan 1, 2006, at 8:04 AM, Matthew Smillie wrote: > but the first thing that struck me when reading the problem was > "dynamic programming" - did anyone take this route and hence give > me a bit of satisfaction that my instincts were right? I had the same thought, then decided it doesn't fit. But too, I'm interested in watching these solutions. I have a feeling they'll be based on exhaustive searches with a pinch of pruning and a dash of optimization. --Steve

on 2006-01-01 17:28

Hey, My solution's similar in style [breadth first, don't duplicate search], though I've also roof-limited it so it can't explore the search space above 2*[max(target,start)] + 4 which provides a fair speed up for e.g. 222, 9999. I'm not sure if that loses the optimality property though. I can't get to the swaits.com test suite, but the other one my solver finds smaller solutions for. Regards, Tris ---- require 'set' class MazeSolver def solve start, finish visited = Set.new tul, tll = if start > finish [(start << 1) + 4, nil] else [(finish << 1) + 4, nil] end solve_it [[start]], finish, visited, tul, tll end def solve_it lpos, target, visited, tul, tll n = [] lpos.each do |vs| v = vs.last next if tul and v > tul next if tll and v < tll return vs if v == target d = v << 1 # double h = v >> 1 unless (v & 1) == 1 # half p2 = v + 2 # plus 2 n << (vs.clone << d) if visited.add? d n << (vs.clone << h) if h and visited.add? h n << (vs.clone << p2) if visited.add? p2 end return solve_it(n, target, visited,tul, tll) end end if __FILE__ == $0 puts MazeSolver.new.solve(ARGV[0].to_i, ARGV[1].to_i).join(" ") end

on 2006-01-01 17:34

My solution is not optimal nor fast.. but different than the other solutions so far. -- Simon Strandgaard def solve(a, b) t = "h#{b}" t = "h#{b*=2}" + t while b < a s = "#{a}d#{a*2}" a *= 2;b *= 2 s += "a#{a+=2}" while a < b s += t loop do l = s.length s.gsub!(/(\d+)d\d+a\d+a/) { "#{$1}a#{$1.to_i + 2}d" } s.gsub!(/4a6a8/, '4d8') s.gsub!(/(\D|^)(\d+)(?:\D\d+)+\D\2(\D|$)/) {$1 + $2 + $3} break if s.length == l end s.scan(/\d+/).map{|i|i.to_i} end

on 2006-01-01 18:00

On 12/30/05, Ruby Quiz <james@grayproductions.net> 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

on 2006-01-01 18:03

I guess we're allowed to submit solutions now... here's my first ever ruby quiz solution (these quizzes are a great idea, btw): It's is an iterated-depth DFS w/ memoization written in a functional style for fun. It exploits the fact that the optimal path through the maze will never have consecutive double/halves, which reduces the avg branching factor of the search tree to ~2. Keeping track of this state makes the code a little uglier, but faster on the longer searches. Maurice #! /usr/bin/ruby # These return the next number & state ARROWS = [lambda { |x,state| (state != :halve) ? [x*2, :double] : nil }, # double lambda { |x,state| (x.modulo(2).zero? and state != :double) ? [x/2, :halve] : nil }, #halve lambda { |x,state| [x+2, :initial]}] # add_two def solver(from, to) # constraining depth on a DFS retval = nil depth = 1 @memo = nil # special case return [from] if from == to while (retval.nil?) retval = memo_solver(from, to, depth) depth += 1 end retval end # cant use hash default proc memoization since i dont want to memoize on the # state parameter, only on the first 3 def memo_solver(from, to, maxdepth, state=:initial) @memo ||= Hash.new key = [from, to, maxdepth] if not @memo.has_key? key @memo[key] = iter_solver(from, to, maxdepth, state) @memo[key] else @memo[key] end end def iter_solver(from, to, maxdepth, state) return nil if maxdepth.zero? # generate next numbers in our graph next_steps = ARROWS.map { |f| f.call(from, state) }.compact if next_steps.assoc(to) [from, to] else # havent found it yet, recur kids = next_steps.map { |x,s| memo_solver(x, to, maxdepth-1, s) }.compact if kids.length.zero? nil else # found something further down the tree.. return the shortest list up best = kids.sort_by { |x| x.length }.first [from, *best] end end end list = [ [1,1], [1,2], [2,9], [9,2], [2, 1234], [1,25], [12,11], [17,1], [22, 999], [2, 9999], [222, 9999] ] require 'benchmark' list.each do |i| puts Benchmark.measure { p solver(*i) } end

on 2006-01-01 18:21

#!/usr/bin/env ruby # # Ruby Quiz #60, Numeric Maze # http://www.rubyquiz.com/quiz60.html # # You have a starting point and a target, say 2 and 9. # You have a set of three operations: # double, halve (odd numbers cannot be halved), add_two. # # Problem: Move from the starting point to the target, # minimizing the number of operations. # Examples: # solve(2,9) # => [2,4,8,16,18,9] # solve(9,2) # => [9,18,20,10,12,6,8,4,2] # # # This solution builds a tree with each node having up to # three subnodes, one for each operation. It builds the # tree one level at a time and checks for a solution before # proceeding down to the next level. This brute force # approach performs much better after adding an optimization # suggested by Dominik Bathon: track what numbers have been # visited and do not build subnodes for previously visited # numbers. # module NumericMaze class Node attr_accessor :parent, :value, :children def initialize(parent, value) @parent = parent @value = value @children = {} end def double @children[:double] = Node.new(self, @value * 2) end def halve return :halve_failed if @value % 2 != 0 @children[:halve] = Node.new(self, @value / 2) end def add_two @children[:add_two] = Node.new(self, @value + 2) end end def NumericMaze.solve(start, target) # Initialize node arrays with root node node_arrays = [] node_arrays[0] = [] node_arrays[0] << Node.new(:root, start) # Initialize hash of visited numbers; do not # visit a number twice (thanks to Dominik Bathon) visited_numbers = {} # Check for a solution at each level level = 0 while true # Examine nodes at this level and # build subnodes when appropriate node_arrays[level+1] = [] node_arrays[level].each do |node| # Skip if method "halve" failed next if node == :halve_failed # Skip if this number has been tried already next if visited_numbers[node.value] visited_numbers[node.value] = true # Has a solution been found? If yes, # print it and exit if node.value == target # Build array of values used # (from bottom up) value_array = [] node_ptr = node while true break if node_ptr.parent == :root value_array << node_ptr.value node_ptr = node_ptr.parent end # Display answer and exit p [start] + value_array.reverse exit end # Collect new results at this level node_arrays[level+1] << node.double node_arrays[level+1] << node.halve node_arrays[level+1] << node.add_two end level += 1 end end end ######################################## if ARGV.length != 2 puts "Usage: #{$0} <start> <target>" exit end NumericMaze.solve(ARGV[0].to_i, ARGV[1].to_i)

on 2006-01-01 18:24

On 1/1/06, Christer Nilsson <janchrister.nilsson@gmail.com> wrote: > > Is it possible that the complete problem is solved optimally? > > Christer It's possible, but I don't know.

on 2006-01-01 18:42

On Jan 1, 2006, at 11:01 AM, Maurice Codik wrote: > I guess we're allowed to submit solutions now... Yes, 48 hours have passed sent the quiz was sent in > here's my first ever ruby quiz solution Awesome. Thanks for joining the fun! > (these quizzes are a great idea, btw): Thanks. I truly hope people find them helpful. > It exploits the fact that the optimal path through the maze will > never have > consecutive double/halves, which reduces the avg branching factor > of the > search tree to ~2. Keeping track of this state makes the code a little > uglier, but faster on the longer searches. Hey, that's clever. Thanks for sharing. James Edward Gray II

on 2006-01-01 19:30

For this quiz I took what I made for the word chain quiz and modified it a bit. It uses a bi-directional breadth first search. I didn't allow negative numbers at all just to make it simple for me. -----Horndude77 def solve(from, to) return [from] if from == to ops = [] ops << lambda {|n| n*2} ops << lambda {|n| n/2 if n%2 == 0} ops << lambda {|n| n+2} invops = [] invops << lambda {|n| n/2 if n%2 == 0} invops << lambda {|n| n*2} invops << lambda {|n| n-2} fromedges = {from => :start} toedges = {to => :start} fromqueue = [from] toqueue = [to] 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)

on 2006-01-01 19:39

I've posted my solution, along with a few words about my approach, at <http://www.io.com/~jimm/rubyquiz/quiz60/>. Jim -- Jim Menard, jim.menard@gmail.com, jimm@io.com http://www.io.com/~jimm "Generics in Java are an apology for having collections of Objects, and are somewhat like the puritan's suspicion that someone, somewhere, might be enjoying themselves." -- Steven T Abell in comp.lang.smalltalk

on 2006-01-01 20:12

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

on 2006-01-01 20:54

Mark: could you explain what you mean? these were outputs from that prog: solve(3,1233): [3, 6, 8, 16, 18, 36, 38, 76, 152, 154, 308, 616, 1232, 2464, 2466, 1233] solve(1,25): [1, 3, 6, 12, 24, 48, 50, 25] looks like it finds them just fine... or do u mean that these arent the optimal paths? James: Now that I think about it, your optimization and mine are almost equivalent, I think-- I'm fairly certain that the only way to get to a number that you've been to already is by using consecutive pairs of double/half.. since the add_two operation isn't invertable in this quiz. Maurice

on 2006-01-01 21:28

On 2005-12-31, James Edward Gray II <james@grayproductions.net> wrote: > On Dec 31, 2005, at 12:26 PM, Jim Menard wrote: > >> Damn. I got it down from 7 minutes to 18 seconds on a 667 MHz PPC, but >> it looks like I have a bit more work to do. > > 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

on 2006-01-01 21:43

My first quiz, as well. Simple optimizations of don't-double-after-halving (and vice versa) and pruning. I enjoy the aesthetic feel of moving through one long queue. Not too fast on the large cases though. :) The use of detect is a bit ungainly, but it still seemed like the appropriate function. dave ---- #!/usr/bin/ruby class Array def uniquepush(num) self.push(num) if (self.assoc(num[0]) == nil) end end def interpret(val, solution) returnval = "[" + val.to_s solution[1].each{|step| val = val/2 if (step == 0) val = val+2 if (step == 1) val = val*2 if (step == 2) returnval += "," + val.to_s } returnval += "]" end def solve(initial, target) queue = [[initial, Array.new]] solution = queue.detect{|step| if (step[0] == target) true else queue.uniquepush([step[0]/2, step[1].clone().push(0)]) if (step[0] % 2 == 0 && step[1].last != 2) queue.uniquepush([step[0]+2, step[1].clone().push(1)]) queue.uniquepush([step[0]*2, step[1].clone().push(2)]) if (step[1].last != 0) false end } interpret(initial, solution) end puts solve(ARGV[0].to_i, ARGV[1].to_i)

on 2006-01-01 22:19

On Jan 1, 2006, at 19:54, Maurice Codik wrote: > James: Now that I think about it, your optimization and mine are > almost > equivalent, I think-- I'm fairly certain that the only way to get to a > number that you've been to already is by using consecutive pairs of > double/half.. since the add_two operation isn't invertable in this > quiz. > > Maurice OK, so this sort of counter-example is pretty trivial, but the +2 can be composed to be equivalent to the double operation starting from even numbers, so the double/halve optimisation doesn't necessarily eliminate re-visiting a number in a path (but strikes me that it would do in the overwhelming majority of cases). 4, 6, 8, 4 +2 +2 /2 | *2 | You could heuristicise (neologisms are a New Year's resolution of mine) your way out of this by limiting chains of +2 but, there also exist other more complicated composite operations which are equivalent to doubling, but aren't as easy to optimise away: 6, 3, 5, 10, 12, 6 oops! /2 +2 *2 +2 /2 | *2 | 14, 7, 9, 11, 22, 24, 26, 28, 14 oops! /2 +2 +2 *2 +2 +2 +2 /2 | *2 | For both these sorts of exceptions, though, you'd need more and more instances of +2 in the double-equivalent sequence as the initial number becomes higher and higher, so I don't expect this will cause any particular pain in a practical implementation. matt.

on 2006-01-01 22:40

I'm another newbie to the ruby-quiz. This is a dirt-simple BFS. it takes 8 seconds on my machine to do solve(22,999); i make sure no path hits upon a number a previous path had ever hit upon, and i discovered it'd run slightly faster by simply checking to see if my path is halving right after doubling or doubling right after halving, and *then* checking the entire list of numbers passed. (hope that made sense) i had toyed around with other optimizations but none seemed elegant and time-saving enough to be worth it. what i was hoping for was a nice way to identify when certain paths are careening insanely off-path and clearly won't be the correct answer...i have yet to see the solution that can do things like solve(222,9999) in milliseconds...i am anxiously awaiting one...or did i miss it? here is mine: -------------------------------- def solve(start, finish) paths = [[start, start+2], [start, start*2]]; paths.push([start, start/2]) if (start%2 == 0); allNum = paths.flatten.uniq; loop { newP = Array.new(); paths.each{ |path| curN = path.last; unless(allNum.include?(curN+2)) return path.push(curN+2) if (curN+2 == finish); allNum.push(curN+2); newP.push(path.clone.push(curN+2)); end unless (allNum.include?(curN*2)) return path.push(curN*2) if (curN*2 == finish); allNum.push(curN*2); newP.push(path.clone.push(curN*2)); end if (curN%2 == 0 and not allNum.include?(curN/2)) return path.push(curN/2) if (curN/2 == finish); allNum.push(curN/2); newP.push(path.clone.push(curN/2)); end } paths = newP; } end

on 2006-01-01 23:14

Here's my solution. It uses the A* algorithm and the priority queue stuff from quiz #44. Btw, I'm new to ruby quiz, too. :) Pablo --- #!/usr/bin/ruby INF = 1.0/0.0 LOG2 = Math.log(2) # The priority queue is taken from Ruby Quiz #44 (by Levin Alexander). 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

on 2006-01-01 23:20

> 1248, 2496, 2498, 4996, 4998, 9996, 19992, 19994, 9997, 9999 > > real 96m13.978s > user 49m27.502s > sys 46m22.817s > > Guess I need more than my one optimization now. <laughs> I stopped at 222 -> 4998 which took 43 seconds. Each next step will take a rough factor 3, so I'll end up near 3 hours. Oops... First pruning... Slices running time to less than 0.2 seconds *wheee* and to 9999 in slightly more than 0.2 seconds (which proves I got rid of that nasty exponential thing).

on 2006-01-01 23:20

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

on 2006-01-01 23:38

In article <C95D3FF1-B62F-468B-B791-431D961E29F6@sms.ed.ac.uk>, Matthew Smillie <M.B.Smillie@sms.ed.ac.uk> 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

on 2006-01-01 23:47

Ilmari Heikkinen wrote: > # > # Problems appear when trying to make 255 into 257: > # 11111111 -> 100000001 > # > # The shortest way is by adding 2. > # But the algorithm below fails at that and goes the long way: > # 11111111 << 1 > # 111111110 + 2 > # 1000000000 + 2 > # 1000000010 >> 1 > # 100000001 > # Ilmari, I tried to replicate your solution, before seeing it, and strangely run into exactly the same behaviour. The code is not complete, but the idea is to go downwards to 1 with both numbers. I'm using the complement of +2, -2 for the target number. t up(255), [255, 510, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1] --> --> --v <-- <-- <-- t down(257), [257, 514, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1] Having these two sequences, I find the largest common number, in this case 512. This gives me the non optimal solution [255,510,512,514,257], which is exactly the same as yours. I'm not sure if identifying shortcuts afterwards, will find the shortest path, though, in all cases. (Finding 255 + 2 = 257, is easy, but what about finding 255 -> 259 if 257 is missing.) I tried the six digit subproblem of your big problem, and it worked out perfectly optimal. So I was surprised 255 -> 257 behaved so bad. Christer def down(x) return [] if x==0 return [1] if x==1 return [2,1] if x==2 return [x] + down(x*2) if x.modulo(2)==1 return [x] + down(x/2) if x.modulo(4)==0 [x] + down(x-2) end def up(x) return [] if x==0 return [1] if x==1 return [2,1] if x==2 return [x] + up(x*2) if x.modulo(2)==1 return [x] + up(x/2) if x.modulo(4)==0 [x] + up(x+2) end require 'test/unit' class TestIlmari < Test::Unit::TestCase def t (actual, expect) assert_equal expect, actual end def test_all t up(255), [255, 510, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1] t down(257), [257, 514, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1] #t up(72), [72,36,18,20,10,12,6,8,4,2,1] #t down(28), [28,14,12,6,4,2,1] #t up(150128850109293).size,82 #t down(8591982807778218492).size, 100 end end

on 2006-01-02 00:05

> [snip...] > > 483 tests, 738 assertions, 0 failures, 114 errors > > I'm having my solve method throw an error when it is taking too long > to evaluate to more easily distinguish giving an invalid result from > just taking too long. > > Slightly updated test suite: http://rafb.net/paste/results/SKaTxv60.nln.html So very sorry... http://rafb.net/paste/results/bsHQO336.html

on 2006-01-02 00:11

Ok, my solution. It keeps track of all reached numbers *and* how it gets there in a hash (path). When the target is in the hash we simply have to go backwards and remember the values we pass on the way. It does the 222 -> 9999 in 6.2s on my 2GHz+something system. (should be easy to do a search from both sides, but no time [yet]) cheers Simon ---------------------------------------------------------------- from, to = ARGV.shift || 222, ARGV.shift || 9999 t = Time.now path = {from => :found} while not path.include? to path.keys.each do |n| path[n + 2] = :add unless path.include?(n + 2) path[n * 2] = :mul unless path.include?(n * 2) path[n / 2] = :div unless (n % 2) != 0 || path.include?(n / 2) end end result = [to] loop do case path[result.last] when :add then result << result.last - 2 when :mul then result << result.last / 2 when :div then result << result.last * 2 else break end end p result.reverse puts "Time: #{Time.now - t}s"

on 2006-01-02 00:26

On Jan 1, 2006, at 4:37 PM, Phil Tomson 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 Gray II

on 2006-01-02 00:35

On Jan 1, 2006, at 11:01 AM, Maurice Codik wrote: > here's my first ever ruby quiz solution On Jan 1, 2006, at 2:41 PM, Dave Lewis wrote: > My first quiz, as well. On Jan 1, 2006, at 3:39 PM, Justin Bishop wrote: > I'm another newbie to the ruby-quiz. On Jan 1, 2006, at 4:14 PM, Pablo Hoch wrote: > Btw, I'm new to ruby quiz, too. :) 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 Gray II

on 2006-01-02 00:39

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

on 2006-01-02 00:45

In article <60768b90601011339l5a8bd2ecq514eb3c2fa59d52c@mail.gmail.com>, Justin Bishop <jubishop@gmail.com> 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

on 2006-01-02 01:12

This is my first Ruby quiz. I was hoping to have the whole thing done by the end of the first 48 hours, but I kept getting hung up on edge cases. I did figure out the binary approach on my own, though. On Mon, Jan 02, 2006 at 08:42:56AM +0900, Reinder Verlinde 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

on 2006-01-02 02:04

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

on 2006-01-02 02:18

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

on 2006-01-02 03:04

> My solution's similar in style [breadth first, don't duplicate search], > though I've also roof-limited it so it can't explore the search space > above 2*[max(target,start)] + 4 which provides a fair speed up for e.g. > 222, 9999. I'm not sure if that loses the optimality property though. I use @@max = [(source + 2) * 2, target * 2].max which matches your roof almost exactly (The small assymetry is due to the missing sub2 operator, naturally.). The speedup is huge, as you can see in some other posting of mine. I'm not entirely certain about the optimality property, but look at the following example: 13, 15, 30, 32, 16, 8 # what I thought of myself, pushing through the roof 13, 26, 28, 14, 16, 8 # what the program found, not going through the roof Where the point is that an odd number either +1 or +3 can always be halved twice, and there is no point in adding two first (though maybe in between). I'm even thinking [source*2+2, target*2].max could be the roof, but hey, what's 2 more or less. Ah well, this is not my field of expertise. Somebody can shed more light on this? Bye, Kero.

on 2006-01-02 03:25

Hey everyone, Like so many people before me, this is my first Ruby Quiz 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 }

on 2006-01-02 03:52

On Mon, Jan 02, 2006 at 10:19:00AM +0900, Kenneth Collins wrote: } Kenneth Collins wrote: } > Gregory Seidman wrote: } >> This is my first Ruby quiz. I was hoping to have the whole thing done } >> by the end of the first 48 hours, but I kept getting hung up on edge } >> cases. } >> I did figure out the binary approach on my own, though. } >> } > } > Gregory, this is an amazing solution! However I got a failure trying } > some arbitrarily selected src and dst values: } > } > $ ruby test60.rb 4934939 39329291 } > ./60.rb:47:in `halve': Trying to halve an odd number: 49 (RuntimeError) } > from ./60.rb:127:in `solve' } > from test60.rb:7 } } Another case with smaller numbers: } } $ ruby test60.rb 49 64 } ./60.rb:47:in `halve': Trying to halve an odd number: 49 (RuntimeError) } from ./60.rb:127:in `solve' } from test60.rb:7 Ratzafratz. I'll look into it. Did I mention running into problems with edge cases? Oy. Thanks for the test cases. --Greg

on 2006-01-02 06:37

On 1/2/06, Gregory Seidman <gsslist+ruby@anthropohedron.net> wrote: > I'm pretty sure the results are guaranteed to > be optimal, too. > $ ruby test60.rb 255 257 [255, 510, 512, 514, 257] Ops = 4: daah Same problem I ran into :)

on 2006-01-02 06:55

On 1/2/06, Christer Nilsson <janchrister.nilsson@gmail.com> 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

on 2006-01-02 08:26

Here's my (first) solution (ever) for quiz #60. I also choose a breadth-first search algorithm because I'm probably going to need a decent searching algorithm in the near future. To maximize reusability, I implemented 6 methods in the Integer class that abstract the problem-specific logic out of the searching algorithm. When I use a different 'node' class, I will also need to include the Comparable mix-in and define the <=> method for the Array.max method on line #40. The running time for the algorithm is O(N), where N is the number of integers the algorithm 'visits'. To limit the number of visited 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 Gray II) unless ARGV.size == 2 and ARGV.all? { |n| n =~ /\A[1-9]\d*\Z/ } puts "Usage: #{File.basename($0)} START_NUMBER FINISH_NUMBER" puts " Both number arguments must be positive integers." exit end start, finish = ARGV.map { |n| Integer(n) } p solve(start, finish) end

on 2006-01-02 17:25

On Sun, 01 Jan 2006 19:27:56 +0100, <horndude77@gmail.com> wrote: > For this quiz I took what I made for the word chain quiz and modified > it a bit. I did that, too ;-) My solution uses unidirectional BFS (like many others). The NumericMaze class is generic, meaning that it can also work with other ops, so naturally it doesn't have any optimizations for this special problem. I only limit the search space in the "if $0 == __FILE__" part. Dominik class NumericMaze OP_DOUBLE = lambda { |x| x * 2 } OP_HALVE = lambda { |x| x % 2 == 0 ? x / 2 : nil } OP_ADD_TWO = lambda { |x| x + 2 } # ops is an array of lambdas, each lambda returns a next step for a given # number, or nil if no next step is possible for the given number def initialize(ops = [OP_DOUBLE, OP_HALVE, OP_ADD_TWO]) @ops = ops end def solve(start, target, max_num = nil) # build chain with simple breadth first search current = [start] return current if start == target pre = { start => nil } # will contain the predecessors catch(:done) do until current.empty? next_step = [] current.each do |num| @ops.each do |op| unless (step_num = op[num]).nil? # have we seen this number before? unless pre.has_key?(step_num) || (max_num && step_num > max_num) pre[step_num] = num throw(:done) if step_num == target next_step << step_num end end end end current = next_step end return nil # no chain found end # build the chain (in reverse order) chain = [target] chain << target while target = pre[target] chain.reverse end end if $0 == __FILE__ a, b, = *ARGV.map { |str| Integer(str) } p NumericMaze.new.solve(a, b, [a, b].max.abs * 3) end

on 2006-01-02 17:28

On Mon, 02 Jan 2006 08:25:08 +0100, J. Ryan Sobol <ryansobol@gmail.com> 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

on 2006-01-02 18:08

On Jan 2, 2006, at 11:24 AM, Dominik Bathon wrote: > On Mon, 02 Jan 2006 08:25:08 +0100, J. Ryan Sobol > <ryansobol@gmail.com> 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 ~

on 2006-01-02 18:29

I didn't like having the roof calculation done inside the solve method. So here is my revised algorithm, including Dominik's suggestions and a new roof class method for Integer. #!/usr/bin/env ruby class Integer 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 Gray II) unless ARGV.size == 2 and ARGV.all? { |n| n =~ /\A[1-9]\d*\Z/ } puts "Usage: #{File.basename($0)} START_NUMBER FINISH_NUMBER" puts " Both number arguments must be positive integers." exit end start, finish = ARGV.map { |n| Integer(n) } p solve(start, finish) end ~ ryan ~

on 2006-01-02 20:54

okay here's my shot at the quiz, it's quite large for such a simple problem, but i couldn't resist to use :* in my code ;-) class Integer def even? self % 2 == 0 end def odd? not even? end end # solves rubyquiz #60 class Solver def initialize(start, goal) @start, @goal = start, goal @visited = {} @queue = [[@goal, []]] @ops = [] [AddTwo, Double, Halve].each {|op| @ops << op.new(@start, @goal) } end # are we there yet? def done_with?(temp_goal) @start == temp_goal end # transforms the carried steps into a valid solution def solution(steps) steps.reverse.unshift @start end # does all the work def solve # there should be a better way to recover the steps than carrying them # around in the search tree (depth first search for example?) while current = @queue.shift temp_goal, steps = *current # parallel assignment in conditionals won't work return solution(steps) if done_with? temp_goal next if @visited[temp_goal] # been there, done that #puts "#{@start} -> #{@goal}: testing #{temp_goal}, steps so far: #{steps.join(" ")}" #gets @visited[temp_goal] = true new_steps = steps + [temp_goal] @ops.each do |op| @queue << [op.apply(temp_goal), new_steps] if op.makes_sense? temp_goal end end # my guess is, that there's always a solution. any proof? raise "no solution found" end # creates a new solver and attempts to solve(a,b) def self.solve(a,b) new(a,b).solve end end # Applies a method with the argument 2 # maybe too much OO? :-) class TwoOperation def initialize(start, goal) @start, @goal = start, goal end def apply(temp_goal) temp_goal.send(@meth, 2) end def makes_sense? false end end # inverse of double class Double < TwoOperation def initialize(start, goal) super @meth = :/ end def makes_sense?(temp_goal) temp_goal.even? end end # inverse of halve class Halve < TwoOperation def initialize(start, goal) super @meth = :* # heh a kissing smiley, ruby is soo cute end def makes_sense?(temp_goal) # was (@goal < @start and temp_goal.even?) or (not temp_goal.even?) temp_goal.odd? or @goal < @start end end # 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

on 2006-01-02 22:14

Here it is, my solution. From mathematical and algorithmic point of view, you won't find anything new. However: - One of the few times that class variables come in handy: I put the halve/double operations into Integer and then decided to make the do-all method Integer.solve_num_maze but the steps are done in Integer#handle_num_maze - Both optimizations are done in the method #enqueue 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)

on 2006-01-02 22:54

Hello dear quizzers, could someone please confirm (or disprove) that this i correct? [222222222, 222222224, 111111112, 55555556, 27777778, 27777780, 13888890, 13888892, 6944446, 6944448, 3472224, 1736112, 868056, 434028, 217014, 217016, 108508, 54254, 54256, 27128, 13564, 6782, 6784, 3392, 1696, 848, 424, 212, 106, 108, 54, 27, 29, 31, 33, 35, 37, 39, 78, 156, 158, 316, 632, 634, 1268, 1270, 2540, 2542, 5084, 5086, 10172, 20344, 40688, 40690, 81380, 162760, 325520, 651040, 1302080, 1302082, 2604164, 2604166, 5208332, 10416664, 10416666, 20833332, 41666664, 41666666, 83333332, 166666664, 166666666, 333333332, 666666664, 666666666, 333333333] 75 items Time: 62.015s There seems to be more potential in the brute force attack than i thought possible. cheers Simon

on 2006-01-02 23: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

on 2006-01-02 23:57

Thanks for the testcases, i just found a shorter one for (700, 1) [700, 350, 352, 176, 88, 44, 22, 24, 12, 6, 8, 4, 2, 1] and a different one for test_minus_one_two_three_five_and_ten(TestNumericMaze) [quiz60.rb:448]: <[159, 318, 320, 160, 80, 40, 20, 10, 5, 7, 9, 18, 36, 72, 74, 76, 78, 156, 158]> expected but was <[159, 318, 320, 160, 80, 40, 20, 10, 12, 14, 16, 18, 36, 38, 76, 78, 156, 158]>. cheers Simon

on 2006-01-03 00:13

I always learn something from Ruby Quiz! 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 Quiz #60, Numeric Maze # http://www.rubyquiz.com/quiz60.html # # You have a starting point and a target, say 2 and 9. # You have a set of three operations: # double, halve (odd numbers cannot be halved), add_two. # # Problem: Move from the starting point to the target, # minimizing the number of operations. # Examples: # solve(2,9) # => [2,4,8,16,18,9] # solve(9,2) # => [9,18,20,10,12,6,8,4,2] # # # This solution builds a tree with each node having up to # three subnodes, one for each operation. It builds the # tree one level at a time and checks for a solution before # proceeding down to the next level. This brute force # approach performs much better after adding two optimizations # suggested by Dominik Bathon 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 Bathon) visited_numbers = {} # Check for a solution at each level level = 0 while true # Examine nodes at this level and # build subnodes when appropriate node_arrays[level+1] = [] node_arrays[level].each do |node| # Skip if method "halve" failed next if node == :halve_failed # Skip if 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)

on 2006-01-03 01:16

```
On Jan 2, 2006, at 2:57 PM, Simon KrÃ¶ger wrote:
> Thanks for the testcases,
You're welcome. Thanks for trying them.
--Steve
```

on 2006-01-03 01:20

Simon wrote: > Hello dear quizzers, > > could someone please confirm (or disprove) that this i correct? > my subproblem solution to (868056,651040) gave the same result as your, in 76 secs. I investigated the ideas suggested by Ilmari and Greg, but found that there is no way of knowing if the result is optimal. The result are impressing, but misses often trivial cases. It seems as hard to patch the non optimal solution as it is to solve it normally. Are you using a different approach? Christer

on 2006-01-03 01:39

0x002A@gmail.com 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

on 2006-01-03 02:47

On Monday 02 January 2006 15:57, Simon KrÃƒÂ¶ger wrote: > and a different one for > test_minus_one_two_three_five_and_ten(TestNumericMaze) [quiz60.rb:448]: > <[159, 318, 320, 160, 80, 40, 20, 10, 5, 7, 9, 18, 36, 72, 74, 76, 78, > 156, 158]> expected but was > <[159, 318, 320, 160, 80, 40, 20, 10, 12, 14, 16, 18, 36, 38, 76, 78, > 156, 158]>. (BTW, the second on there *is* shorter. =)

on 2006-01-03 06:15

Ok, It's a day late, but I've got my solution. I've also updated the test suite I submitted earlier with some shorter solutions. All it assumes is that you have a method solve that takes two whole numbers (some tests use 0 as a starting point) that returns a list of numbers representing the path. I found it useful for testing and benchmarking. http://rafb.net/paste/results/zoPwZL59.html Initially I tried a blind breath first search, which worked pretty well, but there were a lot of values in my test suite that took an obscene amount of time to run. Today I decided to switch over to an A* search, which improved things a lot. My heuristic (abs(log_base(2,a) - log_base(2,b))) is based on the idea that (except for 0 and 1) multiplying/dividing by two is the fastest way of moving toward the goal number. I apologize if that didn't make any sense. Anyway, assuming I implimented it correctly, and my heuristic is optimistic (the latter claim I'm moderately sure of) this should return the shortest path. http://rafb.net/paste/results/exPug998.html I'd be interested in seeing other's benchmarks on this suite. ~/Documents/Projects/ruby_quiz peter$ ruby 60.rb Loaded suite 60 Started ..................................................................................................... ..................................................................................................... ..................................................................................................... ..................................................................................................... ............................................................................... Finished in 90.666885 seconds. 483 tests, 966 assertions, 0 failures, 0 errors [On a iBook G4, 512 meg ram]

on 2006-01-03 14: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 Sobol, was the leader, clocking in at 2.376 secs with #60.20 on the Quiz list. Your #60.22, clocks in at 1.972 seconds, a decrease by 17%. I'm challenging every quizzer: There is more to fetch! 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 Nilsson

on 2006-01-03 17:00

On Jan 3, 2006, at 8:01 AM, Christer Nilsson wrote: > Before you, Ryan Sobol, was the leader, clocking in at 2.376 > secs with #60.20 on the Quiz list. Your #60.22, clocks in at 1.972 > seconds, a decrease by 17%. Nuts. :) Kudos, Kero! ~ ryan ~

on 2006-01-03 20:15

0x002A@gmail.com wrote: > okay here's my shot at the quiz, it's quite large for such a simple > problem, but i couldn't resist to use > :* in my code ;-) now without :* but much shorter.. class Integer def even? self % 2 == 0 end def odd? not even? end end # solves rubyquiz #60 class Solver def initialize(start, goal) @start, @goal = start, goal @visited = {} @queue = [[@goal, []]] @ops = [] @ops << lambda {|x| x - 2 if x > 1 } @ops << lambda {|x| x * 2 if x.odd? or @goal < @start } @ops << lambda {|x| x / 2 if x.even? } end # are we there yet? def done_with?(temp_goal) @start == temp_goal end # transforms the carried steps into a valid solution def solution(steps) steps.reverse.unshift @start end # does all the work def solve while current = @queue.shift temp_goal, steps = *current return solution(steps) if done_with? temp_goal # been there, done that next if @visited[temp_goal] @visited[temp_goal] = true new_steps = steps + [temp_goal] @ops.each do |op| if (new_goal = op.call temp_goal) @queue << [new_goal, new_steps] end end end raise "no solution found" end # creates a new solver and attempts to solve(a,b) def self.solve(a,b) new(a,b).solve end end # for the testcases def solve(a, b) Solver.solve(a,b) end

on 2006-01-03 21:20

0x002A@gmail.com wrote: > > now without :* but much shorter.. > Still doesn't solve (222,999) correctly. One step too much. 222 224 112 56 58 60 62 124 248 496 498 996 998 1996 1998 999 expected but was 222 111 113 115 117 119 121 123 246 248 496 498 996 1992 1994 997 999 Christer

on 2006-01-03 23:58

Here is my solution, very much a derivative of my solution to the Knight's Travails quiz (#27). It will return a shortest solution (chosen at random if there are more than one). It will always find a shortest solution, though not necessarily fast. (I haven't tried timing this.) # Helper methods class Integer def even? self & 1 == 0 end 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)

on 2006-01-04 00:45

Here's my solution. It's a bi-directional depth-first search. I'm not sure anyone else did that. It's reasonably fast for small numbers, but takes 25 secs to do 22222->99999 It also solves Quiz60B, if you adjust the costs. use 22->34 for an example where the different costs affect the solution. -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

on 2006-01-04 06:13

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

on 2006-01-04 13:30

>> Here it is, my solution. From mathematical and algorithmic point of >> view, you won't find anything new. > > Kero, this is really the quickest solution so far, passing my little > test suite. Before you, Ryan Sobol, was the leader, clocking in at 2.376 > secs with #60.20 on the Quiz list. Your #60.22, clocks in at 1.972 > seconds, a decrease by 17%. > > I'm challenging every quizzer: There is more to fetch! You don't say? You do 868056 -> 651040 in 76 seconds. I broke my program off after 15 minutes. I can not accept the title of fastest solution. However, I need 21 seconds for 868056 -> 27 so I would assume that searching for prefixes, or the approach from two sides has lots of potential. > By refactoring Kero's code, I was able to squeeze the execution time to > 0.37 seconds, that's another 80%. Did you do other things than eliminating method calls? > I'm not submitting this code, as I'm sure there are more improvements to > be done. If you did other things, I'd be interested to see it, still. My mail address is mangled, "kero@chello.single-dot.nl".split(/\./).values_at(0,2).join(".") Thanks.

on 2006-01-04 16:50

Kero wrote: > I can not accept the title of fastest solution. I think there are a lot of winners here. Your code executed fastest for one problem. It's quite difficult to filter out a single winner. A lot of different problems has to be defined. So, the person owning the problem formulation privilege, has all the power. One remedy for this would be to let every participant suggest one problem (start and target) each. Then every solver has to solve all suggested problems, and the solvers will get a score according to their rank for each individual problem. That's a lot to administer. A cut off time has to be decided, say one second. And then we have the problem with "dirty" integers, some solutions leave after execution. Should the clean up time be included? "Dirty" Integer: By attaching data to the Integer objects, like "parent" and "queue", Arrays can be avoided. But the next call to "solve" will be affected, if the Integers are not clean. See Quiz#60.20, line 2. As I submitted this Quiz, I wouldn't like to be part af that contest. > Did you do other things than eliminating method calls? Inline code only account for an improvement of 7%, so the answer is yes. > If you did other things, I'd be interested to see it, still. I've sent the code to James. Eventually it will published in his wrap-up. If not, it will be submitted to the ML. > However, I need 21 seconds for 868056 -> 27 so I would assume that > searching for prefixes, or the approach from two sides has lots of potential. Agreed, searching from two sides could probably gain a lot. If we have a distance from start to target of 10, with an average branching factor of 2, the workload should be proportional to 1024. Starting from both sides, the workload should be something like 32 + 32 = 64, with a potential of being 16 times faster. I haven't even tried this approach, yet. Christer

on 2006-01-04 18:12

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

on 2006-01-04 18:13

On Jan 4, 2006, at 9:50 AM, Christer Nilsson 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 Gray II

on 2006-01-04 18:13

Yup, my solution is really slow. I made a minor change which reduces the search space a little (and avoids things such as double followed by halve, and v-v). Still rather slow, but I didn't expect it to be fast. class Integer def even? self & 1 == 0 end 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)

on 2006-01-04 18:14

Christer Nilsson wrote: > in 76 secs. > > I investigated the ideas suggested by Ilmari and Greg, but found that > there is no way of knowing if the result is optimal. The result are > impressing, but misses often trivial cases. It seems as hard to patch > the non optimal solution as it is to solve it normally. > > Are you using a different approach? > > Christer Oops, sorry i kind of 'lost' this thread.. My approach isn't that different but a little bit more optimized. I use strings instead of hashs (or arrays like you do) to store the information (and i only store which operation leads us there, ?X is an empty field, ?M - multiply, ?D - divide, ?A - add, ?S - sub). I need ?S (Sub 2) because search is done from both sides. Well, here it is, it solves the the subproblem in 0.062s. --------------------------------------------------------------------- require 'set' def find_path from, to pathf = ''.ljust([from + 2, to + 2].max * 2, 'X') pathb = pathf.dup pathf[from] = ?F pathb[to] = ?F forward, backward, newbees = [from], [to], [] loop do forward.each do |n| pathf[newbees.push(n + 2).last] = ?S if pathf[n+2] == ?X pathf[newbees.push(n + n).last] = ?D if pathf[n+n] == ?X pathf[newbees.push(n / 2).last] = ?M if (n%2) == 0 && pathf[n/2] == ?X end forward, newbees = newbees, [] forward.each {|n|return pathf, pathb, n if pathb[n] != ?X} backward.each do |n| pathb[newbees.push(n - 2).last] = ?A if n > 1 && pathb[n-2] == ?X pathb[newbees.push(n + n).last] = ?D if pathb[n+n] == ?X pathb[newbees.push(n / 2).last] = ?M if (n % 2) == 0 && pathb[n/2] == ?X end backward, newbees = newbees, [] backward.each {|n|return pathf, pathb, n if pathf[n] != ?X} end end def solve from, to return nil if from < 0 || to <= 0 return [from] if from == to pathf, pathb, n = find_path(from, to) result = [n] [pathf, pathb].each do |path| loop do case path[result.last] when ?A then result << result.last + 2 when ?S then result << result.last - 2 when ?D then result << result.last / 2 when ?M then result << result.last * 2 else break end end result.reverse! end result.reverse end from, to = (ARGV.shift || 868056).to_i, (ARGV.shift || 651040).to_i t = Time.now p solve(from, to) puts "Time: #{Time.now - t}" --------------------------------------------------------------------- cheers Simon

on 2006-01-04 22: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

on 2006-01-05 14: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

on 2006-01-06 19:51

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

on 2006-01-06 20:00

```
On Jan 6, 2006, at 12:49 PM, Robert Retzbach wrote:
> Don't let us wait too long for that dice riddle :>
Sorry, crazy day. It's up now.
James Edward Gray II
```