--Apple-Mail-2--609648688
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
	charset-ASCII;
	formatðïwed


On 2.5.2005, at 20:19, James Edward Gray II wrote:

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

And here's mine. Quick hack, but seems to work.

Uses Dijkstra's graph search algorithm with a block-customizable edge 
cost. No much interface to speak of, just finds the shortest (by 
duration) playlist between two random songs. It caches the parsed XML 
song list into songlist.cache and then uses that on subsequent runs, 
since XML parsing was taking a whole lot of time.

Would need some extra fiddling to find a playlist closest to a given 
time by passing the weigher block the current cost and then subtracting 
that from the wanted time to get the weight. Or something like that.


--Apple-Mail-2--609648688
Content-Transfer-Encoding: 7bit
Content-Type: application/octet-stream;
	x-unix-mode44;
	nameonkey_barrel.rb"
Content-Disposition: attachment;
	filenamenkey_barrel.rb

require 'rexml/document'
require 'zlib'
require 'rand'


class Configurable

  def initialize(config  efault_config, &optional_config_block)
    config  efault_config.merge(config)
    config.each{|k,v| instance_variable_set("@#{k}", v)}
    optional_config_block.call(self) if block_given?
  end

  def default_config
    {}
  end

end


class Song < Configurable

  attr_reader :name, :artist, :id, :duration
  
  def find_first_alnum(str)
    (str.match(/[[:alnum:]]/i) || str[0,1]).to_s
  end
  
  def first_letter
    @first_letter || ind_first_alnum(name).downcase
  end
  
  def last_letter
    @last_letter || ind_first_alnum(
                       name.split(/[\(\[]/).first.reverse
                     ).downcase
  end
  
end


class MonkeyBarrel

  attr_accessor :songs
  attr_reader :song_starts, :song_ends

  # Create new MonkeyBarrel that uses the given song list.
  def initialize(songs)
    self.songs  ongs
  end
  
  # Sets @songs to the given value and
  # generates a hashtable of the songs:
  # keyed by the first letter of the song name.
  #
  def songsew_songs)
    @songs  ew_songs
    @song_starts  }
    @songs.each{|song|
      fl  ong.first_letter
      (@song_starts[fl] || ]) << song
    }
  end

  # Search for the shortest playlist that starts with start
  # and ends with goal. If a playlist is found, it is returned in
  # an array. If a playlist can't be found, returns nil.
  #
  # If a weigher block is given, it is used to determine playlist length.
  # If there is no weigher block, the length is determined as amount of
  # songs.
  #
  # Implemented as Dijkstra graph search with some pessimizations.
  #
  def find_playlist(start, goal, &weigher)
    weigher  ambda{ 1 } unless block_given? 
    open  [weigher[start], :start, start]]
    closed  }
    found  oop do
      len, prev, curr  open.shift
      break false unless curr # open heap empty
      oid  urr.object_id
      next if closed[oid]
      closed[oid]  len, prev]
      break curr if curr goal # this is after closed-list insert 
                                 # so that goal goes to closed too
      unless closed[curr.last_letter] and 
             closed[curr.last_letter] < en
        children  @song_starts[curr.last_letter] || []).
                   map{|c| [len + weigher[c], curr, c]} 
        if block_given?
          heap_insert(open, children)
        else
          children.shuffle!
          open.push(*children)
        end
        closed[curr.last_letter]  en
      end
    end
    if found
      compose_path(goal, closed)
    else
      nil
    end
  end

  private
  # Min "heap" insert :P
  def heap_insert(open, inserts)
    inserts.sort!{|a,b| a[0] <b[0]}
    (0...open.size).each{|i|
      open[i,0]  inserts.shift] while not inserts.empty? and 
                                        open[i][0] > inserts.first[0]
      break if inserts.empty?
    }
    open.push *inserts
  end
  
  def compose_path(goal, closed)
    curr  oal
    path  curr]
    loop do
      arr  losed[curr.object_id]
      curr  rr[1]
      break if curr :start
      path << curr
    end
    path.reverse
  end
  
end



# Load song list and find a random playlist.

song_list  il
unless File.exists?("songlist.cache")
  puts "Reading song list from SongLibrary.xml.gz"
  song_list  ]
  doc  EXML::Document.new(
          Zlib::GzipReader.open("SongLibrary.xml.gz"){|f| f.read})
  doc.each_element('Library/Artist'){|a|
    artist  .attributes['name']
    a.each_element('Song') do |e| 
      song_list << Song.new(
        :artist artist,
        :name e.attributes['name'].to_s,
        :id e.attributes['id'].to_s.to_i,
        :duration e.attributes['duration'].to_s.to_i
      )
    end
  }
  puts "Song list read."
  puts "Caching song list to songlist.cache."
  File.open("songlist.cache",'wb'){|f| f.write Marshal.dump(song_list)}
else
  puts "Loading song list from songlist.cache"
  song_list  arshal.load(File.read("songlist.cache"))
end

mb  onkeyBarrel.new(song_list)
s1  ong_list.pick
s2  ong_list.pick

puts
puts %Q(Trying to find playlist from "#{s1.name}" to "#{s2.name}")

playlist  b.find_playlist(s1, s2){|s| s.duration}

if playlist
  puts "", "Found playlist:"
  song_names  laylist.map{|s| s.name}
  longest_song  ong_names.max{|a,b| a.size <b.size}.size
  puts playlist.map{|s|
    raw_seconds  .duration / 1000
    minutes  aw_seconds / 60
    seconds  aw_seconds % 60
    timestr  (#{minutes}:#{seconds.to_s.rjust(2,"0")})"
    "#{s.name.ljust(longest_song)}\t #{timestr.ljust(7)} by #{s.artist}"
  }
else
  puts "No playlist found."
end

--Apple-Mail-2--609648688--