Home ›

Google Code Jam - The Snapper Chain

Nico Heid's picture
by Nico Heid on Sun, 06/20/2010 - 12:23
in

The Google problems are always nice, sometimes even a bit too tricky. This years entry problem was quite nice with some difficulties you could run in.

You need to read the problem first, to follow the article, so here's the link: http://code.google.com/codejam/contest/dashboard?c=433101#s=p0&a=0

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:

  1.                         // snapping
  2.                         boolean toggle = true;
  3.                         for (int j = 0; j < snaps; j++) {
  4.                                 toggle = true;
  5.                                 for (int k = 0; k < snapperCount; k++) {
  6.                                         if(toggle == false){
  7.                                                 break;
  8.                                         }
  9.                                         if (toggle == true) {
  10.                                                 snapper[k] = !snapper[k];
  11.                                         }
  12.                                         if (snapper[k] == true) {
  13.                                                 toggle = false;
  14.                                         }
  15.  
  16.                                 }
  17.                         }
  18.  
  19.                         // we need power on all snappers
  20.                         boolean power = true;
  21.                         for (int j = 0; j < snapperCount; j++) {
  22.                                 if (snapper[j] == false) {
  23.                                         power = false;
  24.                                         break;
  25.                                 }
  26.                                
  27.                         }

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.

So it's time to take a closer look to the different states of the snappers. Try writing down the first couple of steps on a piece of paper. You will notice that it's just a binary count. So instead of iterating you can define the output right away, I don't have to tell you what performance benefit this will give.

So let's do this here, with an example.
We take 4 snappers and we snap 47 times. Ok you might notice that is the last example of the challenge, but it's good enough.
So let's look at the binary representation of 47:

  1. 101111

We have to read the chain from right to left, so that we can see how far the power actually travels. Now we have 6 digits but only 4 snappers. So we need to truncate the top. So we AND our binary number with our desired result. If we get the desired number, the light's on, if not, it's off.

  1. 101111        (the 47)
  2. 001111        (we need 4 snappers powered on)
  3. --------------   (AND)
  4. 001111        (light is on)

Let's do snap nr. 48

  1. 110000       (48 snaps)
  2. 001111       (the 4 snappers powered)
  3. ----------
  4. 000000       (well, the ligh's off now)

So let's see how the code could look like for this way of implementing the problem

  1.                 int n=4;
  2.                 int k=47;
  3.                
  4.                 String needed = Integer.toBinaryString((1<<n)-1);
  5.                 String current = Integer.toBinaryString(47);
  6.                
  7.                 System.out.println("state needed : "+ needed);
  8.                 System.out.println("current state: "+ current );
  9.                
  10.                 System.out.println("result of AND: "+ Integer.toBinaryString(k & (1<<n)-1) );

For me, with my somewhat rusted binary skills, the tricky part was to convert the decimal 4 into the four bits we need: 1111. To achieve this, take a 1 and shift it 4 times to the left (the 1 << n part). Then we end up with 10000. If we now subtract 1 we have 01111 or 1111, exactly what we need.

With this approach you can calculate the result without stressing your CPU with loops.

You can find the code here: http://github.com/nheid/unitedcoders-examples/tree/master/src-java/com/u...

Comments

Twitter Trackbacks for Google Code Jam - The Snapper Chain 's picture
Pingback
Twitter Trackbacks for Google Code Jam - The Snapper Chain (not verified) - Sun, 06/20/2010 - 14:10

[...] Google Code Jam - The Snapper Chain | united-coders.com united-coders.com/nico-heid/google-code-jam-the-snapper-chain – view page – cached The Google problems are always nice, sometimes even a bit too tricky. This years entry problem was quite nice with some difficulties you could run in. Tweets about this link Topsy.Data.Twitter.User['nicoheid'] = {"photo":"http://a3.twimg.com/profile_images/689457719/nico_2_normal.jpg","url":"http://twitter.com/nicoheid","nick":"nicoheid"}; nicoheid: “RT @united_coders New post: Google Code Jam - The Snapper Chain http://bit.ly/beD09z ” 30 minutes ago retweet Topsy.Data.Twitter.User['united_coders'] = {"photo":"http://a1.twimg.com/profile_images/705668504/qrcode_colorful_normal.png","url":"http://twitter.com/united_coders","nick":"united_coders"}; united_coders: “New post: Google Code Jam - The Snapper Chain http://tinyurl.com/274smvm ” 31 minutes ago retweet Filter tweets [...]

Serban's picture
Or much more elegant...
Serban (not verified) - Mon, 06/21/2010 - 19:04

This will print a row of the solution presuming that you already read n and k values.
The basic operation is to test if k+1 exactly divides with 2^N.

System.out.println("Case #" + (i + 1) + ": " + (((((k + 1) >> n) << n) == (k + 1)) ? ("ON") : ("OFF")));

Nico Heid's picture
elegant indeed.
Nico Heid - Thu, 06/24/2010 - 21:44

i like it. even though it took me a bit to understand.

didxga's picture
what a elegant and concise
didxga (not verified) - Tue, 08/03/2010 - 09:42

what a elegant and concise solution

Salvage Trucks's picture
Hi, it seems the same jam was
Salvage Trucks (not verified) - Thu, 06/09/2011 - 17:00

Hi, it seems the same jam was troubling many. Now me along with others got the solution of it. Thanks for share.

Solutions for the google code jam 2012 qualify round | unite's picture
Pingback
Solutions for the google code jam 2012 qualify round | unite (not verified) - Mon, 04/16/2012 - 06:17

[...] Snapper Chain from Qualification Round [...]