If you have ever had any exposure to Japanese or East Asian culture you will have surely encountered the Amidakuji game:
As Wikipedia explains, it is a type of lottery drawn on paper and used to randomly select a permutation of N items.
For example, it may be used to randomly assign a starting sequence to N people, or N prizes to N people, and so on.
The trick to understanding why the game represents a permutation is to realize that every horizontal stroke (called a "leg") swaps its two items in place.
The same Wikipedia page also explains that each permutation P of N items corresponds to an infinite number of Amidakuji diagrams. The one(s) with the least number of horizontal strokes (legs) are called the "primes" of that particular permutation P.
Your task is to receive an Amidakuji diagram with 2 or more vertical lines (in this example they are 6) in this format (minus the letters):
A B C D E F | | | | | | |-| |-| |-| | |-| |-| | | | | | |-| | |-| |-| | | | |-| |-| | | |-| | | |-| | |-| | |-| |-| | | | |-| | |-| | | | | | | B C A D F E
And produce one of its primes (again, minus the letters):
A B C D E F | | | | | | |-| | | |-| | |-| | | | | | | | | | B C A D F E
The first and last lines with the letters are not part of the format. I have added them here to show the permutation. It is also not required that the first or last lines contain no legs
|-|, nor that the output be as compact as possible.
This particular input example is one of the (infinite) ASCII representations of the Amidakuji diagram at the top of the Wikipedia page.
There is one non-obvious rule about these ASCII diagrams: adjacent legs are forbidden.
|-|-| <- NO, this does not represent a single swap!
Wikipedia explains a standard procedure to obtain a prime from a diagram, called "bubblization", which consists of applying the following simplifications over and over:
1) Right fork to left fork:
| |-| |-| | |-| | -> | |-| | |-| |-| |
2) Eliminating doubles:
|-| | | |-| -> | |
I am not sure whether that explanation is unambiguous. Your code may use that technique or any other algorithm that produces the required primes.
Shortest code wins.
Standard rules and standard allowances apply. (If the input is not valid, your program may catch fire. Input/output formats may be stdin/stdout, string argument, list of lines, matrix of chars, whatever works best for you, etc.)