[Kc] February's Puzzle: 100 Monkey's Redux

[Garrett Goebel]

100 Monkeys Redux: 2003-02-11

Credit: The following puzzle is loosely based on a problem from one of the
ACM International Collegiate Programming Contests.


[- Problem -]

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.

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.

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.

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.

  (1) -> (2) -> (3) -> (4) -> (5) -> back to (1)

  (1) -> (2) -> (3) -> back to (1),  (4) -> (5) -> back to (4)

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.  The script will accept multiple dance requests. For each case
print the maximum possible number of beats on a separate line.

Example:
  >dance.pl 5 8
  6
  15
  >


[- Prize -]

Choice from our library of O'Reilly book to

o  randomly selected entrant with valid solution
o  fastest script to caclulate the correct output
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.pm.org/pipermail/kc/attachments/20030212/8081ce00/attachment.htm