Thread: 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?

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,