<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<HTML>
<HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
<META NAME="Generator" CONTENT="MS Exchange Server version 5.5.2654.45">
<TITLE>February's Puzzle: 100 Monkey's Redux</TITLE>
</HEAD>
<BODY>

<P><FONT SIZE=2>100 Monkeys Redux: 2003-02-11</FONT>
</P>

<P><FONT SIZE=2>Credit: The following puzzle is loosely based on a problem from one of the ACM International Collegiate Programming Contests.</FONT></P>
<BR>

<P><FONT SIZE=2>[- Problem -]</FONT>
</P>

<P><FONT SIZE=2>You've just taken a job as a choreographer for 100 trained dancing monkeys. The monkeys are trained to dance in a manner where each starts by sitting in a different circle and jumps from one circle to the next on the beat of a drum. They determine where to jump by following an arrow from the current circle into the next.</FONT></P>

<P><FONT SIZE=2>Because the monkeys are easily confused, each circle shall have exactly one arrow leading out and one leading in. Likewise, an arrow may not start and end at the same circle.</FONT></P>

<P><FONT SIZE=2>For each performance your eccentric employer will request a different number of monkeys. You will be given an equal number of circles and arrows. Given the already stated constraints you may arrange the circles and arrows as you see fit. Your employer will pay you per beat of the drum until the beat on which all the monkeys have simultaneously returned to their starting circle. At which point the dance ends.</FONT></P>

<P><FONT SIZE=2>For example, listed below is a figure which depicts the 2 possible groupings of circles for a 5 monkey dance. The first will last 5 beats, whereas the second will take 6 beats before all the monkeys are exactly where they started.</FONT></P>

<P><FONT SIZE=2>&nbsp; (1) -&gt; (2) -&gt; (3) -&gt; (4) -&gt; (5) -&gt; back to (1)</FONT>
</P>

<P><FONT SIZE=2>&nbsp; (1) -&gt; (2) -&gt; (3) -&gt; back to (1),&nbsp; (4) -&gt; (5) -&gt; back to (4)</FONT>
</P>

<P><FONT SIZE=2>Your task should you chose to accept it, is to write a Perl script that will determine the maximum number of beats possible for a given number of monkeys.&nbsp; The script will accept multiple dance requests. For each case print the maximum possible number of beats on a separate line.</FONT></P>

<P><FONT SIZE=2>Example:</FONT>
<BR><FONT SIZE=2>&nbsp; &gt;dance.pl 5 8</FONT>
<BR><FONT SIZE=2>&nbsp; 6</FONT>
<BR><FONT SIZE=2>&nbsp; 15</FONT>
<BR><FONT SIZE=2>&nbsp; &gt;</FONT>
</P>
<BR>

<P><FONT SIZE=2>[- Prize -]</FONT>
</P>

<P><FONT SIZE=2>Choice from our library of O'Reilly book to</FONT>
</P>

<P><FONT SIZE=2>o&nbsp; randomly selected entrant with valid solution</FONT>
<BR><FONT SIZE=2>o&nbsp; fastest script to caclulate the correct output</FONT>
</P>

</BODY>
</HTML>