Here’s my solution. It got longer and messier than I wanted, but I tried
to be
fairly general. Here’s the basic structure:
Button: A struct of a label, an x-coord, and a y-coord
ButtonSequence: An array of Buttons.
Pad: A hash of String labels (‘0’ thru ‘9’ & ‘*’) to Buttons
metrics: Not a class of their own, just a Proc taking a ButtonSequence
and
returning a numeric score (lower is better)
MetricStack: An array of metrics to be tried in order when there’s a
tie.
alternator: Not a class, just Procs taking a seconds value and returing
an
Enumerable of alternate, equivalent seconds values to try
(used
for tolerance).
Then there is the main microwave() function that takes a seconds value,
a Pad,
an alternator, and a MetricStack [and a list() function to run
microwave() on
a bunch of values). These are spread among the 4 files below. Here’s
some
examples of how it can be used:
Use default pad, the Exact alternator which returns just [76], and the
EuclideanMetric for a distance metric.
to_s is called because a ButtonSequence is returned.
microwave(76).to_s
=> “76*”
Use a pad with buttons twice as wide.
microwave(76, Pad.stretched_pad(2,1)).to_s
=> “76*”
Allow a tolerance of up to 5 seconds.
microwave(76, Pad.normal_pad, Tolerance[5]).to_s
=> “80*”
First, try to minimize Euclidean distance. If there’s a tie, try to
minimize
the total number of buttons pressed. If there’s still a tie, try to
minimize
the number of unique buttons pressed.
ms = MetricStack.new([EuclideanMetric, LowButtonMetric,
MinButtonMetric])
microwave(71, Pad.normal_pad, Exact, ms).to_s
=> “111*”
And now here’s the code:
pad.rb
Ruby Q. 118: Microwave Numbers
Button = Struct.new(:label, :x, :y)
Holds Buttons. I thought about making this a Comparable, or of making
subclasses of this for different orderings, but didn’t.
class ButtonSequence < Array
def to_s
self.map{ |b| b.label }.join
end
end
Maps button labels (Strings) to Buttons.
class Pad < Hash
Return an Array containing all ways of entering the given number of
seconds into the microwave. Each entry will be a pair of minutes &
seconds.
def Pad.entries(seconds)
ent = []
minutes = seconds / 60
(0…minutes).each do |min|
sec = seconds - 60*min
ent << [min, sec] if sec < 100
end
ent
end
Return a String of keys to press on the microwave to enter the given
number of minutes and seconds. sec must be < 100.
def Pad.what_to_press(min, sec)
raise ‘sec is too large’ if sec >= 100
str = ‘’
str << min.to_s if min > 0
str << ‘0’ if sec < 10 and min > 0
str << sec.to_s
str << ‘*’
str
end
For the given number of seconds, yield each possible button sequence
as an
ButtonSequence.
def each_button_sequence(seconds)
Pad.entries(seconds).each do |ent|
press_str = Pad.what_to_press(*ent)
bs = ButtonSequence.new(press_str.split(//).map { |char|
self[char] })
yield(bs)
end
end
Generate a pad like this:
x
0 1 2
#Â ±–±--±–+
#Â 0 | 1 | 2 | 3 |
#Â ±–±--±–+
#Â 1 | 4 | 5 | 6 |
y ±–±--±–+
#Â 2 | 7 | 8 | 9 |
#Â ±–±--±–+
#Â 3 Â Â | 0 | * |
#Â Â Â ±–±--+
def Pad.normal_pad
stretched_pad(1, 1)
end
Generate a pad like the normal one, but stretched either
horizontally,
vertially, or both. x_factor and y_factor must be integers. For
example,
Pad.stretched_pad(3,1) would produce a pad with buttons 3 times
wider
than they are tall.
def Pad.stretched_pad(x_factor, y_factor)
pad = Pad.new
(1…9).each do |n|
pad[n.to_s] = Button.new(n.to_s, x_factor*((n-1) % 3),
y_factor*((n-1) / 3))
end
pad.merge!( { ‘0’ => Button.new(‘0’, x_factor, 3y_factor),
'’ => Button.new(’’, 2x_factor, 3*y_factor) } )
pad
end
end
metrics.rb
Ruby Q. 118: Microwave Numbers
To decide which button sequences are better than others, a metric is
used. I
didn’t bother creating a Metric class, so they’re just a Proc that
takes a
ButtonSequence as an argument and returns a numeric score (lower is
always
better). To settle ties, a MetricStack is used, which is an Array of
metrics
that are tried in order until the tie is broken (if its ever broken).
require ‘set’
class Array
Yield all Arrays containing two adjacent elements.
def each_adjacent_pair
(1…self.size).each do |i|
yield([self[i-1], self[i]])
end
end
Return the number of unique elements.
def num_uniq
Set[*self].size
end
end
Create a Proc returns the n-norm of two Buttons.
def create_norm_distancer(n)
lambda do |b1, b2|
((b1.x - b2.x).absn + (b1.y - b2.y).absn) ** (1.0/n)
end
end
ManhattanDistance = create_norm_distancer(1)
EuclideanDistance = create_norm_distancer(2)
Create a distance-measuring metric from the given distance measurer.
def create_distance_metric(dist_measurer)
lambda do |button_sequence|
dist = 0
button_sequence.each_adjacent_pair do |button_pair|
dist += dist_measurer[button_pair.first, button_pair.last]
end
dist
end
end
ManhattanMetric = create_distance_metric(ManhattanDistance)
EuclideanMetric = create_distance_metric(EuclideanDistance)
A metric that minimizes the total number of buttons pressed.
MinButtonMetric = lambda do |button_sequence|
button_sequence.size
end
A metric that minimizes the number of unique buttons pressed.
LowButtonMetric = lambda do |button_sequence|
button_sequence.num_uniq
end
A MetricStack is an Array of metrics that compare ButtonSequences.
Earlier
metrics take precedence over later metrics.
class MetricStack < Array
Return true if button_seq_1 is better than button_seq_2.
def better?(button_seq_1, button_seq_2)
return true if not button_seq_1.nil? and button_seq_2.nil?
better = nil
self.each do |metric|
s1, s2 = metric[button_seq_1], metric[button_seq_2]
s1 < s2 ? better = true : s2 < s1 ? better = false : nil
break if not better.nil?
end
better.nil? ? false : better
end
end
alternators.rb
Ruby Q. 118: Microwave Numbers
For “something that produces alternate seconds values” I’m using the
word
“alternator” - it can be any Proc that takes as an argument the number
of
seconds, and returns an Enumerable of “close enough” seconds to try.
require ‘set’
Exact = lambda { |seconds| [seconds] }
Produce an alternator that will return all seconds within the given
tolerance
from the target number of seconds (eg, Tolerance[2][10] will return
(8…12)).
Tolerance = lambda do |tolerance|
lambda do |seconds|
([seconds - tolerance, 0].max…seconds + tolerance)
# Any way to pass a block to a Proc?
#([seconds - tolerance, 0].max…seconds + tolerance).each do |sec|
# yield(sec)
#end
end
end
Produce a few values close by. This isn’t really useful, just an
example of
another alternator.
RandomClose = lambda do |seconds|
s = Set[seconds]
(rand(10)+1).times { s << [seconds + rand(21) - 10, 0].max }
s
end
microwave.rb
Ruby Q. 118: Microwave Numbers
require ‘metrics’
require ‘pad’
require ‘alternators’
alternator is a Proc that takes the number of seconds and produces an
Enumerable of equivalent values.
metrics can be:
- a MetricStack
- a single metric Proc
- an Array of metric Procs
def microwave(seconds, pad = Pad.normal_pad,
alternator = Exact, metrics = EuclideanMetric)
case metrics
when Proc; metrics = MetricStack.new([metrics])
when Array; metrics = MetricStack.new(metrics)
end
best = nil
alternator[seconds].each do |sec|
pad.each_button_sequence(sec) do |bs|
best = bs if metrics.better?(bs, best)
end
end
best
end
Print out the best button sequences for all seconds in the given
Enumerable.
Other arguments are passed into microwave(). The thing that sucks
about
this is that if there’s a tolerance of > 0, identical sequences will
be
scored more than once. Maybe memo-ize that or something…
def list(enum, pad = Pad.normal_pad,
alternator = Exact, metrics = EuclideanMetric)
puts “Seconds Buttons”
puts “------- -------”
enum.each do |i|
best = microwave(i, pad, alternator, metrics)
puts “#{i} #{best}”
end
end