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.

int finishers = 0; boolean[] isFastEnough = new boolean[startposition.length]; for (int i = 0; i < startposition.length; i++) { if ((startposition[i] + speed[i] * time) >= barnPosition) { isFastEnough[i] = true; finishers++; } else { isFastEnough[i] = false; } } if (finishers < chicksNeedToFinish) { return "IMPOSSIBLE"; }

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

barn at position 10 with 5 seconds on the clock position: 0 2 3 5 7 speed: 2 1 1 1 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.

// start from closest to barn to furthest swap speedy chicken until we have the required number finishers = 0; int position = startposition.length - 1; int priceOfSwap = 0; int swaps = 0; for (int i = startposition.length - 1; i >= 0; i--) { if (isFastEnough[i]) { finishers++; if (priceOfSwap > 0) { swaps += priceOfSwap; } } else { priceOfSwap++; } if (chicksNeedToFinish == finishers) { return String.valueOf(swaps); } }

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

#### Nico Heid

#### Latest posts by Nico Heid (see all)

- Raspberry Pi Supply Switch, start and shut down your Pi like your PC - August 24, 2015
- Infinite House of Pancakes – code jam 2015 - July 13, 2015
- google code jam 2014 – magic trick - April 18, 2014