Open lockers problem - can't use arrays. I'm lost!

[DavidGambino]

Hi all,

I was given the following assignment and have been stuck on it for a while, I am slowly losing my mind.

A high school has 1000 students and 1000 lockers, one locker for each student. On the first day
of school, the math teacher plays the following game; she asks
- The first student to go and open all the lockers.
- The second student to go and close all the even-numbered lockers.
- The third student to check every third locker. If it is open, the student closes it; if it is
closed, the student opens it.
- The fourth student is asked to check every fourth locker. If it is open, the student closes
it; if it is closed, the student opens it.
- The remaining students continue this game. In general the nth student checks every nth
locker. If it is open, the student closes it; if it is closed, the student opens it.
After all the students have taken their turn, some of the lockers are open and some are closed.
Write a program that prompts the user to enter the number of lockers in the school. After the
game is over, the program outputs the number of lockers that are open.

This is what I have so far.

int main()
{
	bool closed = true;
	int lockers, student, visits=0, openlockers=0;

	cout << "Enter how many lockers: ";
	cin >> lockers;

	for (student = 1; student < lockers; student++)
		for (int i = 0; i < lockers; i += student)
			while (lockers%student == 0)
				visits++;
			if (visits % 2 == 1) //since all numbers with an odd amount of factors will be left open
				openlockers++;
	cout << openlockers;
}

Not sure if I'm getting there or I'm far off, but everywhere I look I'm told to use arrays which my class has not covered yet. I'm meant to use nested for loops.

Any help is much appreciated. Let me know if I'm on the right track or should scrap what I have (already have several times).

Thanks!
DG

[Esslercuffi]

you'll need to reset your visits counter to 0 for each locker.

if you're concerned if the logic is sound, write a version that uses arrays and compare the results of both methods.

also, you need a set of {} for the for loops, otherwise the if() will not be evaluated when you think is is here.

This is how what you currently have actually looks properly formatted:

int main()
{
	bool closed = true;
	int lockers, student, visits = 0, openlockers = 0;

	cout << "Enter how many lockers: ";
	cin >> lockers;

	for( student = 1; student < lockers; student++ )
		for( int i = 0; i < lockers; i += student )
			while( lockers%student == 0 )
				visits++;
	if( visits % 2 == 1 ) //since all numbers with an odd amount of factors will be left open
		openlockers++;
	cout << openlockers;
}

this is what you're trying to do (I think):

int main()
{
	bool closed = true;
	int lockers, student, visits = 0, openlockers = 0;

	cout << "Enter how many lockers: ";
	cin >> lockers;

	for( student = 1; student < lockers; student++ )
	{
		for( int i = 0; i < lockers; i += student )
		{
			while( lockers%student == 0 )
				visits++;
			if( visits % 2 == 1 ) //since all numbers with an odd amount of factors will be left open
				openlockers++;
		}
	}
	cout << openlockers;
}

Also your while() loop is infinite. That should be an if().

[Esslercuffi]

if I've modified your code to correctly reflect what you were trying to do, then there's some serious problems there

#include <iostream>
#include <string>

using namespace std;

int main()
{
	bool closed = true;
	const int lockers = 1000;
	int student, visits = 0, openlockers = 0;

	//cout << "Enter how many lockers: ";
	//cin >> lockers;

	for( student = 1; student < lockers; student++ )
	{
		visits = 0;
		for( int i = 0; i < lockers; i += student )
		{
			if( lockers%student == 0 )
				visits++;
			if( visits % 2 == 1 ) //since all numbers with an odd amount of factors will be left open
				openlockers++;
		}
	}
	cout << openlockers << endl;



	openlockers = 0;
	bool doors[lockers]; // true = open
	for( int i = 0; i < lockers; i++ )
		doors[i] == true;

	for( student = 1; student < lockers; student++ )
	{
		for( int i = student-1; i < lockers; i += student )
		{
			doors[i] = !doors[i]; // open or close the door
		}
	}
	for( int i = 0; i < lockers; i++ )
		if( doors[i] )
			openlockers++;

	cout << openlockers << endl;

}

Output:

1171
968

[DavidGambino]

Thanks a lot for you help so far. I ended up figuring my old approach wasn't really getting me anywhere so I took on a new one and I'm still having trouble.

int main()
{
	int lockers, student, currentlocker, lockersOpened;
	bool openlocker = true;    //default true cause I chose to ignore the first student (opens all lockers)

	cout << "Enter how many lockers: ";
	cin >> lockers;

	for (student = 2; student < lockers; student++)
		for (lockersOpened=0; openlocker==true; lockersOpened++)
			for (currentlocker = 0; currentlocker < lockers; currentlocker += student)
				openlocker = !openlocker;

	cout << counter << endl;

}

However now I'm getting an output of 0 no matter what I enter. For all I know this will output something even further off!

[Esslercuffi]

Interresting problem. Here's my first stab at fixing it... doesn't work.

	for( int i = 0; i < lockers; i++ ) // each locker
	{
		visits = 0;
		for( student = 1; student < lockers; student++ )
		{
			if( i % student == 0 )
				visits++;
		}
		if( visits % 2 == 1 ) //since all numbers with an odd amount of factors will be left open
			openlockers++;
	}

[Esslercuffi]

nailed it:

	bool open = true;
	for( int i = 0; i < lockers; i++ ) // each locker
	{
		open = true;
		for( student = 1; student < lockers; student++ )
		{
			if( i % student == 0 )
				open = !open;
		}
		if( open )
			openlockers++;
	}

at least it agrees with my array example.

[DavidGambino]

I got the reverse (output closed lockers) but i switched it around and this seems to work:

int main()
{
	int lockers, student, currentlocker, counter=0, visits = 0;
	bool closed = true;

	cin >> lockers;

	for (int i = 0; i < lockers; i++) // each locker
	{
		visits = 0;
		closed = true;
		for (student = 1; student < lockers; student++)
		{
			if (i % student == 0)
				closed = !closed;
		}
		if (!closed)
			counter++;
	}

	cout << counter;
}

.
Thanks a ton man, I would've been stuck on this for ages. Learned from your corrections, A+

[Esslercuffi]

The only problem I see with what you have is that they doors all start closed, and the instructions state that the first student opens all of them. This is also why we start counting students at 1 rather than 0.
It's really just a matter of variable naming. All the logic is the same, just changing the name form 'closed' to 'open' makes it a little clearer. Or change line 11 to 'closed = false'

[Esslercuffi]

Just thought of a logic error in my solution above. The if( i % student == 0 ) check is going to be off because we're not checking 1-1000 students, we're checking 0-999 students. The problem was also present in my array example.

Here's the fix:

#include <iostream>
#include <string>

using namespace std;

int main()
{
	const int lockers = 1000;
	int student = 0, openlockers = 0;

	//cout << "Enter how many lockers: ";
	//cin >> lockers;

	bool open = true;
	for( int i = 1; i <= lockers; i++ ) // each locker
	{
		open = true;
		for( student = 2; student <= lockers; student++ )
		{
			if( i % student == 0 )
				open = !open;
		}
		if( open )
			openlockers++;
	}

	cout << openlockers << endl;



	openlockers = 0;
	bool doors[lockers + 1]; // true = open
	doors[0] = false; // this door will be ignored
	for( int i = 1; i <= lockers; i++ )
		doors[i] = true;

	for( student = 2; student <= lockers; student++ )
	{
		for( int i = student; i <= lockers; i += student )
		{
			doors[i] = !doors[i]; // open or close the door
		}
	}
	for( int i = 1; i <= lockers; i++ )
		if( doors[i] )
			openlockers++;

	cout << openlockers << endl;

}

[keskiverto]

Note:

arrays which my class has not covered yet

const int lockers = 1000;
bool doors[lockers + 1];

The above is standard C++, but the next is not:

int lockers;
cin >> lockers;
bool doors[lockers + 1]; // error 

The array doors is allocated statically, i.e. the compiler has to create the instructions for allocating the array already during compilation, but the size (lockers) is not known before the program runs. That is a no.

The solution is to allocate memory dynamically, during runtime. There are low-level means (which you are likely see on the course), but you should learn to prefer the standard library alternative for dynamic array:

std::size_t lockers;
cin >> lockers;
std::vector<bool> doors( lockers + 1, true );

(A bonus is that these doors are all open to start with.)

[Esslercuffi]

which is why the cin>> stuff is commented out. in the OPs post, his program needs to take the input and do the calculation without using arrays. I changed it to const int and made the array code as a logic check on the non-array algorithm. What he turns in will not contain the array part at all.

[PCrumley48]

A high school has 1000 students and 1000 lockers, one locker for each student.

. . . .

Write a program that prompts the user to enter the number of lockers in the school.

To quote Mr. S; "That is illogical -- the number of lockers has already been defined, as well as the number of students."

[PCrumley48]

Working it out in excel - every locker having a number that is a perfect square is open, all others closed.

Lockers 1, 4, 9, 16, 25, 36, 49 etc. are open, for example.

Backtracking from there, maybe you can find an iterative routine that avoids arrays.

[Esslercuffi]

"every locker having a number that is a perfect square is open, all others closed."
What's the reasoning behind that?

And I already got the routine without arrays. it's the top part of my above code.

[dhayden]

The key to doing this without arrays is recognizing that you need to look at each locker and see how many students open/close it. In other words, the outer loop is for the lockers and the inner loop is for the students. Esslercuffi's solution does this.

[DavidGambino]

Just thought of a logic error in my solution above. The if( i % student == 0 ) check is going to be off because we're not checking 1-1000 students, we're checking 0-999 students. The problem was also present in my array example.

[...]

Somebody give this man a cookie. Seriously, thanks a ton.

[...]

To quote Mr. S; "That is illogical -- the number of lockers has already been defined, as well as the number of students."

I think it's fairly obvious that the bit with the constant lockers/students is just an example to help better understand the situation...


To everybody else who posted, thank you very much.
Esslercuffi gave me the answer and the rest of you helped me really understand where my logic went wrong. Much appreciated!

[PCrumley48]

I just wrote a 100 x 100 matrix in Excel using the logic of the initial problem - at the end, by using a true/false comparison, only the 1,4,9,16,25,36, 49 ,64, 81 and 100 doors were open. I haven't worked out the math on this, but it's got to do with the progression:

For doors 1 through 4, for example:

The first student opens all four, the second one closes door 2 and four. The third one ignores four, the fourth one opens it, and everyone else bypasses it. You can keep on doing this with a table full of coins - heads are open, tails are closed.

Assuming the number of students and doors are equal, only the integer-squared doors will be open.

So if there are 1000 students and 1000 doors, after all the students have finished there will be 31 doors open. (31 * 31 = 961, 32* 32 = 1024) If your program shows more or fewer than 31, something is wrong.

[keskiverto]

Beautiful, absolutely beautiful (and fun).

At first one is inclined to ponder: Which doors does student S touch?

That is fine and dandy, but requires an array. Then we discover that you can turn the question around (like Esslercuffi did show):

Which students touch door N?

No array needed. One can even neatly encapsulate the question into a predicate function:
bool isOpen( int doorNumber );

PCrumley48 is right though, there is a mathematical way to proof the squares. Primes. Think our naive primes and how we usually make them a bit smarter. This problem is closely related. As a result, the isOpen() can be discarded.

All the "complex" loops can suddenly be replaced with different complex loop:

size_t doors;
cin >> doors;
cout << static_cast<size_t>( sqrt( doors ) );

That has only two obvious hazards:
1. Can you explain to the teacher why and how that does "the Right Thing"?
2. Could the floating point math round you into Davy Jones' locker?


An apparently trivial assignment has many solutions, and the leap to the last algorithm demonstrates that good old "Why is there math in school?"

Beautiful.

[dhayden]

Dang! Even the loops can be replaced. There is a formula for the sum of the first N squares, so the original problem (how many doors are open with N students and N lockers) can computed directly from N.

OP, this is an example of how a program can be 50 lines of comments and 1 line of code. Figure out the math involved and then explain that in your comments. Then the code becomes about 3 lines.

[PCrumley48]

Proof of squares:

1. Each locker may only be altered by a student whose number is a factor of the locker number.
2. Each time a locker is touched (starting with student 1 and all lockers closed), it changes state.
Therefore, the only lockers to remain open will be those touched an odd number of times.
3. Only numbers that are perfect squares have an odd number of distinct factors:
for each factor, there must be another factor with which it can be multiplied to result in the original number:
for example (n = 36)
1 x 36
2 x 18
3 x 12
4 x 9
6 x 6 the second six is not distinct, so the count of distinct factors is 9 (odd number) and 36 is therefore a square.

So one minimum program not involving FP math rounding errors is:

int lockers(0);
cin >> lockers;
for (int i = 0; lockers >= i*i; i++);
cout << "Open lockers: " << i -1;