# Interview puzzle on traveling on a line segment

On a number line of length `M`, where `0 < M <= 1,000,000,000`, you given `N` (`1 < N <= 100,000`) integer pairs of points. In each pair, the first point represents where an object is currently located, and the second point represents where an object should be moved. (Keep in mind the `second` point may be smaller than the `first`).

Now, assume you start at the point `0` and have a cart that can hold `1` object. You want to move all objects from their initial positions to their respective final positions while traveling the least distance along the number line (not displacement). You have to end up on point `M`.

Now, I've been trying to reduce this problem to a simpler problem. To be honest I can't even think of a brute force (possibly greedy) solution. However, my first thought was to degenerate a backwards movement to two forward movements, but that doesn't seem to work in all cases.

I drew out these `3` sample test cases in here:

The answer to the first testcase is `12`. First, you pick up the `red` item at point `0`. Then you move to point `6` (distance = `6`), drop the `red` item temporarily, then pick up the `green` item. Then you move to point `5` (distance = `1`) and drop the `green` item. Then you move back to point `6` (distance = `1`) and pick up the `red` item you dropped, move to point 9 (distance = `3`), then move to point `10` (distance = `1`) to finish off the sequence.

The total distance traveled was `6 + 1 + 1 + 3 + 1 = 12`, which is the minimum possible distance.

The other two cases have answers of `12`, I believe. However, I can't find a general rule to solve it.

Anyone got any ideas?

• If I'm not mistaken, wouldn't you need a datastructure to count the "overlap"? Otherwise I'm solving it the wrong way. Feb 9, 2013 at 20:51
• you can still flag and if the mod agrees he will reopen and migrate Feb 10, 2013 at 2:29
• We can move questions between sites automatically (even if they are closed), please do not cross post. Instead, follow @ratchetfreak's advice, flag for moderation attention and ask for the question to be migrated. Feb 10, 2013 at 3:44
• This sounds really nieve, but what if you start by moving to the right until you hit a piece of cargo. Once you hit that cargo, drop whatever you are carrying, pick up that cargo, and proceed to place it in the right spot. If you hit another piece of cargo that needs to be moved, drop the current, pick it up, and deal with it. When you have no cargo, move right. Feb 10, 2013 at 3:53
• Do objects exist at all points or just the given ones? Is it possible to have multiple objects at a given location? Is it allowable to temporarily set an object down in a location other than its final one? Feb 22, 2013 at 18:04

1. If you're empty, start moving to the right.

2. Whenever you reach an object and you're empty, pick it up (duh) and move toward its destination.

3. Whenever you reach an object `a` and you're already carrying `b`, always choose whichever of the objects has the numerically smallest destination (furthest to the left).

4. If you're not yet at M, go back to step 1.

This is optimal: The only place where you have a real choice is in step 3. Handling the leftmost destination first ensures that by the time you've dispatched both objects, you'll be as far to the right as possible.

Why is this question on programmers.sx? Yes, "interview question", but it's just a nice riddle.

PS. In terms of implementation, all you need is the list of tasks (the integer pairs of points) sorted by original position.

Suppose you are given these moves `(a, b), (c, d), (e, f), ...` then the minimum distance you have to travel is `abs(b - a) + abs(d - c) + abs(f - e) + ...` and the actual distance you travel is `abs(b - a) + abs(c - b) + abs(d - c) + abs(e - d) + ...`.
Basically, given an array of moves the point is to minimize the "travel distance" function by swapping elements around. If you consider a particular combination as a node and all the combinations you can reach from it as edges you can use one of the many graph search algorithms around which make use of an heuristic. One example is the beam search.

May be I am missunderstanding the problem but what about the following:

1. Sort the pairs by the first number of the pair which is the current location
2. Move along the line swapping elements to their proper location (you have a temp variable)

The fact that it is sorted guarantees that you don't go back and forth the elements to place them in the proper location (regardless if the line is represented as an array or list)

Update after @templatetypedef comment:
Use a `HashTable` to store all the pairs. Use the current location of each pair as index key.
Use a second index over the pairs.

`````` 1. Get next pair according to index from the line.
2. If current pair exists in hashtable then place element to its target location.
2.a Remove pair from hashtable.
2.b Make current pair the target location. Then go to step 1
ELSE
Increment current index until you get a pair present in the hashtable. Go to step 2
``````
• You can only move one unit at a time, so many times you have to retrace your path I think Feb 9, 2013 at 20:56
• I don't really follow you.It seems that the requirement is just to move forward and swap numbers.You already know the current location and the target location.Just swap them (using the cart variable as you say it) and move to the next pair Feb 9, 2013 at 20:57
• Consider this counterexample: (1, 10), (10, 1), (2, 3), (3, 4). The optimal way to do this would be to carry object 1 to position 10, then pick up the object at position 10 and carry it to position 1, then to carry the 2 to the 3 and the 3 to the 4. Doing this in sorted order of starting position would carry the 1 to the 10, then back all the way up to the start to carry the 2 to the 3, the 3 to the 4, then go all the way to the end to pick up the 10 and bring it back. Feb 9, 2013 at 20:58
• @templatetypedef:I see what you mean.Updated answer Feb 9, 2013 at 21:13
• In your updated answer, does the "current index" just indicate the current position? Feb 9, 2013 at 22:31

My inclination as to an algorithm which is basically greedy:

Build a list of points that need to be moved. Since optimizing this isn't part of the required problem I'm not going to worry about organizing it.

``````while !Done
if CartIsEmpty()
FindClosestObjectToMove()
MoveToObject()
else
Destination = Cart.Contains.Target
CurrentMove = [Location, Destination]
SubList = List.Where(Move.Within(CurrentMove))
if !SubList.Empty
Destination = SubList.FindSmallest(Location, Move.Origin)
MoveTo(Destination)
if !Destination.Empty
SwapCart()
else
EmptyCart()
``````

I think this covers all cases. In a sense it's recursive but through updating it's list rather than calling itself.

• Thanks for the answer. Can you explain `Destination = SubList.FindSmallest(Location, Move.Origin)`? What does `Move.Origin` represent? Feb 10, 2013 at 17:01
• Move.Origin is the location where the object to be moved currently is--it's origin. Basically, when looking at a move first do any smaller moves contained within it's span. Feb 11, 2013 at 0:43

This is the asymmetric traveling salesman problem. You can think of this as a graph. The edges will be each (start, finish) pair, one for each (0, start), and all other pairs of (finish, start).

Assuming NP!=P, it will have an exponential expected running time.

• I'm not sure that's true. This is a special case of asymmetric TSP, so it might have a polynomial-time solution. Feb 9, 2013 at 22:18
• Don't you need an edges like (finish, M), where `M` is the endpoint of the number line? Feb 9, 2013 at 22:47
• Also, an exponential algorithm is way too slow, for `N` can be 100,000. Feb 9, 2013 at 22:48
• To back this statement up, presumably you have a have a method of transforming every asymmetric travelling salesman problem into an equivalent problem of this description? Feb 22, 2013 at 17:25
• It's not equivalent. The traveling salesman must visit all vertices of the graph. Your formulation requires him/her to visit all edges. Feb 22, 2013 at 18:01