Begin forwarded message: > From: Gavin Stark <gstark / mindspring.com> > Date: April 2, 2007 2:05:46 PM CDT > To: submission / rubyquiz.com > Subject: Please Forward: Ruby Quiz Submission > > > First time posting a Ruby Quiz solution.... > > [ I'm not sure of the code formatting rules, so I apologize if this > is hard to read when posted ] > > > module Enumerable > # > # output a collection after yielding successive pairs > # such that an collection of [1,2,3,4,5,6] will yield > # [1,2] then [2,3] then [3,4] then [4,5] then [5,6] > # > # I'm no ruby Enumerable guru so there is proably a > # more correct way to do this. > # > def collect_with_successive_pairs > result = [] > for i in 0..self.length-2 > result << ( yield self[i], self[i+1] ) > end > return result > end > end > > # > # Compute cost based on number of unique keys pressed > # > class KeyCounterCost > > def initialize > @seen_keys = [] > end > > # Since we are passed successive pairs, we return > # 0 if the first member of the pair is nil or if > # we have seen this key so far, otherwise mark that > # we've seen it and return a cost of 1. > def cost( source, dest ) > return 0 if source.nil? > return 0 if @seen_keys.include?( source ) > > @seen_keys << source > return 1 > end > > end > > > > # > # Base class for cartesian distance computations > # > class CartesianKeypadDistance > protected > @@COORDINATES = { '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] } > end > > # > # Compute based on the manhattan distance which is always the > # horizontal distance plus the vertical distance between keys > # > class ManhattanDistanceCost < CartesianKeypadDistance > def cost( source, dest ) > return 0 if source.nil? || dest.nil? > > source_coord = @@COORDINATES[ source ] > dest_coord = @@COORDINATES[ dest ] > > return (dest_coord[0]-source_coord[0]).abs + (dest_coord[1]- > source_coord[1]).abs > end > > end > > # > # Compute cost based on cartesian distance between keys > # > class CartesianCost < CartesianKeypadDistance > > def cost( source, dest ) > return 0 if source.nil? || dest.nil? > > source_coord = @@COORDINATES[ source ] > dest_coord = @@COORDINATES[ dest ] > > return Math.sqrt( (dest_coord[0]-source_coord[0])**2 + > (dest_coord[1]-source_coord[1])**2 ) > end > > end > > # > # Compute cost based on cartesian distance between keys if > # each key were twice as wide as it is tall > # > class DoubleWideCartesianCost < CartesianKeypadDistance > > def cost( source, dest ) > return 0 if source.nil? || dest.nil? > > source_coord = @@COORDINATES[ source ] > dest_coord = @@COORDINATES[ dest ] > > return Math.sqrt( 2*(dest_coord[0]-source_coord[0])**2 + > (dest_coord[1]-source_coord[1])**2 ) > end > > end > > class MicrowaveKeypad > > # Compute the most efficient key press > def most_efficient_press_sequence( seconds, tollerance = 0 ) > seconds = seconds.to_i > > throw "Invalid number of seconds" if seconds > 60*60 > > # Iterate over a range of number of seconds > results_hash = Hash.new > Range.new( seconds - tollerance, seconds + tollerance ).each do > |current_seconds| > # Compute the key sequences to test > sequences_to_test = [ seconds.to_s ] + > seconds_to_minutes_and_seconds( seconds ) > > # For each sequence, compute its cost and store it in the > results. If we see the > # same sequence more than once, it should have the same total > cost so we only > # compute it once > sequences_to_test.each do |current_sequence| > next if results_hash[ current_sequence ] > results_hash[ current_sequence ] = total_cost > ( current_sequence ) > end > end > > # Sort the result hash by the total cost and return the key > (sequence) of the lowest > sorted_results = results_hash.sort_by { |sequence,total_cost| > total_cost } > sorted_results.each { |result| puts "Sequence: #{result[0]} has > a cost of #{result[1]}"} if @options[:debug] > return sorted_results.first[0].to_i > end > > private > > # Store the computing class and any options > def initialize( cost_computer_class, *args ) > @options = args.last.is_a?(Hash) ? args.pop : {} > @cost_computer_class = cost_computer_class > > end > > def total_cost( key_sequence ) > # Create a cost computer, collect all of the pair wise costs > and then sum them. > @cost_computer = @cost_computer_class.new > > # Make sure there is a "*" (cook) button at the end of each > sequence and split the sequency by character > split = ( key_sequence.to_s + "*" ).split(//) > return split.collect_with_successive_pairs { |a,b| > @cost_computer.cost( a,b ) }.inject(0) { |total,cost| total + cost } > end > > def seconds_to_minutes_and_seconds( seconds ) > representations = [] > > # If the number of seconds is than a minute we won't convert > if seconds < 60 > representations << seconds.to_s > else > minutes, remaining_seconds = seconds.divmod(60) > > # Always try the number of seconds directly as input > representations << seconds.to_s > > # Add the "mss" formatted string > representations << "#{minutes}#{remaining_seconds.to_s.rjust > (2,"0")}" > > # Use values like "272" when we encouter an input of 3 > minutes and 12 seconds. > # I doubt most people will use this format, but what the > heck... > representations << "#{minutes-1}#{(remaining_seconds > +60).to_s.rjust(2,"0")}" if ( minutes > 1 ) && ( ( 60 + > remaining_seconds ) < 100 ) > end > > return representations > end > > end > > puts MicrowaveKeypad.new(ManhattanDistanceCost, :debug => > false ).most_efficient_press_sequence( "100" ) > puts MicrowaveKeypad.new(KeyCounterCost, :debug => > true ).most_efficient_press_sequence( 3*60+12 ) >