On May 1, 2005, at 8:55 PM, Gavin Kistner wrote: > Following is my solution to the Barrel of Monkeys quiz. Here is my solution. It's not terribly clever. I basically punt on the whole weird names issue, for example. I ran out of time to even handle the situation where there is no path. (Haven't found an example of this yet with the default song list.) Perhaps the only point of interest here is that I search from both ends of the list simultaneously. I branch forward from the start song and backwards from the end song, until the branches meet. I did this to keep the search space as small as possible, for as long as possible. It does find the shortest list. James Edward Gray II #!/usr/local/bin/ruby -w require "rexml/document" # Global song list. $songs = [ ] # A simple data class for representing songs. class Song # Create an instance of Song from _title_, _artist_, and _duration_. def initialize( title, artist, duration ) @title, @artist, @duration = title, artist, duration end # Readers for song details. attr_reader :title, :artist, :duration # This method returns true if this Song's _title_ makes sense in a "Barrel # of Monkeys" playlist. def for_barrel?( ) @title =~ /[A-Za-z0-9]/ end # Returns the first letter or digit in a Song _title_. def first( ) @title[/[A-Za-z0-9]/].downcase end # Returns the last letter or digit in a Song _title_. def last( ) @title[/[A-Za-z0-9](?=[^A-Za-z0-9]*$)/].downcase end # Convert to user readable display. def to_s( ) "#@title by #@artist <<#@duration>>" end # For camparison. All attributes must match. def ==( other ) to_s == other.to_s end end # This object represents a node in a "Barrel of Monkeys" playlist tree. Each # of these nodes has a Song associated with it, Songs that can be played next, # and a previously played Song. class BarrelOfMonkeysTreeNode # Create an instance of BarrelOfMonkeysTreeNode. You must pass a _song_ for # this node, but _previous_ is optional. def initialize( song, previous = nil ) @song, @previous = song, previous @next = [ ] end # The song held by this node. attr_reader :song # The Song played before this Song. attr_reader :previous # Adds _next_song_ to the list of Songs that can be played next for this # node. Returns, the new Song's node. def add_next( next_song ) new_node = self.class.new(next_song, self) @next << new_node new_node end # For node comparison. Nodes are equal if they hold the same Song. def ==( other ) @song == other.song end end # This class holds an expandable tree of Songs for a "Barrel of Monkeys" # playlist. The tree can grow forward or backward, from the starting Song. class BarrelOfMonkeysTree # Create an instance of BarrelOfMonkeysTree. The _song_ parameter will be # used as the root of this tree. If _forward_ is set to true, the tree will # grow down the playlist from the Song. If not, growth will be towards # preceeding Songs. def initialize( song, forward = true ) @root = BarrelOfMonkeysTreeNode.new(song) @leaves = [@root] @forward = forward end # For internal use only. Allows other trees to compare _leaves_. attr_reader :leaves protected :leaves # This method will fill in the next set of branches for this tree, expanding # the search. def grow( ) new_leaves = [ ] @leaves.each do |leaf| if @forward search = lambda { |song| leaf.song.last == song.first } else search = lambda { |song| leaf.song.first == song.last } end $songs.find_all(&search).each do |next_song| new_leaves << leaf.add_next(next_song) end end @leaves = new_leaves end # Returns the generated playlist of Songs, in order to be played. The # playlist will begin with the Song initially used to build the tree and end # with the provided _end_node_. Note that this will order will be backwards # from how the Songs would play unless _forward_ is +true+ for this tree. def playlist( end_node ) current = @leaves.find { |leaf| leaf == end_node } nodes = [ current ] while current previous = current.previous nodes << previous current = previous end songs = nodes.compact.map { |node| node.song } if @forward songs.reverse else songs end end # This method returns a true value if the end points of this tree and the # provided _other_ tree intersect. That true value is the node of their # intersection. def touch?( other ) common_leaves = [ ] other.leaves.each do |leaf| @leaves.include?(leaf) and common_leaves << leaf end if common_leaves.size > 0 common_leaves.first else false end end end #:enddoc: if __FILE__ == $0 # Read song list. puts puts "Reading library file..." xml = File.open("SongLibrary.xml", "r") { |file| REXML::Document.new(file) } xml.elements.each("Library/Artist") do |artist| artist.elements.each("Song") do |song| $songs << Song.new( song.attributes["name"], artist.attributes["name"], song.attributes["duration"] ) $songs.pop unless $songs[-1].for_barrel? end end # Locate start and end songs. start = $songs.find { |song| song.title.downcase.index(ARGV[0].downcase) } finish = $songs.find { |song| song.title.downcase.index(ARGV[1].downcase) } raise "Couldn't find #{ARGV[0]} in song list." if start.nil? raise "Couldn't find #{ARGV[1]} in song list." if finish.nil? puts puts "Start song: #{start}" puts " End song: #{finish}" # Search for playlist. puts puts "Building playlist..." if start == finish songs = [start] elsif start.last == finish.first songs = [start, finish] else start = BarrelOfMonkeysTree.new(start) finish = BarrelOfMonkeysTree.new(finish, false) until (join_node = start.touch?(finish)) start.grow finish.grow end songs = start.playlist(join_node) songs.push(*finish.playlist(join_node)).uniq! end # Show playlist. puts songs.each_with_index { |song, index| puts "#{index + 1}: #{song}" } puts end