[SOLUTION] Barrel of Monkeys (#30)

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