Czy to jest kod prefiksu?

33

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.

DJMcMayhem
źródło
Czy chcesz spójną wartość zgodną z prawdą, czy może to być np. „Dodatnia liczba całkowita” (która może różnić się w zależności od różnych danych wejściowych).
Martin Ender
@DrGreenEggsandHamDJ Nie sądzę, że odpowiedź ma na celu w ogóle odniesienie się do spójności wyników, stąd pytanie. ;)
Martin Ender
Właśnie z ciekawości: Wyzwanie mówi: „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”. Jak coś takiego 001byłoby wyjątkowo rozszyfrowalne? Może to być 00, 1albo 0, 11.
Joba
2
@Joba To zależy od tego, jakie są twoje klucze. Jeśli masz 0, 00, 1, 11wszystko 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, 11jest to kod prefiksowy i jednoznacznie rozszyfrowalny. 001nie jest ważny komunikat, ale 0011czy 0010są wyjątkowo odczytania.
DJMcMayhem

Odpowiedzi:

11

Pyth, 8 bajtów

.AxM.PQ2

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

isaacg
źródło
12

Haskell, 37 bajtów

f l=[x|x<-l,y<-l,zip x x==zip x y]==l

Każdy element xz ljest 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ącej x.

xnor
źródło
To eleganckie rozwiązanie (+1)
Michael Klein
9

Java, 128 127 126 125 124 121 bajtów

(Dzięki @Kenny Lau, @Maltysen, @Patrick Roberts, @Joba)

Object a(String[]a){for(int i=0,j,l=a.length;i<l;i++)for(j=0;j<l;)if(i!=j&a[j++].startsWith(a[i]))return 1<0;return 1>0;}

Bez golfa

Object a(String[] a) {
    for (int i = 0, j, l = a.length; i < l; i++) 
        for (j = 0; j < l;) 
            if (i != j & a[j++].startsWith(a[i])) return 1<0;
    return 1>0;
}

Wydajność

[Hello, World]
true

[Code, Golf, Is, Cool]
true

[1, 2, 3, 4, 5]
true

[This, test, case, is, true]
true

[111, 010, 000, 1101, 1010, 1000, 0111, 0010, 1011, 0110, 11001, 00110, 10011, 11000, 00111, 10010]
true

[4, 42]
false

[1, 2, 3, 34]
false

[This, test, case, is, false, t]
false

[He, said, Hello]
false

[0, 00, 00001]
false

[Duplicate, Duplicate, Keys, Keys]
false
Marv
źródło
1
idk o java, ale czy &działałoby zamiast &&?
Maltysen
1
Racja, zapisuje kolejny bajt. W Javie użycie operatorów bitowych z operandami logicznymi zachowuje się tak jak normalne operatory logiczne, z tym wyjątkiem, że nie powodują zwarcia, co nie jest w tym przypadku potrzebne.
Marv
Czy nie możesz po prostu zmienić typu zwracanej funkcji na inti powrócić 0i 1? Pozwoliłoby to zaoszczędzić kilka bajtów. Również zapomnieć, jeśli jest to ważne w Javie, ale jeśli deklarują i, ji lwewnątrz zewnętrznej forpętli, która będzie ratować jeden bajt z jednego mniej średnikiem.
Patrick Roberts
@PatrickRoberts Maltysen zasugerował to wcześniej, ale nie jest to zgodne z najbardziej popularną definicją truey / falsey . Umieszczanie deklaracji w pętli jest jednak całkowicie poprawne i dość oczywiste teraz, kiedy o tym myślę. Oto, co dostajesz za grę w golfa o 4 rano: ^)
Marv
3
@Joba Dość pewny, że to nie jest poprawne, ponieważ indexOf zwraca -1, gdy łańcuch nie zostanie znaleziony; indexOf(a[i])==0w takim przypadku nie byłoby żadnych oszczędności.
Pokechu22
6

Python 2, 48 51 bajtów

lambda l:all(1/map(a.find,l).count(0)for a in l)

Dla każdego elementu az lfunkcja a.findznajduje indeks pierwszego wystąpienia aw ciągu wejściowego, dzięki czemu -1w nieobecności. Tak, 0oznacza prefiks. Na liście wolnej od prefiksów mapowanie tej funkcji zwraca tylko jeden 0dla asiebie. Funkcja sprawdza, czy tak jest w każdym przypadku a.


51 bajtów:

lambda l:[a for a in l for b in l if b<=a<b+'~']==l

Zamień ~na znak o kodzie ASCII 128 lub wyższym.

Dla każdego elementu aw lkopia jest włączone dla każdego elementu, który jest prefiksem niego. W przypadku listy bez prefiksów jedynym takim elementem jest asam, więc daje to oryginalną listę.

xnor
źródło
4

CJam, 14 bajtów

q~$W%2ew::#0&!

Zestaw testowy.

Wyjaśnienie

q~   e# Read and evaluate input.
$    e# Sort strings. If a prefix exists it will end up directly in front 
     e# of a string which contains it.
W%   e# Reverse list.
2ew  e# Get all consecutive pairs of strings.
::#  e# For each pair, find the first occurrence of the second string in the first.
     e# If a prefix exists that will result in a 0, otherwise in something non-zero.
0&   e# Set intersection with 0, yielding [0] for falsy cases and [] for truthy ones.
!    e# Logical NOT.
Martin Ender
źródło
4

JavaScript ES6, 65 43 40 bajtów

a=>!/(.*)\1/.test(''+a.sort().join``)
      ^            ^               ^ embedded NUL characters

Moje poprzednie rozwiązanie, które obsługiwało tablice ciągów wszystkich znaków UTF-8:

a=>!/[^\\]("([^"]*\\")*[^\\])",\1/.test(JSON.stringify(a.sort()))

Byłem w stanie uniknąć JSON.stringify ponieważ wyzwanie określa tylko drukowalne znaki ASCII.

Test

f=a=>!/(\0.*)\1/.test('\0'+a.sort().join`\0`) // since stackexchange removes embedded NUL characters

O.textContent += 'OK: '+
[["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"]
].map(a=>f(a)) 

O.textContent += '\nKO: '+
[["4", "42"]                             
,["1", "2", "3", "34"]                   
,["This", "test", "case", "is", "false", "t"]
,["He", "said", "Hello"]
,["0", "00", "00001"]
,["Duplicate", "Duplicate", "Keys", "Keys"]
].map(a=>f(a))
<pre id=O></pre>

Patrick Roberts
źródło
3

Haskell, 49 bajtów

g x=[1|z<-map((and.).zipWith(==))x<*>x,z]==(1<$x)

To składa się z kilku części:

-- Are two lists (or strings) equal for their first min(length_of_1,length_of_2) elements, i.e. is one the prefix of the other?
(and.).zipWith(==)

-- Check whether one element is the prefix of the other, for all pairs of elements (including equal pairs)
map((and.).zipWith(==))x<*>x

-- This is a list of 1's of length (number of elements that are the prefix of the other)
[1|z<-map((and.).zipWith(==))x<*>x,z]

-- This is the input list, with all the elements replaced with 1's
(1<$x)

Jeśli dwie listy są równe, element jest tylko przedrostkiem samego siebie i jest prawidłowy.

Michael Klein
źródło
3

Retina , 19 bajtów

Liczba bajtów zakłada kodowanie ISO 8859-1.

O`.+
Mm1`^(.+)¶\1
0

Wejście powinno być oddzielone od linii. Wyjście dotyczy 0fałszu i 1prawdy.

Wypróbuj online! (Nieznacznie zmodyfikowano, aby obsługiwał wiele przypadków testowych oddzielonych spacjami).

Wyjaśnienie

O`.+

Posortuj linie na wejściu. Jeśli prefiks istnieje, kończy się bezpośrednio przed ciągiem, który go zawiera.

Mm1`^(.+)¶\1

Spróbuj dopasować ( M) pełną linię, która znajduje się również na początku następnej linii. mAktywuje tryb multilinii takie, że ^początki linii mecze i 1zapewnia, że tylko my liczyć co najwyżej jeden mecz tak, że wyjście jest 0albo 1.

0

Do zamiany 0i 1w związku z tym liczyć liczbę 0s.

Martin Ender
źródło
3

Java, 97 bajtów

Object a(String[]a){for(String t:a)for(String e:a)if(t!=e&t.startsWith(e))return 1<0;return 1>0;}

Wykorzystuje większość sztuczek znalezionych w odpowiedzi @ Marv , ale korzysta również z pętli foreach i równości referencji łańcucha.

Unminified:

Object a(String[]a){
    for (String t : a)
        for (String e : a)
            if (t != e & t.startsWith(e))
                return 1<0;
    return 1>0;
}

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:

System.out.println(a(new String[] {new String("Hello"), new String("World")}));
System.out.println(a(new String[] {new String("Code"), new String("Golf"), new String("Is"), new String("Cool")}));
System.out.println(a(new String[] {new String("1"), new String("2"), new String("3"), new String("4"), new String("5")}));
System.out.println(a(new String[] {new String("This"), new String("test"), new String("case"), new String("is"), new String("true")}));
System.out.println(a(new String[] {new String("111"), new String("010"), new String("000"), new String("1101"), new String("1010"), new String("1000"), new String("0111"), new String("0010"), new String("1011"), new String("0110"), new String("11001"), new String("00110"), new String("10011"), new String("11000"), new String("00111"), new String("10010")}));
System.out.println(a(new String[] {new String("4"), new String("42")}));
System.out.println(a(new String[] {new String("1"), new String("2"), new String("3"), new String("34")}));
System.out.println(a(new String[] {new String("This"), new String("test"), new String("case"), new String("is"), new String("false"), new String("t")}));
System.out.println(a(new String[] {new String("He"), new String("said"), new String("Hello")}));
System.out.println(a(new String[] {new String("0"), new String("00"), new String("00001")}));
System.out.println(a(new String[] {new String("Duplicate"), new String("Duplicate"), new String("Keys"), new String("Keys")}));
Pokechu22
źródło
@Jo King Zobacz drugą połowę mojej odpowiedzi; jest to trochę skomplikowane i zależy od tego, jak określono dane wejściowe. Jednak nie pamiętam, żeby to pisać
Pokechu22
3

PostgreSQL, 186 , 173 bajtów

WITH y AS(SELECT * FROM t,LATERAL unnest(c)WITH ORDINALITY s(z,r))
SELECT y.c,EVERY(u.z IS NULL)
FROM y LEFT JOIN y u ON y.i=u.i AND y.r<>u.r AND y.z LIKE u.z||'%' GROUP BY y.c

Wydajność:

enter image description here

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:

  1. Podziel tablicę ciągów na numer i nazwij ją y
  2. Zdobądź całe y
  3. LEFT OUTER JOINdo tej samej tabeli pochodnej opartej na tym samym i(id), ale z różnymi, oridinalktóre zaczynają się od przedrostkay.z LIKE u.z||'%'
  4. Wynik grupy na podstawie c(tablica początkowa) i użyj EVERYfunkcji grupowania. Jeśli każdy wiersz z drugiej tabeli IS NULLoznacza, że ​​nie ma przedrostków.

Wprowadź, jeśli ktoś jest zainteresowany:

CREATE TABLE t(i SERIAL,c text[]);

INSERT INTO t(c)
SELECT '{"Hello", "World"}'::text[]
UNION ALL SELECT  '{"Code", "Golf", "Is", "Cool"}'
UNION ALL SELECT  '{"1", "2", "3", "4", "5"}'
UNION ALL SELECT  '{"This", "test", "case", "is", "true"}'         
UNION ALL SELECT  '{"111", "010", "000", "1101", "1010", "1000", "0111", "0010", "1011","0110", "11001", "00110", "10011", "11000", "00111", "10010"}'
UNION ALL SELECT  '{"4", "42"}'
UNION ALL SELECT  '{"1", "2", "3", "34"}'                   
UNION ALL SELECT  '{"This", "test", "case", "is", "false", "t"}'
UNION ALL SELECT  '{"He", "said", "Hello"}'
UNION ALL SELECT  '{"0", "00", "00001"}'
UNION ALL SELECT  '{"Duplicate", "Duplicate", "Keys", "Keys"}';

EDYTOWAĆ:

SQL Server 2016+ realizacja:

WITH y AS (SELECT *,z=value,r=ROW_NUMBER()OVER(ORDER BY 1/0) FROM #t CROSS APPLY STRING_SPLIT(c,','))
SELECT y.c, IIF(COUNT(u.z)>0,'F','T')
FROM y LEFT JOIN y u ON y.i=u.i AND y.r<>u.r AND y.z LIKE u.z+'%' 
GROUP BY y.c;

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 ORDINALITYmożna go wymienić:

WITH y AS(SELECT *,ROW_NUMBER()OVER()r FROM t,LATERAL unnest(c)z)
SELECT y.c,EVERY(u.z IS NULL)
FROM y LEFT JOIN y u ON y.i=u.i AND y.r<>u.r AND y.z LIKE u.z||'%' GROUP BY y.c

SqlFiddleDemo

lad2025
źródło
3

Brachylog , 8 bajtów

¬(⊇pa₀ᵈ)

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

¬(     )    It cannot be shown that
   p        a permutation of
  ⊇         a sublist of the input
      ᵈ     is a pair of values [A,B] such that
    a₀      A is a prefix of B.

Mniej trywialny 9-bajtowy warianty niż ¬(⊇Ċpa₀ᵈ)który prowadzony jest w rozsądnym czasie ¬(⊇o₁a₀ᵈ), ¬(⊇o↔a₀ᵈ)i ¬(⊇oa₀ᵈ¹).

Niepowiązany ciąg
źródło
Gdyby w tym wyzwaniu zastosowano „dwie odrębne i spójne wartości” zamiast „prawdy / fałszu”, zajęłoby to tylko 5 bajtów.
Ciąg niepowiązany
2

Perl 6 , 24 bajtów

{.all.starts-with(.one)}

Wypróbuj online!

Wow, zaskakująco krótko, używając długiego wbudowanego.

Wyjaśnienie

{                      }  # Anonymous code block taking a list
 .all                     # Do all of the strings
     .starts-with(    )   # Start with
                  .one    # Only one other string (i.e. itself)
Jo King
źródło
Napisałem 50 bajtową odpowiedź, ale twoja właśnie wysadziła moją z wody.
bb94
1
@ bb94 Tak, zacząłem od podobnej odpowiedzi, ale natknąłem się na ten sam problem, co twój z zestawami ze zduplikowanymi kluczami zwracającymi prawdę. Napisanie tej odpowiedzi było niezwykle satysfakcjonujące
Jo King
1

Rakieta, 70 bajtów

(λ(l)(andmap(λ(e)(not(ormap(curryr string-prefix? e)(remv e l))))l))
Winny
źródło
1

Python, 58 55 bajtów

lambda l:sum(0==a.find(b)for a in l for b in l)==len(l)
DJMcMayhem
źródło
a.index(b)==0jest nieco krótszy. Alternatywnie możesz to zrobić 0**sum(a.index(b)for a in l for b in l).
Mego
@Mego To nie działa, ponieważ indexzgłasza wyjątek, gdy go bnie znaleziono. I dlatego powinno być ==, nie >=. Jednak finddziała. (I jest też krótszy!)
DJMcMayhem
Ups, chciałem pisać find. Senny mózg jest śpiący. Druga wersja również powinna współpracować find.
Mego
@Mego Nie jestem pewien, czy dostanę drugą wersję. Czy to nie zawsze zwróci 0?
DJMcMayhem
@Mego Działa to tylko wtedy, gdy każdy ciąg znaków jest taki sam. Powodem, dla którego to porównujemy, jest len(l)to, że powtarzamy wszystkie bs na każdym a, zawsze będzie co najmniej jeden mecz na a. Sprawdzamy więc, czy liczba dopasowań jest taka sama jak liczba elementów.
DJMcMayhem
1

JavaScript (ES6), 52 54

Edytuj 2 bajty zapisane thx @ Neil

a=>!a.some((w,i)=>a.some((v,j)=>i-j&&!w.indexOf(v)))

Test

f=a=>!a.some((w,i)=>a.some((v,j)=>i-j&&!w.indexOf(v)))

O.textContent += 'OK: '+
[["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"]
].map(a=>f(a)) 

O.textContent += '\nKO: '+
[["4", "42"]                             
,["1", "2", "3", "34"]                   
,["This", "test", "case", "is", "false", "t"]
,["He", "said", "Hello"]
,["0", "00", "00001"]
,["Duplicate", "Duplicate", "Keys", "Keys"]
].map(a=>f(a))
<pre id=O></pre>

edc65
źródło
!w.indexOf(v)?
Neil
@Nie ma racji, dzięki
edc65
1

Mathematica 75 69 68 bajtów

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

f@a_:=!Or@@(Join@@Array[a~Drop~{#}~StringStartsQ~a[[#]]&,Length@a])

f@{"111", "010", "000", "1101", "1010", "1000", "0111", "0010", "1011", "0110", "11001", "00110", "10011", "11000", "00111", "10010"}

Prawdziwe


f@{"He", "said", "Hello"}

Fałszywe


Metoda 2: Przechowywanie danych wyjściowych w List

(69 bajtów)

f@a_:=!Or@@Flatten[a~Drop~{#}~StringStartsQ~a[[#]]&/@Range@Length@a]
DavidC
źródło
Zasady pierwszeństwa powinny a~Drop~{#}~StringStartsQ~a[[#]]zadziałać. ArrayPowinieneś także zaoszczędzić trochę bajtów Length, zwłaszcza, że ​​pozwoli ci to używać Join@@zamiast Flatten@(pod warunkiem, że używasz Flattentylko dla jednego poziomu).
Martin Ender
Dzieki za sugestie. Zajmę się Arraypóźniej.
DavidC
1

Mathematica, 41 bajtów

!Or@@StringStartsQ@@@Reverse@Sort@#~Subsets~{2}&
Simmons
źródło
1

APL (Dyalog Unicode) , 13 bajtów SBCS

-2 bajty:

≢=∘≢∘⍸∘.(⊃⍷)⍨

Wypróbuj online!

Wyjaśnienie:

≢=∘≢∘⍸∘.(⊃⍷)⍨   Monadic function train
               "Find": Convert the right argument into a boolean vector,
                where ones correspond to instances of the left argument
              Take the first item of the above vector (i.e., only prefixes)
     ∘.(  )⍨   Commutative outer product: take the above function and apply
               it for each possible pair of elements in the input
               If the input is a prefix code, the above should have a number of ones
               equal to the length of the input (i.e., each item is a prefix of only itself)
               To test this...
              Find the location of all ones in the above
   ≢∘          Take the length of the above
≢=∘            Compare to the length of the input
jastrząb
źródło
~2∊+\⊃¨∘.⍷⍨⎕­
ngn
1

J , 17 bajtów

#=1#.1#.{.@E.&>/~

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

0=1#.2{.@E.&>/\/:~

Próba innego podejścia. To rozwiązanie sortuje i sprawdza sąsiednie pary.

Wypróbuj online!

Jonasz
źródło
1

R , 48 bajtów

function(s)sum(outer(s,s,startsWith))==length(s)

Wypróbuj online!

Objaśnienie: outer(s,s,startsWith)wyświetla macierz logiki sprawdzającą, czy s[i]jest prefiksem s[j]. Jeśli sjest to kod przedrostka, to w wyniku tego są dokładnie length(s)PRAWDZIWE elementy, odpowiadające elementom ukośnym ( s[i]jest to sam przedrostek).

Robin Ryder
źródło
1
Znalazłem wiele innych 48-bajtowych alternatyw, na przykład, function(s)all(colSums(outer(s,s,startsWith))<2)ale pozostaje startsWithfunkcja, o której nie wiedziałam! Niezłe znalezisko.
Giuseppe
1
@Giuseppe Próbowałem kilku sposobów sprawdzenia, czy matryca jest matrycą tożsamości, ale nie mogłem uzyskać jej poniżej 48 bajtów. Pomyślałem, że ten sposób jest najłatwiejszy do zrozumienia, ale jestem pewien, że ktoś to zagra!
Robin Ryder
47 bajtów przez odwrócenie TRUEi FALSE...
Giuseppe
@Giuseppe Czy to dozwolone? Reguły wyraźnie proszą o podanie prawdy, gdy dane wejściowe są poprawnymi kodami prefiksów. (Również link jest do wersji 48 bajtów, ale zgaduję, że sugestia jest zastąpienie == ze >:-).)
Robin Ryder
0

Rubinowy, 48 bajtów

Wykorzystuje argumenty jako dane wejściowe, a standardowe jako dane wyjściowe.

p !$*.map{a,*b=$*.rotate!
a.start_with? *b}.any?
ezrast
źródło
0

Scala, 71 bajtów

(s:Seq[String])=>(for{x<-s;y<-s}yield x!=y&&x.startsWith(y)).forall(!_)
Jakub
źródło
0

Rakieta 130 bajtów

(define g #t)(for((n(length l)))(for((i(length l))#:unless(= i n))(when(string-prefix?(list-ref l i)(list-ref l n))(set! g #f))))g

Nie golfowany:

(define(f l)
  (define g #t)
  (for ((n (length l)))
    (for ((i (length l)) #:unless (= i n))
      (when (string-prefix? (list-ref l i) (list-ref l n))
        (set! g #f))))g)

Testowanie:

(f [list "Hello" "World"])             
(f [list "Code" "Golf" "Is" "Cool"])
(f [list "1" "2" "3" "4" "5"])
(f [list "This" "test" "case" "is" "true"])          
(f [list "111" "010" "000" "1101" "1010" "1000" "0111" "0010" "1011" 
         "0110" "11001" "00110" "10011" "11000" "00111" "10010"])

(f [list "4" "42"])                             
(f [list "1" "2" "3" "34"])                   
(f [list "This" "test" "case" "is" "false" "t"])
(f [list "He" "said" "Hello"])
(f [list "0" "00" "00001"])
(f [list "Duplicate" "Duplicate" "Keys" "Keys"])

Wydajność:

#t
#t
#t
#t
#t
#f
#f
#f
#f
#f
#f
rnso
źródło
0

C (gcc) , 93 bajty

p(r,e,f,i,x)char**r;{for(f=i=0;i<e;++i)for(x=0;x<e;++x)f|=x!=i&&strstr(r[i],r[x])==r[i];r=f;}

Wypróbuj online!

Proste podwójne dla pętli za pomocą strstr(a,b)==ado sprawdzania prefektów. Dodane głównie, ponieważ wydaje się, że nie ma jeszcze odpowiedzi w języku C.

LambdaBeta
źródło
88 bajtów
ceilingcat
0

05AB1E , 13 bajtów

2.ÆDí«ε`Å?}O_

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:

2.Æ             # Get all combinations of two elements from the (implicit) input-list
   Dí           # Duplicate and reverse each pair
     «          # Merge the lists of pairs together
      ε         # Map each pair to:
       `        #  Push both strings to the stack
        Å?      #  And check if the first starts with the second
          }O    # After the map: sum to count all truthy values
            _   # And convert it to truthy if it's 0 or falsey if it's any other integer
                # (which is output implicitly as result)
Kevin Cruijssen
źródło
0

Japt , 8 bajtów

á2 ËrbÃe

Spróbuj

á2 ËrbÃe     :Implicit input of array
á2           :Permutations of length 2
   Ë         :Map each pair
    r        :  Reduce by
     b       :  Get the index of the second in the first - 0 (falsey) if it's a prefix
      Ã      :End map
       e     :All truthy (-1 or >0)
Kudłaty
źródło
0

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.

rekurencyjny
źródło