Amidakuji (阿弥陀籤) simplification

Question

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

Answer 1

Python 2, 322 240 bytes

def f(X):
 X=[[c>' 'for c in s.split('|')]for s in X.split('\n')];h=L=len(X[0])-1;p=range(L)
 for x in X:p=[a-x[a]+x[a+1]for a in p]
 while h:h=i=0;exec"if p[i]>p[i+1]:print'|'+i*' |'+'-|'+(L-i-2)*' |';h=p[i],p[i+1]=p[i+1],p[i]\ni+=1\n"*~-L

Try it online!

A function which takes the string in the specified form, and prints out the reduced Amidakuji in that form as well.

The basic idea here is to first convert the input into a permutation (in the for x in X loop); and then in the while loop, perform a bubble sort of that permutation, since as the wikipedia article notes, this results in a 'prime' Amidakuji.

Answer 2

Haskell, 288 bytes

p x(_:[])=x
p(x:y:z)(_:b:c)|b=='-'=y:p(x:z)c|0<1=x:p(y:z)c
c 0='-'
c _=' '
_#1="|"
m#n='|':c m:(m-1)#(n-1)
p?q=(p:fst q,snd q)
f%b|b==f b=b|0<1=f%f b
f l=reverse$snd$(g 0)%(foldl p[1..n]l,[])where n=1+div(length$l!!0)2;g b((x:y:z),a)|x>y=y?g(b+1)(x:z,a++[b#n])|0<1=x?g(b+1)(y:z,a);g _ x=x

Try it online!

Explanation

-- the function p performs the permutation of a list
-- according to a single line from amidakuji board
p x (_:[]) = x
p (x:y:z) (_:b:c)
    | b == '-' = y : p (x : z) c
    | otherwise = x : p (y : z) c

-- helper to select either leg '-' or empty cell
c 0 = '-'
c _ = ' '

-- the # operator generates an amidakuji line containing one leg
-- which corresponds to one swap during bubble sort

-- terminal case, just one edge left
_ # 1 = "|"
-- each cell contains an edge '|' and either space or a '-' for the "active" cell
m # n = '|' : c m : (m - 1) # (n - 1)

-- helper to find the limit value of a function iteration
f % b
    | b == f b = b  -- return the value if it is unchanged by the function application 
    | otherwise = f % f b -- otherwise repeat

-- helper to appropriately combine q which is the result of invocation of 
-- the function g (see below), and a character p
p ? q = (p : fst q, snd q)

-- the function that does the work
f l = reverse $ snd $ (g 0) % (foldl p [1..n] l, []) where
    -- number of lines on the board
    n = 1 + div (length $ l !! 0) 2
    -- apply one iteration of bubble sort yielding (X, Y)
    -- where X is partially sorted list and Y is the output amidakuji
    g b ((x:y:z), a)
        -- if we need to swap two elements, do it and add a line to our board
        | x > y = y ? g (b + 1) (x:z, a ++ [b # n])
        -- if we don't need to, just proceed further
        | otherwise = x ? g (b + 1) (y:z, a)
    -- terminal case when there is only one element in the list
    g _ x = x

Answer 3

Retina 0.8.2, 105 bytes

$
¶$%`
r`.?.\G
 1$.'$*
+r-1=`\|(-?.?[- 1]*¶.*)(1+)
$2$1
-
 
1G`
;{`\b(1+) \1
$1-$1
*`1+
|
(1+)-(1+)
$2 $1

Try it online! Explanation:

$
¶$%`

Duplicate the last line.

r`.?.\G
 1$.'$*

Number the columns in the last line.

+r-1=`\|(-?.?[- 1]*¶.*)(1+)
$2$1

Move the numbers up until they get to the first line. At each iteration, only the rightmost number -1= is moved. It is moved to the rightmost | unless it is preceded by a - in which case it is moved to the previous |. (The r indicates that the regex is processed as if it was a lookbehind, which makes it marginally easier to match this case.) This calculates the permutation that the Amidakuji transforms into sorted order.

-
 
1G`

Keep just the list of numbers, deleting the -s and anything after the first line.

;{`

The rest of the program then is then repeated sort the list back into order, but the final list is not printed, however as it takes an iteration for Retina 0.8.2 to notice that the list is in order, a line with no legs is generated at the end, which I believe is acceptable.

\b(1+) \1
$1-$1

Mark all available pairs of adjacent unsorted numbers with -s for the legs.

*`1+
|

Print the legs but with the numbers replaced with |s.

(1+)-(1+)
$2 $1

Actually perform the swaps.

Answer 4

Python 3, 524 488 486 bytes

-38 bytes thanks to ovs!

from numpy import*
A=array;E=array_equal
K=[0]
def r(a,m,n):
	X=len(m);Y=len(m[0]);W,H=a.shape
	for x in range(W-X+1):
		for y in range(H-Y+1):
			if E(a[x:x+X,y:y+Y],A(m)):a[x:x+X,y:y+Y]=A(n)
	return a
def p(a):
	b=A([[j>" "for j in i]for i in[i.split("|")for i in a.split("\n")]])
	while E(a,b)<1:a=b;Z=K*3;O=[0,1,0];T=[K+O,O+K]*2;D=[O,O],[Z,Z];P=[Z,O],[O,Z];*R,_=T;_,*L=T;b=r(r(r(r(r(r(a[any(a,1)],R,L),*D),*P),L,R),*D),*P)
	for i in a:print("",*[" -"[j]for j in i[1:-1]],"",sep="|")

Try it online!

This converts the Amidakuji to a 2D binary array, and directly reduces it using the rules.

Answer 5

Stax, 45 bytes

⌐φ²MC½↕uö∩┴║%≤Oo╧i╕ïô§ê{δ¿k>┴ê◘►╢lµ∙→Z↔8╨─(·£

Run and debug it