[QUIZ] [Solution] Barrel of monkeys

  • Thread starter Brian Schröder
  • Start date
B

Brian Schröder

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

Brian Schröder

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/

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
 
G

Gavin Kistner

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

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

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

Brian Schröder

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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top