skip to content W3C SVG

Code Jam 2010: Incrementing a Binary Counter

The Problem

Problem A in the qualifying round of this year’s Google CodeJam contest was really clever. The problem used a classic made-for-TV gadget from the 80s: The Clapper™ (“snapper” in google’s version) and went like this:

The Snapper is a clever little device that, on one side, plugs its input plug into an output socket, and, on the other side, exposes an output socket for plugging in a light or other device.

When a Snapper is in the ON state and is receiving power from its input plug, then the device connected to its output socket is receiving power as well. When you snap your fingers – making a clicking sound – any Snapper receiving power at the time of the snap toggles between the ON and OFF states.

In hopes of destroying the universe by means of a singularity, I have purchased N Snapper devices and chained them together by plugging the first one into a power socket, the second one into the first one, and so on. The light is plugged into the Nth Snapper.

Initially, all the Snappers are in the OFF state, so only the first one is receiving power from the socket, and the light is off. I snap my fingers once, which toggles the first Snapper into the ON state and gives power to the second one. I snap my fingers again, which toggles both Snappers and then promptly cuts power off from the second one, leaving it in the ON state, but with no power. I snap my fingers the third time, which toggles the first Snapper again and gives power to the second one. Now both Snappers are in the ON state, and if my light is plugged into the second Snapper it will be on.

I keep doing this for hours. Will the light be on or off after I have snapped my fingers K times? The light is on if and only if it’s receiving power from the Snapper it’s plugged into.

It’s a great problem because we have a situation that is easily modeled with a computer program, and yet a naive solution will be far too inefficient to process the inputs that google provides (e.g. 10^8 claps).

Here is a direct-to-code translation of the functioning of a “chain of snappers” implemented in (very verbose) Haskell:

module Main
    where

type ClapperChain = [Bool]

clapOnOff :: ClapperChain -> ClapperChain
clapOnOff [] = []
clapOnOff (c:cs) =
    if isPowered cs
        then toggleState c : clapOnOff cs
        else c : clapOnOff cs

isPowered :: ClapperChain -> Bool
isPowered []     = True -- at the outlet
isPowered (c:cs) = inOnState c && isPowered cs

inOnState = id
toggleState = not

We can then look at a few iterations (snaps) and see how the chain changes. True is a “snapper” in the ON state:

*Main> take 4 $ iterate clapOnOff [False,False,False]
[[False,False,False],[False,False,True],[False,True,False],[False,True,True]]

A Solution

After working out a few iterations on paper I realized that the snappers follow the pattern of an ascending binary number count: 000, 001, 010, 011...

The lamp will be on when all of the snappers are 1s (i.e. in the ON state) which will occur every (2^number_of_snappers) snaps. Thus my solution was simply the following:

caseAlgorithm (n,k) =
    if (((k+1) `mod` 2^n) == 0)
        then ON
        else OFF

More Code and Thoughts

Here is a more terse and better version of the Snapper simulation code I posted above, now simply called increment for incrementing a binary number:

increment :: ClapperChain -> ClapperChain
increment [] = [] -- [] is the outlet
increment chain@(c:cs)
    | and cs = map not chain
    | otherwise = c : increment cs

We can convert our lists into pretty strings with…

showBinary :: ClapperChain -> String
showBinary = map (\b-> if b then '1' else '0')

And play with it like so:

*Main> map showBinary $ take 9 $ iterate increment  [False,False,False]
["000","001","010","011","100","101","110","111","000"]

I liked realizing that a binary count could be represented recursively and mechanically. It led me to look into how binary counter circuits are implemented in electronics (it turns out The Clapper™ is not generally involved), and got me thinking about cellular automata.

A binary counter could be implemented as Cellular Automata in which each bit is an Automaton with two states: an ON/OFF state and a POWERED/UNPOWERED state.

…although I think POWERED or UNPOWERED would have to be evaluated lazily, which might not fit the model.

Oh well, good luck to everyone doing the competition this year!