Picking Up Chicks

Problem:
A number of chicks in a straight line begin running at different speeds, starting at different points along that line. When a speedy chick catches the chick in front, it slows to the slower speed. You are following in a crane and can lift a chick off the ground, allowing any chicks behind to pass. This operation takes no time.
Given the initial locations of N chicks and their speeds, what is the minimum number of swaps you have to perform to get K of the N chicks to the barn, which is B meters away, within time T.
Musings:
We want to know the minimum number of swaps that need to be done to get K chicks to the barn in time T. Thinking of the problem in terms of the chicks can lead to unnecessary complexity. We are after swaps, so let that be the primary concern of the algorithm.
Consider the total distance coverable by a chick within the allotted time + the starting position. If this distance is less than the position of the barn, this chick cannot make it in time. If the chick’s range is greater than the barn position, then the chick can make it, providing it isn’t slowed by a chick with a range less than the barn.
If a speedy chick catches a slower chick, we need to decide if we should allow the faster to pass. If the slower chick will also make it (its position at time T is greater than the barn) then there is no reason to swap, both the faster and the slower will make it. If the slower will not make it, however, we need to swap to allow this chick to get to the barn. But we might not care if this particular chick makes it, as we are only after a certain target number.

Solution:

  1. Calculate each chick’s range as (starting position + (speed * time allowed))
  2. For each chick
  3.     If this chicks range < the position of the barn, this chick can’t make it
  4.     Compare the range of this chick (a) with those in front of it (b)
  5.     If the range of a is greater than b and the range of b < the barn’s position
  6.     Add a swap to the total needed for chick a
  7. Begin adding chicks to the “made it to barn” list, beginning with those that require 0 swaps, keeping track of the total swaps required, then adding those that require 1 swap, 2 swaps, etc
  8. When the total gets to the target number of chicks, however many swaps we’ve made is the answer

 

Notes:
This is a google code jam puzzle. You can see their description of the problem and their solution here.

Leave a Reply