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?

Quiz Summary

The solutions this time around are fantastic. Really. I mean Ryan Leavengood is back. Enough said.

No matter which solution I select I'll be doing you a disservice, so you are all honor-bound to read through the code I don't show. Since I must choose one though, I'm going with Christian Neukirchen's solution this time around. It's a trivial 48 lines with comments and whitespace, it solves the quiz, and it even hits two of the extra credit suggestions. Beyond that, I just thought the code was pretty without even building any classes.

Let's dive in:

You can see that enumerator is pulled in here for some fancy iteration tricks we will see very soon.

The FUZZ constant is actually a control for the first extra credit point. You can set it to the number of seconds the suggested keystrokes can differ from the requested time. The default, zero, disables any number fudging.

POS holds the column and row coordinates of each button on the keypad. We will see this used in the distance calculation routine. In fact, that's the next bit of code:

This code takes a String of keystrokes and returns the total distance of all the button traveling needed to enter it. Here are some examples of usage:

The iterators are the trickiest part of this code, so let's work through them.

First, String's default iteration is by lines of the String, so map() would normally transform each line. Christian wants to work with each character though and there isn't a map_byte(). So he made one. In other words, you can think of enum_for(:each_byte).map { |b| ... } as map_byte { |b| ... }. Once you understand that, it's easy to see that each character is just translated into the coordinates for that key.

The next iterator, enum_for(:each_cons, 2), allows you group adjacent keys and iterate over the pairs. This is easier to see than explain, so here's another example:

I used simple Integers instead of the coordinate tuples the code is actually looping through, but see how they are perfectly grouped for calculating distance? That leads us to the final iterator in this chain.

The inject() iterator is just a hand-rolled sum() method. The tricky part is how the parentheses are used are used to unwrap the nested Arrays. The outer set separates the two points we are comparing, joined by each_cons(). The inner sets divide the points themselves which are then assigned to local variables. There's quite a bit of wrapping and unwrapping in there.

The actual body of all this iteration is easy stuff: it does a running sum of the euclidean distance between all of the buttons. Well, that's the uncommented version. If you switch the comments, the other line does the Manhattan distance, which covers the second extra credit point.

Now that we have a way to get the distance, we just need a way to generate the keystroke combinations. Here's that code:

This method is very straightforward. An Array is constructed, all the possible keystroke entries for the passed time are added to the Array, and the Array is returned.

There are only three possible choices for reasonable keystroke entries. The standard case is the one in the middle, a traditional minutes and seconds entry. Now for low second counts that's going to give us keystrokes like "040*" which is pointless. The first condition handles that, by adding manual entry of the seconds. This is set to work for all times below 100 seconds though, just in case "80*" turns out to be a better choice than "120*". Finally, the third option covers any case where we have at least one minute and 39 seconds or less. In those cases, we could drop the time by a minute and add that back as extra seconds. For example, "230*" can also be entered as "190*".

Now we just need a little more code to tie these two methods together. Christian choose to show all mappings between one and 999 seconds. Here's the code for that:

The upto() iterator is just the range of solutions I described. The first line inside there pulls all possible entries() for the selected time, remembering to account for fudging of the numbers. Entries are then sorted using the metric() method and a keystroke count for tie-breaking. The pattern that sorts to top is selected. Then the last line just prints the results.

My thanks to all who spend a lot more quality time with their microwave than I do. I enjoyed the discussion of edge cases and I really did learn something cool from every single solution.

Tomorrow we'll tackle a question Gavin Kistner captured off the radio for us...

1. Paul M. Lambert
2. Ryan Leavengood
3. Ken Bloom
4. Christian Neukirchen
5. Jesse Merriman
6. James Koppel
7. Gavin Stark
8. harlan
9. Dave

Download Solutions

Back to Quiz Listing