Walking Ant Problem - Part 2

Source: Original problem adapted from the "Ants Problem" (Link removed) at "CMU ACM Programming Contest" . Extension to the 4 year old problem on CSE Blog - Walking Ants Puzzle . Problem also available at J. Paulson Programming Blog

Problem:

You have a bunch of ants on a meter stick, each walking 1cm/s in some direction. If an ant hits the end of the stick, it falls off. If two ants collide, they both reverse direction.

Walking Ants Puzzle earlier essentially asked: Given the starting positions and directions of all the ants, how long until the last ant falls off?

The new problem is :
Given the starting positions and directions of all the ants, which ant(s) are the last to fall off?

Disclaimer: I do not have the solution to the problem. It just looks like an interesting problem to solve.

Update (24 June 2014):
Solution: Posted by Strilanc and me in comments!

1. We can come up with a solution by DP Recurrence relation.

2. First, to find out what time does it take for last ant to fall, consider collision as just passage and solve. It should give you time of an ant that falls last. Second, to find which one, count the number of ants in front of it which are walking in opposite direction Say k . The k'th ant in front of it is the last one to fall.

To know how, draw all ants on a line, on x-axis. Draw lines from each ant with 45d angle in initial direction. Count number of collision that line will have (say k). After separating collisions, it is obviously k'th ant line which is longest.

1. Ameya, The solution is not very clear to me. How would intersections give us which ant goes down last. Look at the solution in my comment. Its awesome.

3. If there are L ants initially moving left and R ants initially moving right then, at the end, L will have fallen off the left side and R off the right side.

Since ants never walk over each other, the L that fell off the left must the the first L from the left. The last one that fell off to the left is the L'th ant. The next ant is the one that fell off to the right.

Therefore the last ant to fall off is the L'th or (L+1)'th ant.

If the leftmost ant is closer to its edge than the rightmost ant to its edge, then the (L+1)'th ant is last. Vice versa it's the L'th ant. In a tie it's both.

1. Thanks Strilanc. Great solution.

4. Great solution Strilanc.

Let me explain your solution in greater detail.

Consider this question: "how many ants fall off to the left?" By the argument from the Ant Walking Problem - I, it's the number of ants L which are initially facing left.

But which ones? Here's the key observation: the ants can't pass each other! So it must have been the L leftmost ants. So the last ant to fall off to the left is the Lth ant, and the last ant to fall off to the right is the (L+1)st ant, and one or both of those is the last ant to fall off.

Now the third question, "which side will the last ant fall - right or left?", By the construction in Ant Walking Problem - I, if the leftmost element facing right is closer to the edge than the right most element facing left, the last ant will fall off the right side. If the last ant to fall is on the right side, then the "winner" ant is (L+1)th ant. Else, the "winner" ant in Lth ant.

Cheers!

1. Just taking care of the corner random case: "... if the leftmost element facing right is closer to the left edge than the right most element facing left to the right edge ... "