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

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 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.