From: Ruby Quiz <james@...>
Date: 2005-04-29T21:43:07+09:00
Subject: [QUIZ] Barrel of Monkeys (#30)

The three rules of Ruby Quiz:

1.  Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2.  Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3.  Enjoy!

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Gavin Kistner

Last week one of the local radio stations was having a "Barrel of Monkey"
afternoon. While a song was playing, listeners would call in and suggest the
next song, which had to begin with the same letter as the current song ended in.

So, for example, a sample (eclectic) Barrel of Monkeys playlist might be:

	Peace Train
	No More "I Love You's"
	Super Trooper
	Rock Me, Amadeus
	Song of the South
	Hooked on a Feeling
	Go Tell it on the Mountain
	...
	(See how each song name begins with the last letter of the song before it?)

Just creating ANY playlist would be too easy, however. We need a Worthy Problem
to solve.

	1) Given any starting and ending song, create a playlist that connects the
	   two songs.
	
	2) For extra credit, try to create a playlist of a specific duration (to
	   fill a particular time slot on the radio).
	
	3) For more extra credit, try to find the shortest playlist that links the
	   songs. (Either in terms of number of songs, or total play time.)

You can find an XML file with over 5,000 song names and play time at
http://rubyquiz.com/SongLibrary.xml.gz (100k compressed). The song durations are
in milliseconds.

Finally, because this problem may be enough fun without having to discover
trouble yourself, I offer a few (spoiler?) things to think about below. (Far
below, in case you want to skip them.)

THE END OF THIS QUIZ MENTIONS A FEW PITFALLS THAT I THOUGHT OF WHILE WRITING IT
UP

IT'S UP TO YOU TO DECIDE IF YOU WANT TO READ THEM

I DON'T HAVE ANY DOMAIN KNOWLEDGE IN THIS PROBLEM AREA
AND I HAVEN'T TRIED TO SOLVE THE PROBLEM MYSELF
SO THESE AREN'T SUBTLE NUANCES THAT WILL GREATLY HELP YOU

DO NOT READ ANY FURTHER IF YOU DO NOT WANT TO READ THEM

THERE IS NOTHING MORE OF ANY INTEREST IN THIS QUIZ AFTER THIS TEXT OTHER THAN
THE PITFALLS

SO YOU DON'T NEED TO KEEP READING IF YOU WANT TO THINK ABOUT THE PROBLEM IN A
VIRGIN STATE

I THINK THIS MAY BE ENOUGH OF A WARNING

	* What do you do with songs with names like "'74-'75" or "Seventy Times 7"
	  or "=:0 :("?

	* How about a song named "Candy Everybody Wants (unplugged)" or "Voulez-Vous
	  [Extended Remix, 1979 US Promo]" or "Speed Racer - Hardcore Mix" or
	  "Breathe Remix Feat Sean Paul"?

	* What do you do if there IS no way to connect two songs? (And how do you
	  know for sure?)