Identify this Algorithm: Slots and Pegs

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.

-------------Problems Reply------------

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.

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.

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

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

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

Queueing theory or mathematics...

Category:algorithm Views:0 Time:2009-02-06
Tags: algorithm math

Related post

  • Identifying which Algorithm is which and explaining the running times 2010-09-11

    For a given problem with input size n, Algorithms A,B,C are executed. In terms of running time, one of the algorithms is O(n), one O(nlogn) and one O(n^2). Some measured running times of these algorithms are given below Input Size 512 1024 2048 A 70

  • Disassemble to identify encryption algorithm 2012-02-25

    Goal (General) My ultimate (long term) goal is to write an importer for a binary file into another application Question Background I am interested in two fields within a binary file format. One is encrypted, and the other is compressed and possibly a

  • Please identify this algorithm: probabilistic top-k elements in a data stream 2009-07-19

    I remember hearing about the following algorithm some years back, but can't find any reference to it online. It identifies the top k elements (or heavy hitters) in a data stream of n elements using only m counters. This is particularly useful for fin

  • How to identify encryption algorithm used in ciphertext? 2009-09-02

    Is there any ways to try to guess encryption algorithm used to encrypt the ciphertext? --------------Solutions------------- Yes. There are some differences: Is it a block cipher or not can be guessed from the length. Block length Entropy of the outpu

  • Can anyone help me identify the algorithm? 2011-03-24

    This proprietary network protocol uses a weird (CRC?) hashing algorithm I've not seen before. It calculates this from the port. From investigation, I've got the following hashes: 0-85 1-84 85-d0 7770-df 7771-de 7772-c9 7773-d0 7774-db 7775-da 7776-e5

  • What steps should I take to identify this algorithm 2011-04-05

    I have a application that stores passwords in a ms sql database, I wish to replicate the algorithm used to generate those passwords. I have to admit I am abit lost at exactly what I should try next. Str in => Output 0 = 0x81 00 = 0x81 0x95 000 = 0

  • Identifying algorithm used to generate codes 2009-08-13

    How would one identify what algorithm is used to generate codes with? Both common, open source ones, and the more difficult, custom unpublished algorithms? For example here are a sample... x3vbhzcouy g3zy453f4 srix1gtvri 3ewnubic5vz 4bu9ksba6yj r1u3r

  • When should the STL algorithms be used instead of using your own? 2010-07-06

    I frequently use the STL containers but have never used the STL algorithms that are to be used with the STL containers. One benefit of using the STL algorithms is that they provide a method for removing loops so that code logic complexity is reduced.

  • I want to detect objects in the image and redraw it in another page, so anyone would please suggest which algorithm can be used? 2012-02-08

    I am doing project on image processing (molecule identification in an image and drawing those molecules in an editor). so please help in identifying, which algorithm can be used to detect the objects like lines, curves, bifurcations and characters in

  • Algorithm improvement for Coca-Cola can shape recognition 2012-04-16

    One of the most interesting projects I've worked in the past couple years as I was still a student, was a final project about image processing. The goal was to develop a system to be able to recognize Coca-Cola cans (note that I'm stressing the word

  • Hanoi towers iterative with n > 3 pegs 2013-04-08

    Iterative algorithm for 3 pegs (or rods, or whatever you call them) is to repeat two following points: 1. Move smallest disks to the right/left (if odd/even) 2. Make one possible move left without touching the smallest disk My question is - Is there

  • What language/platform would you recommend for CPU-bound application? 2008-10-11

    I'm developing non-interactive cpu-bound application which does only computations, almost no IO. Currently it works too long and while I'm working on improving the algorithm, I also think if it can give any benefit to change language or platform. Cur

  • How does this work? Weird Towers of Hanoi Solution 2010-02-05

    I was lost on the internet when I discovered this unusual, iterative solution to the towers of Hanoi: for (int x=1; x < (1 << nDisks); x++) { FromPole = (x&x-1)%3; ToPole = ((x|x-1)+1)%3; moveDisk(FromPole,ToPole); } This post also has s

  • Does PHP's APC reclaim memory after apc_delete() is called? 2010-05-21

    More generally, does anyone know where the way APC works internally is documented? --------------Solutions------------- The short answer is yes, it appears to free and reclaim memory. Below I have listed the main functions involved, descending furthe

  • How to properly reserve identity values for usage in a database? 2010-06-16

    We have some code in which we need to maintain our own identity (PK) column in SQL. We have a table in which we bulk insert data, but we add data to related tables before the bulk insert is done, thus we can not use an IDENTITY column and find out th

  • Recursively Insert Element Into A Binary Tree 2010-06-25

    So I finished my List exercise and went ahead with Binary Trees. My code thus far: Tree.h #include "Node.h" class Tree { private: int mCount; Node *root; public: Tree(); ~Tree(); void insert(int, Node *); }; Tree.cpp void Tree::insert(int data, Node

  • Initial User Password Import to MYSQL 2010-07-27

    I inherited a site with a with a large user base. My client is updating their records and I need to import some predetermined passwords for about 900 users into a mysql table. The row that I am importing to seems to encrypt the passwords if I enter t

  • wordpress, passwordhash, in java 2010-08-02

    I have a Java application that needs to communicate with my server application (java application proxy forward by apache). In my web site, I am using wordpress, so in order to use the same users in my site and in my application, I decided to use the

  • Deal with document() func for transformation from 2 XML source file to 1 target file 2010-09-08

    I have two xml document: one as source file and one as dictionary file. Because I need to restructure the source file and also combine extra information for each element in first source file. I'm new bie in XSL transformation that why this is the har

Copyright (C) dskims.com, All Rights Reserved.

processed in 0.262 (s). 11 q(s)