Alpha DevCon 2018
Results 1 to 24 of 24

Thread: Programming Puzzle 25 - The Great Escape

  1. #1
    "Certified" Alphaholic
    Real Name
    Tom Cone Jr
    Join Date
    Apr 2000
    Location
    Florida
    Posts
    23,300

    Default 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

  2. #2
    "Certified" Alphaholic
    Real Name
    Andrew Schone
    Join Date
    Dec 2005
    Location
    Kansas
    Posts
    1,044

    Default Re: Programming Puzzle 25 - The Great Escape

    What is the status of the doors prior to the first guard checking?
    Andrew

  3. #3
    "Certified" Alphaholic
    Real Name
    Tom Cone Jr
    Join Date
    Apr 2000
    Location
    Florida
    Posts
    23,300

    Default Re: Programming Puzzle 25 - The Great Escape

    Andrew, have a cup of coffee, then read the first line of the puzzle carefully.

    -- tom

  4. #4
    "Certified" Alphaholic
    Real Name
    Andrew Schone
    Join Date
    Dec 2005
    Location
    Kansas
    Posts
    1,044

    Default Re: Programming Puzzle 25 - The Great Escape

    doh! I withdraw my previous question.
    Andrew

  5. #5
    "Certified" Alphaholic
    Real Name
    Andrew Schone
    Join Date
    Dec 2005
    Location
    Kansas
    Posts
    1,044

    Default 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.
    Attached Files Attached Files
    Andrew

  6. #6
    "Certified" Alphaholic Keith Hubert's Avatar
    Real Name
    Keith Hubert
    Join Date
    Jul 2000
    Location
    London, UK
    Posts
    6,930

    Default 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 ?
    Regards
    Keith Hubert
    Alpha Guild Member
    London.
    KHDB Management Systems
    Skype = keith.hubert


    For your day-to-day Needs, you Need an Alpha Database!

  7. #7
    "Certified" Alphaholic
    Real Name
    Andrew Schone
    Join Date
    Dec 2005
    Location
    Kansas
    Posts
    1,044

    Default 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.
    Attached Files Attached Files
    Andrew

  8. #8
    "Certified" Alphaholic Keith Hubert's Avatar
    Real Name
    Keith Hubert
    Join Date
    Jul 2000
    Location
    London, UK
    Posts
    6,930

    Default Re: Programming Puzzle 25 - The Great Escape

    Hi Andrew,

    This looks much better. This puzzle is along the lines of Josephus Problem.
    Regards
    Keith Hubert
    Alpha Guild Member
    London.
    KHDB Management Systems
    Skype = keith.hubert


    For your day-to-day Needs, you Need an Alpha Database!

  9. #9
    "Certified" Alphaholic
    Real Name
    Govindan Gandhi
    Join Date
    Aug 2008
    Location
    New York, NY
    Posts
    4,294

    Default 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
    Last edited by GGandhi; 05-31-2012 at 04:42 AM.
    thanks for reading

    gandhi

    version 11 3381 - 4096
    mysql backend
    http://www.alphawebprogramming.blogspot.com
    ggandhi344@gmail.com
    Skype:ggandhi344@gmail.com
    1 914 924 5171

  10. #10
    "Certified" Alphaholic
    Real Name
    Govindan Gandhi
    Join Date
    Aug 2008
    Location
    New York, NY
    Posts
    4,294

    Default 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
    thanks for reading

    gandhi

    version 11 3381 - 4096
    mysql backend
    http://www.alphawebprogramming.blogspot.com
    ggandhi344@gmail.com
    Skype:ggandhi344@gmail.com
    1 914 924 5171

  11. #11
    "Certified" Alphaholic
    Real Name
    Tom Cone Jr
    Join Date
    Apr 2000
    Location
    Florida
    Posts
    23,300

    Default 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.

    Your code:
    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!

  12. #12
    "Certified" Alphaholic Keith Hubert's Avatar
    Real Name
    Keith Hubert
    Join Date
    Jul 2000
    Location
    London, UK
    Posts
    6,930

    Default 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).
    Regards
    Keith Hubert
    Alpha Guild Member
    London.
    KHDB Management Systems
    Skype = keith.hubert


    For your day-to-day Needs, you Need an Alpha Database!

  13. #13
    "Certified" Alphaholic
    Real Name
    Govindan Gandhi
    Join Date
    Aug 2008
    Location
    New York, NY
    Posts
    4,294

    Default 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
    thanks for reading

    gandhi

    version 11 3381 - 4096
    mysql backend
    http://www.alphawebprogramming.blogspot.com
    ggandhi344@gmail.com
    Skype:ggandhi344@gmail.com
    1 914 924 5171

  14. #14
    "Certified" Alphaholic
    Real Name
    Tom Cone Jr
    Join Date
    Apr 2000
    Location
    Florida
    Posts
    23,300

    Default Re: Programming Puzzle 25 - The Great Escape

    Keith, you're on the right path. Only 90 more guards to go!

  15. #15
    "Certified" Alphaholic Keith Hubert's Avatar
    Real Name
    Keith Hubert
    Join Date
    Jul 2000
    Location
    London, UK
    Posts
    6,930

    Default Re: Programming Puzzle 25 - The Great Escape

    All my guards came out on strike!!!
    Regards
    Keith Hubert
    Alpha Guild Member
    London.
    KHDB Management Systems
    Skype = keith.hubert


    For your day-to-day Needs, you Need an Alpha Database!

  16. #16
    "Certified" Alphaholic
    Real Name
    Tom Cone Jr
    Join Date
    Apr 2000
    Location
    Florida
    Posts
    23,300

    Default Re: Programming Puzzle 25 - The Great Escape

    gandhi,

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

    Have fun sorting it out.

    -- tom

  17. #17
    "Certified" Alphaholic
    Real Name
    Govindan Gandhi
    Join Date
    Aug 2008
    Location
    New York, NY
    Posts
    4,294

    Default 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
    thanks for reading

    gandhi

    version 11 3381 - 4096
    mysql backend
    http://www.alphawebprogramming.blogspot.com
    ggandhi344@gmail.com
    Skype:ggandhi344@gmail.com
    1 914 924 5171

  18. #18
    "Certified" Alphaholic
    Real Name
    Tom Cone Jr
    Join Date
    Apr 2000
    Location
    Florida
    Posts
    23,300

    Default Re: Programming Puzzle 25 - The Great Escape

    gandhi,

    Nice!

    -- tom

  19. #19
    "Certified" Alphaholic
    Real Name
    Tom Cone Jr
    Join Date
    Apr 2000
    Location
    Florida
    Posts
    23,300

    Default 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.

    Comments? Questions? Corrections?

  20. #20
    "Certified" Alphaholic
    Real Name
    Andrew Schone
    Join Date
    Dec 2005
    Location
    Kansas
    Posts
    1,044

    Default 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
    Andrew

  21. #21
    "Certified" Alphaholic
    Real Name
    Tom Cone Jr
    Join Date
    Apr 2000
    Location
    Florida
    Posts
    23,300

    Default 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.

  22. #22
    Member StephenP's Avatar
    Real Name
    Stephen Pilon
    Join Date
    Apr 2000
    Location
    Front Royal, Virginia
    Posts
    490

    Default 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
    Stephen Pilon
    Associate Librarian
    Christendom College

  23. #23
    Member StephenP's Avatar
    Real Name
    Stephen Pilon
    Join Date
    Apr 2000
    Location
    Front Royal, Virginia
    Posts
    490

    Default Re: Programming Puzzle 25 - The Great Escape

    Professor,

    By the way, I didn't look at your result until after I took the test.
    Stephen Pilon
    Associate Librarian
    Christendom College

  24. #24
    "Certified" Alphaholic
    Real Name
    Tom Cone Jr
    Join Date
    Apr 2000
    Location
    Florida
    Posts
    23,300

    Default Re: Programming Puzzle 25 - The Great Escape

    Stephen,

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

Similar Threads

  1. Programming Puzzle 23 - For / Next Loop
    By Tom Cone Jr in forum Xbasic Programming Puzzles
    Replies: 9
    Last Post: 07-18-2012, 06:54 PM
  2. Programming Puzzle 22 - What do you Mean?
    By Tom Cone Jr in forum Xbasic Programming Puzzles
    Replies: 5
    Last Post: 05-23-2012, 07:09 AM
  3. Programming Puzzle 3 - Fractions, anyone?
    By Tom Cone Jr in forum Xbasic Programming Puzzles
    Replies: 7
    Last Post: 11-08-2011, 05:40 AM
  4. Programming Puzzle 21 - Got ini ?
    By Tom Cone Jr in forum Xbasic Programming Puzzles
    Replies: 5
    Last Post: 09-08-2011, 09:19 PM
  5. Programming Puzzle 11 - More Loops
    By Tom Cone Jr in forum Xbasic Programming Puzzles
    Replies: 11
    Last Post: 08-20-2011, 04:50 PM

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •