When I code a program, I start out by slapping together the various elements. I setup the variables, I write some quick routines, and I add comments to the tune of /* Do something here*/. With those bricks in place, I go back and fill in the mortar to make it all work. If the code runs, great! That rarely happens, so more work is involved.
For the 100 Doors puzzle, I first created two parts of the program, which I discussed in last week’s Lesson: the array of 100 doors and the routine that opens or closes a door. The steps that remain are processing the puzzle — the loop — and displaying the results.
The loop is the heart of the puzzle, the virtual representation of opening and closing 100 doors. According to the puzzle’s rules, you must visit all doors, 1 through 100. To solve that problem I wrote a prototype loop:
/* start at door 1 and work up to door DOORS */
for(pass=0; pass<DOORS; pass++)
{
door[thisdoor] = !door[thisdoor];
}
The for loop uses the pass (int) variable to process all 100 doors. I tossed the open/close statement into the loop. At this point, the code opens all the doors. (The door[] array is initialized to 0, all doors closed.) So step one of the problem is solved, and my code has a placeholder. At this point, I review the rest of the puzzle, i.e., to skip a given number of doors and continue processing.
So on the second pass, you skip every other door. On the third pass you skip every third door. As I thought of the process, I mapped out the skipping pattern:
First pass, skip 1 door
Second pass, skip 2 doors
Third pass, skip 3 doors
This pattern represents a loop. Indeed, the loop is already in the code:
for(pass=0; pass<DOORS; pass++)My conclusion is that a nested for loop is needed. It can conveniently use the first loop’s pass variable as both the starting point and skip value. Here’s what I came up with:
/* start at door 1 and work up to door DOORS */
for(pass=0; pass<DOORS; pass++)
{
for(thisdoor=pass; thisdoor<DOORS; thisdoor+=pass)
door[thisdoor] = !door[thisdoor];
}
The inner for loop starts at the value of variable pass and processes all the doors, skipping in increments of variable pass in the process. It’s this loop that opens/closes the doors.
To me, this code looked good. I added a simple output routine to display the results:
/* Display results */
for(x=0;x<DOORS;x++)
printf("Door %d is %s\n",
x+1,
door[x] ? "open" : "closed");
I saved. I compiled. I ran. And . . .
It didn’t work. The code generated no output and didn’t stop. I knew it got stuck in an endless loop, but where? So I read the source code again and again.
In my C programming books, I mention reading code aloud as one way to track down bugs. In this case, that method helped me to find the problem, which occurs in the inner for loop: thisdoor+=pass When pass is equal to zero (its starting value), the loop becomes endless; variable thisdoor never increments.
To fix the code, I switched from initializing variable pass at at zero and used 1 instead. Here are the modified nested loop statements:
/* start at door 1 and work up to door DOORS */
for(pass=1; pass<=DOORS; pass++)
{
for(thisdoor=pass-1; thisdoor<DOORS; thisdoor+=pass)
door[thisdoor] = !door[thisdoor];
}
The outer for loop starts at 1. The inner for loop must subtract 1 from pass in order to reference the first element of array door[]. Now the statement thisdoor+=pass properly calculates the skip values.
Click here to see the end result of my efforts.
My solution is rather mundane when compared with other programmers’ solutions. Some coders attempt to optimize the code, some to obfuscate. Mine is rather straightforward and not particularly clever, but more than the solution I wanted to illustrate how I approach such programming puzzles.
By the way, the solution for the 100 Doors puzzle is that after the process is complete, only the door numbers matching the squares of the first 10 numbers remain open: 1, 4, 9, 16, 25, 36, 49, 64, 81, and 100.