Gavin Kistner
5/2/2005 1:55:00 AM
Following is my solution to the Barrel of Monkeys quiz. I got the
'extra credit' for short playlists, but didn't have time to try out
the only solution I came up with for the 'specific duration' extra
credit.
(There is a bug exposed by the test case, where (for reasons I
haven't figured out) it doesn't always find the absolutely shortest
playlist.)
I'll discuss some of the lessons I learned when I write up the
Summary on Wednesday.
A sample of the output:
[Sliver:~/Desktop/Barrel of Monkeys] gkistner$ ruby barrel.rb
Stopwatch started at Sun May 01 19:20:21 MDT 2005
+0.1s to load marshalled library from file
Looking for a path between 'Moab' and 'I'm On My Way'
#0 - Jamie Janover :: Moab :: 9:05
#1 - Shamwari :: Babmudiki :: 5:26
#2 - The Proclaimers :: I'm On My Way :: 3:44
+0.1s to create playlist
Looking for a path between 'My Girl' and 'I'm A Rainbow Too'
#0 - The Mamas & The Papas :: My Girl :: 3:30
#1 - Creedence Clearwater Revival :: Lodi :: 3:11
#2 - Bob Marley & Fatboy Slim :: I'm A Rainbow Too :: 8:00
+0.1s to create playlist
Looking for a path between 'Sand in My Shoes' and 'Bug City'
#0 - Dido :: Sand in My Shoes :: 5:00
#1 - Isao Tomita :: Syncopated Clock :: 2:31
#2 - Fats Waller :: Keepin' Out of Mischief Now :: 3:16
#3 - The Offspring :: Why Don't You Get A Job? :: 2:52
#4 - The Presidents of the United States of America :: Bug City :: 3:05
+0.0s to create playlist
What I found surprising is how often (given the supplied library)
there is a single 3-song playlist that connects just about any two
end songs.
There are six files:
barrel.rb -- loads the SongLibrary.xml file and picks two songs at
random and tries to find a playlist.
barrel_of_classes.rb -- all the classes used in the solution
barrel_of_tests.rb -- some limited unit tests (which helped my find
some bugs, yay testing!)
stopwatch.rb -- an unrelated class just for my own trivial timing
tests
arabicnumerals.rb -- (not included here) The solution to quiz number
25 by Eliah Hecht
==================================================
barrel.rb
==================================================
require 'rexml/document'
require 'rexml/xpath'
require 'barrel_of_classes'
require 'stopwatch'
$library_file = 'library.marshal'
Stopwatch.start
if File.exist?( $library_file )
library = Marshal.load( File.new( $library_file, 'r+' ) )
Stopwatch.mark( 'load marshalled library from file')
else
include REXML
xml = Document.new( File.new( 'SongLibrary.xml' ) )
Stopwatch.mark( 'load XML')
song_nodes = XPath.match( xml, '//Song' )
Stopwatch.mark( 'find songs in xml' )
library = SongLibrary.new( song_nodes.inject( [] ) do |lib,
song_node|
lib << Song.new( song_node.attributes['name'],
song_node.attributes['duration'].to_i, song_node.parent.attributes
['name'] )
end )
Stopwatch.mark( 'fill library' )
# Get rid of songs with useless names
library.songs.delete_if{ |song| song.clean_name.length < 2 }
puts "Deleted #{song_nodes.length - library.songs.length} songs"
Stopwatch.mark( 'clean library' )
# Save the library just to save time for future runs.
Marshal.dump( library, File.new( $library_file, 'w+' ) )
Stopwatch.mark( 'save library to file' )
end
all_songs = library.songs
100.times{
start_index = rand( library.songs.length )
end_index = rand( library.songs.length )
start_song = all_songs[ start_index ]
end_song = all_songs[ end_index ]
puts "\nLooking for a path between '#{start_song.name}' and '#
{end_song.name}'"
pl = Playlist::BarrelOfMonkeys.new( library.songs, start_song,
end_song )
puts pl
Stopwatch.mark( 'create playlist' )
}
Stopwatch.stop
==================================================
barrel_of_classes.rb
==================================================
require 'arabicnumerals'
class Song
attr_reader :artist, :name, :duration
# The song name made turned into only [a-z ], with no leading or
trailing spaces
attr_reader :clean_name
# The first and last letters of the song name (after 'cleaning')
attr_reader :first, :last
def initialize( name, duration=0, artist='' )
@artist = artist
@duration = duration
@name = name
@clean_name = name.downcase
# "forever young (dune remix)" => "forever young"
@clean_name.gsub!( /\s*\([^)]*mix[^)]*\)/, '' )
# "voulez-vous [extended remix, 1979 us promo]" => "voulez-
vous"
@clean_name.gsub!( /\s*\[[^\]]*mix[^\]]*\]/, '' )
# "hava nagila (live)" => "hava nagila"
@clean_name.gsub!( /\s*\([^)]*\blive\b[^)]*\)/, '' )
# "everything in its own time [live]" => "everything in
its own time"
@clean_name.gsub!( /\s*\[[^\]]*\blive\b[^\]]*\]/, '' )
# "it's a fine day (radio edit)" => "it's a fine day"
@clean_name.gsub!( /\s*\([^)]*\bedit\b[^)]*\)/, '' )
# "pearl's girl [7" edit]" => "pearl's girl"
@clean_name.gsub!( /\s*\[[^\]]*\bedit\b[^\]]*\]/, '' )
# "can't stop raving - remix" => "can't stop raving -"
@clean_name.gsub!( /\s*remix\s*$/, '' )
# "50,000 watts" => "50000 watts"
@clean_name.gsub!( /,/, '' )
# "50000 watts" => "fifty thousand watts"
@clean_name.gsub!( /\b\d+\b/ ){ |match| match.to_i.to_en }
@clean_name.gsub!( /[^a-z ]/, '' )
@clean_name.strip!
@first = @clean_name[ 0..0 ]
@last = @clean_name [ -1..-1 ]
end
def to_s
self.artist + ' :: ' + self.name + ' :: ' +
self.duration.as_time_from_ms
end
end
class Numeric
# Treat the number as a number of milliseconds and return a
formatted version
# Produces "0:07" for 7124
# Produces "8:17" for 497000
# Produces "1:07:43" for 4063000
# Produces "59:27:44" for 214063999
# (Only handles units of time up to hours)
def as_time_from_ms
minutes = 0
seconds = (self / 1000.0).round
if seconds >= 60
minutes = seconds / 60
seconds %= 60
if minutes >= 60
hours = minutes / 60
minutes %= 60
end
end
seconds = seconds.to_s
seconds = '0' + seconds unless seconds.length > 1
minutes = minutes.to_s
minutes = '0' + minutes unless minutes.length > 1 or not hours
"#{hours}#{hours ? ':' : ''}#{minutes}:#{seconds}"
end
end
class Array
def random
self[ rand( self.length ) ]
end
end
class SongLibrary
attr_accessor :songs
def initialize( array_of_songs = [] )
@songs = array_of_songs
end
end
class Playlist
attr_reader :songs
def initialize( *songs )
@songs = songs
@current_song_number = 0
end
def to_s
out = ''
songs.each_with_index{ |song,i| out << "##{i} - #{song}\n" }
if songs
out
end
class BarrelOfMonkeys < Playlist
# Given an array of Song items and songs to start with and
end with
# produce a playlist where each song begins with the same
letter as
# the previous song ended with
def initialize( songs, start_song, end_song, options={} )
# Create a map to each song, by first letter and then
last letter
@song_links = {}
songs.each do |song|
first_map = @song_links[ song.first ] ||= {}
( first_map[ song.last ] ||= [] ) << song
end
# For speed, pick only one song for each unique
first_last pair
@song_links.each_pair do | first_letter,
songs_by_last_letters |
songs_by_last_letters.each_key do |last_letter|
songs_by_last_letters[ last_letter ] =
songs_by_last_letters[ last_letter ].random
end
end
# Get rid of any songs which start and end with the same
letter
@song_links.each_pair do | first_letter,
songs_by_last_letters |
songs_by_last_letters.delete( first_letter )
end
@songs = shortest_path( start_song, end_song )
unless @songs
warn "There is no path to make a Barrel of Monkeys
playlist between '#{start_song.name}' and '#{end_song.name}' with the
supplied library."
end
end
private
def shortest_path( start_song, end_song,
start_letters_seen='', d=0 )
# Bail out if a shorter solution was already found
return nil if @best_depth and ( @best_depth <= d )
#puts( ( "." * d ) + start_song.name )
path = [ start_song ]
if start_song.last == end_song.first
best_path = [ end_song ]
@best_depth = d
else
best_length = nil
songs_by_last_letters = @song_links
[ start_song.last ]
if songs_by_last_letters
songs_by_last_letters.each_pair do |
last_letter, song|
if start_letters_seen.include?
( song.first ) || ( start_letters_seen.include?( song.last ) &&
( song.last != end_song.first ) )
next
end
start_letters_seen += start_song.first
trial_path = shortest_path( song,
end_song, start_letters_seen, d+1 )
if trial_path && ( !best_length ||
( trial_path.length < best_length ) )
best_path = trial_path
end
end
end
end
if best_path
path << best_path
path.flatten!
else
nil
end
end
end
end
==================================================
barrel_of_tests.rb
==================================================
require 'test/unit'
require 'barrel_of_classes.rb'
class SongTest < Test::Unit::TestCase
def test_cleaning
song_name = 'Hello World'
clean_name = song_name.downcase
s1 = Song.new( song_name )
assert_equal( clean_name, s1.clean_name )
song_name = 'Hello World (remix)'
s1 = Song.new( song_name )
assert_equal( clean_name, s1.clean_name )
song_name = ' Hello World - remix'
s1 = Song.new( song_name )
assert_equal( clean_name, s1.clean_name )
song_name = ' Hello World Remix '
s1 = Song.new( song_name )
assert_equal( clean_name, s1.clean_name )
song_name = "'74 - '75"
s1 = Song.new( song_name )
assert_equal( 's', s1.first )
assert_equal( 'e', s1.last )
song_name = 'As Lovers Go [Ron Fair Remix]'
clean_name = 'as lovers go'
s1 = Song.new( song_name )
assert_equal( clean_name, s1.clean_name )
end
end
class BarrelTest < Test::Unit::TestCase
def setup
@lib = SongLibrary.new
('A'..'H').each{ |x| @lib.songs << Song.new( 'Alpha ' + x ) }
@lib.songs << Song.new( 'Beta F' )
('A'..'I').each{ |x| @lib.songs << Song.new( 'Foo ' + x ) }
@lib.songs << Song.new( 'Icarus X' )
('A'..'H').each{ |x| @lib.songs << Song.new( 'Jim ' + x ) }
@links = { }
@lib.songs.each{ |song|
link = song.first + song.last
@links[ link ] = song
}
end
def test1_valid
af = @links[ 'af' ]
fg = @links[ 'fg' ]
pl = Playlist::BarrelOfMonkeys.new( @lib.songs, af, fg )
desired_playlist = [ af, fg ]
assert_equal( desired_playlist, pl.songs )
ab = @links[ 'ab' ]
bf = @links[ 'bf' ]
fi = @links[ 'fi' ]
pl = Playlist::BarrelOfMonkeys.new( @lib.songs, ab, fi)
desired_playlist = [ ab, bf, fi ]
assert_equal( desired_playlist, pl.songs )
ix = @links[ 'ix' ]
pl = Playlist::BarrelOfMonkeys.new( @lib.songs, ab, ix )
desired_playlist << ix
assert_equal( desired_playlist, pl.songs )
aa = @links[ 'aa' ]
pl = Playlist::BarrelOfMonkeys.new( @lib.songs, aa, ix )
desired_playlist = [ aa, af, fi, ix ]
assert_equal( desired_playlist, pl.songs )
end
def test3_broken
aa = @links[ 'aa' ]
ab = @links[ 'ab' ]
jh = @links[ 'jh' ]
pl = Playlist::BarrelOfMonkeys.new( @lib.songs, aa, jh )
assert_nil( pl.songs )
pl = Playlist::BarrelOfMonkeys.new( @lib.songs, ab, jh )
assert_nil( pl.songs )
end
end
=============================================
stopwatch.rb
=============================================
module Stopwatch
class Lap
attr_reader :name, :time
def initialize( name )
@name = name
@time = Time.new
end
end
def self.start
@laps = [ ]
self.mark :start
end
def self.mark( lap_name )
lap = Lap.new( lap_name )
if @laps.empty?
puts "Stopwatch started at #{lap.time}"
else
last_lap = @laps.last
elapsed = lap.time - last_lap.time
puts "+#{(elapsed*10).round/10.0}s to #{lap_name}" # +
" (since #{last_lap.name})"
end
@laps << lap
end
def self.time( lap_name )
yield
self.mark lap_name
end
def self.stop
now = Time.new
elapsed = now - @laps.first.time
puts "Stopwatch stopped at #{now}; #{(elapsed*10).round/10.0}
s elapsed"
end
end