Problem A. Snapper Chain - Qualification Round 2010 - Google Code Jam

Dashboard - Qualification Round 2010 - Google Code Jam

Problem

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.

Input

The first line of the input gives the number of test cases, T. T lines follow. Each one contains two integers, N and K.

Output

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is either "ON" or "OFF", indicating the state of the light bulb.

Input	Output
4 1 0 1 1 4 0 4 47	Case #1: OFF Case #2: ON Case #3: OFF Case #4: ON

http://articles.leetcode.com/2010/05/problem-snapper-chain-gcj-qualification.html

Let k be the number of times you snap your finger, n be the light’s position, and assume 0 = OFF and 1 = ON.

The configuration of the first five snappers (with the first snapper on the far left side) as k increases are:
00000 k = 0
10000 k = 1
01000 k = 2
11000 k = 3
00100 k = 4
10100 k = 5
01100 k = 6
11100 k = 7
00010 k = 8

See the pattern? The configuration of the snapper for any k is the binary representation of k itself!

For example, when k=3 and n=3, we know that the light is OFF because the snapper is in the OFF position (because the 3rd bit of k=3 is 0). When k=3 and n=2, the light is ON. However, when k=5 and n=3, the light is OFF even though the 3rd bit is 1. As the 2nd bit is 0, the electric couldn’t “flow” to the light bulb.

Therefore, in order for a bulb to light, it requires all of the bits from 1 to n to be all 1s.

int main() {
  int T,N,K;
  cin >> T;
  for(int t = 0; t < T; t++) {
    cin >> N >> K;
    int mask = (1 << N) - 1;
    printf("Case #%d: ",t+1);
    if ( (mask & K) == mask) puts("ON");
    else puts("OFF");
  }
  return 0;
}

http://united-coders.com/nico-heid/google-code-jam-the-snapper-chain/

If you’re a hands on programmer first you might just want implement the chain without looking at the problem more extensively. So you might end up with something like this:

                        // snapping
// snapping
boolean toggle = true;
for (int j = 0; j < snaps; j++) {
        toggle = true;
        for (int k = 0; k < snapperCount; k++) {
                if(toggle == false){
                        break;
                }
                if (toggle == true) {
                        snapper[k] = !snapper[k];
                }
                if (snapper[k] == true) {
                        toggle = false;
                }

        }
}
// we need power on all snappers
boolean power = true;
for (int j = 0; j < snapperCount; j++) {
        if (snapper[j] == false) {
                power = false;
                break;
        }
        }

This basically simulates the toggling of the switch. Works fine. Does solve the small input set without a problem. The thing is, it doesn’t perform that good and is really ugly to read.

Read full article from Dashboard - Qualification Round 2010 - Google Code Jam