# Programming Puzzle 25 - The Great Escape

• 05-30-2012, 08:12 AM
Tom Cone Jr
Programming Puzzle 25 - The Great Escape
' There are 100 prisoners in 100 separate locked cells.
' There are 100 guards who visit the cells during the night.
' The first guard visits all 100 cells.
' The second guard visits every other cell.
' The third guard visits every third cell.
' ... and so on
' Until, finally, the 100th guard visits the 100th cell.
'
' Now here's the catch. When a guard visits a cell he or she
' locks the cell door if it's open, and unlocks the cell door
' if it's locked.
'
' After the last guard has done his duty, prisoners in cells
' with open (unlocked) doors can escape. In the morning,
' how many prisoners have escaped? For extra credit can
' you tell us which cells were left open?
'
' Write your answer to the trace window.
'
' Have fun!
'
' Credit plus.maths.org
• 05-30-2012, 10:25 AM
aschone
Re: Programming Puzzle 25 - The Great Escape
What is the status of the doors prior to the first guard checking?
• 05-30-2012, 10:30 AM
Tom Cone Jr
Re: Programming Puzzle 25 - The Great Escape
Andrew, have a cup of coffee, then read the first line of the puzzle carefully. :grin:

-- tom
• 05-30-2012, 10:34 AM
aschone
Re: Programming Puzzle 25 - The Great Escape
doh! I withdraw my previous question.
• 05-30-2012, 03:56 PM
aschone
Re: Programming Puzzle 25 - The Great Escape
Chances are good my calculation is wrong but I am sure the Professor will be kind enough to correct me.
• 05-30-2012, 05:06 PM
Keith Hubert
Re: Programming Puzzle 25 - The Great Escape
Andy, Looks good to me. However, working it out on paper with only 10 and 10, I get 5 and 5. So I imagine the 50% would be the same for 100 ?
• 05-30-2012, 06:18 PM
aschone
Re: Programming Puzzle 25 - The Great Escape
Second go; first had a few mistakes. Am very curious to see what others come up with for a solution.
• 05-31-2012, 02:52 AM
Keith Hubert
Re: Programming Puzzle 25 - The Great Escape
Hi Andrew,

This looks much better. This puzzle is along the lines of Josephus Problem.
• 05-31-2012, 05:36 AM
GGandhi
Re: Programming Puzzle 25 - The Great Escape
hello
here is my solution. but somehow i am getting 9. i do not know why.

Code:

```dim n as n dim cell[100] as c for n = 1 to 100         cell[n]="locked"         'trace.writeln(cell[n]+crlf())         next n dim guard as n dim pass as n for pass = 1 to 100         for guard = 1 to 100 step pass         if cell[guard]="locked" then             cell[guard]="open"             else             cell[guard]="locked"         end if                 next guard next pass dim open as n=0 dim i as n trace.clear() for i = 1 to 100         if cell[i]="open" then                 trace.writeln("cell number " + i + "was left open")             open = open+1         end if         next                 trace.writeln("Total number of " + open + " prisioners will escape")         'msgbox("Open Cells",str(open) + " Prisioners will escape when all is done")         end```
• 05-31-2012, 06:01 AM
GGandhi
Re: Programming Puzzle 25 - The Great Escape
hello
the cell number 1 should have been left open but in mine it was closed. so i changed to while...end while and now the result is 10, which i think is correct.

Code:

```dim n as n dim cell[100] as c for n = 1 to 100         cell[n]="locked"         'trace.writeln(cell[n]+crlf())         next n dim guard as n dim pass as n pass = 1 while pass < 100         for guard = 1 to 100 step pass         if cell[guard]="open" then             cell[guard]="locked"             else             cell[guard]="open"         end if                 next guard pass = pass + 1 end while dim open as n=0 dim i as n trace.clear() for i = 1 to 100         if cell[i]="open" then                 trace.writeln("cell number " + i + " was left open")             open = open+1         end if         next                 trace.writeln("Total number of " + open + " prisioners will escape")         'msgbox("Open Cells",str(open) + " Prisioners will escape when all is done")         end```
• 05-31-2012, 06:36 AM
Tom Cone Jr
Re: Programming Puzzle 25 - The Great Escape
Gandhi,

The professor applauds your effort, but has a couple of small bones to pick with you.

I don't fully understand his comments, but maybe they'll mean something to you.

Code:

```pass = 1 while pass < 100         for guard = 1 to 100 step pass             if cell[guard]="open" then                 cell[guard]="locked"             else                 cell[guard]="open"             end if         next guard         pass = pass + 1 end while```
1) The professor thinks your While ... End While code block never reaches the 100th guard, since the block is exited when pass equals 100.

2) In the For ... Next block the professor insists that all 100 guards visit door 1, when only guard #1 should visit that cell.

3) The professor applauds your use of the "step" parameter in the For ... Next block. Very clever, grasshopper!
• 05-31-2012, 07:21 AM
Keith Hubert
Re: Programming Puzzle 25 - The Great Escape
Manually I have
1=open
2=locked
3=locked
4=open
5=locked
6=locked
7=locked
8=locked
9=open
and 10 = locked

Which is the same as Andrew's solution. (His is better than mine as it goes all the way).
• 05-31-2012, 07:30 AM
GGandhi
Re: Programming Puzzle 25 - The Great Escape
hello

thanks
i looked at the result of both solutions presented and
the outcome from mine was wrong. while total remains correct.(different prisoners will get out)
will need to clean up the thinking process.

thanks again
• 05-31-2012, 07:31 AM
Tom Cone Jr
Re: Programming Puzzle 25 - The Great Escape
Keith, you're on the right path. Only 90 more guards to go! :eek:
• 05-31-2012, 07:52 AM
Keith Hubert
Re: Programming Puzzle 25 - The Great Escape
All my guards came out on strike!!!
• 05-31-2012, 08:33 AM
Tom Cone Jr
Re: Programming Puzzle 25 - The Great Escape
gandhi,

No problem. That's why they're called "puzzles" !

Have fun sorting it out.

-- tom
• 05-31-2012, 09:07 AM
GGandhi
Re: Programming Puzzle 25 - The Great Escape
okay tom
here is the corrected one

Code:

```dim x as n dim cell[100] as c for x=1 to 100         cell[x]="locked"         next x dim guard as n dim doorNumber as n         for doorNumber = 1 to 100 'guard will visit all the doors                 for guard = 1 to 100                                         if mod(doorNumber,guard)=0 then ' but enter only few                                 if cell[doorNumber]="locked" then                                     cell[doorNumber]="open"                                     else                                     cell[doorNumber]="locked"                                 end if                         end if                 next         next                 dim count as n trace.clear() for i = 1 to 100         if cell[i]="open"                 trace.writeln("Cell number "+ i +" was left open")                 count = count+1         end if next trace.writeln("Total of "+count+" prisoners will escape") 'msgbox("Open cells",str(count)) end```
• 05-31-2012, 09:22 AM
Tom Cone Jr
Re: Programming Puzzle 25 - The Great Escape
gandhi,

Nice!

-- tom
• 05-31-2012, 07:25 PM
Tom Cone Jr
Re: Programming Puzzle 25 - The Great Escape
And, here's Tom's solution.

I used a For ... Next code block with a variable STEP parameter to do the heavy lifting.

• 05-31-2012, 09:35 PM
aschone
Re: Programming Puzzle 25 - The Great Escape
Code:

```if cells[x] = 0 then         cells[x] = 1 else         cells[x] = 0        end if```
I believe all three solutions used something similar to this if..else.. end if.

This could have shortened saving a assignment of the value 0 (locked) to the cell array element. In other words, if the cell is already locked why relock it?

Code:

```if cells[x] = 0 then         cells[x] = 1 end if```
• 06-01-2012, 04:52 AM
Tom Cone Jr
Re: Programming Puzzle 25 - The Great Escape
Andrew, I don't understand your point. I must be missing something. The puzzle specifies that each guard must either open or close (lock or unlock) each cell door he or she visits.
• 06-01-2012, 10:09 AM
StephenP
Re: Programming Puzzle 25 - The Great Escape
Professor:

My simple, uncommented code:

Code:

```dim cellblock[100] as l for g = 1 to 100         for c = 1 to 100 step g                 cellblock[c] = iif(cellblock[c], .f., .t.)         next c next g for c = 1 to 100         iif(cellblock[c],trace.writeln(c+": Open"),"") next c```
and with my comments:

Code:

```'All cellblocks are locked by default (.f.): dim cellblock[100] as l 'work through each of the 100 guards: for g = 1 to 100         'visiting each of the 100 cellblocks:         for c = 1 to 100 step g                 'unlocking, if locked, and vice versa:                 cellblock[c] = iif(cellblock[c], .f., .t.)         'visiting the next cellblock:         next c 'moving on to the next guard: next g 'checking all 100 cellblocks: for c = 1 to 100         'tracing out only the unlocked cells:         iif(cellblock[c],trace.writeln(c+": Open"),"") next c```
In the end, I had nine cellblocks open:

2: Open
5: Open
10: Open
17: Open
26: Open
37: Open
50: Open
65: Open
82: Open

Ah, but what if the guards each started, not at cellblock 1, but cellblock N:

Code:

```'All cellblocks are locked by default (.f.): dim cellblock[100] as l 'work through each of the 100 guards: for g = 1 to 100         'visiting each of the 100 cellblocks:  ***** Note that each guard starts at cellblock N *****         for c = g to 100 step g                 'unlocking, if locked, and vice versa:                 cellblock[c] = iif(cellblock[c], .f., .t.)         'visiting the next cellblock:         next c 'moving on to the next guard: next g 'checking all 100 cellblocks: for c = 1 to 100         'tracing out only the unlocked cells:         iif(cellblock[c],trace.writeln(c+": Open"),"") next c```
Now we end up with ten cellblocks open:

1: Open
4: Open
9: Open
16: Open
25: Open
36: Open
49: Open
64: Open
81: Open
100: Open
• 06-01-2012, 10:12 AM
StephenP
Re: Programming Puzzle 25 - The Great Escape
Professor,

By the way, I didn't look at your result until after I took the test. :smile:
• 06-01-2012, 11:38 AM
Tom Cone Jr
Re: Programming Puzzle 25 - The Great Escape
Stephen,

Very nice! The "professor" likes your second solution. Good work. Hope you enjoyed the exercise!