Czy to jest jednoznacznie powiązane?

10

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]
code-golf Leaky Nun
źródło
Żeby upewnić się, że poprawnie rozumiem wyzwanie, nie jest jednoznacznie powiązane, jeśli jeden z ciągów składa się z dowolnej kombinacji pozostałych? Powinieneś wyjaśnić te szczegóły.
James
Czy na pewno nie jest to równoważne z problemem zatrzymania?
feersum
Czy potrafisz wykazać, dlaczego jest to równoważne z problemem zatrzymania?
Leaky Nun
Nie powiedziałem, że tak, ale zastanawiałem się, że tak może być. Po chwili namysłu wierzę, że tak nie jest.
feersum
@feersum Oto algorytm wielopoziomowy dla tego problemu: en.wikipedia.org/wiki/Sardinas%E2%80%93Patterson_algorithm
isaacg

Odpowiedzi:

5

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

Adnan
źródło
3
Niezwykle imponujące jest to, że możesz wpisać to na swoim telefonie.
James
3
@DrGreenEggsandHamDJ Zajęło to około 40 minut ...
Adnan
2
@Adnan Zastanawiam się, co przewidujący tekst klawiatury telefonu myśli o wszystkich symbolach śmieci :-)
Luis Mendo
1
@LuisMendo Haha, zdarzyło się to tylko raz, gdy wysłałem losowy program 05AB1E znajomemu.
Adnan
Zgaduję, że działa to poprzez umieszczenie górnej granicy długości najkrótszej kolizji. Czy mam rację?
Peter Taylor
4

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*&!
Peter Taylor
źródło