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);
}

---

>btw, what is "unreachable code?"

Code:

---

for (i=1; 1<=LAST; i++) locker[1]=0;

---

When is one not less than 1000?

darn! ok, I changed that 1 to a i, but still doesn't work. :(

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:-)

what does

int shift=2;


do?

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.

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;
}

---

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

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,