Wednesday, November 19, 2008

Toggle door puzzle, fast solution

I was recently asked the following question:

You have 100 doors in a row that are all initially closed. you make 100 passes by the doors starting with the first door every time. the first time through you visit every door and toggle the door (if the door is closed, you open it, if its open, you close it). the second time you only visit every 2nd door (door #2, #4, #6). the third time, every 3rd door (door #3, #6, #9), etc, until you only visit the 100th door.

question: what state are the doors in after the last pass? which are open which are closed?

If the questions is expressed as is door N open, the answer is

bool doorOpen = (Math.Sqrt(doorNumber) % 1) == 0;

However, as part of going through the puzzle I noticed that there seemed to be a sequence in the offset of the open doors (1, 4, 9), which looked suspiciouly like odd number offsets: 1=1, 4=1+3, 9=4+5 i.e. the value of the offset of the next open door is the previous open door offset plus the next odd number.

Which when I applied it to larger doorsets worked as well. Looking at 50 doors, which doors are open (O) vs closed (c):
[OccOccccOccccccOccccccccOccccccccccOccccccccccccOc]

If you are given the problem of find all open doors in the set, then using the square root approach is O(n). So the square root approach would look like:
private static BitArray GenerateDoorTogleSeriesResult(int doors)
  {
   BitArray result = new BitArray(doors);

   for (int door = 1; door <= doors; door++)
    result[door - 1] = (Math.Sqrt(door) % 1) == 0;

   return result;
  }

whilst my approach looks like:

private static BitArray GenerateDoorTogleResult(int doors)
  {
   BitArray result = new BitArray(doors);

   int odd = 1;
   for (int door = odd; door <= doors; door += odd)
   {
     result[door - 1] = true;
     odd += 2; // next odd number
   }
   return result;
  }

The difference being that for 1,000 doors the square root apprach requires 1,000 square root calculation, whilst mine requires 31 summations. Or in big-oh O(√n).

The calling code looks like:
static void Main(string[] args)
  {
   const int DOORS = 10;
   BitArray suggestedAnswer = GenerateDoorTogleResult(DOORS);
   BitArray fastAnswer = GenerateDoorTogleSeriesResult(DOORS);

   Console.WriteLine("suggested:\n{0}", ShowDoors(suggestedAnswer));
   Console.WriteLine("fast\n{0}", ShowDoors(fastAnswer));
   Debug.Assert(ShowDoors(suggestedAnswer).CompareTo(ShowDoors(fastAnswer)) == 0);
  }

  private static string ShowDoors(BitArray doors)
  {
   StringBuilder sb = new StringBuilder(doors.Length+4);
   sb.Append("[");
   foreach (bool doorOpen in doors)
    sb.Append(doorOpen == true ? 'O' : 'c');
   sb.Append("]\n");

   return sb.ToString();
  }

I subsequently found the proof for this by Francesco Maurolico in 1575.

1575: "Arithmeticorum Libri Duo" by Francesco Maurolico is the first book
to prove a theorem by Mathematical Induction. The theorem was known 2000
years earlier by Pythagorus, but they proved it geometrically. The
theorem is that the sum of the first N odd numbers
1 + 3 + 5 + 7 + 9 + 11 + 13 +... + (2N-1) = N x N

No comments: