Asp Forum - [QUIZ] [Solution] Barrel of monkeys

Brian Schröder

5/3/2005 4:24:00 PM

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-sch...quiz/mo...

#!/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-sch...

multilingual _non rails_ ruby based vocabulary trainer:
http://www.vocabu... | http://www.g... | http://www.vok...

3 Answers

Brian Schröder

5/6/2005 9:48:00 AM

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-sch...quiz/mo...
>

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
------
30.00m
took 141.35s

Thanks for the quiz,

Brian

--
http://ruby.brian-sch...

multilingual _non rails_ ruby based vocabulary trainer:
http://www.vocabu... | http://www.g... | http://www.vok...

Gavin Kistner

5/6/2005 12:03:00 PM

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)

Brian Schröder

5/6/2005 12:38:00 PM

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)
>

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

regards,

Brian

--
http://ruby.brian-sch...

multilingual _non rails_ ruby based vocabulary trainer:
http://www.vocabu... | http://www.g... | http://www.vok...

comp.lang.ruby

[QUIZ] [Solution] Barrel of monkeys

Brian Schröder

Brian Schröder

Gavin Kistner

Brian Schröder

x Login to ForumsZone