[QUIZ] Micrrowave Numbers (#118)

Discussion in 'Ruby' started by Ruby Quiz, Mar 30, 2007.

1. Ruby QuizGuest

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!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
if you can.

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

by Matthew Moss

Microwave ovens have had a significant impact on how we cook today. One report
from 1997 indicated that 90% of US households owned one. Assuming the promise of
faster cooking times, that's a lot of time saved.

But I imagine there are microwave users out there who know the trick to saving
even more time. Knowing that many microwave ovens recognize 90 seconds as the
same as 1 minute 30 seconds, finger-travel distance is saved. (Yes, it's rather
insignificant, but don't tell them... us... whatever.)

Your task is to write a function in Ruby that determines the optimal pattern of
buttons to hit based on this example button pad (where * is "Cook"):

+---+---+---+
| 1 | 2 | 3 |
+---+---+---+
| 4 | 5 | 6 |
+---+---+---+
| 7 | 8 | 9 |
+---+---+---+
| 0 | * |
+---+---+

Your function should accept an integral time value representing desired seconds
and should output an integer that indicates the buttons to press on the
microwave's input pad. The metric for determining what input is more efficient
is distance (not number of buttons hit). Distance to the Cook button must be
included in your efficiency calculation. For simplicity in distance
calculations, you may consider the shape of each button to be square.

Examples:

# 99 seconds is 1:39, but 99 is less movement than 139
microwave(99) => 99

# 71 seconds is only two keys, but entering 111 is far less movement.
microwave(71) => 111

# 120 seconds is 2 minutes, and 200 is slightly less movement than 120
microwave(120) => 200

# 123 seconds is 2:03, but 203 is a lot more distance
microwave(123) => 123

Once you've done the basic version, try modifying your code enough to handle
these:

1. We often don't care to be exact. 99 seconds, for example, is basically the
same as 95 seconds, but more efficient to enter. Modify your function to accept
a tolerance in seconds, and return answers that are within that tolerance of the
desired time. Try +-5 and +-10 seconds.

2. Try changing the efficiency metric, to something like number of buttons
pressed, or Manhattan distance.

3. Try changing the button dimensions... For example, what happens if each
button is twice as wide as it is high?

Ruby Quiz, Mar 30, 2007

2. Karl von LaudermannGuest

Re: Micrrowave Numbers (#118)

On Mar 30, 7:55 am, Ruby Quiz <> wrote:

> # 99 seconds is 1:39, but 99 is less movement than 139
> microwave(99) => 99
>
> # 71 seconds is only two keys, but entering 111 is far less movement.
> microwave(71) => 111
>
> # 120 seconds is 2 minutes, and 200 is slightly less movement than 120
> microwave(120) => 200
>
> # 123 seconds is 2:03, but 203 is a lot more distance
> microwave(123) => 123

Unless I'm missing something (and I usually am), the problem with the
last two examples is that the microwave will interpret "120" and "123"
as 1:20 and 1:23 when typed in, not as a raw number of seconds. How
the microwave interprets the number depends solely on whether the last
two digits exceed 59. If they do, it's a number of seconds, otherwise
it's minutes and seconds.

Maybe there should be an additional requirement of the quiz: the
program will never suggest the number of seconds representation, even
when that's more efficient than the minutes and seconds
representation, if the the number of seconds representation will be
misinterpreted (i.e. the last two digits are 60 or greater).

Actually, I'm not even convinced that a microwave would interpret e.g.
"170" as 170 seconds, or 2:50. Perhaps 170 would be interpreted as one
minute and 70 seconds? In other words, after counting down for 70
seconds, the display would read "1:00", and then proceed to 59 instead
of 99, not remembering the 70 that it started with.

Karl von Laudermann, Mar 30, 2007

3. Karl von LaudermannGuest

Re: Micrrowave Numbers (#118)

On Mar 30, 10:08 am, "Karl von Laudermann" <>
wrote:

> misinterpreted (i.e. the last two digits are 60 or greater).

Clearly, I meant "the last two digits *aren't* 60 or greater".

Karl von Laudermann, Mar 30, 2007
4. James Edward Gray IIGuest

Re: Micrrowave Numbers (#118)

On Mar 30, 2007, at 9:10 AM, Karl von Laudermann wrote:

> Actually, I'm not even convinced that a microwave would interpret e.g.
> "170" as 170 seconds, or 2:50. Perhaps 170 would be interpreted as one
> minute and 70 seconds? In other words, after counting down for 70
> seconds, the display would read "1:00", and then proceed to 59 instead
> of 99, not remembering the 70 that it started with.

Yes, I just tested mine and this is how it behaved (1 minute and 70
seconds).

James Edward Gray II

James Edward Gray II, Mar 30, 2007
5. Matthew MossGuest

On 3/30/07, Brown, Warren <> wrote:
> James,
>
> > # 120 seconds is 2 minutes, and 200 is slightly less
> > movement than 120
> > microwave(120) => 200
> >
> > # 123 seconds is 2:03, but 203 is a lot more distance
> > microwave(123) => 123

>
> How is the microwave supposed to know that "120" is 120 seconds but
> "200" is two minutes? My experience is that microwaves will interpret
> two-digit numbers as seconds and three-digit numbers as minutes and
> seconds. Therefore, "99" is 99 seconds, but "120" is one minute, twenty
> seconds. Am I missing something?

I think the confusion is that I specified input and output to both be
integers, but they don't really mean the same thing.

Input is always seconds... two minutes is "120", five minutes is
"600". Input is NOT the keys you would press.

Output is always the keys to press... It would have been clearer,
perhaps, if I requested the output as an array such as [1, 2, 0,
:cook], or even a string like "120*". When I proposed the problem, I
realized that the "*" (cook) button is always part of the output, so I
could have the function return an integer and the "*" would be
implicit. But this, I think, confused things.

So 120 (or "120*") as output means to push, in order, the buttons 1,
2, 0 and *. Which, for a microwave means 1:20, or 80 seconds.

Does this clear things up?

Matthew Moss, Mar 30, 2007
6. Matthew MossGuest

On 3/30/07, Brown, Warren <> wrote:
> James,
>
> > # 120 seconds is 2 minutes, and 200 is slightly less
> > movement than 120
> > microwave(120) => 200
> >
> > # 123 seconds is 2:03, but 203 is a lot more distance
> > microwave(123) => 123

>
> How is the microwave supposed to know that "120" is 120 seconds but
> "200" is two minutes? My experience is that microwaves will interpret
> two-digit numbers as seconds and three-digit numbers as minutes and
> seconds. Therefore, "99" is 99 seconds, but "120" is one minute, twenty
> seconds. Am I missing something?

The input is always "desired seconds", so 200 as input means 3 mins,
20 secs, and 120 as input means 2 mins.

The output is always "buttons to press", so 200 as output always means
2:00, and 120 _as output_ means 1:20.

And the convention for this quiz (not well specified, sorry) is that
if the buttons I press on the microwave are 170, the microwave will
treat that as 1:70... it will first countdown 70 seconds to 1:00,
then 0:59, 0:58... etc.

Matthew Moss, Mar 30, 2007
7. Hans FugalGuest

My microwave will win in every case. It has a dial timer.

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.rubyquiz.com/
>
> 3. Enjoy!
>
> Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
> if you can.
>
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
>
> by Matthew Moss
>
> Microwave ovens have had a significant impact on how we cook today. One report
> from 1997 indicated that 90% of US households owned one. Assuming the promise of
> faster cooking times, that's a lot of time saved.
>
> But I imagine there are microwave users out there who know the trick to saving
> even more time. Knowing that many microwave ovens recognize 90 seconds as the
> same as 1 minute 30 seconds, finger-travel distance is saved. (Yes, it's rather
> insignificant, but don't tell them... us... whatever.)
>
> Your task is to write a function in Ruby that determines the optimal pattern of
> buttons to hit based on this example button pad (where * is "Cook"):
>
> +---+---+---+
> | 1 | 2 | 3 |
> +---+---+---+
> | 4 | 5 | 6 |
> +---+---+---+
> | 7 | 8 | 9 |
> +---+---+---+
> | 0 | * |
> +---+---+
>
> Your function should accept an integral time value representing desired seconds
> and should output an integer that indicates the buttons to press on the
> microwave's input pad. The metric for determining what input is more efficient
> is distance (not number of buttons hit). Distance to the Cook button must be
> included in your efficiency calculation. For simplicity in distance
> calculations, you may consider the shape of each button to be square.
>
> Examples:
>
> # 99 seconds is 1:39, but 99 is less movement than 139
> microwave(99) => 99
>
> # 71 seconds is only two keys, but entering 111 is far less movement.
> microwave(71) => 111
>
> # 120 seconds is 2 minutes, and 200 is slightly less movement than 120
> microwave(120) => 200
>
> # 123 seconds is 2:03, but 203 is a lot more distance
> microwave(123) => 123
>
> Once you've done the basic version, try modifying your code enough to handle
> these:
>
> 1. We often don't care to be exact. 99 seconds, for example, is basically the
> same as 95 seconds, but more efficient to enter. Modify your function to accept
> a tolerance in seconds, and return answers that are within that tolerance of the
> desired time. Try +-5 and +-10 seconds.
>
> 2. Try changing the efficiency metric, to something like number of buttons
> pressed, or Manhattan distance.
>
> 3. Try changing the button dimensions... For example, what happens if each
> button is twice as wide as it is high?
>

Hans Fugal, Mar 30, 2007
8. Ken BloomGuest

On Fri, 30 Mar 2007 20:55:46 +0900, 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.rubyquiz.com/
>
> 3. Enjoy!
>
> Suggestion: A [QUIZ] in the subject of emails about the problem helps
> original quiz message, if you can.
>
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

=-=-=-=-=
>
> by Matthew Moss
>
> Microwave ovens have had a significant impact on how we cook today. One
> report from 1997 indicated that 90% of US households owned one. Assuming
> the promise of faster cooking times, that's a lot of time saved.
>
> But I imagine there are microwave users out there who know the trick to
> saving even more time. Knowing that many microwave ovens recognize 90
> seconds as the same as 1 minute 30 seconds, finger-travel distance is
> saved. (Yes, it's rather insignificant, but don't tell them... us...
> whatever.)
>
> Your task is to write a function in Ruby that determines the optimal
> pattern of buttons to hit based on this example button pad (where * is
> "Cook"):
>
> +---+---+---+
> | 1 | 2 | 3 |
> +---+---+---+
> | 4 | 5 | 6 |
> +---+---+---+
> | 7 | 8 | 9 |
> +---+---+---+
> | 0 | * |
> +---+---+
>
> Your function should accept an integral time value representing desired
> seconds and should output an integer that indicates the buttons to press
> on the microwave's input pad. The metric for determining what input is
> more efficient is distance (not number of buttons hit). Distance to the
> Cook button must be included in your efficiency calculation. For
> simplicity in distance calculations, you may consider the shape of each
> button to be square.
>
> Examples:
>
> # 99 seconds is 1:39, but 99 is less movement than 139 microwave

(99) =>
> 99
>
> # 71 seconds is only two keys, but entering 111 is far less

movement.
> microwave(71) => 111
>
> # 120 seconds is 2 minutes, and 200 is slightly less movement

than 120
> microwave(120) => 200
>
> # 123 seconds is 2:03, but 203 is a lot more distance microwave

(123) =>
> 123
>
> Once you've done the basic version, try modifying your code enough to
> handle these:
>
> 1. We often don't care to be exact. 99 seconds, for example, is
> basically the same as 95 seconds, but more efficient to enter. Modify
> your function to accept a tolerance in seconds, and return answers that
> are within that tolerance of the desired time. Try +-5 and +-10 seconds.
>
> 2. Try changing the efficiency metric, to something like number of
> buttons pressed, or Manhattan distance.
>
> 3. Try changing the button dimensions... For example, what happens if
> each button is twice as wide as it is high?

Someone want to verify my answers?

For euclidian distance:
0 (0:00): 0*
1 (0:01): 1*
2 (0:02): 2*
3 (0:03): 3*
4 (0:04): 4*
5 (0:05): 5*
6 (0:06): 6*
7 (0:07): 7*
8 (0:08): 8*
9 (0:09): 9*
10 (0:10): 10*
11 (0:11): 11*
12 (0:12): 12*
13 (0:13): 13*
14 (0:14): 14*
15 (0:15): 15*
16 (0:16): 16*
17 (0:17): 17*
18 (0:18): 18*
19 (0:19): 19*
20 (0:20): 20*
21 (0:21): 21*
22 (0:22): 22*
23 (0:23): 23*
24 (0:24): 24*
25 (0:25): 25*
26 (0:26): 26*
27 (0:27): 27*
28 (0:28): 28*
29 (0:29): 29*
30 (0:30): 30*
31 (0:31): 31*
32 (0:32): 32*
33 (0:33): 33*
34 (0:34): 34*
35 (0:35): 35*
36 (0:36): 36*
37 (0:37): 37*
38 (0:38): 38*
39 (0:39): 39*
40 (0:40): 40*
41 (0:41): 41*
42 (0:42): 42*
43 (0:43): 43*
44 (0:44): 44*
45 (0:45): 45*
46 (0:46): 46*
47 (0:47): 47*
48 (0:48): 48*
49 (0:49): 49*
50 (0:50): 50*
51 (0:51): 51*
52 (0:52): 52*
53 (0:53): 53*
54 (0:54): 54*
55 (0:55): 55*
56 (0:56): 56*
57 (0:57): 57*
58 (0:58): 58*
59 (0:59): 59*
60 (1:00): 60*
61 (1:01): 61*
62 (1:02): 62*
63 (1:03): 63*
64 (1:04): 64*
65 (1:05): 65*
66 (1:06): 66*
67 (1:07): 67*
68 (1:08): 68*
69 (1:09): 69*
70 (1:10): 70*
71 (1:11): 111*
72 (1:12): 112*
73 (1:13): 113*
74 (1:14): 114*
75 (1:15): 115*
76 (1:16): 116*
77 (1:17): 77*
78 (1:18): 78*
79 (1:19): 79*
80 (1:20): 80*
81 (1:21): 121*
82 (1:22): 122*
83 (1:23): 123*
84 (1:24): 84*
85 (1:25): 85*
86 (1:26): 86*
87 (1:27): 87*
88 (1:28): 88*
89 (1:29): 89*
90 (1:30): 90*
91 (1:31): 91*
92 (1:32): 92*
93 (1:33): 133*
94 (1:34): 94*
95 (1:35): 95*
96 (1:36): 96*
97 (1:37): 97*
98 (1:38): 98*
99 (1:39): 99*

For Manhattan Distance:
0 (0:00): 0*
1 (0:01): 1*
2 (0:02): 2*
3 (0:03): 3*
4 (0:04): 4*
5 (0:05): 5*
6 (0:06): 6*
7 (0:07): 7*
8 (0:08): 8*
9 (0:09): 9*
10 (0:10): 10*
11 (0:11): 11*
12 (0:12): 12*
13 (0:13): 13*
14 (0:14): 14*
15 (0:15): 15*
16 (0:16): 16*
17 (0:17): 17*
18 (0:18): 18*
19 (0:19): 19*
20 (0:20): 20*
21 (0:21): 21*
22 (0:22): 22*
23 (0:23): 23*
24 (0:24): 24*
25 (0:25): 25*
26 (0:26): 26*
27 (0:27): 27*
28 (0:28): 28*
29 (0:29): 29*
30 (0:30): 30*
31 (0:31): 31*
32 (0:32): 32*
33 (0:33): 33*
34 (0:34): 34*
35 (0:35): 35*
36 (0:36): 36*
37 (0:37): 37*
38 (0:38): 38*
39 (0:39): 39*
40 (0:40): 40*
41 (0:41): 41*
42 (0:42): 42*
43 (0:43): 43*
44 (0:44): 44*
45 (0:45): 45*
46 (0:46): 46*
47 (0:47): 47*
48 (0:48): 48*
49 (0:49): 49*
50 (0:50): 50*
51 (0:51): 51*
52 (0:52): 52*
53 (0:53): 53*
54 (0:54): 54*
55 (0:55): 55*
56 (0:56): 56*
57 (0:57): 57*
58 (0:58): 58*
59 (0:59): 59*
60 (1:00): 60*
61 (1:01): 61*
62 (1:02): 62*
63 (1:03): 63*
64 (1:04): 64*
65 (1:05): 65*
66 (1:06): 66*
67 (1:07): 67*
68 (1:08): 68*
69 (1:09): 69*
70 (1:10): 70*
71 (1:11): 111*
72 (1:12): 112*
73 (1:13): 113*
74 (1:14): 114*
75 (1:15): 115*
76 (1:16): 116*
77 (1:17): 77*
78 (1:18): 78*
79 (1:19): 79*
80 (1:20): 80*
81 (1:21): 121*
82 (1:22): 122*
83 (1:23): 123*
84 (1:24): 84*
85 (1:25): 85*
86 (1:26): 86*
87 (1:27): 87*
88 (1:28): 88*
89 (1:29): 89*
90 (1:30): 90*
91 (1:31): 131*
92 (1:32): 132*
93 (1:33): 133*
94 (1:34): 94*
95 (1:35): 95*
96 (1:36): 96*
97 (1:37): 97*
98 (1:38): 98*
99 (1:39): 99*

--
Ken Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/

Ken Bloom, Mar 30, 2007
9. Josef 'Jupp' SchugtGuest

--------------enig97B57A0F9012E2DABA691387
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

* Hans Fugal, 30.03.2007 17:50:
> My microwave will win in every case. It has a dial timer.

If it wins or not is not decided. Mine has a dial timer as well. As a
shootout we would have to compare degrees per minute

Besides: I wonder why microwave ovens don't simply have an up and a
dow button (like those present on most mobile phones) to
increment/decrement the time setting(s).

A dial timer is quite imprecise (especially for short time intervals)
for mechanical reasons while a numerical pad is unnecessarily
complicated meaning that it has many parts that may fail. They won't
fail? Hmm, perhaps you compare it to your PC keyboard, but: In most
households the s/p probability density peaks near the microwave, and
not near the keyboard.

s/p: softdrink/pizza

Josef 'Jupp' Schugt, eagerly awaiting tomorrow's RFC
--=20
Blog available at http://www.mynetcologne.de/~nc-schugtjo/blog/
PGP key with id 6CC6574F available at http://wwwkeys.de.pgp.net/

--------------enig97B57A0F9012E2DABA691387
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: OpenPGP digital signature
Content-Disposition: attachment; filename="signature.asc"

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.7 (GNU/Linux)

iD8DBQFGDbdgrhv7B2zGV08RAv5cAKCFCUVbYpUjd0Kv2/JFzsudf5EsvwCfSVM7
Lh9YfMLcKW2mYY1AKVsXbEk=
=gFjD
-----END PGP SIGNATURE-----

--------------enig97B57A0F9012E2DABA691387--

Josef 'Jupp' Schugt, Mar 31, 2007
10. Bill KellyGuest

From: "Josef 'Jupp' Schugt" <>
>
> Besides: I wonder why microwave ovens don't simply have an up and a
> dow button (like those present on most mobile phones) to
> increment/decrement the time setting(s).

Ours does. It has an "add a minute" button, but also +/- 10 seconds
buttons. (They can be used before or after pressing the "Start"
button.)

Semi-interestingly, the "add a minute" button includes an implicit
"Start" button press.

So I almost invariably choose "add a minute; add a minute" over
"2 0 0 <start>".

LOL

Regards,

Bill

Bill Kelly, Mar 31, 2007
11. Rick DeNataleGuest

On 3/30/07, Josef 'Jupp' Schugt <> wrote:
> * Hans Fugal, 30.03.2007 17:50:
> > My microwave will win in every case. It has a dial timer.

>
> If it wins or not is not decided. Mine has a dial timer as well. As a
> shootout we would have to compare degrees per minute
>
> Besides: I wonder why microwave ovens don't simply have an up and a
> dow button (like those present on most mobile phones) to
> increment/decrement the time setting(s).
>
> A dial timer is quite imprecise (especially for short time intervals)
> for mechanical reasons while a numerical pad is unnecessarily
> complicated meaning that it has many parts that may fail. They won't
> fail? Hmm, perhaps you compare it to your PC keyboard, but: In most
> households the s/p probability density peaks near the microwave, and
> not near the keyboard.

Well our MW has a digital timer with a dial input. The dial works
like the dreaded BMW iDrive control, you can turn it AND push it.

To set the timer you hit the timer or cook time button, then twist the
dial to set the minutes which show up on the digital display. You
then push the dial in which shifts it to setting the seconds, a second
push on the dial completes the process.

And no, you can't enter seconds greater than 59 with this setup.

--
Rick DeNatale

My blog on Ruby

Rick DeNatale, Mar 31, 2007
12. Robert DoberGuest

On 3/31/07, Rick DeNatale <> wrote:
> On 3/30/07, Josef 'Jupp' Schugt <> wrote:
> > * Hans Fugal, 30.03.2007 17:50:
> > > My microwave will win in every case. It has a dial timer.

> >
> > If it wins or not is not decided. Mine has a dial timer as well. As a
> > shootout we would have to compare degrees per minute
> >
> > Besides: I wonder why microwave ovens don't simply have an up and a
> > dow button (like those present on most mobile phones) to
> > increment/decrement the time setting(s).
> >
> > A dial timer is quite imprecise (especially for short time intervals)
> > for mechanical reasons while a numerical pad is unnecessarily
> > complicated meaning that it has many parts that may fail. They won't
> > fail? Hmm, perhaps you compare it to your PC keyboard, but: In most
> > households the s/p probability density peaks near the microwave, and
> > not near the keyboard.

>
> Well our MW has a digital timer with a dial input. The dial works
> like the dreaded BMW iDrive control, you can turn it AND push it.
>
> To set the timer you hit the timer or cook time button, then twist the
> dial to set the minutes which show up on the digital display. You
> then push the dial in which shifts it to setting the seconds, a second
> push on the dial completes the process.
>
> And no, you can't enter seconds greater than 59 with this setup.
>
>
> --
> Rick DeNatale
>
> My blog on Ruby
>
>

Wait I second guys my MW has a Ruby interpreter [1.6 though, Matz
did you abandon the Microwave edition?]

Robert

--
You see things; and you say Why?
But I dream things that never were; and I say Why not?
-- George Bernard Shaw

Robert Dober, Mar 31, 2007
13. Ken BloomGuest

On Sat, 31 Mar 2007 19:38:03 +0900, Christian Neukirchen wrote:

> Ken Bloom <> writes:
>
>> 74 (1:14): 114*
>> 75 (1:15): 115*
>> 76 (1:16): 116*

>
> I think 74* is faster, because it's one keypress less?

The quiz only discussed distance moved, not keys pressed (in the main
solution). This appears to be a tie for distance, so my program just
picked one. I suppose it's not too hard to add a tiebreaker metric though.

--Ken

--
Ken Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/

Ken Bloom, Apr 1, 2007
14. Ken BloomGuest

On Fri, 30 Mar 2007 20:55:46 +0900, 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.rubyquiz.com/
>
> 3. Enjoy!
>
> Suggestion: A [QUIZ] in the subject of emails about the problem helps
> original quiz message, if you can.
>
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

=-=-=-=-=
>
> by Matthew Moss
>
> Microwave ovens have had a significant impact on how we cook today. One
> report from 1997 indicated that 90% of US households owned one. Assuming
> the promise of faster cooking times, that's a lot of time saved.
>
> But I imagine there are microwave users out there who know the trick to
> saving even more time. Knowing that many microwave ovens recognize 90
> seconds as the same as 1 minute 30 seconds, finger-travel distance is
> saved. (Yes, it's rather insignificant, but don't tell them... us...
> whatever.)
>
> Your task is to write a function in Ruby that determines the optimal
> pattern of buttons to hit based on this example button pad (where * is
> "Cook"):
>
> +---+---+---+
> | 1 | 2 | 3 |
> +---+---+---+
> | 4 | 5 | 6 |
> +---+---+---+
> | 7 | 8 | 9 |
> +---+---+---+
> | 0 | * |
> +---+---+
>
> Your function should accept an integral time value representing desired
> seconds and should output an integer that indicates the buttons to press
> on the microwave's input pad. The metric for determining what input is
> more efficient is distance (not number of buttons hit). Distance to the
> Cook button must be included in your efficiency calculation. For
> simplicity in distance calculations, you may consider the shape of each
> button to be square.
>
> Examples:
>
> # 99 seconds is 1:39, but 99 is less movement than 139 microwave

(99) =>
> 99
>
> # 71 seconds is only two keys, but entering 111 is far less

movement.
> microwave(71) => 111
>
> # 120 seconds is 2 minutes, and 200 is slightly less movement

than 120
> microwave(120) => 200
>
> # 123 seconds is 2:03, but 203 is a lot more distance microwave

(123) =>
> 123
>
> Once you've done the basic version, try modifying your code enough to
> handle these:
>
> 1. We often don't care to be exact. 99 seconds, for example, is
> basically the same as 95 seconds, but more efficient to enter. Modify
> your function to accept a tolerance in seconds, and return answers that
> are within that tolerance of the desired time. Try +-5 and +-10 seconds.
>
> 2. Try changing the efficiency metric, to something like number of
> buttons pressed, or Manhattan distance.
>
> 3. Try changing the button dimensions... For example, what happens if
> each button is twice as wide as it is high?

require 'matrix'
require 'enumerator'
class Matrix
# returns the row and column of the value requested, or nil if not
# found
def find value
row_vectors.each_with_index do |row,rownum|
row=row.to_a
row.each_with_index do |col,colnum|
return rownum,colnum if col==value
end
end
end
end

#these functions are the distance metrics

def euclidian_distance array1, array2
Math.sqrt(array1.zip(array2).inject(0){|a,(v1,v2)| a+(v2-v1)**2})
end
def manhattan_distance array1, array2
array1.zip(array2).inject(0){|a,(v1,v2)| a+(v2-v1).abs}
end
def num_buttons array1, array2
1
end
def rand_metric array1, array2
rand
end

#make it easy to try out different distance metrics by changing these
#aliases
alias distance_metric euclidian_distance
alias tiebreaker_metric num_buttons

# now we compute acutal Primary for all pairs
# if we wanted, we could write a function that computes this every
# time rather than memoizing it in a hash
Positions=Matrix[['1','2','3'],['4','5','6'],['7','8','9'],['-','0','*']]
Primary={}
Tiebreaker={}

('0'..'9').each do |from|
('0'..'9').each do |to|
Primary[[from,to]]=distance_metric(
Positions.find(from),
Positions.find(to))
Tiebreaker[[from,to]]=tiebreaker_metric(
Positions.find(from),
Positions.find(to))
end
Primary[[from,'*']]=distance_metric(
Positions.find(from),
Positions.find('*'))
Tiebreaker[[from,'*']]=tiebreaker_metric(
Positions.find(from),
Positions.find('*'))
end

# computes the distance and the string used for a specific (possibly
# improper) number of minutes and seconds to be entered into the
# microwave
def make_array min,sec
("%d%02d*" % [min,sec]).gsub(/^0+([^*])/,'\1').split(//)
end

def compute_dist array,distances
array.enum_cons(2).inject(0){|a,v| a+distances[v]}
end

# given the number of seconds to run the microwave for, this function
# returns the shortest path of buttons that one can press to make the
# microwave run for that period of time
#
# if both possibilites have the same total distance, then the function
# just picks one in some undefined way
def compute_best_distance sec
min_improper,sec_improper=(min_proper,sec_proper=sec.divmod(60))
if min_improper>0 and sec_improper<40
min_improper-=1
sec_improper+=60
else
#the improper time will be the same as the proper time, which
#isn't a problem
end
proper=make_array(min_proper,sec_proper)
improper=make_array(min_improper,sec_improper)
[[
compute_dist(proper,Primary),
compute_dist(proper,Tiebreaker),
proper
],[
compute_dist(improper,Primary),
compute_dist(improper,Tiebreaker),
improper
]].sort[0][-1].join
end

#print a the values for runs up to 5 minutes long
(0..300).each do |x|
printf "%d (%s): %s\n", x, "%d:%02d" % x.divmod(60),
compute_best_distance(x)
end

--
Ken Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/

Ken Bloom, Apr 1, 2007
15. Jesse MerrimanGuest

[QUIZ][SOLUTION] Microwave Numbers (#118)

Here's my solution. It got longer and messier than I wanted, but I tried to=
be
fairly general. Here's the basic structure:

Button: A struct of a label, an x-coord, and a y-coord

ButtonSequence: An array of Buttons.

Pad: A hash of String labels ('0' thru '9' & '*') to Buttons

metrics: Not a class of their own, just a Proc taking a ButtonSequence and
returning a numeric score (lower is better)

MetricStack: An array of metrics to be tried in order when there's a tie.

alternator: Not a class, just Procs taking a seconds value and returing an
Enumerable of alternate, equivalent seconds values to try (used
for tolerance).

Then there is the main microwave() function that takes a seconds value, a P=
an alternator, and a MetricStack [and a list() function to run microwave() =
on
a bunch of values). These are spread among the 4 files below. Here's some
examples of how it can be used:

# Use default pad, the Exact alternator which returns just [76], and the
# EuclideanMetric for a distance metric.
# to_s is called because a ButtonSequence is returned.
microwave(76).to_s
=3D> "76*"

# Use a pad with buttons twice as wide.
=3D> "76*"

# Allow a tolerance of up to 5 seconds.
=3D> "80*"

# First, try to minimize Euclidean distance. If there's a tie, try to minim=
ize
# the total number of buttons pressed. If there's still a tie, try to minim=
ize
# the number of unique buttons pressed.
ms =3D MetricStack.new([EuclideanMetric, LowButtonMetric, MinButtonMetric])
=3D> "111*"

And now here's the code:

# -------------------------------------------------------------------------=
=2D--
# Ruby Quiz 118: Microwave Numbers

Button =3D Struct.newlabel, :x, :y)

# Holds Buttons. I thought about making this a Comparable, or of making
# subclasses of this for different orderings, but didn't.
class ButtonSequence < Array
def to_s
self.map{ |b| b.label }.join
end
end

# Maps button labels (Strings) to Buttons.
# Return an Array containing all ways of entering the given number of
# seconds into the microwave. Each entry will be a pair of minutes &
# seconds.
ent =3D []
minutes =3D seconds / 60
(0..minutes).each do |min|
sec =3D seconds - 60*min
ent << [min, sec] if sec < 100
end
ent
end

# Return a String of keys to press on the microwave to enter the given
# number of minutes and seconds. sec must be < 100.
raise 'sec is too large' if sec >=3D 100
str =3D ''
str << min.to_s if min > 0
str << '0' if sec < 10 and min > 0
str << sec.to_s
str << '*'
str
end

# For the given number of seconds, yield each possible button sequence as=
an
# ButtonSequence.
def each_button_sequence(seconds)
bs =3D ButtonSequence.new(press_str.split(//).map { |char| self[char]=
})
yield(bs)
end
end

# Generate a pad like this:
# x
# 0 1 2
#=C2=A0 +---+---+---+
#=C2=A0 0 | 1 | 2 | 3 |
#=C2=A0 +---+---+---+
#=C2=A0 1 | 4 | 5 | 6 |
# y +---+---+---+
#=C2=A0 2 | 7 | 8 | 9 |
#=C2=A0 +---+---+---+
#=C2=A0 3 =C2=A0 =C2=A0| 0 | * |
#=C2=A0 =C2=A0 =C2=A0+---+---+
end

# Generate a pad like the normal one, but stretched either horizontally,
# vertially, or both. x_factor and y_factor must be integers. For example,
# than they are tall.
(1..9).each do |n|
pad[n.to_s] =3D Button.new(n.to_s, x_factor*((n-1) % 3),
y_factor*((n-1) / 3))
end
pad.merge!( { '0' =3D> Button.new('0', x_factor, 3*y_factor),
'*' =3D> Button.new('*', 2*x_factor, 3*y_factor) } )
end
end

# -------------------------------------------------------------------------=
=2D--
# metrics.rb
# Ruby Quiz 118: Microwave Numbers

# To decide which button sequences are better than others, a metric is used=
=2E I
# didn't bother creating a Metric class, so they're just a Proc that takes a
# ButtonSequence as an argument and returns a numeric score (lower is always
# better). To settle ties, a MetricStack is used, which is an Array of metr=
ics
# that are tried in order until the tie is broken (if its ever broken).

require 'set'

class Array
# Yield all Arrays containing two adjacent elements.
(1...self.size).each do |i|
yield([self[i-1], self])
end
end

# Return the number of unique elements.
def num_uniq
Set[*self].size
end
end

# Create a Proc returns the n-norm of two Buttons.
def create_norm_distancer(n)
lambda do |b1, b2|
((b1.x - b2.x).abs**n + (b1.y - b2.y).abs**n) ** (1.0/n)
end
end

ManhattanDistance =3D create_norm_distancer(1)
EuclideanDistance =3D create_norm_distancer(2)

# Create a distance-measuring metric from the given distance measurer.
def create_distance_metric(dist_measurer)
lambda do |button_sequence|
dist =3D 0
dist +=3D dist_measurer[button_pair.first, button_pair.last]
end
dist
end
end

ManhattanMetric =3D create_distance_metric(ManhattanDistance)
EuclideanMetric =3D create_distance_metric(EuclideanDistance)

# A metric that minimizes the total number of buttons pressed.
MinButtonMetric =3D lambda do |button_sequence|
button_sequence.size
end

# A metric that minimizes the number of unique buttons pressed.
LowButtonMetric =3D lambda do |button_sequence|
button_sequence.num_uniq
end

# A MetricStack is an Array of metrics that compare ButtonSequences. Earlier
# metrics take precedence over later metrics.
class MetricStack < Array
# Return true if button_seq_1 is better than button_seq_2.
def better?(button_seq_1, button_seq_2)
return true if not button_seq_1.nil? and button_seq_2.nil?
better =3D nil
self.each do |metric|
s1, s2 =3D metric[button_seq_1], metric[button_seq_2]
s1 < s2 ? better =3D true : s2 < s1 ? better =3D false : nil
break if not better.nil?
end
better.nil? ? false : better
end
end

# -------------------------------------------------------------------------=
=2D--
# alternators.rb
# Ruby Quiz 118: Microwave Numbers

# For "something that produces alternate seconds values" I'm using the word
# "alternator" - it can be any Proc that takes as an argument the number of
# seconds, and returns an Enumerable of "close enough" seconds to try.

require 'set'

Exact =3D lambda { |seconds| [seconds] }

# Produce an alternator that will return all seconds within the given=20
tolerance
# from the target number of seconds (eg, Tolerance[2][10] will return=20
(8..12)).
Tolerance =3D lambda do |tolerance|
lambda do |seconds|
([seconds - tolerance, 0].max..seconds + tolerance)
# Any way to pass a block to a Proc?
#([seconds - tolerance, 0].max..seconds + tolerance).each do |sec|
# yield(sec)
#end
end
end

# Produce a few values close by. This isn't really useful, just an example =
of
# another alternator.
RandomClose =3D lambda do |seconds|
s =3D Set[seconds]
(rand(10)+1).times { s << [seconds + rand(21) - 10, 0].max }
s
end

# -------------------------------------------------------------------------=
=2D--
# microwave.rb
# Ruby Quiz 118: Microwave Numbers

require 'metrics'
require 'alternators'

# alternator is a Proc that takes the number of seconds and produces an
# Enumerable of equivalent values.
#
# metrics can be:
# - a MetricStack
# - a single metric Proc
# - an Array of metric Procs
alternator =3D Exact, metrics =3D EuclideanMetric)
case metrics
when Proc; metrics =3D MetricStack.new([metrics])
when Array; metrics =3D MetricStack.new(metrics)
end
best =3D nil
alternator[seconds].each do |sec|
best =3D bs if metrics.better?(bs, best)
end
end
best
end

# Print out the best button sequences for all seconds in the given Enumerab=
le.
# Other arguments are passed into microwave(). The thing that sucks about
# this is that if there's a tolerance of > 0, identical sequences will be
# scored more than once. Maybe memo-ize that or something..
alternator =3D Exact, metrics =3D EuclideanMetric)
puts "Seconds Buttons"
puts "------- -------"
enum.each do |i|
best =3D microwave(i, pad, alternator, metrics)
puts "#{i} #{best}"
end
end
# -------------------------------------------------------------------------=
=2D--

=2D-=20
Jesse Merriman

http://www.jessemerriman.com/

Jesse Merriman, Apr 2, 2007
16. Sharon PhillipsGuest

Hi,

Here's my solution, finally.
Takes wanted time as argument 0 and variation as argument 1

Any suggestion on improving this welcome.

Cheers,
Dave

------------------------
KEY_WIDTH= 10
KEY_HEIGHT= 10

def get_pos (key)
case key.to_s
when '1'..'9': row, col= (key-1)/3, (key-1)%3
when '0': row, col= 3,0
when '*': row, col= 3,1
end
return row, col
end

def calc_dist (from_key, to_key)
from_row, from_col= get_pos(from_key)
to_row, to_col= get_pos(to_key)
Math.sqrt((KEY_HEIGHT* (to_row- from_row))**2 +
(KEY_WIDTH* (to_col- from_col))**2)
end

def total_dist (keys)
return 0 if keys.size==0
dist= 0
keys.each_with_index do |key, i|
dist+= calc_dist(keys[i-1], key) if i>0
end
dist
end

def mins_secs_to_keys(mins, secs)
keys= []
keys<< mins unless mins.zero?
keys<< secs/ 10 unless mins.zero? and (secs/ 10).zero?
keys<< secs% 10
keys<< '*'
keys
end

def time_to_candidates(seconds_wanted)
mins= seconds_wanted/ 60
secs= seconds_wanted% 60
candidates= []
candidates<< mins_secs_to_keys(mins, secs)
candidates<< mins_secs_to_keys(mins- 1, secs+ 60) if mins.nonzero?
and secs<40
candidates
end

seconds= ARGV[0].to_i || 60
variation= ARGV[1].to_i || 0

combos=[]
(seconds- variation).upto(seconds+ variation) do |time|
combos+= (time_to_candidates(time).map do|keys|
{:keys => keys, :dist => total_dist(keys)}
end)
end

print "Best keypad combination for #{seconds}+/-#{variation} seconds
is "
puts combos.sort{|a, b| a[:dist] <=> b[:dist]}.first[:keys].join(" ")

Sharon Phillips, Apr 6, 2007