Puzzles/ErrorProneSort

Puzzle

You are running a factory that produces widgets. The widgets come off the assembly line in random order, and are so stacked. However, in order to be shipped, the widgets must stacked in a specific order.

You have a computer that tracks the order the widgets come off the asssembly line, but cannot afford to automate the process of reordering them. You must therefore rely on an error prone human operator to reorder the stacks.

Given an unordered stack and the required order for the stack, produce a list of sequential instructions so that the human can reorder the stack. To make it easy for the operator, and to minimize the number of errors, the instruction list must:

1. Only refer to 3 instructions:

   TOP X

   Place widget X on top of the stack

   BELOW X, Y

   Insert widget Y below widget X

   SWAP X, Y

   Swap widgets X and Y

2. Be as short as possible
3. Be as easy as possible. That is: if there is more than one instruction list of minimal length, choose the easiest one. Placing widgets on top of the stack is easier than inserting widgets within the stack, which is easier than swapping two widgets (i.e. the instructions were defined in order from easiest to hardest).

4. End with the no-op instruction DONE.

Example

Here is some code to generate assembly line outputs:

   PROPERLY_ORDERED_WIDGETS =:  ;: 'RED ORANGE YELLOW GREEN BLUE INDIGO VIOLET'
   assembly_line            =:  ({~ ?~@:#) bind PROPERLY_ORDERED_WIDGETS
   ] AL =:  assembly_line ''
+----+------+------+------+------+---+-----+
|BLUE|INDIGO|VIOLET|ORANGE|YELLOW|RED|GREEN|
+----+------+------+------+------+---+-----+
   human_sort AL
1. TOP RED 
2. BELOW RED, ORANGE
3. BELOW ORANGE, YELLOW 
4. BELOW YELLOW, GREEN
5. DONE.

Exposition

If the widgets are properly ordered thus:

1. RED
2. ORANGE
3. YELLOW
4. GREEN
5. BLUE
6. INDIGO
7. VIOLET

and they came off the assembly line thus:

1. BLUE
2. INDIGO
3. VIOLET
4. ORANGE
5. YELLOW
6. RED
7. GREEN

then you should produce the instruction list:

1. TOP RED

2. BELOW RED , ORANGE_

3. BELOW ORANGE, YELLOW

4. BELOW YELLOW, GREEN

5. DONE.

Which would cause the operator to produce, after each step:

1. TOP RED

   1. RED
   2. BLUE
   3. INDIGO
   4. VIOLET
   5. ORANGE
   6. YELLOW
   7. GREEN

2. BELOW RED, ORANGE

   1. RED
   2. ORANGE
   3. BLUE
   4. INDIGO
   5. VIOLET
   6. YELLOW
   7. GREEN

3. BELOW ORANGE, YELLOW

   1. RED
   2. ORANGE
   3. YELLOW
   4. BLUE
   5. INDIGO
   6. VIOLET
   7. GREEN

4. BELOW YELLOW, GREEN

   1. RED
   2. ORANGE
   3. YELLOW
   4. GREEN
   5. BLUE
   6. INDIGO
   7. VIOLET

5. DONE.

Note that the following instruction list, while effective and equally short, is harder. Therefore it is not to be produced:

1. TOP RED

2. SWAP VIOLET , GREEN

3. SWAP YELLOW , INDIGO

4. SWAP BLUE , ORANGE

5. DONE.

Solutions

Post your solutions here.

Comments

You can use @SIG@ to sign your comments. This section is possibly temporary(?).

• This seems like a better sequence for the "human" in the above example:

  1. TOP GREEN

  2. TOP YELLOW

  3. TOP ORANGE

  4. TOP RED

  5. DONE

  -- Raul Miller 2005-11-04 04:22:24

• To generate a sequence of TOP instructions sufficient to sort the widgets (any better sequence which contains BELOW or SWAP instructions must be shorter) you might use:

   tsort=: (}. #~ [: +./\ 2: </\ ])@\:@i. { ]
   PROPERLY_ORDERED_WIDGETS tsort AL
+-----+------+------+---+
|GREEN|YELLOW|ORANGE|RED|
+-----+------+------+---+

• -- Raul Miller 2005-11-04 04:29:44