Numeric Maze (#60)

Ruby
1

The three rules of Ruby Q.:

  1. Please do not post any solutions or spoiler discussion for this quiz
    until
    48 hours have passed from the time on this message.

  2. Support Ruby Q. by submitting ideas as often as you can:

http://www.rubyquiz.com/

  1. Enjoy!

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Christer N.

You have a starting point and a target, say 2 and 9.

You have a set of three operations:

double
halve    (Odd numbers cannot be halved.)
add_two

Problem: Move from the starting point to the target, minimizing the
number of
operations.

Examples:

solve(2,9)  # => [2,4,8,16,18,9]
solve(9,2)  # => [9,18,20,10,12,6,8,4,2]
2

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

~ ryan ~

3

On Dec 30, 2005, at 2:18 PM, J. Ryan S. wrote:

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

Zero seems fine as a starting number. You can always add_two.

You can’t get a negative, unless you start with one. If you do,
other negative targets and even a target of 0, seem fine. Some
numbers would be impossible to reach though.

I think allowing them is fine. Let’s just add that you’re program
won’t be fed a start and end that have no solution (at least by me).
Sound fair?

James Edward G. II

4

J. Ryan S. wrote:

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

~ ryan ~

I made a quick analysis:

target

  • 0 +
  • ok ok ok
    0 no ok ok
  • no no ok
    start

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

Christer N.

5

On Sat, Dec 31, 2005 at 05:36:58AM +0900, James Edward G. II wrote:

On Dec 30, 2005, at 2:18 PM, J. Ryan S. wrote:

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

Zero seems fine as a starting number. You can always add_two.

You can’t get a negative, unless you start with one. If you do, other
negative targets and even a target of 0, seem fine. Some numbers would be
impossible to reach though.

Heh, I couldn’t figure out how to get a negative number using double,
halve,
and add_two from the number 1. Then I realized the problem wasn’t with
my
math, but with my English :slight_smile:

That, or I’m really confused.
Jeff

6

On Dec 30, 2005, at 2:57 PM, Christer N. wrote:

  • ok ok ok
    0 no ok ok
  • no no ok
    start

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

Works for me. Let’s do that.

James Edward G. II

7

On Dec 30, 2005, at 8:37 AM, Ruby Q. wrote:

The three rules of Ruby Q.:

  1. Please do not post any solutions or spoiler discussion for this
    quiz until
    48 hours have passed from the time on this message.

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

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

This is the first Number Theory exercise I’ve done in a while and I’m
not 100% confident I can test my algorithm against my the solutions I
come up with by hand. :slight_smile: 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.

8

Jeffrey D. wrote:

Heh, I couldn’t figure out how to get a negative number using double,
halve,
and add_two from the number 1.

You are correct Jeffrey, see the matrix in my last reply. Starting with
a positive number, you can only reach positive numbers.

This quiz should be interesting enough, using only positive numbers, as
any positive number can be reached from any positive number.

Christer N.

9

On Dec 30, 2005, at 4:17 PM, J. Ryan S. wrote:

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

Absolutely. Please do.

Then people can counter post if they think they have a better
answer… :wink:

PS- I’m new here and I hope I’m not over overstepping the rules.

Welcome to Ruby Q., Ryan. And no worries, you are doing just fine.

James Edward G. II

10

On 12/30/05, Christer N. [email protected] wrote:

J. Ryan S. wrote:

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

Some examples:

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

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

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

11

On Dec 30, 2005, at 23:37, Jim F. wrote:

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

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

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

m.s.

12

J. Ryan S. wrote:

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

Some examples:

solve(1, 1) # => [1]
solve(1, 2) # => [1, 2]
solve(1, 25) # => [1, 3, 6, 12, 24, 48, 50, 25]
solve(12, 11)# => [12, 14, 7, 9, 11]
solve(2, 9) # => [2, 4, 8, 16, 18, 9]
solve(9, 2) # => [9, 18, 20, 10, 12, 6, 8, 4, 2]
solve(17, 1) # => [17, 34, 36, 18, 20, 10, 12, 6, 8, 4, 2, 1]

There may exist equivalent paths, of the same length.

Christer N.

13

Jim F. wrote:

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

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

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

Only positive integers are allowed.
That means you can’t divide odd numbers with two (operation halve)

If start equals target, zero steps are needed.

Christer N.

14

J. Ryan S. schrieb:

this question? For example,

~ ryan ~

PS- I’m new here and I hope I’m not over overstepping the rules.

Hello.
I really enjoyed this puzzle, but my brain and my cpu are burning.

In a german ruby channel we used the example 22->999.
My really slow brute force algo came up with
122002000200212

0 - double
1 - halve
2 - add_two

It took 20-30min :smiley:

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

But thinking about a no BF solution makes my head hurt :frowning:
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.

15

Robert R. wrote:

J. Ryan S. schrieb:

this question? For example,

~ ryan ~

PS- I’m new here and I hope I’m not over overstepping the rules.

Hello.
I really enjoyed this puzzle, but my brain and my cpu are burning.

In a german ruby channel we used the example 22->999.
My really slow brute force algo came up with
122002000200212

0 - double
1 - halve
2 - add_two

It took 20-30min :smiley:

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

But thinking about a no BF solution makes my head hurt :frowning:
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

16

On 12/30/05, Christer N. [email protected] wrote:

Jim F. wrote:

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

Only positive integers are allowed.

That means you can’t divide odd numbers with two (operation halve)

Ok, I’ll change the example
(2,2) #=> [2,4,2] or [2,1,2]

17

On Dec 30, 2005, at 5:37 PM, Jim F. wrote:

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

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

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

On Dec 30, 2005, at 7:37 AM, Ruby Q. wrote:

You have a set of three operations:

double
halve (Odd numbers cannot be halved.)
add_two

Problem: Move from the starting point to the target, minimizing the
number of
operations.

The key phrase seems to be “minimizing the number of operations”. I
don’t think we can get any smaller than zero and I don’t see anything
disallowing it, so I imagine it’s fine.

Just my opinion on an obviously debatable topic.

James Edward G. II

18

On 12/30/05, Christer N.

If start equals target, zero steps are needed.

Wouldn’t that be a ‘times 1’ transformation? I don’t see that in the
list.

19

On 12/30/05, James Edward G. II

You have a set of three operations:

  double
  halve    (Odd numbers cannot be halved.)
  add_two

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

double
halve (evens only)
add_two
times_one

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

or, we use the original tranformations to get:

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

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

$0.02

20

Jim F. wrote:

we either have:

double
halve (evens only)
add_two
times_one

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

or, we use the original tranformations to get:

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

My suggestion is:

consider the original transformations having cost one. The new
operation, times_one, will have cost zero. Find the minimum cost
transforming a to b.

Hmm, this is getting interesting…

Christer