Solutions to 'Loopy C puzzle'

Saturday, October 1, 2011

Solutions to 'Loopy C puzzle'

In my blog post yesterday, I shared this puzzle:

Add or modify exactly one operator in the following code such that it prints exactly 6 dots.

int i;
for (i = 0; i < 6; i--)
    printf(".");

Let me first list all the possible solutions I know.

for (i = 0; i < 6; i++)
for (i = 0; i < 6; ++i)
for (i = 0; -i < 6; i--)
for (i = 0; i + 6; i--)
for (i = 0; i ^= 6; i--)

The last solution in the list is not quite obvious and needs a little analysis to understand why it works. To generalize the problem, let us use n instead of 6. So, the loop becomes:

int i;
for (i = 0; i ^= n; i--)
    printf(".");

If we use XOR to represent bitwise exclusive OR, first i is set to (n XOR i) before we enter the loop. Since, the initial value of i is 0, this amounts to setting i = n before we enter the loop.

Thereafter, every iteration prints a dot and sets i = n XOR (i - 1). If we try to represent two such consecutive iterations as one operation, this composite operation prints two dots and sets i = n XOR ((n XOR (i - 1)) − 1) where i on the RHS is the value of i before the pair of iterations and i on the LHS is the value of i after the pair of iterations complete. … (A)

Before we proceed further, note that

k XOR 1 = k − 1 for an odd integer k. … (1)
k XOR 1 = k + 1 for an even integer k. … (2)
a XOR b is an odd integer if a and b have different parities. … (3)

I'm not presenting the proof of these results since they are very trivial. We'll use these results in the discussion below.

If n is odd, i is odd initially because i is set to n before we enter the loop. We'll show that i always remains odd and never changes for every pair of iterations.

i = n XOR ((n XOR (i − 1)) − 1)    … from (A)
  = n XOR ((n XOR (i − 1)) XOR 1)    … from (1) and (3)
  = (n XOR n) XOR ((i − 1) XOR 1)    … from associativity of XOR
  = 0 XOR ((i − 1) + 1)    … from (2) and (3)
  = i

Note that i begins as i = n. Since, i is set to n again after every two iterations, the loop never terminates.

If n is even, i is even initially because i is set to n before we enter the loop. We'll show that i always remains even and decrements by 2 for every pair of iterations.

i = n XOR ((n XOR (i − 1)) − 1)    … from (A)
  = n XOR ((n XOR (i − 1)) XOR 1)    … from (1) and (3)
  = (n XOR n) XOR ((i − 1) XOR 1)    … from associativity of XOR
  = 0 XOR ((i − 1) − 1)    … from (1) and (3)
  = i − 2