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];
Read more