[QUIZ] Numeric Maze (#60)

[Ruby Quiz]

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]

 

[J. Ryan Sobol]

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

~ ryan ~

 

[James Edward Gray II]

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

 

[Christer Nilsson]

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

 

[James Edward Gray II]

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.

Works for me. Let's do that.

James Edward Gray II

 

[Christer Nilsson]

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

 

[J. Ryan Sobol]

--Apple-Mail-31-907533850
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
charset=US-ASCII;
delsp=yes;
format=flowed

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.




--Apple-Mail-31-907533850--

 

[James Edward Gray II]

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) # => ???

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

 

[Christer Nilsson]

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

 

[Kero]

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

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.

 

[Jim Freeze]

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

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

Some examples:

solve(1, 1) # =3D> [1]

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

[1,2,1]
[1,0.5,1]

 

[Matthew Smillie]

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]

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

m.s.

 

[Christer Nilsson]

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

 

[Robert Retzbach]

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.

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

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

But thinking about a no BF solution makes my head hurt
I have created some algos but they all don't find the shortest way.

I also have to mention that there are often more than 1 'shortest' ways.

I exspect the best of you!
Good luck.

 

[Christer Nilsson]

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

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

But thinking about a no BF solution makes my head hurt
I have created some algos but they all don't find the shortest way.

I also have to mention that there are often more than 1 'shortest' ways.

I exspect the best of you!
Good luck.

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

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

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

Christer

 

[Jim Freeze]

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

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.

 

[Jim Freeze]

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

solve(1, 1) # =3D> [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) #=3D> [2,4,2] or [2,1,2]

 

[James Edward Gray II]

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]

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

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

 

[Jim Freeze]

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

On 12/30/05, James Edward Gray II


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) #=3D> [1,1]

or, we use the original tranformations to get:

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

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

$0.02

 

[Christer Nilsson]

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