"Open and closed doors" riddle

Question

Riddle Description:

\$N\$ doors are closed. In the first pass, I open all of them. In the second pass, I toggle every second door. In the third pass, I toggle every third door. I continue this until I have completed the \$N\$th pass. Find all the doors that will remain open after \$N\$ passes.

public static void printDoorsOpened(int passes)
{
        HashMap<Integer, Boolean> doors=new HashMap<Integer, Boolean>();
        int i = 0;
        //Close all doors as default in the start
        while(i < passes)
        {
            doors.put(i, false);
            i++;
        }

        for(int j = 1; j <= passes; j++)
        {
            for(int k = j - 1; k < passes; k += j)
                doors.put(k, !(doors.get(k)));
        }

        for(int l = 0; l < passes; l++)
        {
            System.out.println("The door number "+(l + 1)+" is "+(doors.get(l) == true ? "Opened" : "Closed"));
        }
}

Please feel free to review it based on best practices, style and any other efficient solution, but please refrain from solely style-based reviews.

Answer 1

This looks like something that can get optimized to a mathematical function.

Let's run it pass by pass and try to interpret the result.

N = 12

Doors #1 through #12

Pass 1:  1 1 1  1 1 1  1 1 1  1 1 1 //All opened
Pass 2:  1 0 1  0 1 0  1 0 1  0 1 0 //2, 4, 6, 8, 10, 12 closed
Pass 3:  1 0 0  0 1 1  1 0 0  0 1 1 //3 and 9 closed, 6 and 12 opened
Pass 4:  1 0 0  1 1 1  1 1 0  0 1 0 //4 and 8 opened, 12 closed
Pass 5:  1 0 0  1 0 1  1 1 0  1 1 0 //5 closed, 10 opened
Pass 6:  1 0 0  1 0 0  1 1 0  1 1 1 //6 closed, 12 opened
Pass 7:  1 0 0  1 0 0  0 1 0  1 1 1 //7 closed
Pass 8:  1 0 0  1 0 0  0 0 0  1 1 1 //8 closed
Pass 9:  1 0 0  1 0 0  0 0 1  1 1 1 //9 opened
Pass 10: 1 0 0  1 0 0  0 0 1  0 1 1 //10 closed
Pass 11: 1 0 0  1 0 0  0 0 1  0 0 1 //11 closed
Pass 12: 1 0 0  1 0 0  0 0 1  0 0 0 //12 closed

It's a factor detector!

It detects whether for each positive integer \$N\$ or lower whether its divisible an even or uneven amount of times by its possible factors.

That is, 12 can be factorized as \$1\times 12\$, \$2\times 6\$, \$3\times 4\$, \$4\times 3\$, \$6\times 2\$, \$12\times 1\$. That's even, so the door ends up at 0, which is closed. 9 can be factorized as \$1\times 9\$, \$3\times 3\$ and \$9\times 1\$. That's uneven, so the door ends up at 1, which is opened.

Now, for any factorization \$x\times y\$ of a number, there exists an inverse factorization: \$y\times x\$. Unless \$x\$ equals \$y\$. If that's the case, then there is no inverse factorization because the inverse is the same!

So it's a square root detector! (Any number that has a positive integer as a square root has an uneven number of factorizations, the rest have an even number).

Now, this doesn't implement the algorithm that your problem statement describes, but it does end up with the same result:

public static void printDoorsOpened(final int passes)
{
    int j = 1;
    for(int i = 1; i <= passes; i++)
    {
        if(j*j == i){
            j++;
            System.out.println("The door number "+i+" is Opened");
        } else {
            System.out.println("The door number "+i+" is Closed");
        }
    }
}

Answer 2

• Use a java.util.BitSet

• somebool == true should just be somebool, and, while we are at it, use printf. Replace:

  System.out.println("The door number "+(l + 1)+" is "+(doors.get(l) == true ? "Opened" : "Closed"));
  

  with:

  System.out.printf("The door number %d is %s%n", (l + 1), doors.get(l) ? "Opened" : "Closed");
  

---

Now, about your style.... ;-)

There are three well-known style guides for Java, the basic/original Java guideline (with revisions), the Google Java guideline, and the IDE (Netbeans, Eclipse, IntelliJ, etc.) formatters.

In each case, there are common themes, and you are doing it wrong.

• the opening block brace should be at the end of the previous block conditional. For example:

  while(i < passes)
  {
      doors.put(i, false);
      i++;
  }
  

  should rather be:

  while(i < passes) {
      doors.put(i, false);
      i++;
  }
  

• you should use braces for 1-liner statements (as recommended in all coding standards for Java, and most other languages that use braces) because over time it leads to more maintainable code, and reduces the likelihood of bugs being introduced. This:

  for(int k = j - 1; k < passes; k += j)
      doors.put(k, !(doors.get(k)));
  

  should be:

  for(int k = j - 1; k < passes; k += j) {
      doors.put(k, !(doors.get(k)));
  }
  

• On Code Review, and Stack Exchange in general, tabs do not format well. You use tabs. As it happens, both the official Java guidelines, and the Google Java guidelines advise spaces for indentation. I realize that people who use tabs feel it is better, and I am not arguing that you are wrong. What I am saying is that if you insist on presenting code with tabs then you can expect that other people will think your code messy, and that is your fault, not theirs.

Answer 3

There is no need to use a HashMap, because you already know the number of doors from the start you can use:

boolean[] doors = new boolean[doorCount];

As a boolean[] is initialized to all false, you won't need the initialization step.

---

I think your method is doing too much right now, I would use a couple of different methods, such as:

public static boolean[] switchDoors(boolean[] doors)
public static boolean[] switchDoorsInRange(boolean[] doors, int min, int max) // just for the fun of it
public static void printDoors(boolean[] doors)

Note that switchDoors calls switchDoorsInRange(doors, 1, doors.length)

---

When using a boolean[] doors for the doors this code:

doors.put(k, !(doors.get(k)));

can simply be doors[k] = !doors[k];

---

Some boring comments:

• Think about your variable names, try to avoid single character names
• Use braces with Java convention instead of C# convention

---

Side note:

Whether or not a door will be open or closed at the end depends on how the prime-factorization of it looks.

Consider the number \$12\$ for example. How to prime-factorize it?

\$12 = 3*2*2\$

And the door will toggle on \$1, 2, 3, 4, 6, 12\$.

Note that those numbers can be written as 1, 2, 3, 2*2, 2*3, 2*2*3. That's \$6\$ times, which means that the door will end as being closed.

Unfortunately, there is no efficient way to prime-factorize a number. What you have built here is very similar to a number sieve, but instead of removing non-primes you are toggling them. Modifying your code to be a real sieve instead would not require many changes to the code.

Answer 4

Actually it's a math puzzle that I've solved some years ago. So I know the shortcut, but if this question was asked in any interview don't try to be over-smart at first and make a gotcha' mistake.

The puzzle is about which door number has odd number of factors will be leaved as open. Only the perfect square numbers have odd number of factors. Boiling down the solution into code

    final int totalDoors = 200;
    boolean[] state = new boolean[totalDoors+1]; // at first all doors are closed

    for (int door = 1; door * door <= totalDoors; door++) {
        state[door * door] = true;
    }

    for (int door = 1; door <= totalDoors; door++) {
        System.out.println("Door number : [" + door + "] is " + (state[door] ? "Opened" : "Closed"));
    }