Weblogism

The (Silly) Locker Problem

This problem is a recurrent one in the Java forum: the locker problem. Imagine the scene: one morning, the principal decides to carry out an experiment with the 1,000 lockers, and her 1,000 students: she asks student 1 to go down and open all lockers; student 2 to close every second lockers; student 3 to go through every third locker, and close it if it’s open, or open if it’s closed (student 3 must be passably more intelligent than his 2 previous friends), etc. ; student n to go through every n locker, and open it if it’s closed, or close it if it’s open.

The question is, how many lockers are open after the 1,000 students have completed their stupid task? (and do they get extra points at the end of the year?).

The code solution is pretty simple: you just need to loop through every student, and for every locker, if the student number divides the locker number (i%n == 0), just revert the locker state by not’ing the boolean. All that remains is to count the true in the aray.

public class Lockers {
    public static void main(String[] args) {
	final int lockersNumber = 100;

	// All lockers are closed at beginning of this silly experiment.
	boolean[] lockers = new boolean[lockersNumber];
	// Students
	for (int n = 1; n <= lockersNumber; n++) {
	    // Lockers
	    for (int i = 1; i <= lockersNumber; i++) {
		if (i%n == 0) {
		    lockers[i-1] = !lockers[i-1]; 
		}
	    }
	}

	// Let's now check how many lockers are open
	int openLockers = 0;
	for (int i = 0; i < lockersNumber; i++) {
	    if (lockers_) {
		openLockers++;
	    }
	}

	System.out.println(openLockers);
    }
}

The code above just simulates the students going down the hall, and opening and closing the lockers. But this exercise is also a mathematical one, whose result is pretty much well known: the number of open lockers is the number of squares below the total number of lockers. For example, below 1,000, with Ruby, we find:

irb(main):001:0> puts (1..1_000).to_a.select{ |n| Math.sqrt(n).floor == Math.sqrt(n) }.size
31

There are 31 squares. Which happens to be the solution returned by the Java class defined above. Fewww!