Solution: Microwave Numbers (#118)


#1

Well much like my recent return to posting on the O’Reilly Ruby blog,
I couldn’t resist getting back into the Ruby Q. 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 Q. #118: Microwave

Solution by Ryan L.

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 :slight_smile:
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 (or nothing to run the test cases)”
exit(1)
end
# Don’t run the test case
Test::Unit.run = true
end
end


#2

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


#3

On Apr 1, 2007, at 10:32 AM, Ryan L. wrote:

Ruby Q. #118: Microwave

Solution by Ryan L.

I’m glad to be back…

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

James Edward G. II