Identify this Algorithm: Slots and Pegs

Question

I have a number of slots and pegs arranged in a straight line. The pegs can be moved and need to be moved to a slot each. A slot can be left empty only if all pegs are taken. When a peg is moved, it is not allowed to go past another peg. In other words the order of the pegs must be maintained. Preferably, the total distance moved by all pegs should be kept at a minimum. As far as possible, a peg should be placed in the nearest available slot.

All I want to know is: What field of mathematics deals with such a problem? What are the names of any well known algorithms which deal with similar problems? I am looking for Google fodder. Some keywords.

+--oooo-+--+---+---o--+------+--+-ooo+o-+-------o--+-----o-o-+-o

+ - Slots
o - Pegs

EDIT: I think that this visualization makes more sense. They are two separate tracks that need to line up.

Slots: +-------+--+---+------+------+--+----+--+----------+---------+--
Pegs:  ---oooo------------o--------------ooo-o---------o--------o-o---o

EDIT: Just want to make it clear that the number of slots can be greater than, less than or equal to the number of pegs.

Answer 1

Queueing theory or mathematics...

Answer 2

I don't know where this problem comes from but I am pretty sure that it's a form of combinatorial optimization, and more specifically one that can be solved using (integer) linear programming.

Answer 3

Combinatorics. Combinatorial algorithms. Concrete mathematics. (Also the title of an excellent and relevant book by Donald Knuth.

Answer 4

I think this is classic fodder for a dynamic programming solution. In fact, have a look a "sequence alignment" which might be another good search term on that wikipedia page.

The key insight is this:

Imagine you have your pegs as a list of peg positions (peg1:more pegs) and slots as a list of slot positions (slot1:more slots). Call this problem (peg1:pegs, slot1:slots). Then the solution is either peg1 in slot1 & the solution to (pegs, slots), or it is the solution to (peg1:pegs, slots).

This gives a recursive definition of how to solve it.

Or in pseudo-code (written in a functional programming style), imagine a function distance(peg, slot):

distance([]) = 0
distance((peg,slot):matches) = distance(peg,slot)+distance(matches)

solution(peg:[], slot:[]) = [(peg,slot)]
solution(peg:pegs, slot:slots) = if distance(a)<distance(b) then a else b
   where a = solution(peg:pegs, slots) and b=(peg,slot):solution(pegs, slots)

This solution should be made more efficient by combining the distance into the data structure.

Answer 5

"the total distance moved by all pegs should be kept at a minimum"

Unless I'm missing something, this is a non-problem.

Since the order of pegs must be maintained, you can just number the pegs 1, 2, 3, ...

+--1234-+--+---+---5--+------+--+-678+9-+-------10--+-----11-12-+-13

and the final state has to be peg 1 in slot 1, peg 2 in slot 2, etc.

+--1-+-2-+-3-+-4-+-5-+-6-+-7-+-8-+-9-+-10-+-11-+-12-+-13-+

Not being able to jump pegs past each other doesn't matter, each peg has to move a certain distance from it's starting point to its final point. As long as all moves are in the right direction and a peg never has to back up, then the distance each individual peg has to move is a simple constant (it doesn't depend on the order of the moves), and the sum of those distances, your cost function is constant, too.

I don't see any need for dynamic programming or linear programming optimization problem here.

If you introduce a cost for picking up a peg and setting it down, then maybe there's an optimization problem here, but even that might be trivial.

Edit in response to 1800 Information's comment

That is only true if the number of slots is equal to the number of pegs - this was not assumed in the problem statement – 1800 INFORMATION (2 hours ago)

OK, I missed that. Thanks for pointing out what I was missing. I'm still not convinced that this is rocket science, though.

Suppose # pegs > # holes. Compute the final state as above as if you had the extra holes; then pick the N pegs that got moved the furthest and remove them from the problem: those are the ones that don't get moved. Recompute ignoring those pegs.

Suppose # holes > # pegs. The correct final state might or might not have gaps. Compute the final state as above and look for where adjacent pegs got moved towards each other. Those are the points where you can break it into subproblems that can be solved trivially. There's one additional variable when you have holes on both ends of a contiguous subproblem -- where the final contiguous sequence begins.

Yes, it is a little more complicated than I thought at first, but it still seems like a little pencil-and-paper work should show that the solution is a couple of easily understood and coded loops.

Answer 6

If the number of pegs == number of slots, there exists only one solution. The first peg MUST go to the first slot, the next peg MUST go to the next slot, etc.

The the numbers are different, then it is slightly more complex because a peg or slot ( does not matter which one we can move ) can be moved to many places.

Brute force: Suppose the number of objects are m pegs and n slots ( interchangeably ), m < n

1. For each way (n-m) slots can be chosen ( refer to some combinatorics algorithms to see how to do this )
   1. There (n-m) chosen slots will be empty.
   2. Fill the m remaining slots with pegs. Calculate distance moved. This become the same as the case discussed at the top.
2. Choose the arrangement with minimujm distance moved.

A recursive solution:

    int solve(int pegs, int *peg_x, int slots, int *slot_x)
    {
      if (slots > pegs )
        return solve(slots, slot_x, pegs, peg_x);
      if (slots == 0 || pegs==0)
        return 0; // Cannot move

      int option1 = INT_MAX, options2 = INT_MAX;


      if (pegs > slots ) // Can try skipping a peg
        option1 = solve(pegs-1, peg_x+1 /* Move over one element */
                          slots, slot_x);
      // pegs >= slots 
      option2 = solve(pegs-1, peg_x+1, slots-1, slot_x+1)
                + abs(peg_x[0]-slot_x[0]);
      return min(option1, option2);
    }

This solution still requires storing the results in a table so that no subproblem is solved multiple times, to be a dynamic solution.

Thinking .... will update .....