Re: [QUIZ] Micrrowave Numbers (#118)

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
> everyone on Ruby Talk follow the discussion.  Please reply to the
> 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/