[QUIZ] [Solution] Barrel of monkeys

Brian_Schroder1 · 3 May 2005 16:23

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/

Brian_Schroder1 · 6 May 2005 09:48

After removing the typos that somehow crept in there and adding a
ending condition for the fill_time search it now works. It finds a
playlist to fit into 30m +/- 5s of time and starting with a ending
with z in a little more than two minutes.

Alarm Call - Björk 4.33m
Afternoon In The Desert - Tangerine Dream 3.32m
A Different Drum - Peter Gabriel 4.67m
Asian tropical rain forest - SOUND EFFECTS 0.85m
Acceptance - Gabriel Yared 1.02m
Ersatz - Fischerspooner 3.93m
Waltz - Gabriel Yared 1.97m
Santa Cruz - David Qualey 2.18m
Tremolo Blooz - The Presidents of the United States of America 2.88m
Channel Z - The B-52's 4.84m

···

On 03/05/05, Brian Schröder <ruby.brian@gmail.com> wrote:

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/

------
30.00m
took 141.35s

Thanks for the quiz,

Brian

--
http://ruby.brian-schroeder.de/

multilingual _non rails_ ruby based vocabulary trainer:
http://www.vocabulaire.org/ | http://www.gloser.org/ | http://www.vokabeln.net/

Gavin_Kistner2 · 6 May 2005 12:03

Nice fit, but it doesn't appear to be a Barrel of Monkeys playlist.

(AL -> AT -> AM -> AT -> AE -> EZ -> WZ -> SZ -> TZ -> CZ)

···

On May 6, 2005, at 3:48 AM, Brian Schröder wrote:

Alarm Call - Björk 4.33m
Afternoon In The Desert - Tangerine Dream 3.32m
A Different Drum - Peter Gabriel 4.67m
Asian tropical rain forest - SOUND EFFECTS 0.85m
Acceptance - Gabriel Yared 1.02m
Ersatz - Fischerspooner 3.93m
Waltz - Gabriel Yared 1.97m
Santa Cruz - David Qualey 2.18m
Tremolo Blooz - The Presidents of the United States of America 2.88m
Channel Z - The B-52's 4.84m
------
30.00m
took 141.35s

Brian_Schroder1 · 6 May 2005 12:38

One should not work on two things at the same time. Nicely spotted ;). *blush*

regards,

Brian

···

On 06/05/05, Gavin Kistner <gavin@refinery.com> wrote:

On May 6, 2005, at 3:48 AM, Brian Schröder wrote:
> Alarm Call -
> Björk 4.33m
> Afternoon In The Desert - Tangerine
> Dream 3.32m
> A Different Drum - Peter
> Gabriel 4.67m
> Asian tropical rain forest - SOUND
> EFFECTS 0.85m
> Acceptance - Gabriel
> Yared 1.02m
> Ersatz -
> Fischerspooner 3.93m
> Waltz - Gabriel
> Yared 1.97m
> Santa Cruz - David
> Qualey 2.18m
> Tremolo Blooz - The Presidents of the United States of
> America 2.88m
> Channel Z - The
> B-52's 4.84m
>
> ------
>
> 30.00m
> took 141.35s

Nice fit, but it doesn't appear to be a Barrel of Monkeys playlist.

(AL -> AT -> AM -> AT -> AE -> EZ -> WZ -> SZ -> TZ -> CZ)

--
http://ruby.brian-schroeder.de/

multilingual _non rails_ ruby based vocabulary trainer:
http://www.vocabulaire.org/ | http://www.gloser.org/ | http://www.vokabeln.net/

Topic		Replies	Views
[QUIZ] Barrel of Monkeys (#30) ruby-talk	15	94	6 May 2005
[SOLUTION] Please Forward: Ruby Quiz Subumission ruby-talk	0	117	6 May 2005
Please Forward: Ruby Quiz Submission ruby-talk	0	126	16 January 2007
[solution] quizz 126 ruby-talk	0	67	3 June 2007
[SUMMARY] Shirt Reader (#140) ruby-talk	1	64	27 September 2007

[QUIZ] [Solution] Barrel of monkeys

Related topics