The 100 prison doors problem

ruby_booby · #1 08-Nov-2005, 15:10

after getting such great help last time, im back for some more

I am trying to create a solution to this problem, if you are not familiar with it i have found an explaination online:

http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml

it is the third puzzle down called "CIRCULAR JAIL CELL"

here is the code i have written but i cant figure out why it does not work:

CPP / C++ / C Code:


#include <stdio.h>

int door_array[101] = {1};
int i;
int y;
int z;


int main()
{

printf("Prison Doors\n");
printf("============\n");


for (y=1;y<=100;y++){
     
  
   for(i=y;i<=101;i=i+y){
       
       
       if(door_array[i] = 1){
          
           door_array[i] = 0;
           
           }else{
               
            
               door_array[i] = 1;
                
               }
   }
   
 
}


for(z=0;z<=101;z++){
    
    if(door_array[z] = 1){
        
        printf("%d Door No.  %d  is open\n", z, door_array[z]);
        
        }
    
}


getchar();
}

and the output i get is the following a hundred times

Code:


Door No.  1  is open

as i said last time i was here i am new to c so any help would be greatly appreciated.

thanks

r_b

Guidelines Plz · #2 08-Nov-2005, 16:46

Quote:

Originally Posted by ruby_booby

after getting such great help last time, im back for some more

And we're glad to have you back...

As Paramesh mentioned last time, you need to read the Guidelines. They explain:
Guideline 1) The proper code tags to use
Guideline 2) What you should tell us so we can help fast and accurately

Give us a synopsis of the problem being solved. Including a link is good for additional info, but the jist of the problem should be in the post.

davekw7x · #3 08-Nov-2005, 16:52

Quote:

Originally Posted by ruby_booby

CPP / C++ / C Code:


       
       if(door_array[i] = 1){
          
  
    if(door_array[z] = 1){

and the output i get is the following a hundred times

Code:


Door No.  1  is open

One of the easiest mistakes to make (and if I had a nickel for every time I have done this, I would have --- well more than a nickel)

you want

CPP / C++ / C Code:


  if (door_array[z] == 1)

There are a couple of "minor" mistakes, but it's a pretty good start. I can come pretty close to saying that like it.

I think you mean to check cell number 1 to 100, but the inner loop goes from 1 to 101. Then at the very end, you go from 0 to 101. Check it carefully. The array itself goes from 0 to 100 (and you can ignore 0 if you like to count like most of us humans to --- starting at 1).

As for your algorithm, I think you just about have it.

Regards,

Dave

WaltP · #4 08-Nov-2005, 17:07

Quote:

Originally Posted by ruby_booby

after getting such great help last time, im back for some more

I am trying to create a solution to this problem, if you are not familiar with it i have found an explaination online:

http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml

it is the third puzzle down called "CIRCULAR JAIL CELL"

here is the code i have written but i cant figure out why it does not work:

CPP / C++ / C Code:

#include <stdio.h>
int door_array[101] = {1};
int i;
int y;
int z;

int main()
{
    printf("Prison Doors\n");
    printf("============\n");

    for (y=1; y<=100; y++)
    {
        for (i=y; i<=101; i=i+y)
        {
            if (door_array[i] = 1)
            {
                door_array[i] = 0;
            }
            else
            {
                door_array[i] = 1;
            }
        }
    }

    for (z=0; z<=101; z++)
    {
        if(door_array[z] = 1)
        {
            printf("%d Door No.  %d  is open\n", z, door_array[z]);
        }
    }

    getchar();
}

CPP / C++ / C Code:

if(door_array[z] = 1)

should be

CPP / C++ / C Code:

if(door_array[z] == 1)

You assigned 1 to door_array[z] instead of comparing.

Another thing to consider is to write the program based on door_array[100] (0-99) as C likes it, then in the printf() add 1 for the display. You have problems dealing with the 0 vs. 1 starting point of your doors.

I also formatted the code you posted so it's more readable. Check out this info for other formatting options.

The difficulty I see with the problem statement is during one cycle do you operate on fully 100 doors, or once around until you pass door 100?

ruby_booby · #5 09-Nov-2005, 13:16

i only provided the link cos i think itll explain it better than i can but here goes:

There are 100 prison cell doors and 100 wardens. At the beginning of the day the prison doors are closed. When warden 1 arrives he will open any closed doors and close any open doors, as they are all closed he will open them all, starting at door one.

When warden 2 arrives he does the same (opens closed doors or closes open doors) except he starts at door 2 and then up through the doors in multiples of 2 -> 2, 4, 6, 8, 10...

When warden 3 arrives he starts on door 3 then 6, 9, 12 and so on..

I wont go any further im sure you get the idea now. So basically at the end i want to find out which doors are still open.

This is why i have the two loops - the first represents the wardens and the second represents their relevant doors.

At the end im am trying to print out which doors are open in the array - is c like php in that you can print out the index and the value for that index from an array?

for instance

door_array[5] = 1 could be presented as

door 5 is open

i hope that makes sense.

r_b

davekw7x · #6 09-Nov-2005, 13:28

Quote:

Originally Posted by WaltP

The difficulty I see with the problem statement is during one cycle do you operate on fully 100 doors, or once around until you pass door 100?

I thought it was pretty clear:
Cycle 1: start at 1, open doors 1, 2, 3, ..., 98, 99, 100 (so now they are all open)

Cycle 2: start at 2, close doors 2, 4, 6, ..., 96, 98, 100 (so now, even numbers are closed, the rest are open)

Cycle 3: start at 3, toggle doors 3, 6, 9, ..., 90, 93, 96, 99 (no more narrative: you are on your own)

Cycle 4: start at 4, toggle doors 4, 8, 12, ..., 88, 92, 96, 100

etc.

Now, verify the program by testing against the (intuitively obvious) actual results:

If you run N cycles with N cells in the above described manner, the doors that will be open at the end are those whose cell number has an integer square root.

Output for N = 100:

Code:

cell number     1 is open:   sqrt(1)     =    1
cell number     4 is open:   sqrt(4)     =    2
cell number     9 is open:   sqrt(9)     =    3
cell number    16 is open:   sqrt(16)    =    4
cell number    25 is open:   sqrt(25)    =    5
cell number    36 is open:   sqrt(36)    =    6
cell number    49 is open:   sqrt(49)    =    7
cell number    64 is open:   sqrt(64)    =    8
cell number    81 is open:   sqrt(81)    =    9
cell number   100 is open:   sqrt(100)   =   10

After circuit number 100: total number open = 10

Try it for 1000. Try it for 12345. Etc. (For N = 12345678, the highest open door at the end is for cell number 12341169, and you see the squares of the 1, 2, 3, ..., 3513.)

This is a very practical problem if you ever find yourself in a jail with a drunken jailer and you can talk him/her into playing the game (just be sure that you remember the valuable lesson learned today).

Regards,

Dave

"The purpose of computing is insight, not numbers."
---Richard W. Hamming

davekw7x · #7 09-Nov-2005, 16:17

Quote:

Originally Posted by ruby_booby

i only provided the link cos i think itll explain it better than i can but here goes:

At the end im am trying to print out which doors are open in the array - is c like php in that you can print out the index and the value for that index from an array?

for instance

door_array[5] = 1 could be presented as

door 5 is open

i hope that makes sense.

r_b

It makes perfect sense.

Your original program was almost right, as I mentioned. Change the two places where you had

CPP / C++ / C Code:

  if (something = something_else)

to

CPP / C++ / C Code:

if (something == something_else)

.

Clean up your loops so the place where you have lower limit set to zero, make the lower limit one. And in the place where you had the upper limit set to 101, set the upper limit to 100.

Your approach to the program and your explanation make me think that we both see it the same way.

There are a few style issues, but I don't want to insist on any changes other than what it takes to make it work and to make it legal.

Regards,

Dave

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Graphic problem in Unreal Tournament 2004	zerox	Computer Software Forum - Games	10	09-Oct-2005 12:31
Runtime Problem involving "printf" in C Program	supamakia	C Programming Language	2	09-Oct-2005 10:09
a significant problem after installing Xp	mohammad	Computer Software Forum - Windows	10	09-Aug-2005 07:03
String problem	vaha	C Programming Language	3	24-May-2005 18:21
Another FX 5600 problem (but with details that might shed light on this)	BobDaDuck	Computer Hardware Forum	2	16-Apr-2004 07:53

The 100 prison doors problem

Re: The 100 prison doors problem

Re: The 100 prison doors problem

Re: The 100 prison doors problem

Re: The 100 prison doors problem

Re: The 100 prison doors problem

Re: The 100 prison doors problem