W tym wyzwaniu dotyczącym kodu prefiksu dowiedzieliśmy się, że kody prefiksów są jednoznacznie powiązane.

Oznacza to, że można je łączyć bez separatora i bez dwuznaczności.

Na przykład, ponieważ [1,2,45] jest kodem prefiksu, mogę połączyć je razem bez separatora jako takiego: 1245245112145, i nie będzie dwuznaczności.

Jednak odwrotność nie zawsze jest prawdą.

Na przykład [3,34] nie jest kodem prefiksu. Mogę jednak zrobić to samo: 3333434334333 i nie będzie żadnych dwuznaczności. Potrzebujesz tylko inteligentniejszego parsera.

Jednak [1,11] nie jest jednoznacznie konkatenowalny, ponieważ 1111 można interpretować na 5 sposobów.

Cel

Twoim zadaniem jest napisanie programu / funkcji, która pobiera listę ciągów znaków (ASCII) jako dane wejściowe i ustalenie, czy można je jednoznacznie połączyć.

Detale

Duplikat liczy się jako fałsz.

Punktacja

To jest golf golfowy . Najkrótsze rozwiązanie w bajtach wygrywa.

Przypadki testowe

Prawdziwe:

[12,21,112]
[12,112,1112]
[3,4,35]
[2,3,352]

Fałszywe:

[1,1]
[1,2,112]
[1,23,4,12,34]
[1,2,35,4,123,58,8]

05AB1E , 15 bajtów

Na telefonie, więc wyjaśnienie będzie musiało nastąpić później. Kod:

gF¹N>ã})€`€JDÚQ

Wykorzystuje kodowanie CP-1252 . Wypróbuj online! .

Zajmuje zbyt dużo pamięci dla ostatniego przypadku testowego, więc może nie działać ...

CJam (54 bajty)

q_N/:A\,{_Am*:${~1$,<=},{~\,>}%La:L-}*A,A_&,-A*](\M*&!

Pobiera dane wejściowe na stdin jako listę oddzieloną znakiem nowej linii.

Demo online

Gdybyśmy nie musieli obsługiwać zduplikowanych słów kodowych, można by to skrócić do 44:

q_N/\,{_W$m*:${~1$,<=},{~\,>}%La:L-}*](\M*&!

Lub jeśli CJam miał odejmowanie tablic, które usunęło tylko jeden element z pierwszej listy dla każdego elementu w drugim, może to być 48 ...

Sekcja

Jest to algorytm Sardinas-Patterson, ale nie zoptymalizowany. Ponieważ każdy wiszący sufiks pojawia się najwyżej raz, uruchomienie pętli głównej tyle razy, ile znaków jest na wejściu (w tym separatorów), gwarantuje wystarczenie.

Zauważ, że musiałem obejść coś, co prawdopodobnie jest błędem w interpretatorze CJam:

"abc" "a" #   e# gives 0 as the index at which "a" is found
"abc" "d" #   e# gives -1 as the index at which "d" is found
"abc" ""  #   e# gives an error

Sprawdzanie prefiksu jest więc skomplikowane 1$,<=zamiast\#!

e# Take input, split, loop once per char
q_N/\,{
  e# Build the suffixes corresponding to top-of-stack and bottom-of-stack
  _W$m*
  e# Map each pair of Cartesian product to the suffix if one is the prefix of the other;
  e# otherwise remove from the array
  :${~1$,<=},{~\,>}%
  e# Filter out empty suffixes iff it's the first time round the loop
  La:L-
}*
e# If we generated an empty suffix then we've also looped enough times to generate all
e# of the keywords as suffixes corresponding to the empty fix, so do a set intersection
e# to test this condition.
](\M*&!