Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Here's an interesting question I came upon:

Let's just say 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: http://i.stack.imgur.com/zRv4Q.png

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?

share|improve this question
    
If I'm not mistaken, wouldn't you need a datastructure to count the "overlap"? Otherwise I'm solving it the wrong way. –  david Feb 9 '13 at 20:51
    
you can still flag and if the mod agrees he will reopen and migrate –  ratchet freak Feb 10 '13 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. –  Yannis Rizos Feb 10 '13 at 3:44
1  
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. –  supersam654 Feb 10 '13 at 3:53
1  
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? –  Sean McSomething Feb 22 '13 at 18:04
show 2 more comments

5 Answers

  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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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  
share|improve this answer
    
You can only move one unit at a time, so many times you have to retrace your path I think –  david Feb 9 '13 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 –  user10326 Feb 9 '13 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. –  templatetypedef Feb 9 '13 at 20:58
    
@templatetypedef:I see what you mean.Updated answer –  user10326 Feb 9 '13 at 21:13
    
In your updated answer, does the "current index" just indicate the current position? –  david Feb 9 '13 at 22:31
add comment

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.

share|improve this answer
3  
I'm not sure that's true. This is a special case of asymmetric TSP, so it might have a polynomial-time solution. –  templatetypedef Feb 9 '13 at 22:18
    
Don't you need an edges like (finish, M), where M is the endpoint of the number line? –  david Feb 9 '13 at 22:47
    
Also, an exponential algorithm is way too slow, for N can be 100,000. –  david Feb 9 '13 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? –  dan_waterworth Feb 22 '13 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. –  alexis Feb 22 '13 at 18:01
add comment

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()
       LoadCart()
    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()
            UpdateTaskList()
        else
            EmptyCart()
            DeleteTask()

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

share|improve this answer
    
Thanks for the answer. Can you explain Destination = SubList.FindSmallest(Location, Move.Origin)? What does Move.Origin represent? –  david Feb 10 '13 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. –  Loren Pechtel Feb 11 '13 at 0:43
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.