Please Forward: Ruby Quiz Submission

ruby-talk
1

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 )

···

Begin forwarded message: