Forum: Ruby Solution: Microwave Numbers (#118)

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
4b174722d1b1a4bbd9672e1ab50c30a9?d=identicon&s=25 Ryan Leavengood (Guest)
on 2007-04-01 17:33
(Received via mailing list)
Well much like my recent return to posting on the O'Reilly Ruby blog,
I couldn't resist getting back into the Ruby Quiz fray. I'm pretty
pleased with my solution. I developed it test first and implemented
all the "extra credit." I also handle any possible number of seconds,
as I'm pretty sure I came up with the right algorithm when the seconds
are more than 99.

Enjoy the code below (warning I know some of the longer lines at the
bottom will wrap.)

Ryan

# Ruby Quiz #118: Microwave
# Solution by Ryan Leavengood
# I'm glad to be back...

require 'test/unit'

class Microwave
  # Finds the most efficient button combo for the given seconds and
metric
  def self.microwave(seconds, metric = proc {|b| euclidean_distance(b)})
    generate_buttons(seconds).sort_by(&metric).first
  end

  # Allows a tolerance when finding the most efficient button combo
  def self.microwave_give_or_take(seconds, tolerance,
                                  metric = proc {|b|
euclidean_distance(b)})
    ((seconds-tolerance)..(seconds+tolerance)).map do |s|
      generate_buttons(s)
    end.flatten.sort_by(&metric).first
  end

  # Generates the various button combinations for the given seconds
  def self.generate_buttons(seconds)
    result = []
    if seconds < 100
      result << seconds
    end
    if seconds > 59
      min,sec = seconds.divmod(60)
      result << "#{min}#{"%02d" % sec}".to_i
      if min > 1 and sec < 40
        sec += 60
        min -= 1
        result << "#{min}#{"%02d" % sec}".to_i
      end
    end

    result.sort
  end

  # The default button layout
  @points = {
    '1' => [0,0],
    '2' => [0,1],
    '3' => [0,2],
    '4' => [1,0],
    '5' => [1,1],
    '6' => [1,2],
    '7' => [2,0],
    '8' => [2,1],
    '9' => [2,2],
    '0' => [3,1],
    '*' => [3,2]
  }

  # Traverses the buttons calculating Euclidean distance
  def self.euclidean_distance(buttons, points = @points)
    button_path_distance(buttons, :calc_euclidean_distance, points)
  end

  # Traverses the buttons calculating Manhattan distance
  def self.manhattan_distance(buttons, points = @points)
    button_path_distance(buttons, :calc_manhattan_distance, points)
  end

  # Surprise, surprise this gives the number of buttons pressed
  def self.number_of_buttons(buttons)
    # The +1 adds the * button
    buttons.to_s.length + 1
  end

  private

  # The worker function for getting button distance
  def self.button_path_distance(buttons, method, points)
    result = 0.0
    # Get each digit as a string and add the * for the cook button,
    # then convert to the points the buttons represent
    sequence = (buttons.to_s.scan(/./) << '*').map { |b| points[b] }
    start = sequence.shift
    sequence.each do |point|
      result += self.send(method, start, point)
      start = point
    end
    result
  end

  def self.calc_euclidean_distance(start_point, end_point)
    Math.sqrt(
      ((end_point[0] - start_point[0]) ** 2) +
      ((end_point[1] - start_point[1]) ** 2))
  end

  def self.calc_manhattan_distance(start_point, end_point)
    (end_point[0] - start_point[0]).abs +
      (end_point[1] - start_point[1]).abs
  end
end

# Defining the method requested in the quiz
def microwave(seconds)
  Microwave.microwave(seconds)
end

# A pretty darn thorough test case...I did this all test first
class MicrowaveTest < Test::Unit::TestCase
  def test_microwave
    assert_equal(1, microwave(1))
    assert_equal(10, microwave(10))
    assert_equal(35, microwave(35))
    assert_equal(45, microwave(45))
    assert_equal(60, microwave(60))
    assert_equal(74, microwave(74))
    assert_equal(99, microwave(99))
    assert_equal(140, microwave(100))
    assert_equal(159, microwave(119))
    assert_equal(200, microwave(120))
    assert_equal(199, microwave(159))
    assert_equal(240, microwave(160))
    assert_equal(780, microwave(500))
    assert_equal(1700, microwave(1020))
  end

  def test_give_or_take
    # I was lazy and only decided to test for the given case :)
    assert_equal(99, Microwave.microwave_give_or_take(95, 5))
  end

  def test_generate_buttons
    assert_equal([1], Microwave.generate_buttons(1))
    assert_equal([13], Microwave.generate_buttons(13))
    assert_equal([27], Microwave.generate_buttons(27))
    assert_equal([55], Microwave.generate_buttons(55))
    assert_equal([60,100], Microwave.generate_buttons(60))
    assert_equal([68,108], Microwave.generate_buttons(68))
    assert_equal([75,115], Microwave.generate_buttons(75))
    assert_equal([99,139], Microwave.generate_buttons(99))
    assert_equal([140], Microwave.generate_buttons(100))
    assert_equal([141], Microwave.generate_buttons(101))
    assert_equal([159], Microwave.generate_buttons(119))
    assert_equal([160,200], Microwave.generate_buttons(120))
    assert_equal([188,228], Microwave.generate_buttons(148))
    assert_equal([199,239], Microwave.generate_buttons(159))
    assert_equal([240], Microwave.generate_buttons(160))
    assert_equal([250], Microwave.generate_buttons(170))
    assert_equal([259], Microwave.generate_buttons(179))
    assert_equal([260,300], Microwave.generate_buttons(180))
    assert_equal([780,820], Microwave.generate_buttons(500))
    assert_equal([1645], Microwave.generate_buttons(1005))
    assert_equal([1660,1700], Microwave.generate_buttons(1020))
  end

  def test_euclidean_distance
    assert_in_delta(3.61, Microwave.euclidean_distance(1), 0.01)
    assert_in_delta(3.61, Microwave.euclidean_distance(11), 0.01)
    assert_in_delta(3.16, Microwave.euclidean_distance(2), 0.01)
    assert_in_delta(3.16, Microwave.euclidean_distance(22), 0.01)
    assert_in_delta(3.0, Microwave.euclidean_distance(3), 0.01)
    assert_in_delta(3.0, Microwave.euclidean_distance(33), 0.01)
    assert_in_delta(2.83, Microwave.euclidean_distance(4), 0.01)
    assert_in_delta(2.83, Microwave.euclidean_distance(44), 0.01)
    assert_in_delta(2.24, Microwave.euclidean_distance(5), 0.01)
    assert_in_delta(2.24, Microwave.euclidean_distance(55), 0.01)
    assert_in_delta(2.0, Microwave.euclidean_distance(6), 0.01)
    assert_in_delta(2.0, Microwave.euclidean_distance(66), 0.01)
    assert_in_delta(2.24, Microwave.euclidean_distance(7), 0.01)
    assert_in_delta(2.24, Microwave.euclidean_distance(77), 0.01)
    assert_in_delta(1.41, Microwave.euclidean_distance(8), 0.01)
    assert_in_delta(1.41, Microwave.euclidean_distance(88), 0.01)
    assert_in_delta(1.0, Microwave.euclidean_distance(9), 0.01)
    assert_in_delta(1.0, Microwave.euclidean_distance(99), 0.01)
    assert_in_delta(1.0, Microwave.euclidean_distance(0), 0.01)
    assert_in_delta(5.0, Microwave.euclidean_distance(123), 0.01)
    assert_in_delta(4.16, Microwave.euclidean_distance(100), 0.01)
    assert_in_delta(3.83, Microwave.euclidean_distance(159), 0.01)
  end

  def test_manhattan_distance
    assert_equal(5, Microwave.manhattan_distance(1))
    assert_equal(5, Microwave.manhattan_distance(11))
    assert_equal(4, Microwave.manhattan_distance(2))
    assert_equal(4, Microwave.manhattan_distance(22))
    assert_equal(3, Microwave.manhattan_distance(7))
    assert_equal(3, Microwave.manhattan_distance(777))
    assert_equal(5, Microwave.manhattan_distance(100))
  end

  def test_number_of_buttons
    assert_equal(2, Microwave.number_of_buttons(1))
    assert_equal(3, Microwave.number_of_buttons(12))
    assert_equal(4, Microwave.number_of_buttons(567))
    assert_equal(5, Microwave.number_of_buttons(1000))
  end
end

if $0 == __FILE__
  if ARGV.length > 0
    if ARGV[0] =~ /^\d*$/
      seconds = ARGV[0].to_i
      puts "For #{seconds} seconds the ideal minimum microwave buttons
are:"
      puts "\t#{microwave(seconds)} using Euclidean distances"
      puts "\t#{Microwave.microwave(seconds, proc{|b|
Microwave.manhattan_distance(b)})} using Manhattan distances"
      puts "\t#{Microwave.microwave(seconds, proc{|b|
Microwave.number_of_buttons(b)})} using number of buttons"
      puts "\t#{Microwave.microwave_give_or_take(seconds, 5)} using
Euclidean distances and a 5 second threshold"
      puts "\t#{Microwave.microwave_give_or_take(seconds, 10)} using
Euclidean distances and a 10 second threshold"
      wide_points = {
        '1' => [0,0],
        '2' => [0,2],
        '3' => [0,4],
        '4' => [1,0],
        '5' => [1,2],
        '6' => [1,4],
        '7' => [2,0],
        '8' => [2,2],
        '9' => [2,4],
        '0' => [3,2],
        '*' => [3,4]
      }
      puts "\t#{Microwave.microwave(seconds, proc{|b|
Microwave.euclidean_distance(b, wide_points)})} using Euclidean
distances and wide buttons"
    else
      puts "Usage: #$0 <seconds> (or nothing to run the test cases)"
      exit(1)
    end
    # Don't run the test case
    Test::Unit.run = true
  end
end
7264fb16beeea92b89bb42023738259d?d=identicon&s=25 Christian Neukirchen (Guest)
on 2007-04-01 18:03
(Received via mailing list)
# My straight-forward solution.

require 'enumerator'

# How much can the time differ?
FUZZ = 0

POS = { ?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] }

def metric(string)
  string.enum_for(:each_byte).map { |b| POS[b] }.
         enum_for(:each_cons, 2).inject(0) { |sum, ((x1,y1), (x2, y2))|
    # 1-norm
    # sum + (x1-x2).abs + (y1-y2).abs

    # 2-norm
    sum + Math.sqrt((x1-x2)**2 + (y1-y2)**2)
  }
end

def entries(time)
  return []  if time <= 0

  min, sec = time.divmod(60)
  entries = []

  # seconds only
  entries << "%d*" % [time]                 if time < 100

  # usual time format
  entries << "%d%02d*" % [min, sec]

  # more than 60 seconds
  entries << ("%d%02d*" % [min-1, sec+60])  if min > 1 && sec < 40

  entries
end

1.upto(999) { |time|
  entries = (-FUZZ..FUZZ).map { |offset| entries(time + offset)
}.flatten

  # Sort by movement length, then by keypresses.
  quickest = entries.sort_by { |s| [metric(s), s.size] }.first
  puts "%3d (%02d:%02d): %s" % [time, time.divmod(60), quickest].flatten
}

__END__
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2007-04-02 05:18
(Received via mailing list)
On Apr 1, 2007, at 10:32 AM, Ryan Leavengood wrote:

> # Ruby Quiz #118: Microwave
> # Solution by Ryan Leavengood
> # I'm glad to be back...

I, for one, am very glad to have you back.

James Edward Gray II
This topic is locked and can not be replied to.