```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/

```