Reply to thread

Message: [QUOTE="Jesse Merriman, post: 4555133"] 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 P= ad, 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 =3D> "76*" # Use a pad with buttons twice as wide. microwave(76, Pad.stretched_pad(2,1)).to_s =3D> "76*" # Allow a tolerance of up to 5 seconds. microwave(76, Pad.normal_pad, Tolerance[5]).to_s =3D> "80*" # First, try to minimize Euclidean distance. If there's a tie, try to minim= ize # the total number of buttons pressed. If there's still a tie, try to minim= ize # the number of unique buttons pressed. ms =3D MetricStack.new([EuclideanMetric, LowButtonMetric, MinButtonMetric]) microwave(71, Pad.normal_pad, Exact, ms).to_s =3D> "111*" And now here's the code: # -------------------------------------------------------------------------= =2D-- # pad.rb # Ruby Quiz 118: Microwave Numbers Button =3D 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 =3D [] minutes =3D seconds / 60 (0..minutes).each do |min| sec =3D 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 >=3D 100 str =3D '' 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 =3D Pad.what_to_press(*ent) bs =3D ButtonSequence.new(press_str.split(//).map { |char| self[char]= }) yield(bs) end end # Generate a pad like this: # x # 0 1 2 #=C2=A0 +---+---+---+ #=C2=A0 0 | 1 | 2 | 3 | #=C2=A0 +---+---+---+ #=C2=A0 1 | 4 | 5 | 6 | # y +---+---+---+ #=C2=A0 2 | 7 | 8 | 9 | #=C2=A0 +---+---+---+ #=C2=A0 3 =C2=A0 =C2=A0| 0 | * | #=C2=A0 =C2=A0 =C2=A0+---+---+ 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 =3D Pad.new (1..9).each do |n| pad[n.to_s] =3D Button.new(n.to_s, x_factor*((n-1) % 3), y_factor*((n-1) / 3)) end pad.merge!( { '0' =3D> Button.new('0', x_factor, 3*y_factor), '*' =3D> Button.new('*', 2*x_factor, 3*y_factor) } ) pad end end # -------------------------------------------------------------------------= =2D-- # metrics.rb # Ruby Quiz 118: Microwave Numbers # To decide which button sequences are better than others, a metric is used= =2E 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 metr= ics # 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).abs**n + (b1.y - b2.y).abs**n) ** (1.0/n) end end ManhattanDistance =3D create_norm_distancer(1) EuclideanDistance =3D 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 =3D 0 button_sequence.each_adjacent_pair do |button_pair| dist +=3D dist_measurer[button_pair.first, button_pair.last] end dist end end ManhattanMetric =3D create_distance_metric(ManhattanDistance) EuclideanMetric =3D create_distance_metric(EuclideanDistance) # A metric that minimizes the total number of buttons pressed. MinButtonMetric =3D lambda do |button_sequence| button_sequence.size end # A metric that minimizes the number of unique buttons pressed. LowButtonMetric =3D 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 =3D nil self.each do |metric| s1, s2 =3D metric[button_seq_1], metric[button_seq_2] s1 < s2 ? better =3D true : s2 < s1 ? better =3D false : nil break if not better.nil? end better.nil? ? false : better end end # -------------------------------------------------------------------------= =2D-- # alternators.rb # Ruby Quiz 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 =3D lambda { |seconds| [seconds] } # Produce an alternator that will return all seconds within the given=20 tolerance # from the target number of seconds (eg, Tolerance[2][10] will return=20 (8..12)). Tolerance =3D 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 =3D lambda do |seconds| s =3D Set[seconds] (rand(10)+1).times { s << [seconds + rand(21) - 10, 0].max } s end # -------------------------------------------------------------------------= =2D-- # microwave.rb # Ruby Quiz 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 =3D Pad.normal_pad, alternator =3D Exact, metrics =3D EuclideanMetric) case metrics when Proc; metrics =3D MetricStack.new([metrics]) when Array; metrics =3D MetricStack.new(metrics) end best =3D nil alternator[seconds].each do |sec| pad.each_button_sequence(sec) do |bs| best =3D bs if metrics.better?(bs, best) end end best end # Print out the best button sequences for all seconds in the given Enumerab= le. # 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 =3D Pad.normal_pad, alternator =3D Exact, metrics =3D EuclideanMetric) puts "Seconds Buttons" puts "------- -------" enum.each do |i| best =3D microwave(i, pad, alternator, metrics) puts "#{i} #{best}" end end # -------------------------------------------------------------------------= =2D-- =2D-=20 Jesse Merriman [email]jessemerriman@warpmail.net[/email] [URL]http://www.jessemerriman.com/[/URL][/i] [/QUOTE]

Verification