RSS

Google Code Jam 2010 Qualifying Round Solutions (Part 1)

13 May

Okay so now I’ll post some of my solutions for Google Code Jam Qualifying Round 2010. The first one was called the Snapper problem. You can read the description of the problem here.

This solution was a very, very simple brute force solution. It worked well for the small input but obviously did not work for the large input. Anyway, here it is:

import java.util.*;
import java.io.*;

public class Snapper
{
   String filename;

   public Snapper(String f)
   {
      filename = f;
      openFiles();
   }

   private void openFiles()
   {
      Scanner s;

      try
      {
         s = new Scanner(new File(filename));
         int ct;

         ct = s.nextInt();

         for (int i = 0; i < ct; i++)
            output(i + 1, process(s.nextInt(), s.nextInt()));

         s.close();
      }
      catch (Exception e)
      {
         System.err.println("I/O error: " + e);
         System.exit(0);
      }
   }

   private String process(int N, int K)
   {
      ArrayList<Snap> list = new ArrayList<Snap>();

      for (int i = 0; i < N; i++)
         list.add(new Snap());

      // first one has power
      list.get(0).flipPower();

      // snap, snap, snap yo fingers!
      for (int i = 0; i < K; i++)
      {
         // if it has power, flip its state
         for (int j = 0; j < N; j++)
         {
            if (list.get(j).getPower())
               list.get(j).flipState();
         }

         int j = 1;

         // turn on power of all those whose prev's
         // state & power is on
         for (; j < N; j++)
         {
            if (list.get(j - 1).getState() &&
                list.get(j - 1).getPower())
               list.get(j).onPower();
            else
               break;
         }

         // j is the index of the first snapper whose prev's
         // state is off
         // turn rest's power off
         for (; j < N; j++)
            list.get(j).offPower();
      }

      // check if all powers and all states are on.
      int i = 0;

      for (; i < N; i++)
      {
         if (!list.get(i).getState() || !list.get(i).getPower())
            break;
      }

      return (i == N) ? "ON" : "OFF";
   }

   private void output(int caseNum, String result)
   {
      System.out.println("Case #" + caseNum + ": " + result);
   }

   public static void main(String args[])
   {
      Snapper app = new Snapper(args[0]);
   }
}

class Snap
{
   private boolean state;
   private boolean power;

   public Snap()
   {
      state = false;
      power = false;
   }

   public void  flipState() { state = !state; }

   public void flipPower() { power = !power; }

   public boolean getState() { return state; }

   public boolean getPower() { return power; }

   public void offPower() { power = false; }

   public void onPower() { power = true; }

}

I know that it’s super long and unnecessarily OOP’d, but it was my first solution so I figured it was okay. The solution (for small input) ran in 0.647s on an Intel Core 2 Duo 2.53 GHz, 4GB RAM, running Ubuntu 10.04.

The approach is pretty much self-explanatory so I won’t go into the details of it. It’s also sorta commented so you can figure out what I did. Obviously, I could have made it more efficient but it got me the answer quickly anyway so life’s good.

Advertisements
 
2 Comments

Posted by on May 13, 2010 in Uncategorized

 

Tags: , , , ,

2 responses to “Google Code Jam 2010 Qualifying Round Solutions (Part 1)

  1. Anon

    May 14, 2010 at 2:28 PM

    There’s a MUCH simpler solution to this problem. If you draw out from N = 1 to N = 5 or 6, you can see that it follows a binary pattern. So for the light on the Nth snapper to be on, the number of snaps (k), modulo 2^N, must be 2^(N+1) – 1. This gives you a constant time algorithm to check.

     
  2. jrupac

    May 14, 2010 at 2:30 PM

    yeah I realized the same thing after I had already attempted the large input. when I first looked at the problem, i only did the first three or so snaps so I didn’t see a pattern

     

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: