From: Ruby Quiz <james@...>
Date: 2007-04-05T21:22:28+09:00
Subject: [SUMMARY] Micrrowave Numbers (#118)

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:

	# My straight-forward solution.

	require 'enumerator'

	# How much can the time differ?
	FUZZ = 0

	POS = { ?1 => [0,0], ?2 => [1,0], ?3 => [2,0],
	        ?4 => [0,1], ?5 => [1,1], ?6 => [2,1],
	        ?7 => [0,2], ?8 => [1,2], ?9 => [2,2],
	                     ?0 => [1,3], ?* => [2,3] }

	# ...

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:

	# ...

	def metric(string)
	  string.enum_for(:each_byte).map { |b| POS[b] }.
	         enum_for(:each_cons, 2).inject(0) { |sum, ((x1,y1), (x2, y2))|
	    # 1-norm
	    # sum + (x1-x2).abs + (y1-y2).abs

	    # 2-norm
	    sum + Math.sqrt((x1-x2)**2 + (y1-y2)**2)
	  }
	end

	# ...

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:

	>> metric("9*")
	=> 1.0
	>> metric("6*")
	=> 2.0
	>> metric("313*")
	=> 7.0
	>> metric("1*")
	=> 3.60555127546399

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:

	>> [1, 2, 3].enum_for(:each_cons, 2).to_a
	=> [[1, 2], [2, 3]]

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:

	# ...
	
	def entries(time)
	  return []  if time <= 0
	
	  min, sec = time.divmod(60)
	  entries = []
	
	  # seconds only
	  entries << "%d*" % [time]                 if time < 100
	
	  # usual time format
	  entries << "%d%02d*" % [min, sec]
	
	  # more than 60 seconds
	  entries << ("%d%02d*" % [min-1, sec+60])  if min > 1 && sec < 40
	
	  entries
	end
	
	# ...

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:

	# ...
	
	1.upto(999) { |time|
	  entries = (-FUZZ..FUZZ).map { |offset| entries(time + offset) }.flatten
	  
	  # Sort by movement length, then by keypresses.
	  quickest = entries.sort_by { |s| [metric(s), s.size] }.first
	  puts "%3d (%02d:%02d): %s" % [time, time.divmod(60), quickest].flatten
	}

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