[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

[QUIZ] Numeric Maze (#60

James Gray

12/30/2005 1:38:00 PM

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.rub...

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]
110 Answers

J. Ryan Sobol

12/30/2005 8:19:00 PM

0

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 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.
>
> 2. Support Ruby Quiz by submitting ideas as often as you can:
>
> http://www.rub...
>
> 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]
>

James Gray

12/30/2005 8:37:00 PM

0

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

Christer Nilsson

12/30/2005 8:57:00 PM

0

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

--
Posted via http://www.ruby-....

James Gray

12/30/2005 9:06:00 PM

0

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

> 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.

Works for me. Let's do that.

James Edward Gray II

Christer Nilsson

12/30/2005 9:07:00 PM

0

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

--
Posted via http://www.ruby-....

J. Ryan Sobol

12/30/2005 10:18:00 PM

0

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.

James Gray

12/30/2005 10:28:00 PM

0

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

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

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

12/30/2005 11:07:00 PM

0

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


--
Posted via http://www.ruby-....

Kero van Gelder

12/30/2005 11:30:00 PM

0

>>> Are negative numbers and zero allowed to be a starting point or
>>> target? I'm assuming no, but I'd like a confirmation.
>>
>> 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.

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

12/30/2005 11:38:00 PM

0

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]


--
Jim Freeze