Jim F. wrote:
$ xform
0 times_one
1 add_two
2 times_two
4 times_one_half
Jim, you have just defined Quiz #60B !
The original Quiz #60A looks like this:
$ xform
0 times_one
1 add_two
1 times_two
1 halve
Feel free to submit to none, one or both !
Christer
On 12/30/05, Christer N. [email protected] 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
Kero wrote:
I have a generic solution which is perfectly happy with negative numbers
(and Bignums) which is unlikely to be the fastest solution at all. Now
you
allow others to use even more optimizations!
Kero,
You are perfectly right, I should have stated clearly in the Quiz
description, that the domain is positive integers.
There is no reason to include zero or negative numbers. The number of
possible mazes is still infinity squared!
Enjoy!
Christer N.
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.
In article [email protected],
Jim F. [email protected] 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 Dec 30, 2005, at 2:27 PM, James Edward G. II wrote:
On Dec 30, 2005, at 4:17 PM, J. Ryan S. wrote:
Would it be appropriate to post my potential answers (not code) to
this question? For example,Absolutely. Please do.
Since that’s about all I’m going to be able to do on this quiz, here
are some of my test cases. I’m pretty confident in the shorter
solutions, but have less confidence in the longer ones. These were
all discovered via stochastic search.
I hope this won’t qualify as “code”, as mentioned above - since the
idea is that everyone may test their solutions against this, the fact
that it’s already coded as test cases seems naturally acceptable to me.
I’m very much looking forward to the solutions on this one!
For now, I’ve posted them on http://swaits.com/
–Steve
Stephen W. wrote:
Since that’s about all I’m going to be able to do on this quiz, here
are some of my test cases. I’m pretty confident in the shorter
solutions, but have less confidence in the longer ones. These were
all discovered via stochastic search.I hope this won’t qualify as “code”, as mentioned above - since the
idea is that everyone may test their solutions against this, the fact
that it’s already coded as test cases seems naturally acceptable to me.I’m very much looking forward to the solutions on this one!
For now, I’ve posted them on http://swaits.com/
–Steve
Steve, there seem to be at least one difference:
<[300, 302, 304, 152, … , 2, 1]> expected but was
<[300, 150, 152, … , 2, 1]>.
Christer
On Dec 30, 2005, at 5:51 PM, Robert R. wrote:
It took 20-30min
$ time ruby numeric_maze.rb 22 999
22, 24, 26, 28, 30, 60, 62, 124, 248, 496, 498, 996, 1992, 1994, 997,
999
real 0m0.635s
user 0m0.381s
sys 0m0.252s
James Edward G. II
James Edward G. II:
You can’t get a negative, unless you start with one.
Doesn’t 2 / 2 == 1 evaluate as true?
Malte
On Dec 31, 2005, at 11:47 AM, Malte M. wrote:
James Edward G. II:
You can’t get a negative, unless you start with one.
Doesn’t 2 / 2 == 1 evaluate as true?
Yes, but how does that get you a negative number?
James Edward G. II
On Dec 31, 2005, at 10:10 AM, Gavin K. wrote:
I know, I read “one” as “1” the first time also
It happened to me too. Took me at least a minute to figure out my
problem. 
–Steve
On Dec 31, 2005, at 10:47 AM, Malte M. wrote:
James Edward G. II:
You can’t get a negative, unless you start with one.
Doesn’t 2 / 2 == 1 evaluate as true?
He meant “You can’t get a negative, unless you start with a negative”
and not “You can’t get a negative, unless you start with 1”.
I know, I read “one” as “1” the first time also
On 12/31/05, James Edward G. II [email protected] wrote:
1 - halve
sys 0m0.252s
James Edward G. II
Damn. I got it down from 7 minutes to 18 seconds on a 667 MHz PPC, but
it looks like I have a bit more work to do.
Jim M., [email protected], [email protected]
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 Dec 31, 2005, at 9:47 AM, Christer N. wrote:
Steve, there seem to be at least one difference:
<[300, 302, 304, 152, … , 2, 1]> expected but was
<[300, 150, 152, … , 2, 1]>.
Thanks Christer…
I’ll fix that one. My search was far from exhaustive.
–Steve
James G. wrote:
On Dec 30, 2005, at 5:51 PM, Robert R. wrote:
It took 20-30min
$ time ruby numeric_maze.rb 22 999
22, 24, 26, 28, 30, 60, 62, 124, 248, 496, 498, 996, 1992, 1994, 997,
999real 0m0.635s
user 0m0.381s
sys 0m0.252s
James Edward G. II
Very new Rubyist here.
solve(22, 999)
result:
Total time taken in seconds: 0.782
[22, 24, 26, 28, 30, 60, 62, 124, 248, 496, 498, 996, 998, 1996, 1998,
999]
solve(222, 9999)
result:
Total time taken in seconds: 56.0
[222, 224, 226, 228, 230, 232, 234, 236, 238, 240, 242, 244, 246, 248,
250, 252, 254, 256, 258, 260, 262, 264, 266, 268, 270, 272, 274, 276,
278, 280, 282, 284, 286, 288, 290, 292, 294, 296, 298, 300, 302, 304,
306, 308, 310, 312, 624, 1248, 2496, 2498, 4996, 4998, 9996, 9998,
19996, 19998, 9999]
AMD Athlon 1400, 1.6 GHz
On Dec 31, 2005, at 12:26 PM, Jim M. wrote:
Damn. I got it down from 7 minutes to 18 seconds on a 667 MHz PPC, but
it looks like I have a bit more work to do.
I’m using a Dual 2 Ghz G5, so the hardware is at least some of the
difference.
James Edward G. II
Gavin K.:
James Edward G. II:
You can’t get a negative, unless you start with one.
He meant “You can’t get a negative, unless you start with a negative” and
not “You can’t get a negative, unless you start with 1”.
Now I got it. Thank you!
Malte
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
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 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. 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.
James Edward G. II
This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.
Sponsor our Newsletter | Privacy Policy | Terms of Service | Remote Ruby Jobs
