# Please Forward: Ruby Quiz Submission

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
#
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
#
def cost( source, dest )
return 0 if source.nil? || dest.nil?

source_coord = @@COORDINATES[ source ]
dest_coord = @@COORDINATES[ dest ]

return (dest_coord-source_coord).abs + (dest_coord-source_coord).abs
end

end

#
# Compute cost based on cartesian distance between keys
#

def cost( source, dest )
return 0 if source.nil? || dest.nil?

source_coord = @@COORDINATES[ source ]
dest_coord = @@COORDINATES[ dest ]

return Math.sqrt( (dest_coord-source_coord)**2 + (dest_coord-source_coord)**2 )
end

end

#
# Compute cost based on cartesian distance between keys if
# each key were twice as wide as it is tall
#

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-source_coord)**2 + (dest_coord-source_coord)**2 )
end

end

# 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} has a cost of #{result}"} if @options[:debug]
return sorted_results.first.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 )

···

Begin forwarded message: