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/