Jeśli kiedykolwiek miałeś styczność z kulturą japońską lub wschodnioazjatycką, na pewno spotkałeś się z grą Amidakuji:

Jak wyjaśnia Wikipedia , jest to rodzaj loterii rysowanej na papierze i służącej do losowego wybierania permutacji N. przedmiotów.

Na przykład można go użyć do losowego przypisania sekwencji początkowej N osobom lub N nagród N osobom i tak dalej.

Sztuczka, aby zrozumieć, dlaczego gra reprezentuje permutację, polega na uświadomieniu sobie, że każde poziome pociągnięcie (zwane „nogą”) zamienia dwa elementy na swoim miejscu.

Ta sama strona Wikipedii wyjaśnia również, że każda permutacja P elementów N odpowiada nieskończonej liczbie diagramów Amidakuji. Te z najmniejszą liczbą poziomych pociągnięć (nóg) są nazywane „liczbami pierwszymi” tej konkretnej permutacji P.

Twoim zadaniem jest otrzymanie diagramu Amidakuji z 2 lub więcej pionowymi liniami (w tym przykładzie jest ich 6) w tym formacie (bez liter):

A B C D E F
| | | | | |
|-| |-| |-|
| |-| |-| |
| | | | |-|
| |-| |-| |
| | |-| |-|
| | |-| | |
|-| | |-| |
|-| |-| | |
| |-| | |-|
| | | | | |
B C A D F E

I utwórz jedną ze liczb pierwszych (ponownie bez liter):

A B C D E F
| | | | | |
|-| | | |-|
| |-| | | |
| | | | | |
B C A D F E

Pierwszy i ostatni wiersz z literami nie są częścią formatu. Dodałem je tutaj, aby pokazać permutację. Jest również nie wymaga, że pierwsze lub ostatnie wiersze zawierają żadnych nóg |-|, ani że wyjście być możliwie jak najmniejsze.

Ten konkretny przykład wejściowy jest jedną z (nieskończonych) reprezentacji ASCII diagramu Amidakuji na górze strony Wikipedii.

Istnieje jedna nieoczywista zasada dotycząca tych diagramów ASCII: zabronione jest sąsiadowanie nóg.

|-|-|  <-  NO, this does not represent a single swap!

Wikipedia wyjaśnia standardową procedurę uzyskiwania liczby pierwszej z diagramu, zwaną „bubblizacją”, która polega na ciągłym stosowaniu następujących uproszczeń:

1) Od prawego widelca do lewego widelca:

| |-|      |-| |
|-| |  ->  | |-|
| |-|      |-| |

2) Eliminacja podwójnych:

|-|        | |
|-|   ->   | |

Nie jestem pewien, czy to wyjaśnienie jest jednoznaczne. Twój kod może używać tej techniki lub dowolnego innego algorytmu, który generuje wymagane liczby pierwsze.

Najkrótszy kod wygrywa.

Obowiązują standardowe zasady i standardowe dodatki. (Jeśli dane wejściowe są niepoprawne, twój program może się zapalić. Formaty wejścia / wyjścia mogą być standardowe: standardowe / standardowe, argumenty łańcuchowe, lista linii, macierz znaków, cokolwiek działa najlepiej dla ciebie, itp.)

Python 2 , 322 240 bajtów

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

Wypróbuj online!

Funkcja, która przyjmuje ciąg znaków w określonej formie i drukuje również zredukowane Amidakuji w tej formie.

Podstawową ideą jest tutaj najpierw konwersja danych wejściowych na permutację (w for x in Xpętli); a następnie w whilepętli wykonaj bąbelkową permutację, ponieważ jak zauważa artykuł w Wikipedii, skutkuje to „pierwszorzędnym” Amidakuji.

Haskell , 288 bajtów

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

Wypróbuj online!

Wyjaśnienie

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

Retina 0.8.2 , 105 bajtów

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

Wypróbuj online! Wyjaśnienie:

$
¶$%`

Powiel ostatnią linię.

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

Ponumeruj kolumny w ostatnim wierszu.

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

Przesuwaj liczby w górę, aż dojdą do pierwszego wiersza. Przy każdej iteracji -1=przenoszona jest tylko liczba z prawej strony . Zostaje przesunięty na skrajny prawy, |chyba że poprzedza go poprzedni -przypadek |. ( rWskazuje, że wyrażenie regularne jest przetwarzane tak, jakby to był wygląd, co sprawia, że ​​marginalnie łatwiej jest dopasować ten przypadek.) Oblicza to permutację, którą Amidakuji przekształca w uporządkowaną kolejność.

-
 
1G`

Zachowaj tylko listę liczb, usuwając -s i cokolwiek po pierwszym wierszu.

;{`

Następnie reszta programu jest następnie powtarzana, sortuje listę z powrotem w kolejności, ale ostateczna lista nie jest drukowana, jednak ponieważ iteracja dla Retina 0.8.2 wymaga zauważenia, że ​​lista jest w porządku, linia bez nóg jest wygenerowane na końcu, które moim zdaniem są do zaakceptowania.

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

Zaznacz wszystkie dostępne pary sąsiednich nieposortowanych liczb za pomocą -s dla nóg.

*`1+
|

Wydrukuj nogi, ale z liczbami zastąpionymi przez |s.

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

Właściwie wykonaj wymiany.

-38 bajtów dzięki 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="|")

Wypróbuj online!

Konwertuje to Amidakuji na dwuwymiarową tablicę binarną i bezpośrednio redukuje ją za pomocą reguł.

Stax , 45 bajtów

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

Uruchom i debuguj