Home ›

Google Code Jam - Picking Up Chicks

Nico Heid's picture
by Nico Heid on Wed, 04/13/2011 - 18:36
in

This is a problem I particularly enjoyed. I had to turn it around a few times in my head before I found the solution.

First I was thinking about simulation the chickens moving before noticing I am going in the totally wrong direction.
Then it dawned to me, that the solution is quite simple.

We can break the solution down into two parts.

  • Is the specific case solvable
  • How many swaps do we need

Is the specific case solvable

Leaving all other aspects aside, just check if enough chickens can make it to the barn in time. If this is not the case, it's an IMPOSSIBLE one to solve.
For this to find out, you only need to get their position, add the speed multiplied by the time you have at hands and see if they make it into safety, also known as the barn.

  1.         int finishers = 0;
  2.         boolean[] isFastEnough = new boolean[startposition.length];
  3.  
  4.         for (int i = 0; i < startposition.length; i++) {
  5.             if ((startposition[i] + speed[i] * time) >= barnPosition) {
  6.                 isFastEnough[i] = true;
  7.                 finishers++;
  8.             } else {
  9.                 isFastEnough[i] = false;
  10.             }
  11.         }
  12.  
  13.         if (finishers < chicksNeedToFinish) {
  14.             return "IMPOSSIBLE";
  15.         }

How many swaps do we need

This is where the actual work is done. I decided to assign every chicken a tag, if it would make it to the barn. So you end up with an array of ones and zeroes or true and false according to the chicken’s start position. For example:

  1. barn at position 10 with 5 seconds on the clock
  2. position: 0 2 3 5 7
  3. speed:   2 1 1 1 4
  4. finisher: 1 0 0 1 1

This is the information you need to calculate the swaps. Start from the right end of the array and walk to the front. If you find a finisher, increase the chickens which are safe and move on. If you find a slow one, you need to swap the next finisher in front of it, so you increase the costs of swapping by one. For the next speedy chicken you find, you increase swaps by the costs you determined.

  1. // start from closest to barn to furthest swap speedy chicken until we have the required number
  2.         finishers = 0;
  3.         int position = startposition.length - 1;
  4.         int priceOfSwap = 0;
  5.         int swaps = 0;
  6.         for (int i = startposition.length - 1; i >= 0; i--) {
  7.  
  8.             if (isFastEnough[i]) {
  9.                 finishers++;
  10.                 if (priceOfSwap > 0) {
  11.                     swaps += priceOfSwap;
  12.                 }
  13.             } else {
  14.                 priceOfSwap++;
  15.             }
  16.  
  17.             if (chicksNeedToFinish == finishers) {
  18.                 return String.valueOf(swaps);
  19.             }
  20.  
  21.         }

That’s all the you need. The code is, as usual, on github.

Comments

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:16

[...] Picking Up Chicks from Round 1B 2010 [...]