<!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>100 Monkeys: Solved</TITLE>
</HEAD>
<BODY>
<P><FONT SIZE=2>100 Monkeys: 2003-01-14 </FONT>
</P>
<P><FONT SIZE=2>[- Problem -]</FONT>
<BR><FONT SIZE=2>There are 100 doors, all closed. In a nearby cage are 100 monkeys. The first monkey is let out, and runs along the doors opening every one. The second monkey is then let out, and runs along the doors closing the 2nd, 4th, 6th,... all the even-numbered doors. The third monkey is let out. He attends only to the 3rd, 6th, 9th,... doors (every third door, in other words), closing any that is open and opening any that is closed. The fourth monkey does the same for the 4th, 8th, 12th, 16th,... doors, opening the closed ones and closing the open ones. The fifth monkey does the same to the 5th, 10th, 15th,... doors, and so on. After all 100 monkeys have done their work in this way, which doors are left open?</FONT></P>
<BR>
<P><FONT SIZE=2>[- Answers -]</FONT>
</P>
<P><FONT SIZE=2>__PAUL_KULCHENKO__</FONT>
<BR><FONT SIZE=2>for$a(1..(@c=(0)x100)){my$b;$c[($b+=$a)-1]^=1 for 1..@c/$a}</FONT>
</P>
<P><FONT SIZE=2>__GENE_DASCHER__</FONT>
<BR><FONT SIZE=2>my %doors;</FONT>
<BR><FONT SIZE=2>my $OPEN=1;</FONT>
<BR><FONT SIZE=2>my $CLOSED=0;</FONT>
<BR><FONT SIZE=2>my $door_string = "";</FONT>
</P>
<P><FONT SIZE=2>for (my $x = 1; $x <= 100; $x++) {</FONT>
<BR><FONT SIZE=2> my $y = $x;</FONT>
<BR><FONT SIZE=2> while ($y <= 100) {</FONT>
<BR><FONT SIZE=2> $doors{$y} = ((defined $doors{$y})</FONT>
<BR><FONT SIZE=2> ? (($doors{$y} == $OPEN) ? $CLOSED : $OPEN)</FONT>
<BR><FONT SIZE=2> : $OPEN);</FONT>
<BR><FONT SIZE=2> $y += $x;</FONT>
<BR><FONT SIZE=2> }</FONT>
<BR><FONT SIZE=2>}</FONT>
</P>
<P><FONT SIZE=2>foreach $door (sort {$a <=> $b} keys %doors) {</FONT>
<BR><FONT SIZE=2> $door_string .= ((($doors{$door} eq $OPEN))</FONT>
<BR><FONT SIZE=2> ? ((($door_string eq "") ? "" : " ") . $door) : "" );</FONT>
<BR><FONT SIZE=2>}</FONT>
</P>
<BR>
<P><FONT SIZE=2>[- Discussion -]</FONT>
<BR><FONT SIZE=2>I found out the probable source of the puzzle: <A HREF="http://olimu.com/Notes/Monkeys&Doors.htm" TARGET="_blank">http://olimu.com/Notes/Monkeys&Doors.htm</A></FONT>
</P>
<P><FONT SIZE=2>Feel free to post questions about why and how the following code does what it is supposed to do. </FONT>
</P>
<P><FONT SIZE=2>I for one was surprised by @c=(0)x100. I thought x 100 could only be used on strings. For instance to get string of 100 0's is</FONT></P>
<P><FONT SIZE=2> $c='0'x100</FONT>
</P>
<P><FONT SIZE=2>I had no idea you could use the syntax Paul provided to initialize an array with 100 scalar zero elements. Add on to that, he wraps the assignment in parens and immediately uses @c in a scalar context which returns the number of elements in the array... which is used to specify the range of the foreach style for loop.</FONT></P>
<P><FONT SIZE=2> for$a(1..(@c=(0)x100))</FONT>
</P>
<P><FONT SIZE=2>The parens avoid an error which would otherwise occur because perl would read something like 1..@c=1 as attempting to modify a range in scalar assignment. So what we wind up with is extremely compact notation for the construction a loop which increments $a from 1 to 100. I'm not sure where I'd necessarily need to use this, but I like it ;)</FONT></P>
<P><FONT SIZE=2>I was also surprised that Paul's answer while both solving the problem and matching the regex I'd specified, was in a totally different format than I'd imagined. Just goes to show what happens when you don't nail down your specs ;)</FONT></P>
<BR>
<P><FONT SIZE=2>[- Algorithmic Solution -]</FONT>
</P>
<P><FONT SIZE=2>All the submissions solved the problem with brute force. I was a bit disappointed that nobody submitted an answer which solved it algorithmically. So I've included one myself below. The trick with 100 monkeys, is to look at the pattern that emerges, recognize that they are perfect squares and figure out why.</FONT></P>
<P><FONT SIZE=2>In case you're still wondering, the doors left open are: 1 4 9 16 25 36 49 64 81 100</FONT>
</P>
<P><FONT SIZE=2>These numbers as you can see are perfect squares. Why? Each door is visited by a limited set of monkeys. The 9th door will be visited by monkeys 1, 3, and 9. Door 10 by monkeys 1, 2, 5, and 10. If you look at that long enough, you'll realize that the monkeys that will visit the door are the monkeys who's number can exactly divide the door's number... the factors. And it just so happens that perfect squares always have an odd number of distinct factors. So it follows that those doors which are numbered with perfect squares will only be toggled an odd number of times. Consequently you can skip the brute force solution and solve it algorithmically with:</FONT></P>
<P><FONT SIZE=2> join' ',map$_**2,1..10</FONT>
</P>
<BR>
<P><FONT SIZE=2>--</FONT>
<BR><FONT SIZE=2>Garrett Goebel</FONT>
<BR><FONT SIZE=2>IS Development Specialist</FONT>
</P>
<P><FONT SIZE=2>ScriptPro Direct: 913.403.5261</FONT>
<BR><FONT SIZE=2>5828 Reeds Road Main: 913.384.1008</FONT>
<BR><FONT SIZE=2>Mission, KS 66202 Fax: 913.384.2180</FONT>
<BR><FONT SIZE=2>www.scriptpro.com garrett at scriptpro dot com</FONT>
</P>
</BODY>
</HTML>