W teorii informacji „kod prefiksu” to słownik, w którym żaden z kluczy nie jest prefiksem innego. Innymi słowy, oznacza to, że żaden ciąg nie zaczyna się od żadnego z pozostałych.
Na przykład {"9", "55"}
jest kodem prefiksu, ale {"5", "9", "55"}
nie jest.
Największą zaletą tego jest to, że zakodowany tekst można zapisać bez separatora między nimi i nadal będzie on wyjątkowo czytelny. Widać to w algorytmach kompresji, takich jak kodowanie Huffmana , które zawsze generuje optymalny kod prefiksu.
Twoje zadanie jest proste: na podstawie listy ciągów określ, czy jest to prawidłowy kod prefiksu.
Twój wkład:
Będzie listą ciągów znaków w dowolnym rozsądnym formacie .
Będzie zawierać tylko drukowalne ciągi ASCII.
Nie będzie zawierać żadnych pustych ciągów.
Twój wynik będzie miał wartość true / falsey : Prawda, jeśli jest to poprawny kod prefiksu, i falsey, jeśli nie jest.
Oto kilka prawdziwych przypadków testowych:
["Hello", "World"]
["Code", "Golf", "Is", "Cool"]
["1", "2", "3", "4", "5"]
["This", "test", "case", "is", "true"]
["111", "010", "000", "1101", "1010", "1000", "0111", "0010", "1011",
"0110", "11001", "00110", "10011", "11000", "00111", "10010"]
Oto kilka fałszywych przypadków testowych:
["4", "42"]
["1", "2", "3", "34"]
["This", "test", "case", "is", "false", "t"]
["He", "said", "Hello"]
["0", "00", "00001"]
["Duplicate", "Duplicate", "Keys", "Keys"]
Jest to kod-golf, więc obowiązują standardowe luki i wygrywa najkrótsza odpowiedź w bajtach.
źródło
001
byłoby wyjątkowo rozszyfrowalne? Może to być00, 1
albo0, 11
.0, 00, 1, 11
wszystko jako klucze, nie jest to kod prefiksu, ponieważ 0 to prefiks 00, a 1 to prefiks 11. Prefiks to kod, w którym żaden z kluczy nie zaczyna się od innego klucza. Na przykład, jeśli twoje klucze to są,0, 10, 11
jest to kod prefiksowy i jednoznacznie rozszyfrowalny.001
nie jest ważny komunikat, ale0011
czy0010
są wyjątkowo odczytania.Odpowiedzi:
Pyth, 8 bajtów
Zestaw testowy
Weź wszystkie 2 elementy permutacji danych wejściowych, zamapuj każdy na indeks jednego ciągu w drugim (0 dla prefiksu) i zwróć, czy wszystkie wyniki są prawdziwe (niezerowe).
źródło
Haskell, 37 bajtów
Każdy element
x
zl
jest powtarzany raz dla każdego elementu, który jest to prefiks, który jest dokładnie jeden raz na liście prefix-wolny, dając oryginalną listę. Właściwość prefiksu jest sprawdzana przez skompresowanie obu list za pomocąx
, co odcina elementy o długości przekraczającejx
.źródło
Java,
128127126125124121 bajtów(Dzięki @Kenny Lau, @Maltysen, @Patrick Roberts, @Joba)
Bez golfa
Wydajność
źródło
&
działałoby zamiast&&
?int
i powrócić0
i1
? Pozwoliłoby to zaoszczędzić kilka bajtów. Również zapomnieć, jeśli jest to ważne w Javie, ale jeśli deklarująi
,j
il
wewnątrz zewnętrznejfor
pętli, która będzie ratować jeden bajt z jednego mniej średnikiem.indexOf(a[i])==0
w takim przypadku nie byłoby żadnych oszczędności.Python 2, 48
51bajtówDla każdego elementu
a
zl
funkcjaa.find
znajduje indeks pierwszego wystąpieniaa
w ciągu wejściowego, dzięki czemu-1
w nieobecności. Tak,0
oznacza prefiks. Na liście wolnej od prefiksów mapowanie tej funkcji zwraca tylko jeden0
dlaa
siebie. Funkcja sprawdza, czy tak jest w każdym przypadkua
.51 bajtów:
Zamień
~
na znak o kodzie ASCII 128 lub wyższym.Dla każdego elementu
a
wl
kopia jest włączone dla każdego elementu, który jest prefiksem niego. W przypadku listy bez prefiksów jedynym takim elementem jesta
sam, więc daje to oryginalną listę.źródło
CJam, 14 bajtów
Zestaw testowy.
Wyjaśnienie
źródło
JavaScript ES6,
654340 bajtówMoje poprzednie rozwiązanie, które obsługiwało tablice ciągów wszystkich znaków UTF-8:
Byłem w stanie uniknąć
JSON.stringify
ponieważ wyzwanie określa tylko drukowalne znaki ASCII.Test
źródło
Haskell, 49 bajtów
To składa się z kilku części:
Jeśli dwie listy są równe, element jest tylko przedrostkiem samego siebie i jest prawidłowy.
źródło
Retina , 19 bajtów
Liczba bajtów zakłada kodowanie ISO 8859-1.
Wejście powinno być oddzielone od linii. Wyjście dotyczy
0
fałszu i1
prawdy.Wypróbuj online! (Nieznacznie zmodyfikowano, aby obsługiwał wiele przypadków testowych oddzielonych spacjami).
Wyjaśnienie
Posortuj linie na wejściu. Jeśli prefiks istnieje, kończy się bezpośrednio przed ciągiem, który go zawiera.
Spróbuj dopasować (
M
) pełną linię, która znajduje się również na początku następnej linii.m
Aktywuje tryb multilinii takie, że^
początki linii mecze i1
zapewnia, że tylko my liczyć co najwyżej jeden mecz tak, że wyjście jest0
albo1
.Do zamiany
0
i1
w związku z tym liczyć liczbę0
s.źródło
Java, 97 bajtów
Wykorzystuje większość sztuczek znalezionych w odpowiedzi @ Marv , ale korzysta również z pętli foreach i równości referencji łańcucha.
Unminified:
Zauważ, że, jak powiedziałem, używa to równości referencji ciągów. Oznacza to, że kod może zachowywać się dziwnie z powodu internowania String . Kod działa, gdy używa się argumentów przekazywanych z wiersza poleceń, a także gdy używa się czegoś odczytanego z wiersza poleceń. Jeśli jednak chcesz na stałe zakodować wartości do przetestowania, musisz ręcznie wywołać konstruktor String, aby wymusić, że internowanie się nie pojawi:
źródło
PostgreSQL,
186, 173 bajtówWydajność:
Tym razem nie ma demo na żywo. http://sqlfiddle.com obsługuje tylko 9.3 i do uruchomienia tej wersji demo 9.4 jest wymagana.
Jak to działa:
y
LEFT OUTER JOIN
do tej samej tabeli pochodnej opartej na tym samymi
(id), ale z różnymi,oridinal
które zaczynają się od przedrostkay.z LIKE u.z||'%'
c
(tablica początkowa) i użyjEVERY
funkcji grupowania. Jeśli każdy wiersz z drugiej tabeliIS NULL
oznacza, że nie ma przedrostków.Wprowadź, jeśli ktoś jest zainteresowany:
EDYTOWAĆ:
SQL Server 2016+
realizacja:LiveDemo
Uwaga: Jest to lista oddzielona przecinkami, a nie rzeczywista tablica. Ale główna idea jest taka sama jak w
PostgreSQL
.EDYCJA 2:
Właściwie
WITH ORDINALITY
można go wymienić:SqlFiddleDemo
źródło
Brachylog , 8 bajtów
Wypróbuj online!
Dane wyjściowe poprzez sukces / niepowodzenie predykatu. Ostatni prawdomówny test zajmuje więcej niż 60 sekund,
["111","010","000","1101","1010","1000","0111","0010","1011","0110","11001","00110","10011","11000","00111","10010"]
ale szybko mija go z dodanym bajtem, który eliminuje wiele możliwości wcześniej niż program robi inaczej (Ċ
przed sprawdzeniem permutacji zamiastᵈ
po sprawdzeniu permutacji, aby ograniczyć długość podlisty do dwa).Mniej trywialny 9-bajtowy warianty niż
¬(⊇Ċpa₀ᵈ)
który prowadzony jest w rozsądnym czasie¬(⊇o₁a₀ᵈ)
,¬(⊇o↔a₀ᵈ)
i¬(⊇oa₀ᵈ¹)
.źródło
Perl 6 , 24 bajtów
Wypróbuj online!
Wow, zaskakująco krótko, używając długiego wbudowanego.
Wyjaśnienie
źródło
Rakieta, 70 bajtów
źródło
Python,
5855 bajtówźródło
a.index(b)==0
jest nieco krótszy. Alternatywnie możesz to zrobić0**sum(a.index(b)for a in l for b in l)
.index
zgłasza wyjątek, gdy gob
nie znaleziono. I dlatego powinno być==
, nie>=
. Jednakfind
działa. (I jest też krótszy!)find
. Senny mózg jest śpiący. Druga wersja również powinna współpracowaćfind
.len(l)
to, że powtarzamy wszystkieb
s na każdyma
, zawsze będzie co najmniej jeden mecz naa
. Sprawdzamy więc, czy liczba dopasowań jest taka sama jak liczba elementów.JavaScript (ES6), 52
54Edytuj 2 bajty zapisane thx @ Neil
Test
źródło
!w.indexOf(v)
?Mathematica
75 6968 bajtówJak zwykle gadatliwy. Ale Martin B był w stanie zmniejszyć kod o 7 bajtów.
Metoda 1: Przechowywanie danych wyjściowych w
Array
(68 bajtów)
Metoda 2: Przechowywanie danych wyjściowych w
List
(69 bajtów)
źródło
a~Drop~{#}~StringStartsQ~a[[#]]
zadziałać.Array
Powinieneś także zaoszczędzić trochę bajtówLength
, zwłaszcza, że pozwoli ci to używaćJoin@@
zamiastFlatten@
(pod warunkiem, że używaszFlatten
tylko dla jednego poziomu).Array
później.Mathematica, 41 bajtów
źródło
APL (Dyalog Unicode) , 13 bajtów SBCS
-2 bajty:
Wypróbuj online!
Wyjaśnienie:
źródło
~2∊+\⊃¨∘.⍷⍨⎕
J , 17 bajtów
Wypróbuj online!
Uwaga: faktycznie napisałem to przed spojrzeniem na odpowiedź APL, aby podejść do niej bez uprzedzeń. Okazuje się, że podejścia są prawie identyczne, co jest interesujące. Myślę, że to naturalne rozwiązanie typu „tablicowe myślenie”
Weź dane w ramce, ponieważ ciągi mają nierówną długość.
Utwórz tabelę funkcji
/~
dla każdego elementu sparowanego z każdym elementem i sprawdź, czy na początku jest dopasowanie{.@E.
. To da macierz wyników 1-0.Zsumuj to dwukrotnie
1#.1#.
aby uzyskać pojedynczą liczbę reprezentującą „wszystkie w macierzy” i sprawdź, czy liczba ta jest taka sama jak długość danych wejściowych#=
. Jeśli tak, to jedynymi dopasowaniami prefiksów są dopasowania własne, tzn. Mamy kod prefiksu.rozwiązanie sortujące, 18 bajtów
Próba innego podejścia. To rozwiązanie sortuje i sprawdza sąsiednie pary.
Wypróbuj online!
źródło
R , 48 bajtów
Wypróbuj online!
Objaśnienie:
outer(s,s,startsWith)
wyświetla macierz logiki sprawdzającą, czys[i]
jest prefiksems[j]
. Jeślis
jest to kod przedrostka, to w wyniku tego są dokładnielength(s)
PRAWDZIWE elementy, odpowiadające elementom ukośnym (s[i]
jest to sam przedrostek).źródło
function(s)all(colSums(outer(s,s,startsWith))<2)
ale pozostajestartsWith
funkcja, o której nie wiedziałam! Niezłe znalezisko.TRUE
iFALSE
...==
ze>
:-).)Pyth -
1312 bajtówWypróbuj online tutaj .
źródło
Rubinowy, 48 bajtów
Wykorzystuje argumenty jako dane wejściowe, a standardowe jako dane wyjściowe.
źródło
Scala, 71 bajtów
źródło
Rakieta 130 bajtów
Nie golfowany:
Testowanie:
Wydajność:
źródło
C (gcc) , 93 bajty
Wypróbuj online!
Proste podwójne dla pętli za pomocą
strstr(a,b)==a
do sprawdzania prefektów. Dodane głównie, ponieważ wydaje się, że nie ma jeszcze odpowiedzi w języku C.źródło
05AB1E , 13 bajtów
Za długo .. Początkowo miałem rozwiązanie 9-bajtowe, ale nie powiodło się w przypadku duplikatu testowego klucza.
Wypróbuj online lub sprawdź wszystkie przypadki testowe .
Wyjaśnienie:
źródło
Japt , 8 bajtów
Spróbuj
źródło
C # (interaktywny kompilator Visual C #) , 70 bajtów
Wypróbuj online!
źródło
Stax , 6 bajtów
Uruchom i debuguj
To powoduje powstanie niezerowej wartości dla prawdy.
Ogólna idea polega na rozważeniu każdej pary ciągów wejściowych. Jeśli indeks podciągu jednego w drugim jest zawsze równy zero, to nie jest to poprawny kod prefiksu. W stax daje indeks nieistniejącego substratu
-1
. W ten sposób wszystkie wskaźniki parowania podciągów można pomnożyć razem.Jest to ten sam algorytm, co rozwiązanie pyta isaacga, ale opracowałem go niezależnie.
źródło