Załóżmy, że pewnego dnia przekopujesz się przez duże pudło nieużywanych kabli komputerowych i adapterów (USB na USB mini, VGA na DVI itp.). Wszędzie są splątane sznury, które robią niezły bałagan, i zastanawiasz się, czy możesz uprościć rzeczy, łącząc wszystkie sznury w jedną długą nić, a następnie po prostu zwijając.

Pytanie brzmi, czy możliwe jest połączenie wszystkich przewodów i adapterów w jedną długą linię taką jak ta? Oczywiście nie zawsze jest to możliwe, np. Jeśli masz tylko dwa przewody z całkowicie różnymi wtyczkami, nie można ich ze sobą połączyć. Ale jeśli masz trzeci przewód, który można podłączyć do obu z nich, możesz połączyć wszystkie przewody razem.

Nie obchodzi Cię, jakiego rodzaju wtyczki znajdują się na końcach nici typu all-cord. Nie muszą się ze sobą łączyć, aby utworzyć pętlę. Chcesz tylko wiedzieć, czy możliwe jest wykonanie nici z przewodem, a jeśli tak, to jak to zrobić.

Wyzwanie

Napisz program lub funkcję, która pobiera ciąg wielowierszowy, w którym każda linia przedstawia jeden z posiadanych przewodów. Przewód składa się z jednego lub więcej myślników ( -), z wtyczką po obu stronach. Wtyczka jest zawsze jednym z 8 znaków ()[]{}<>.

Oto niektóre prawidłowe przewody:

>->
(--[
}-{
<-----]
(---)

Ale to nie są:

-->
(--
)--
[{
---

Podczas podłączania przewodów można łączyć ze sobą tylko wtyczki dokładnie tego samego typu wspornika.

Oto niektóre prawidłowe połączenia kablowe:

...---((---...
...---))---...
...---]]---...
...---{{---...
...---<<---...

A te są nieprawidłowe:

...---()---...
...---)(---...
...---{]---...
...---{[---...
...---><---...
...--->)---...

Jeśli wszystkie sznury na wejściu mogą zostać uporządkowane i połączone razem w jedną długą nić, wyprowadzić tę nić na stdout w jednym wierszu (z opcjonalnym końcowym znakiem nowej linii). Gdy istnieje wiele rozwiązań, możesz wybrać jedno z nich do wydrukowania. Jeśli utworzenie pojedynczej nici nie jest możliwe, nic nie wypisz (lub wypisz pusty ciąg z opcjonalnym końcowym znakiem nowej linii).

Na przykład, jeśli dane wejściowe to

[-->
{---]
>----{

wyjście może być

[-->>----{{---]

gdzie wszystkie sznury są ze sobą połączone.

Jednak jeśli dane wejściowe były

[-->
{---]

przewody nie mogą być podłączone, więc nie będzie wyjścia.

Należy pamiętać, że sznury można odwrócić tak bardzo, jak to konieczne do wykonania połączeń. np. [-->i <--]są faktycznie tym samym przewodem, ponieważ mogą wykonywać ten sam typ połączeń. Niektóre wyjścia mogą zależeć od odwrócenia przewodów wejściowych.

Na przykład

(-[
}--]

może mieć wynik

(-[[--{

gdzie drugi przewód jest odwrócony, lub

}--]]-)

gdzie pierwszy przewód jest odwrócony.

(Zauważ, że ogólnie przerzucanie całego wyjścia jest poprawne, ponieważ jest takie samo, jak początkowo przerzucanie każdego przewodu osobno).

Długości przewodów wyjściowych powinny oczywiście odpowiadać długości odpowiednich przewodów wejściowych. Ale sznury mogą być ponownie uporządkowane i odwrócone tak, jak chcesz, aby uzyskać pasmo wszystkich kabli. Wejście zawsze będzie zawierało co najmniej jeden przewód.

Najkrótszy kod w bajtach wygrywa.

Przypadki testowe

Obudowy z wyjściem:

[-->
{---]
>----{
gives
[-->>----{{---]
or
[---}}----<<--]

(-[
}--]
gives
(-[[--{
or
}--]]-)

(-)
gives
(-)

[--{
gives
[--{
or
}--]

[-]
]-[
gives
[-]]-[
or
]-[[-]

[----->
)------------[
{--<
}---)
could give
[----->>--}}---))------------[
or
>--}}---))------------[[----->
or
}---))------------[[----->>--}
or
{--<<-----]]------------((---{
etc.

>-->
>->
>--->
could give
>-->>->>--->
or
>--->>-->>->
or
>->>-->>--->
or
<--<<---<<-<
etc.

(-]
]->
>-}
}-)
)-[
[-<
<-{
{-(
could give
(-]]->>-}}-))-[[-<<-{{-(
or
{-((-]]->>-}}-))-[[-<<-{
or
<-{{-((-]]->>-}}-))-[[->
etc.

Obudowy bez wyjścia:

[-->
{---]

[-]
[-]

(-]
]->
}-)

>->
>-->
]---]

[-------------------]
]-------------------[
[-----------------]
[-----------------]

{--[
]--}

Nieczytelny , 3924 bajtów

Po raz pierwszy zaimplementowałem w Unreadable strukturę przypominającą stos wywołań.

(Pierwsza wersja tego miała ponad 5300 bajtów, żeby dać wyobrażenie o tym, ile grałem w golfa.)

„” „” „” „” „” „” „„ ”„ ”„ ”„ ”„ ”„ „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ” „” „” „” „” „„ ”„ ”„ ”„ ”„ ”„ ”„ „” „„ ”„ „” „” „” „” „” „” „” „” „” „” „” „” „” „” „” „” „” „” „” „„ „” „” „” „„ ”„ ”„ ”„ ”„” „” „” „” „„ ”„ ”„ ”„ „” „” „” „„ ”„ „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ” „” „” „” „” „„ ”„ ”„ „” „” „” „” „” „„ ”„ „” „” „” „” „” „” „” „” „” „” „„ ”„ ”„ „” „„ ”„ ”„ ”„ „” „„ ”„ „” „” „„ ”„ ”„ ”„ ”„” „” „” „„ ”„ ”„ „” „„ ”„ ”„ ”„ „” „„ ”„ „” „„ ”„ ”„ ”„ ”„ ”„ ” „” „” „” „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ”„ „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ”„ ” „” „” „” „” „” „” „” „„ ”„ ”„ ”„ „” „” „„ ”„ „” „” „” „” „”„” „” „” „” „„ ”„ ”„ „” „” „” „” „„ ”„ „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ” „” „” „” „” „„ ”„ ”„ ”„ „” „” „” „„ ”„ „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ” „” „„ ”„ ”„ „” „” „„ ”„ ”„ ”„ ”„ ”„ ”„ „” „„ ”„ ”„ ”„ ”„ ”„” „” „” „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ”„ „” „„ ”„ „” „” „” „” „” „” „” „„ ”„ ”„ ”„ ”„ ”„ ”„ „” „” „” „” „„ ”„ „” „” „” „” „” „” „” „” „” „” „„ ”„ ”„ ”„ ”„ „” „” „” „„ ”„ „” „” „” „„ ”„ ”„ ”„ ”„” „” „” „” „„ ”„ ”„ ”„ ”„ ”„ ”„ „” „„ ”„ „” „” „” „” „” „” „” „” „” „” „” „” „” „„ ”„ ”„ ”„ ”„ „” „„ ”„ „” „” „” „” „” „” „” „” „” „„ ”„ ”„ „” „” „„ ”„ „” „” „„ ”„ „” „„ ”„ „” „„ ”„ ”„ ”„ ”„” „” „” „” „„ ”„ ”„ „” „” „” „” „„ ”„ „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ” „” „” „” „” „„ ”„ ”„ ”„ „” „” „” „„ ”„ „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ” „” „” „” „” „„ ”„ ”„ „” „” „” „” „” „„ ”„ „” „” „” „” „” „”„” „” „” „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ”„ „” „„ ”„ ”„ ”„ ”„ ”„ „” „” „” „” „„ ”„ ”„ „” „„ ”„ ”„ ”„ „” „„ ”„ „” „„ ”„ „” „” „” „” „” „” „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ”„ „” „„ ”„ ”„ ”„ „” „” „” „”„” „” „” „” „” „” „„ ”„ „” „” „” „” „„ ”„ „” „” „” „” „” „” „” „” „” „” „„ ”„ ”„ „” „” „” „„ ”„ „” „„ ”„ „” „„ ”„ ”„ ”„ ” „” „” „” „” „” „” „” „„ ”„ ”„ ”„ ”„ ”„ „” „„ ”„ ”„ ”„ ”„ ”„ ”„” „” „” „” „„ ”„ ”„ „” „” „” „” „” „„ ”„ „” „” „” „” „” „” „” „” „” „” „” „” „„ ”„ „” „” „” „„ ”„ „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ” „” „„ ”„ ”„ „” „” „” „” „” „” „” „„ ”„ „„ ”„ ”„ ”„ ”„ ”„ ”„ ”„” „” „” „” „„ ”„ ”„ „” „” „” „” „” „„ ”„ „” „” „” „” „” „” „” „” „” „” „„ ”„ ”„ ”„ „” „” „” „„ ”„ „” „„ ”„ ”„ ” „” „” „” „” „„ ”„ ”„ „” „” „” „” „” „„ ”„ „” „” „” „” „” „”„” „” „” „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ”„ „” „„ ”„ ”„ ”„ ”„ ”„ „” „” „” „” „„ ”„ ”„ „” „„ ”„ ”„ ”„ „” „„ ”„ „” „„ ”„ „” „” „” „” „” „” „” „„ ”„ ”„ ”„ „” „” „” „” „„ ”„ „” „” „„ ”„ ”„ ”„ ”„” „” „” „” „” „” „„ ”„ „” „” „” „„ ”„ „” „„ ”„ ”„ ”„ ”„ „” „” „” „” „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ”„ „” „„ ”„ ”„ ”„ ”„ ”„ „” „” „„ ”„ ”„ „” „” „„ ”„ „” „” „” „„ ”„ ”„ „” „” „” „” „” „”„” „” „” „” „” „” „” „„ ”„ ”„ ”„ „” „” „„ ”„ „” „” „” „” „” „” „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ”„ „” „„ ”„ ”„ ”„ ” „” „” „” „” „„ ”„ ”„ „” „” „” „” „” „„ ”„ „” „” „” „” „” „”„” „” „” „” „„ ”„ „” „” „” „” „” „„ ”„ „” „„ ”„ ”„ „” „” „” „” „” „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ”„ ”„ ”„ ”„ „” „„ ”„ ”„ ”„ ”„ ”„ „” „” „” „” „” „„ ”„ ”„ ”„ ”„ ”„ ”„ „” „„ ”„ „” „” „” „” „” „”„” „” „” „” „„ ”„ „” „” „” „” „„ ”„ „” „„ ”„ „” „„ ” „” „” „” „” „” „” „„ ”„ ”„ ”„ ”„ „” „„ ”„ „” „” „” „” „” „” „” „” „” „” „„ ”„ ”„ „” „” „” „” „” „„ ”„ „” „” „” „” „” „”„” „” „” „” „” „” „” „„ ”„ ”„ ”„ ”„ „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ” „” „” „” „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ”„ ”„ „” „” „” „” „” „” „” „” „” „” „” „„ ”„ ”„ „” „” „” „„ ”„ „” „„ ”„ ”„ ”„ „” „” „”„” „” „” „” „„ ”„ ”„ „” „” „” „” „” „„ ”„ „” „” „” „” „” „” „” „” „” „” „„ ”„ ”„ ”„ „” „” „” „” „„ ”„ „” „” „” „” „” „” „” „” „” „” „” „” „” „„ ”„ ”„ ”„ „” „„ ”„ „” „” „” „” „” „”„” „” „” „” „” „” „„ ”„ ”„ ”„ ”„ „” „„ ”„ „” „” „” „” „” „” „” „” „” „” „” „” „” „„ ”„ ”„ ”„ „” „„ ”„ „” „” „” „” „” „” „” „” „” „” „„ ”„ ”„ ”„ ”„ ”„ ”„ „” „„ ”„ „” „” „” „” „” „”„” „” „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ”„ „” „„ ”„ „” „” „” „” „” „” „” „” „” „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ”„ „” „” „” „” „” „” „” „” „” „” „” „” „„ ”„ „” „” „” „” „” „„ ”„ „” „„ ”„ ”„ ”„ ”„ ”„ ”„” „” „” „” „„ ”„ ”„ ”„ „” „” „” „” „„ ”„ „” „” „” „” „” „” „” „” „” „” „” „„ ”„ ”„ „” „” „” „„ ”„ „” „„ ”„ „” „” „” „” „” „” „” „” „” „” „” „” „„ ”„ ”„ ”„ „” „„ ”„ „” „” „” „” „” „”„” „” „” „” „„ ”„ ”„ „” „” „” „” „„ ”„ „” „„ ”„ ”„ ” „” „” „” „” „„ ”„ ”„ ”„ „” „” „” „„ ”„ „” „„ ”„ ”„ ”„ ”„ ” „” „” „” „” „” „” „” „„ ”„ ”„ ”„ „” „„ ”„ „” „” „” „” „” „”„” „” „” „” „„ ”„ ”„ ”„ „” „” „” „„ ”„ „” „” „” „” „” „” „” „” „” „” „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ”„ „” „„ ”„ ”„ ”„ ” „” „” „” „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ”„ „” „„ ”„ ”„ ”„ ”„ ”„ ”„” „” „” „” „” „” „” „„ ”„ ”„ ”„ „” „” „„ ”„ „” „” „” „” „” „” „” „” „” „” „” „” „„ ”„ ”„ ”„ ”„ „” „„ ”„ „” „” „” „” „” „” „” „” „” „” „” „„ ”„ ”„ ”„ ”„ ”„ „” „„ ”„ ”„ ”„ ”„ ”„ ”„” „” „” „„ ”„ ”„ „” „„ ”„ ”„ ”„ ”„ „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ” „” „” „” „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ”„ „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ” „” „„ ”„ ”„ ”„ ”„ ”„ ”„ „” „” „” „” „„ ”„ „” „” „” „” „” „”„” „” „” „” „” „” „„ ”„ ”„ ”„ ”„ ”„ „” „„ ”„ „” „” „” „” „” „” „” „” „” „„ ”„ ”„ ”„ „” „” „” „” „„ ”„ „” „” „” „” „” „” „” „” „” „” „” „” „” „” „” „” „” „” „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ”„” „” „” „„ ”„ ”„ „” „„ ”„ ”„ ”„ „” „„ ”„ „” „” „„ ” „” „” „” „” „” „” „„ ”„ ”„ ”„ „” „„ ”„ „” „„ ”„ ”„ ”„ ”„ ” „” „„ ”„„” „” „” „” „” „” „” „” „” „” „” „” „„ ”„ „” „” „” „„ ”„ ”„ ” „” „„ ”„ ”„ „” „” „”„” „” „” „” „” „” „” „” „” „” „” „” „„ ”„ „” „” „” „” „„ ” „” „„ ”„ ”„ „” „” „”

Wyjaśnienie

Rozważ przykładowe dane wejściowe:

>--{
[---}

Przez większość wykonywania taśma jest układana w następujący sposób:

• Komórki od 0 do 5 to lokalizacje różnych zmiennych.

• Komórka 6 i następne zawierają wszystkie informacje o zestawie kabli w twoim pudełku:

  

• Pozostałe komórki po „zerowym terminatorze” zawierają stos. Każda „ramka stosu” jest pojedynczą komórką, która wskazuje na pierwszą komórkę kabla (komórkę „start plug”). W powyższym przykładzie, gdy program zdecyduje, że znalazł rozwiązanie, stos będzie zawierał 6 (odnosząc się do >--{pierwszego kabla) i 21 (odnosząc się do {---]lustra drugiego kabla).

Program przebiega w trzech głównych etapach:

1. Przeczytaj całe dane wejściowe i wygeneruj powyższą strukturę, w tym wszystkie kable lustrzane.
2. Wypróbuj wszystkie kombinacje (ale przestań, jeśli znajdziesz rozwiązanie).
3. Jeśli znaleziono rozwiązanie, wypisz je.

Pierwszy etap (odczytywanie danych wejściowych i generowanie struktury kabli) wykorzystuje tylko komórki nr 1 (które wywołam p) i nr 2 (które wywołam ch) i działa w pętli while w następujący sposób:

• Podczas warunku: zwiększaj po 6, odczytaj następny znak (start plug) do komórki *pi sprawdź, czy nie jest -1(EOF).

• Wczytaj kolejne znaki *(p+2)i policz je *(p+1), aż napotkamy coś innego niż -(łącznik). W tym momencie *(p+1)będzie zawierać liczbę łączników (długość kabla) i *(p+2)ostatni znak niebędący łącznikiem (wtyczka końcowa). (Kopiujemy również znaki łącznika do komórki nr 5, abyśmy mogli uzyskać dostęp do tego kodu ASCII później na etapie wyjściowym.)

• W pętli while znajdź wtyczkę lustra i przechowuj ją w *(p+3), a następnie zwiększaj po 2, aż *pwyniesie zero. Pętla wygląda następująco w pseudokodzie:

  while (ch = *p) {
      *(p+3) = (ch -= 40) ? (ch -= 1) ? (ch -= 19) ? (ch -= 31) ? ch-32 ? *p-2 : *p+2 : *p+2 : *p+2 : *p-1 : *p+1
      p += 2
  }
  

• Ta pętla zawsze wykona dwie iteracje (wtyczkę początkową i wtyczkę końcową) i zapisze wyniki w czwartej i szóstej komórce tego kabla. Teraz, jeśli zwróciłeś uwagę, zdajesz sobie sprawę, że szósta komórka jest rzeczywiście właściwym miejscem dla lustrzanej wtyczki końcowej, ale lustrzana wtyczka początkowa znajduje się w komórce oznaczonej „boolean wskazujący oryginalny kabel”. Jest to w porządku, ponieważ potrzebujemy tylko tej komórki, aby była niezerową wartością.

• Ponieważ pwłaśnie zwiększono w sumie 4, teraz wskazuje na komórkę oznaczoną „używany kabel boolowski”. Ustaw *(p+3)na wartość *(p-1). To umieszcza wtyczkę lustrzanego startu we właściwym miejscu.

• Przeczytaj (i odrzuć) jeszcze jeden znak (który, jak się spodziewamy, będzie nową linią, ale program tego nie sprawdza).

ppoczątkowo zaczyna się od 0, ale zwiększa się o 6 wewnątrz warunku while, dlatego dane kabla zaczynają się od komórki nr 6. pjest zwiększany o 4 wewnątrz korpusu pętli, a zatem w sumie 10 dla każdego kabla, co jest dokładnie tym, czego potrzebujemy.

W drugim etapie, komórki # 0-4 są zajęte przez zmienne, że zadzwonię a, p, q, m, i notdone. (Komórka # 5 wciąż pamięta kod ASCII łącznika).

Aby przygotować się do etapu 2, musimy ustawić z *ppowrotem na 0 (komórka oznaczona jako „zero terminator”), aby mogła działać jako terminator dla listy kabli; ustawiamy także q(który jest naszym wskaźnikiem stosu) na p+1(tj. komórkę po „zerowym terminatorze”; tutaj zaczyna się stos); *qdo 1 (pierwszy przedmiot na stosie; dlaczego 1 stanie się później widoczny); i notdonedo 1. Wszystko to odbywa się w jednym oświadczeniu:

*p = (notdone = *(q = p+1) = 1)-1

Drugi etap to także pętla while. Jego stan jest po prostu notdone. W każdej iteracji pętli while może się zdarzyć jedna z następujących czterech rzeczy:

1. Okazuje się, że wszystkie kable są oznaczone jako „w użyciu”. Oznacza to, że znaleźliśmy rozwiązanie (reprezentowane przez bieżącą zawartość stosu).
2. Możemy przejść *qdo innego kwalifikującego się kabla (który natychmiast oznaczamy jako „w użyciu” wraz z jego bliźniakiem), a następnie powrócić (tj. Utworzyć nową ramkę stosu).
3. Nie możemy przejść *qdalej, ponieważ nie ma już innego kwalifikującego się kabla, więc musimy cofnąć się (usunąć ramkę stosu i oznaczyć poprzedni kabel i jego bliźniak jako „nieużywany”).
4. Nie możemy przejść *qdalej, ponieważ nie ma już innego kwalifikującego się kabla i nie możemy cofnąć się, ponieważ doszliśmy do końca stosu. Oznacza to, że nie ma rozwiązania.

Ciało pętli sprawdza każdy z tych czterech warunków w tej kolejności. Oto szczegóły:

1. Ustaw mi pna 1, a następnie w pętli while zwiększaj po 5 (w ten sposób iterując po kablach) i sprawdź, czy *(p+4)(„w użyciu”) jest ustawione. Jeśli nie jest, ustaw mna 0. Na końcu tej pętli mpowie nam, czy wszystkie kable są w użyciu. Jeśli tak, ustaw wartość notdone0, aby zakończyć główną pętlę. W przeciwnym razie przejdź do kroku 2 poniżej.

2. Ustaw pna *q(kabel u góry stosu), a po chwili pętlę podobną do powyższej zwiększaj po 5, aby przejść przez kable. Zaczynając od, *qgwarantujemy, że bierzemy pod uwagę tylko te, których wcześniej nie rozważaliśmy; pamiętaj jednak, że początkowa wartość dla nowej ramki stosu wynosi 1, więc pierwszym spojrzanym kablem jest ten w komórce 6, który jest rzeczywiście pierwszym kablem.

   Dla każdego kabla musimy sprawdzić, *(p+4)czy nie jest on już w użyciu, a także czy *(q-1) ma wartość zero (co oznacza, że ​​jesteśmy na dole stosu, więc nie ma ograniczeń na wtyczce startowej), lub *p (początek kabla wtyczka) jest równa *(*(q-1)+2)(wtyczka końcowa kabla tuż poniżej na stosie). Sprawdzamy równość, ustawiając ana *(*(q-1)+2)i mdo, *p+1a następnie zmniejszając oba w pętli while. Jest +1tak, ponieważ mjest zmniejszane w warunku while, więc jest zmniejszane raz jeszcze a. Jeśli ana końcu jest zero, dwie wtyczki są równe.

   Zatem, jeśli albo *(q-1)było zero, albo porównanie równości się powiodło, kabel kwalifikuje się. Ustaw, *qaby pzastąpić kabel u góry stosu nowym; ustaw mna to samo, aby wskazać, że znaleźliśmy pasujący kabel; a następnie zmniejszenie p. To zmniejszenie jest małą sztuczką, aby spowodować, że pętla while (iteracja po kablach) zakończy się wcześniej; zwiększy psię ponownie o 5, przenosząc go do komórki zawierającej flagę „w użyciu” tego kabla i wiemy, że to zero, ponieważ właśnie to sprawdziliśmy. Wreszcie po iteracji kabla podczas pętli sprawdzamy, czy mnie jest zero. Jeśli tak, znaleźliśmy pasujący kabel i pwskazuje flagę „w użyciu” dla tego pasującego kabla. Ustaw na 1, aby zaznaczyć, że jest w użyciu. Również ustawione*(*(p-1) ? p+5 : p-5)do 1, aby zaznaczyć, że jego bliźniak jest w użyciu. Na koniec zwiększ qi ustaw nowy *qna 1, aby utworzyć nową ramkę stosu.

3. Jeśli po iteracji kabla podczas pętli okaże msię, że wynosi zero, nie ma już pasujących kabli, więc musimy cofnąć się. Zmniejszenie, qaby przejść w dół stosu i sprawdzić, czy nadal wskazuje na kabel (wartość niezerowa). Jeśli tak, oznacz ten kabel i jego bliźniak jako nieużywany. (Przechowujemy wartość *qin, paby to wyrażenie było krótsze w kodzie).

4. Jeśli po zmniejszeniu qokaże się, że wskazuje on na wartość zerową, to jest to „terminator zerowy”, co oznacza, że ​​wyczerpaliśmy stos. Stwierdzamy, że nie ma rozwiązania. Ustawiamy notdonena 0, aby zakończyć główną pętlę.

Trzeci etap to etap wyjściowy. Mogą się zdarzyć dwie rzeczy:

• główna pętla znalazła rozwiązanie, które musimy wyprowadzić, lub
• główna pętla stwierdziła, że ​​nie ma rozwiązania i nic nie wyprowadzamy.

Wygodnie, jeśli nie było żadnego rozwiązania, pjest równa zero, ponieważ możemy ustawić go na wartość *qprzed sprawdzeniem, że do zera; a jeśli nie było to rozwiązanie, pwskazuje na „zero terminatora”, ponieważ tylko powtórzyć za pośrednictwem kabli, dzięki czemu możemy teraz użyć piterację stosie. Więc po prostu iteruj przez stos, wyprowadzając dla każdego kabla wtyczkę początkową ( *(*p)), łączniki (zmniejszając *(*p+1)w pętli while; i używając kodu ASCII łącznika zapisanego w komórce # 5) oraz wtyczkę końcową ( *(*p+2)). Nieważne, że to niszczy informacje o długości kabla; już tego nie potrzebujemy.

CJam, 67

qN%e!{_,2,m*\f{.{_{"()[]{}<>--"_@#1^=}%W%?}_2ew{~\W=#}%0-{;}&}~}%1<

Wypróbuj online

Uwaga: link używa najnowszego kodu z repozytorium (wypchnięty, ale jeszcze nie wydany), ponieważ zawiera poprawkę błędu.

Wyjaśnienie:

Program po prostu wypróbowuje wszystkie permutacje i wszystkie orientacje przewodów.

qN%             read the input and split into lines
e!              generate all permutations
{…}%            map each permutation of cords
  _,            get the number of cords (n)
  2,m*          generate all patterns of n bits (cartesian power of [0 1])
  \f{…}         for each bit pattern and the cord permutation
    .{…}        apply the block to each bit and cord (flipping cords for bit 0)
      _         duplicate the cord
      {…}%      map each character of the cord
        "…"_    push the string of all the plugs (and 2 dashes) and duplicate it
        @#      get the index of the character in the string
        1^      XOR with 1
        =       get the character at this new index (plugs get toggled)
      W%        reverse the cord
                 the stack now has the bit, the original cord and the flipped cord
      ?         if the bit is 1, use the original cord, else use the flipped one
    _           duplicate the array of cords
    2ew         get all pairs of adjacent cords
    {…}%        map each pair of cords
      ~\        dump the 2 cords on the stack and swap them
      W=        get the right plug of the first cord
      #         find its position in the second cord (if 0, we have a match)
    0-          remove all the zeros
    {…}&        if the array is not empty (i.e. we have a mismatch)
      ;         pop the array of cords
  ~             dump all the results for this permutation on the stack
                 (to avoid nested arrays)
1<              get the first result (if any) from the array of all results

JavaScript (ES6), 206

Funkcja rekurencyjna

f=(l,a=l.pop(),x=x=>(z='<>[]{}()')[z.indexOf(x)^1])=>l[0]?l.some((b,i)=>r=[b,x([...b].pop())+b.slice(1,-1)+x(b[0])] .some(b=>r=a[0]==[...b].pop()?b+a:b[0]==[...a].pop()?a+b:0)&&(l=[...l],l[i]=r,f(l)))?r:'':a

Bardziej czytelny

f=(l,a=l.pop(),x=x=>(z='<>[]{}()')[z.indexOf(x)^1])=>
  l[0]?
  l.some((b,i)=>
     r=[b,x([...b].pop())+b.slice(1,-1)+x(b[0])]
     .some(b=>r=a[0]==[...b].pop()?b+a:b[0]==[...a].pop()?a+b:0)
     &&(l=[...l],l[i]=r,f(l))
    )?r:''
 :a

Test

f=(l,a=l.pop(),x=x=>(z='<>[]{}()')[z.indexOf(x)^1])=>l[0]?l.some((b,i)=>r=[b,x([...b].pop())+b.slice(1,-1)+x(b[0])] .some(b=>r=a[0]==[...b].pop()?b+a:b[0]==[...a].pop()?a+b:0)&&(l=[...l],l[i]=r,f(l)))?r:'':a

console.log=(...x)=>O.textContent+=x+'\n'

;[
 //OK
 ['[-->','{---]','>----{']
,['(-[','}--]']
,['(-)']
,['[--{']
,['[-]',']-[']
,['[----->',')------------[','{--<','}---)']
,['>-->','>->','>--->']
,['(-]',']->','>-}','}-)',')-[','[-<','<-{','{-(']
 //KO
,['[-->','{---]']
,['[-]','[-]']
,['(-]',']->','}-)']
,['>->','>-->',']---]']
,['[-------]',']-------[','[-------]','[---------]'] // shortened a little,
,['{--[',']--}']
].forEach(t=>{
  console.log(t+' : "'+f(t)+'"\n')
})

<pre id=O></pre>

JavaScript, 800 bajtów

Dalekie od zoptymalizowanego rozwiązania, ale oto szybki hack razem w javascript (bez fantazyjnego ecma5 lub czegokolwiek, ponieważ go nie znam).

function a(r){function t(r,t){var n=r.slice();return n.splice(t,1),n}function n(r){var t,n={"[":"]","]":"[",">":"<","<":">","(":")",")":"(","{":"}","}":"{"},e=r.split("").reverse();for(t=0;t<e.length;t++)n.hasOwnProperty(e[t])&&(e[t]=n[e[t]]);return e.join("")}function e(r,t){return r.unshift(t),r}var h,u,f=[];if(1==r.length)return r[0];for(h=0;h<r.length;h++){var l=r[h],i=t(r,h),c=l.charAt(0),g=l.charAt(l.length-1);for(u=0;u<i.length;u++){var o=i[u],s=o.charAt(0),p=o.charAt(o.length-1);c==p&&f.push(e(t(i,u),o+l)),g==s&&f.push(e(t(i,u),l+o)),o=n(o),s=o.charAt(0),p=o.charAt(o.length-1),c==p&&f.push(e(t(i,u),o+l)),g==s&&f.push(e(t(i,u),l+o))}}if(f.length<1)return!1;for(h=0;h<f.length;h++){if(1===f[h].length)return f[h][0];f[h]=a(f[h])}for(h=0;h<f.length;h++)if(f[h]!==!1)return f[h];return!1}

Ungolfed, tutaj jest ... Jestem pewien, że co najmniej 2 pętle są tutaj niepotrzebne i że sprawdzanie wejścia pojedynczego elementu na górze i dopasowania pojedynczego elementu na dole jest dziwne ... ale wydaje się, że działa i przetwarza dane wejściowe testu.

function a(inputs)
{
	var i, ii, matches = [];
	if (inputs.length == 1) {
		return inputs[0];
	}
	// For each of the elements in inputs (e1)
	for (i = 0; i < inputs.length; i++) {
		var e1 = inputs[i],
			others = except(inputs,i),
			e1s = e1.charAt(0),
			e1e = e1.charAt(e1.length-1);
		// Compare to each of the other elements in inputs (e2)
		for (ii = 0; ii < others.length; ii++) {
			// get the start and end of the elements to compare (e1s,e1e,e2s,e2e)
			var e2 = others[ii],
				e2s = e2.charAt(0),
				e2e = e2.charAt(e2.length-1);
			// if any of them match up (e1s == e2e || e1s == e2s || e1e == e2s || e1e = e2e)
			// Make a new array of inputs containing the joined elements (as a single element) and all other elements which might join with them
			if (e1s == e2e) {
				matches.push(addTo(except(others,ii),e2+e1));
			}
			if (e1e == e2s) {
				matches.push(addTo(except(others,ii),e1+e2));
			}
			e2 = flip(e2);
			e2s = e2.charAt(0);
			e2e = e2.charAt(e2.length-1);
			if (e1s == e2e) {
				matches.push(addTo(except(others,ii),e2+e1));
			}
			if (e1e == e2s) {
				matches.push(addTo(except(others,ii),e1+e2));
			}
		}
	}

	if (matches.length < 1) {
		return false;
	}

	for (i = 0; i < matches.length; i++) {
		if (matches[i].length  === 1) {
			return matches[i][0];
		} else {
			matches[i] = a(matches[i]);
		}
	};

	for (i = 0; i < matches.length; i++) {
		if (matches[i] !== false) {
			return matches[i];
		}
	};

	return false;

	function except(list,idx)
	{
		var newList = list.slice();
		newList.splice(idx,1);
		return newList;
	}
	function flip(s) {
		var replacements = {
			'[':']',
			']':'[',
			'>':'<',
			'<':'>',
			'(':')',
			')':'(',
			'{':'}',
			'}':'{'
		}, i, a = s.split('').reverse();
		for (i = 0; i < a.length; i++) {
			if (replacements.hasOwnProperty(a[i])) {
				a[i] = replacements[a[i]];
			}
		}

		return a.join('');
	}
	function addTo(arr,newEl)
	{
		arr.unshift(newEl);
		return arr;
	}
}

Python 3, 217 bajtów

from itertools import*
a='()[]{}<>'
all(any(c[-1]!=d[0]for c,d in zip(q,q[1:]))or print(''.join(q))for p in permutations(open(0))for q in product(*[(c[:-1],a[a.find(c[-2])^1]+c[-3:0:-1]+a[a.find(c[0])^1])for c in p]))

( Demo na Ideone )

Lua, 477 bajtów

function r(s)return s:reverse():gsub("[()%[%]{}<>]",{["("]=")",[")"]="(",["["]="]",["]"]="[",["{"]="}",["}"]="{",["<"]=">",[">"]="<"})end
function a(c,b)for i, v in next,b do
m=c:sub(-1,-1)n=v:sub(1,1)o=r(c):sub(-1,-1)p=r(v):sub(1,1)l=table.remove(b,i)if m==n then
return a(c..v,b)elseif o==n then
return a(r(c)..v,b)elseif m==p then
return a(c..r(v),b)elseif o==p then
return a(r(c)..r(v),b)end
table.insert(b,i,l)end
return#b>0 and""or c
end
print(a(table.remove(arg,1),arg))

Akceptuje przewody jako argumenty wiersza poleceń

Python 3.5, 448 432 427 424 286 311 bajtów:

( +25, ponieważ wystąpił błąd, w wyniku którego wyjście może być dłuższe niż powinno być dla niektórych danych wejściowych )

def g3(z):
 B=z.split();M='i[::-1].translate({41:40,40:41,125:123,123:125,62:60,60:62,93:91,91:93})';f=B+[eval(M)for i in B if eval(M)not in B];d=[f.pop(0)]
 for h in d:
  try:[d.append([f.pop(f.index(c))for c in f if h[-1]==c[0]][0])if len(d)<len(B)else E]
  except:break
 return''.join(d)if len(d)>=len(B)else''

Działa świetnie! z wyjątkiem danych wejściowych o 7 lub więcej wartościach. Zajmuje to dużo czasu, najprawdopodobniej dlatego, że musi przejść przez wszystkie te kombinacje wejścia plus odwrócone wejście . Spróbuję to naprawić, jeśli i kiedy będę mógł, ale na razie wydaje się to wystarczająco dobre. Teraz wszystko jest dobrze! Gdybym tylko mógł w jakiś sposób użyć tego try-exceptbloku do zrozumienia listy, mógłby być on nieco krótszy i wyglądałby znacznie ładniej. Niemniej jednak, obecnie pracuje dla wszystkich przypadków testowych, a najlepsze jest to, że używa żadnych importu! :)

Wypróbuj online! (Ideone) (tutaj 284 bajty)

(Wskazówka: aby wypróbować, po prostu wybierz „widelec”, a następnie wprowadź wybrane opcje, oddzielając je spacjami i wybierz „uruchom”)

Wyjaśnienie

Zasadniczo dzieje się ...

1. Lista „ Bjest tworzona na podstawie danych wejściowych przez podzielenie jej w spacji na składowe„ sznury ”.
2. Mto ciąg, który utworzyłem, który po ocenie zwraca listę, na podstawie Bktórej zawiera wszystkie sznury, ale tym razem do tyłu .
3. Utworzona lista Mjest ostatecznie połączona ze Bsobą, aby utworzyć listę f, ze wszystkimi możliwymi orientacjami „linek”.
4. Tworzona djest kolejna lista, która zostanie zainicjowana z pierwszą wartością (wartością f[0]) z f.
5. Na koniec wszystkie wartości w dsą iterowane, a ostatni znak każdej wartości jest porównywany z pierwszym znakiem każdego elementu w f, a po znalezieniu dopasowania znak ten jest usuwany (lub usuwany) i zwracany z listy f. Dzieje się tak, dopóki a nie IndexErrorzostanie podniesione lub długość listy nie dprzekroczy, Ba a NameErrorzostanie wywołane po wywołaniu E, oba są obsługiwane, a następnie dzawartość listy jest łączona w ciąg znaków i zwracana, dopóki długość listy djest większa dłuższa lub równa długości listy B. W przeciwnym razie zwracany jest pusty ciąg znaków ( ''), ponieważ dnie jest tej samej długości co Boznacza, że ​​wszystkie „sznury” na liścieB nie można połączyć w jeden długi „sznur”.