11
\$\begingroup\$

If you have ever had any exposure to Japanese or East Asian culture you will have surely encountered the Amidakuji game:

enter image description here

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

enter image description here

\$\endgroup\$
6
  • 3
    \$\begingroup\$ This is a very interesting challenge. I might take a while producing an ungolfed solution, heh. \$\endgroup\$ Oct 6, 2018 at 16:21
  • \$\begingroup\$ Does the output need to be as compact as possible or is any amount of vertical space allowed as long as the number of legs is minimal? \$\endgroup\$
    – Laikoni
    Oct 6, 2018 at 22:05
  • \$\begingroup\$ @Laikoni any amount of vertical space is allowed. \$\endgroup\$
    – Tobia
    Oct 7, 2018 at 1:59
  • \$\begingroup\$ Do bubblization and inverse bubblization reach every same result Amidakuji ? \$\endgroup\$
    – l4m2
    Oct 22, 2018 at 17:59
  • \$\begingroup\$ @l4m2 what is inverse bubblization? \$\endgroup\$
    – Tobia
    Oct 24, 2018 at 11:01

5 Answers 5

5
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Wow. I just spent a long time making a Python 3 version, but it's 526 bytes, heh. \$\endgroup\$ Oct 7, 2018 at 0:39
  • \$\begingroup\$ I just fed hundreds of random diagrams to your code and I can confirm that it outputs correct primes! \$\endgroup\$
    – Tobia
    Oct 9, 2018 at 6:55
4
\$\begingroup\$

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
\$\endgroup\$
4
  • \$\begingroup\$ Good job! I fed 1000s of random diagrams to your code and it solved them all. \$\endgroup\$
    – Tobia
    Oct 10, 2018 at 18:40
  • 1
    \$\begingroup\$ (_:[]) can be just [_] and p?q=(p:fst q,snd q) can be p?(f,s)=(p:f,s). Instead of defining c 0='-';c _=' '; and then using c m, " -"!!(0^abs m) should work. \$\endgroup\$
    – Laikoni
    Oct 14, 2018 at 13:17
  • 1
    \$\begingroup\$ (g 0) does not need brackets and a let in a guard is shorter than where. All together 274 bytes: Try it online! \$\endgroup\$
    – Laikoni
    Oct 14, 2018 at 13:25
  • 1
    \$\begingroup\$ Your fixpoint function % can be inlined with until(\x->g 0 x==x)(g 0). \$\endgroup\$
    – Laikoni
    Oct 16, 2018 at 17:00
2
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ Do you have any advice on how to run your code with Retina.exe? I think I have the correct source (105 bytes) but it outputs nothing. I tried the Hello World from the Retina examples and it works. Can you upload the source somewhere, or Base64 encode it and put it in a pastebin, in case I got the encoding wrong? \$\endgroup\$
    – Tobia
    Oct 9, 2018 at 7:12
  • \$\begingroup\$ @Tobia Sorry, but I can't remember how to use Retina.exe; I think I might have used it once or twice but these days I just use Try It Online. \$\endgroup\$
    – Neil
    Oct 9, 2018 at 8:03
  • \$\begingroup\$ LOL I'm dumb! I was using some cutting-edge version instead of 0.8.2. Now I got my harness to fed hundreds of random diagrams to your code and I can confirm that it always outputs the correct primes. Good job! \$\endgroup\$
    – Tobia
    Oct 9, 2018 at 15:36
  • \$\begingroup\$ @Tobia Thanks for testing! Tweaks needed for Retina 1: $**; -1=0; 1_; ;. (roughly); **\. \$\endgroup\$
    – Neil
    Oct 10, 2018 at 8:24
1
\$\begingroup\$

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.

\$\endgroup\$
14
  • \$\begingroup\$ I'm curious about your approach; I'll take a look! In the meantime, you can save some bytes by replacing " "+i.replace("|","")+" " with i.split("|") in . the first line of your p function... \$\endgroup\$
    – Chas Brown
    Oct 7, 2018 at 1:05
  • \$\begingroup\$ A few more standard python golfing tweaks to get it to 479 bytes. \$\endgroup\$
    – Chas Brown
    Oct 7, 2018 at 1:21
  • \$\begingroup\$ Looks like my algorithm is suboptimal... \$\endgroup\$ Oct 7, 2018 at 1:28
  • \$\begingroup\$ Yah, not sure why that's happening... \$\endgroup\$
    – Chas Brown
    Oct 7, 2018 at 1:33
  • \$\begingroup\$ Not always...sometimes right-fork to left-fork isn't doable, but left-fork to right-fork is. In that specific case, it's just a matter of doing the opposite there. Perhaps I need to do both? \$\endgroup\$ Oct 7, 2018 at 1:36
0
\$\begingroup\$

Stax, 45 bytes

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

Run and debug it

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.