Hello Group, I once again had the pleasure of solving a ruby quiz. Here's my solution. I implemeted a bidirectional search and a mechanism to devise more general search evaluation functions. As an example I implemented the search for the barrel of monkeys that best fills up a given total duration. I tried to make it work with unicode strings, but I'm not so shure regexps are the way to go here ;) Because I'm a bit short on time (and shouldn't even have made this quiz), I have not even implemented an user interface. have fun, Brian Find everything nicely wrapped up at: http://ruby.brian-schroeder.de/quiz/monkeysongs/ #!/usr/bin/ruby -Ku require 'set' require "rexml/document" include REXML class String def uljust(n) self + " " * [n - self.split(//).length, 0].max end end class MonkeySong attr_reader :artist, :name, :duration, :first_letter, :last_letter, :_id def initialize(id, artist, name, duration) @_id = id; @artist = artist; @name = name; @duration = duration /^(.)/ =~ @name; @first_letter = $1.downcase /(.)$/ =~ @name; @last_letter = $1.downcase end def to_s "#{@name} - #{@artist} (#{@duration / 1000}s)" end def hash @_id.hash end def eql?(o) @_id == o._id end end class MonkeySonglist < Array def add_left_right(left, right) (MonkeySonglist.new() << left).concat(self) << right end def to_s self.inject('') do | r, song | r << "#{song.name} - #{song.artist}".uljust(60) + "%2.2fm\n" % (song.duration / 60000.0) end << " " * 60 + "-----\n" % (self.duration / 60000.0) << " " * 60 + "%2.2fm\n" % (self.duration / 60000.0) end def duration self.inject(0) { | r, s | r + s.duration } end end class MonkeySongs def initialize(library = 'SongLibrary.xml') @starting_with = {} @ending_with = {} doc = Document.new(File.new(library)) @song_count = 0 doc.root.elements.each do | artist | artist_name = artist.attributes['name'] artist.elements.each do | song | song = MonkeySong.new(@song_count, artist_name, song.attributes['name'], song.attributes['duration'].to_i) (@starting_with[song.first_letter.downcase] ||= Set.new) << song (@ending_with[song.last_letter.downcase] ||= Set.new) << song @song_count += 1; end end end def find_any(from, to, max_depth = -1, used = Set.new) return nil if max_depth == 0 starts = (@starting_with[from] || Set.new) - used endings = (@ending_with[to] || Set.new) - used return nil if starts.empty? or endings.empty? connections = starts & endings if !connections.empty? # Found connection connections.each do |s| yield MonkeySonglist.new([s]) end end starts.each do | start_song | start = start_song.first_letter endings.each do | end_song | ending = end_song.last_letter if end_song.first_letter == start_song.last_letter yield MonkeySonglist.new([start_song, end_song]) end find_any(start, ending, max_depth - 1, used | [start_song, end_song]) do | connection | yield connection.add_left_right(start_song, end_song) end end end return nil end def find_best_matching_(from, to, match_evaluator, max_depth = -1, used = Set.new) return nil unless match_evaluator.continue?(used) starts = (@starting_with[from] || Set.new) - used endings = (@ending_with[to] || Set.new) - used return nil if starts.empty? or endings.empty? connections = starts & endings if !connections.empty? # Found connection connections.each do |s| yield MonkeySonglist.new([s]) end end starts.each do | start_song | start = start_song.first_letter endings.each do | end_song | ending = end_song.last_letter if end_song.first_letter == start_song.last_letter yield MonkeySonglist.new([start_song, end_song]) end find_best_matching_(start, ending, match_evaluator, max_depth - 1, used | [start_song, end_song]) do | connection | yield connection.add_left_right(start_song, end_song) end end end return nil end def find_best_matching(from, to, match_evaluator, max_depth = -1) find_best_matching_(from, to, match_evaluator, max_depth) do | connection | match_evaluator.add_result(connection) end match_evaluator.best_match end class BasicMatchEvaluator attr_reader :best_match, :best_delta def add_result(match) delta = evaluate(match) if !@best_delta || (delta < @best_delta) @best_delta = delta @best_match = match $stderr.puts "Best so far: #{@best_delta}" end @best_match end end # Example for an evaluator. Different evaluators can be programmed to implement any kind of minimization class PlaytimeEvaluator < BasicMatchEvaluator attr_reader :best_match, :best_delta def initialize(target_time) @target_time = target_time end def continue?(used) if @best_delta used_time = (used.inject(0) { | r, s | r + s.duration } if used_time < @target_time true else delta = (used_time - @target_time) ** 2 delta < @best_delta end else true end end def evaluate(match) (match.inject(0) { | r, s | r + s.duration } - @target_time) ** 2 end end def find_best_timefill(from, to, time) evaluator = PlaytimeEvaluator.new(time) find_best_matching(from, to, evaluator) end def find_shortest(from, to) 1.upto(@song_count) do | max_depth | $stdout.flush find_any(from, to, max_depth) do | connection | return connection end end end end puts "Loading songlist" monkeysongs = MonkeySongs.new puts "Shortest monkeysonglist for c -> u" puts monkeysongs.find_shortest('c', 'u').to_s $stdout.flush puts puts "Shortest monkeysonglist for f -> y" puts monkeysongs.find_shortest('f', 'y').to_s $stdout.flush puts puts "Shortest monkeysonglist for a -> z" puts monkeysongs.find_shortest('a', 'z').to_s $stdout.flush puts puts "Find best timefill for a -> z 30min" puts monkeysongs.find_best_timefill('a', 'z', 30 * 60 * 1000).to_s $stdout.flush puts puts "All connections for f -> y" monkeysongs.find_any('f', 'y') do | connection | puts connection.to_s, "---" $stdout.flush end -- http://ruby.brian-schroeder.de/ multilingual _non rails_ ruby based vocabulary trainer: http://www.vocabulaire.org/ | http://www.gloser.org/ | http://www.vokabeln.net/