# 1000 Lockers Problem

• 11-20-2003
Hexxx
1000 Lockers Problem
Hey, I have a question to solve.
There are 1000 lockers all in a row, all closed at first.
Starting at the second locker and going to all even no. lockers, open it if closed (and close it if open).
Then start at the 3rd locker (opening if closed, closing if open) and going to the 6th...9th...
Then starting at the 4th locker and going on. (4th, 8th, 12th...)
Then the 5th...going...

I'm suppose to know how many lockers are open and closed after going through all the recursions.

This is what I have so far
btw, what is "unreachable code?"

Code:

```#include <stdio.h> #include <conio.h> #define OPEN 1 #define CLOSE 0 #define LAST 1000 void main (void) { int locker[1001]; int close_count=0, open_count=0; int i, a, start, j, n, p, z=1; locker[0]=-1; for (i=1; i<=LAST; i++) locker[1]=0; for (start=2; start<=LAST; start++) {         for (j=start; j<=LAST; j=((z++)*j)) {                 if (LAST%j==0) {                         for (n=j; j<=LAST; j++) {                                 if (locker[j]==CLOSE) locker[j]=OPEN;                                 if (locker[j]==OPEN) locker[j]=CLOSE;}                                 }                 else                         {for (n=j; j<=((LAST%j)*j); j++) {                                 if (locker[j]==CLOSE) locker[j]=OPEN;                                 if (locker[j]==OPEN) locker[j]=CLOSE;}                 }         } } for (a=1; a<=LAST; a++) {         if (locker[a]==0) close_count++;         if (locker[a]==1) open_count++;         } printf ("Number of open lockers are %d", open_count); printf ("Number of close lockers are %d", close_count); }```
• 11-20-2003
Dave_Sinkula
>btw, what is "unreachable code?"
Code:

`for (i=1; 1<=LAST; i++) locker[1]=0;`
When is one not less than 1000?
• 11-20-2003
Hexxx
darn! ok, I changed that 1 to a i, but still doesn't work. :(
• 11-20-2003
linuxdude
This might work I don't have a compiler on me to test but here is the gerneral algorythm. Maybe atleast i probably have a major flaw.
Code:

```#inlcude <stdio.h> int main(void){         int x, locker[1000];         int shift=2;         do{                 for(x=0;x<1000;x++)                         locker[x]=0;                 for(x=shift;x<1000;x+=shift){                         if(locker[x]==1)                                 locker[x]=0;                         else                                 locker[x]=1;                 }                 shift++;         while(shift!=1000);         return 0; }```
This is also the first time I found a use for the do while loop:-)
• 11-20-2003
Hexxx
what does

int shift=2;

do?
• 11-20-2003
linuxdude
that is the variable that tells where to start and how much to increment. You start on 2 and increment by 2 everytime then you start on 3 and increment by 3 everytime.
• 11-20-2003
Sebastiani
Code:

``` #define OPEN 1 #define CLOSED 0 int  main() {  const int total = 1000;    int lockers[total] = { CLOSED };    int index, inc;  int opened = 0, closed = 0;       for(inc = 2; inc != total; ++inc)   {       for(index = inc - 1;  index + inc < total;  index += inc)       {           if(lockers[index] == CLOSED)           lockers[index] = OPEN;           else           lockers[index] = CLOSED;       }   }     for(index = 0; index < total; ++index)   {       if(lockers[index] == OPEN)         ++opened;               else         ++closed;   }    printf("There are %d lockers open and %d closed.\n", opened, closed);  return EXIT_SUCCESS; }```
• 11-21-2003
Hexxx
how come my logic doesn't work?

btw, when I use the code above for 2 lockers, shouldn't I get 1 closed and 1 opened? I get both closed...
• 11-21-2003
DavT
There are a number of reasons for your code not working, but one of the main reasons is here:
Code:

```  // if locker[j] is closed, we open it,   // if locker[j] is already open we leave it that way ...   if (locker[j]==CLOSE) locker[j]=OPEN;   // ... either way when we get to this line locker[j] is   // always open so we close it.   if (locker[j]==OPEN) locker[j]=CLOSE;}```
The result is that we always end up with all the lockers closed.

Here is a corrected C version of Sebastiani's code:
Code:

```#define OPEN 1 #define CLOSED 0 #define N_LOCKERS 1000 int main(void) {   int lockers[N_LOCKERS] = { CLOSED };   int index, inc;   int opened = 0, closed = 0;     for(inc = 2; inc <= N_LOCKERS; ++inc) {     for(index = inc - 1; index < N_LOCKERS; index += inc) {       if (lockers[index] == OPEN)         lockers[index] = CLOSED;       else         lockers[index] = OPEN;     }   }   for(index = 0; index < N_LOCKERS; ++index) {     if(lockers[index] == OPEN)       ++opened;     else       ++closed;   }     printf("There are %d lockers open and %d closed.\n", opened, closed);   return 0; }```
HTH,