Ist es ein Präfixcode?

33

In der Informationstheorie ist ein "Präfixcode" ein Wörterbuch, in dem keiner der Schlüssel ein Präfix eines anderen ist. Mit anderen Worten bedeutet dies, dass keine der Zeichenfolgen mit einer der anderen beginnt.

Dies ist beispielsweise {"9", "55"}ein Präfixcode, dies {"5", "9", "55"}ist jedoch nicht der Fall.

Der größte Vorteil dabei ist, dass der codierte Text ohne Trennzeichen aufgeschrieben werden kann und dennoch eindeutig entschlüsselbar ist. Dies zeigt sich in Komprimierungsalgorithmen wie der Huffman-Codierung , die immer den optimalen Präfixcode generiert.

Ihre Aufgabe ist einfach: Bestimmen Sie anhand einer Liste von Zeichenfolgen, ob es sich um einen gültigen Präfixcode handelt.

Deine Eingabe:

  • Wird eine Liste von Zeichenfolgen in jedem vernünftigen Format sein .

  • Enthält nur druckbare ASCII-Zeichenfolgen.

  • Enthält keine leeren Zeichenfolgen.

Ihre Ausgabe ist ein Wahrheits- / Falsch- Wert: Wahrheit, wenn es ein gültiger Präfix-Code ist, und Falsch, wenn dies nicht der Fall ist.

Hier sind einige echte Testfälle:

["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"]

Hier sind einige falsche Testfälle:

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

Dies ist Code-Golf, daher gelten Standard-Regelungslücken und die kürzeste Antwort in Bytes gewinnt.

DJMcMayhem
quelle
Möchten Sie einen konsistenten Wahrheitswert oder könnte es zB "eine positive ganze Zahl" sein (die zwischen verschiedenen Eingaben variieren kann).
Martin Ender
@ MartinBüttner Jede positive ganze Zahl ist in Ordnung.
DJMcMayhem
@DrGreenEggsandHamDJ Ich glaube nicht, dass diese Antwort dazu gedacht ist, die Konsistenz der Ausgaben überhaupt anzugehen, daher die Frage. ;)
Martin Ender
Nur aus Neugier: Die Herausforderung lautet: "Der größte Vorteil dabei ist, dass der verschlüsselte Text ohne Trennzeichen aufgeschrieben werden kann und dennoch eindeutig entschlüsselbar ist." Wie wäre so etwas 001eindeutig entzifferbar? Es könnte entweder 00, 1oder sein 0, 11.
Joba
2
@Joba Es kommt darauf an, was deine Schlüssel sind. Wenn Sie 0, 00, 1, 11alle als Schlüssel haben, ist dies kein Präfixcode, da 0 ein Präfix von 00 und 1 ein Präfix von 11 ist. Bei einem Präfixcode beginnt keiner der Schlüssel mit einem anderen Schlüssel. Wenn Ihre Schlüssel also 0, 10, 11beispielsweise ein Präfixcode sind, der eindeutig entschlüsselbar ist. 001ist keine gültige Nachricht, aber 0011oder 0010eindeutig entschlüsselbar.
DJMcMayhem

Antworten:

11

Pyth, 8 Bytes

.AxM.PQ2

Testsuite

Nehmen Sie alle 2 Elementpermutationen der Eingabe, ordnen Sie jede dem Index einer Zeichenfolge in der anderen zu (0 für ein Präfix) und geben Sie zurück, ob alle Ergebnisse wahr sind (nicht Null).

isaacg
quelle
12

Haskell, 37 Bytes

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

Jedes Element xvon lwird einmal für jedes Element, dessen Präfix es ist, wiederholt. Dies ist genau ein Mal für eine Liste ohne Präfix, wobei die ursprüngliche Liste angegeben wird. Die Präfixeigenschaft wird durch Zippen beider Listen mit überprüft x, wodurch Elemente über die Länge von abgeschnitten werden x.

xnor
quelle
Dies ist eine elegante Lösung (+1)
Michael Klein
9

Java, 128 127 126 125 124 121 Byte

(Vielen Dank, @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;}

Ungolfed

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;
}

Ausgabe

[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
quelle
1
Idk Kampf um Java, aber würde &funktionieren, anstatt &&?
Maltysen
1
Richtig, speichert ein weiteres Byte. In Java verhalten sich bitweise Operatoren mit booleschen Operanden genauso wie normale logische Operatoren, außer dass sie keine Kurzschlüsse verursachen, die in diesem Fall nicht benötigt werden.
16.
Könnten Sie nicht einfach den Rückgabetyp der Funktion auf intund return 0und ändern 1? Das würde mehrere Bytes einsparen. Ich vergesse auch, ob dies in Java gültig ist, aber wenn Sie deklarieren i, jund linnerhalb der äußeren forSchleife, die ein Byte von einem Semikolon weniger speichern würde.
Patrick Roberts
@PatrickRoberts Maltysen schlug dies vor, aber dies ist nicht gültig gemäß der am besten bewerteten Definition von Wahrhaftigkeit / Falschheit . Das Einfügen der Deklarationen in die Schleife ist jedoch völlig richtig und ziemlich offensichtlich, jetzt, wo ich darüber nachdenke. Das ist, was Sie zum Golfen um 4 Uhr morgens bekommen: ^)
Marv
3
@Joba Das ist ziemlich sicher nicht gültig, da indexOf -1 zurückgibt, wenn der String nicht gefunden wird. Es müsste indexOf(a[i])==0in diesem Fall keine Einsparungen geben.
Pokechu22
6

Python 2, 48 51 Bytes

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

Für jedes Element avon ermittelt ldie Funktion a.findden Index des ersten Vorkommens ain der Eingabezeichenfolge und gibt -1eine Abwesenheit an. Gibt also 0ein Präfix an. In einer Liste ohne Präfix gibt die Zuordnung dieser Funktion nur eine einzige 0für asich zurück. Die Funktion prüft, ob dies bei jedem der Fall ist a.


51 Bytes:

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

Ersetzen Sie ~durch ein Zeichen mit dem ASCII-Code 128 oder höher.

Für jedes Element ain list eine Kopie für jedes Element enthalten, das ein Präfix davon ist. Bei einer Liste ohne Präfix ist das einzige solche Element aselbst, sodass die ursprüngliche Liste erhalten wird.

xnor
quelle
4

CJam, 14 Bytes

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

Testsuite.

Erläuterung

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
quelle
4

JavaScript ES6, 65 43 40 Bytes

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

Meine vorherige Lösung, die String-Arrays aller UTF-8-Zeichen handhabte:

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

Ich konnte es vermeiden, JSON.stringifyda die Aufforderung nur druckbare ASCII-Zeichen angibt.

Prüfung

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
quelle
3

Haskell, 49 Bytes

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

Dies hat ein paar Teile:

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

Wenn die beiden Listen gleich sind, ist ein Element nur das Präfix von sich selbst und es ist gültig.

Michael Klein
quelle
3

Retina , 19 Bytes

Die Anzahl der Bytes setzt die Kodierung nach ISO 8859-1 voraus.

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

Der Eingang sollte zeilenweise getrennt sein. Ausgabe ist 0für falsch und1 für wahr.

Probieren Sie es online!(Leicht modifiziert, um stattdessen mehrere durch Leerzeichen getrennte Testfälle zu unterstützen.)

Erläuterung

O`.+

Sortieren Sie die Zeilen in der Eingabe. Wenn ein Präfix existiert, endet es direkt vor einer Zeichenfolge, die es enthält.

Mm1`^(.+)¶\1

Versuchen Sie, Meine vollständige Zeile abzugleichen ( ), die sich auch am Anfang der nächsten Zeile befindet. Der maktiviert den Multiline-Modus so, dass er ^mit dem Zeilenanfang übereinstimmt, und 1stellt sicher, dass höchstens eine Übereinstimmung gezählt wird, sodass die Ausgabe 0oder ist 1.

0

Zum Tauschen 0und 1im Ergebnis zählen wir die Anzahl der 0s.

Martin Ender
quelle
3

Java, 97 Bytes

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

Verwendet die meisten Tricks aus @ Marvs Antwort aber auch die Gleichheit von foreach-Schleife und String-Referenz.

Nicht abgeschlossen:

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

Beachten Sie, dass dies, wie gesagt, die Zeichenfolgenreferenzgleichheit verwendet. Das bedeutet, dass sich der Code aufgrund von String-Internierung merkwürdig verhalten kann . Der Code funktioniert nicht nur bei der Verwendung von Argumenten, die über die Befehlszeile übergeben wurden, sondern auch bei der Verwendung von Elementen, die über die Befehlszeile gelesen wurden. Wenn Sie die zu testenden Werte fest codieren möchten, müssen Sie den String-Konstruktor manuell aufrufen, um zu erzwingen, dass keine Internierung stattfindet:

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
quelle
@ Jo King Siehe die zweite Hälfte meiner Antwort; Es ist etwas kompliziert und hängt davon ab, wie die Eingabe angegeben wird. Ich kann mich jedoch nicht erinnern, dies tatsächlich geschrieben zu haben
Pokechu22,
3

PostgreSQL, 186 , 173 Bytes

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

Ausgabe:

Bildbeschreibung hier eingeben

Diesmal keine Live-Demo. http://sqlfiddle.com unterstützt nur 9.3 und zum Ausführen dieser Demo wird 9.4 benötigt.

Wie es funktioniert:

  1. Teilen Sie das String-Array mit der Nummer und dem Namen y
  2. Holen Sie sich alle y
  3. LEFT OUTER JOINauf die gleiche abgeleitete Tabelle basierend auf der gleichen i(id), aber mit unterschiedlichen oridinal, die mit dem Präfix beginneny.z LIKE u.z||'%'
  4. Gruppieren Sie das Ergebnis basierend auf c(anfängliches Array) und verwenden Sie die EVERYGruppierungsfunktion. Wenn jede Zeile aus der zweiten Tabelle IS NULLkeine Präfixe enthält.

Eingabe bei Interesse:

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"}';

BEARBEITEN:

SQL Server 2016+ Implementierung:

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

Hinweis: Es handelt sich um eine durch Kommas getrennte Liste, nicht um ein echtes Array. Aber die Grundidee ist die gleiche wie in PostgreSQL.


EDIT 2:

Tatsächlich WITH ORDINALITYkönnte ersetzt werden:

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
quelle
3

Brachylog , 8 Bytes

¬(⊇pa₀ᵈ)

Probieren Sie es online!

Ausgaben durch Prädikat Erfolg / Misserfolg. Nimmt mehr als 60 Sekunden für den letzten wahrheitsgemäßen Testfall in Anspruch ["111","010","000","1101","1010","1000","0111","0010","1011","0110","11001","00110","10011","11000","00111","10010"] , übergibt ihn jedoch schnell mit einem hinzugefügten Byte , wodurch eine große Anzahl von Möglichkeiten beseitigt wird, die früher als das Programm ( Ċvor dem Prüfen von Permutationen und nicht nach dem Prüfen von Permutationen) auftreten, um die Länge der Unterliste auf zu begrenzen zwei).

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

Weniger trivial 9-Byte - Varianten als ¬(⊇Ċpa₀ᵈ)der Lauf in angemessener Zeit sind ¬(⊇o₁a₀ᵈ), ¬(⊇o↔a₀ᵈ)und ¬(⊇oa₀ᵈ¹).

Nicht verwandte Zeichenfolge
quelle
Wenn diese Herausforderung "zwei unterschiedliche und konsistente Werte" anstelle von "wahr / falsch" verwendet, würde dies nur 5 Bytes dauern.
Nicht verwandte String
2

Perl 6 , 24 Bytes

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

Probieren Sie es online!

Wow, überraschend kurz bei Verwendung eines langen eingebauten.

Erläuterung

{                      }  # Anonymous code block taking a list
 .all                     # Do all of the strings
     .starts-with(    )   # Start with
                  .one    # Only one other string (i.e. itself)
Scherzen
quelle
Ich habe eine 50-Byte- Antwort geschrieben, aber deine hat meine gerade aus dem Wasser geblasen.
BB94
1
@ bb94 Ja, ich habe mit einer ähnlichen Antwort angefangen, bin aber auf dasselbe Problem gestoßen wie deins mit Sets mit doppelten Schlüsseln, die die Wahrheit zurückgeben. Diese Antwort zu schreiben war unglaublich befriedigend
Jo King
1

Schläger, 70 Bytes

(λ(l)(andmap(λ(e)(not(ormap(curryr string-prefix? e)(remv e l))))l))
Winny
quelle
1

Python, 58-55 Bytes

lambda l:sum(0==a.find(b)for a in l for b in l)==len(l)
DJMcMayhem
quelle
a.index(b)==0ist etwas kürzer. Alternativ könnten Sie tun 0**sum(a.index(b)for a in l for b in l).
Mego
@Mego Das funktioniert nicht, da indexeine Ausnahme ausgelöst wird, wenn sie bnicht gefunden wird. Und weil es sein sollte ==, nicht >=. Funktioniert jedoch find. (Und es ist auch kürzer!)
DJMcMayhem
Hoppla, ich wollte tippen find. Schläfriges Gehirn ist schläfrig. Die zweite Version sollte auch funktionieren find.
Mego
@Mego Ich bin mir nicht sicher, ob ich die zweite Version bekomme. Würde das nicht immer 0 zurückgeben?
DJMcMayhem
@Mego Das funktioniert nur, wenn jeder String gleich ist. Der Grund, mit dem wir es vergleichen, len(l)ist , dass es immer mindestens eine Übereinstimmung pro gibt, da wir alle bs durchlaufen . Wir prüfen also, ob die Anzahl der Übereinstimmungen mit der Anzahl der Elemente übereinstimmt. aa
DJMcMayhem
1

JavaScript (ES6), 52 54

Bearbeite 2 Bytes, die dank @Neil gespeichert wurden

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

Prüfung

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
quelle
!w.indexOf(v)?
Neil
@ Neil richtig, danke
edc65
1

Mathematica 75 69 68 Bytes

Laut wie immer. Aber Martin B konnte den Code um 7 Bytes reduzieren.

Methode 1: Speichern der Ausgabe in einem Array

(68 Bytes)

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"}

Wahr


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

Falsch


Methode 2: Speichern der Ausgabe in a List

(69 Bytes)

f@a_:=!Or@@Flatten[a~Drop~{#}~StringStartsQ~a[[#]]&/@Range@Length@a]
DavidC
quelle
Die Vorrangregeln sollten a~Drop~{#}~StringStartsQ~a[[#]]funktionieren. Außerdem Arraysollten Sie ein paar Bytes sparen Length, vor allem, weil es Ihnen ermöglicht, Join@@anstatt zu verwenden Flatten@(vorausgesetzt, Sie verwenden Flattennur für eine einzelne Ebene).
Martin Ender
Danke für den Vorschlag. Ich werde Arrayspäter nachsehen .
DavidC
1

Mathematica, 41 Bytes

!Or@@StringStartsQ@@@Reverse@Sort@#~Subsets~{2}&
Ein Simmons
quelle
1

APL (Dyalog Unicode) , 13 Byte SBCS

-2 Bytes:

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

Probieren Sie es online!

Erläuterung:

≢=∘≢∘⍸∘.(⊃⍷)⍨   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
voidhawk
quelle
~2∊+\⊃¨∘.⍷⍨⎕­
ngn
1

J , 17 Bytes

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

Probieren Sie es online!

Hinweis: Ich habe dies tatsächlich geschrieben, bevor ich mir die APL-Antwort angesehen habe, um mich ihr ohne Vorurteile zu nähern. Es stellt sich heraus, dass die Ansätze fast identisch sind, was interessant ist. Ich denke, das ist die natürliche "Array thinknig" -Lösung

Boxed Input nehmen, da die Strings ungleich lang sind.

Erstellen Sie eine Selbstfunktionstabelle /~für jedes Element, das mit jedem Element gepaart ist, und prüfen Sie, ob am Anfang eine Übereinstimmung vorliegt{.@E. . Dadurch wird eine Matrix mit 1: 0-Ergebnissen erstellt.

Summiere es zweimal 1#.1#., um eine einzelne Zahl zu erhalten, die "alle in der Matrix" darstellt, und überprüfe, ob diese Zahl der Länge der Eingabe entspricht#= . Wenn ja, sind die einzigen Präfix-Übereinstimmungen Selbst-Übereinstimmungen, dh wir haben einen Präfix-Code.

Sortierlösung, 18 Bytes

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

Versuchen Sie einen anderen Ansatz. Diese Lösung sortiert und betrachtet benachbarte Paare.

Probieren Sie es online!

Jona
quelle
1

R , 48 Bytes

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

Probieren Sie es online!

Erläuterung: outer(s,s,startsWith)Gibt eine Matrix von Logiken aus, die prüfen, ob s[i]ein Präfix von ist s[j]. Wenn ses sich um einen Präfixcode handelt, length(s)enthält das Ergebnis genau WAHRE Elemente, die den diagonalen Elementen entsprechen ( s[i]ein Präfix für sich selbst).

Robin Ryder
quelle
1
Ich habe ein paar andere 48-Byte-Alternativen gefunden, function(s)all(colSums(outer(s,s,startsWith))<2)aber es bleibt startsWitheine Funktion, die ich nicht kannte! Schöner Fund.
Giuseppe
1
@ Giuseppe Ich habe verschiedene Möglichkeiten ausprobiert, um zu überprüfen, ob es sich bei der Matrix um eine Identitätsmatrix handelt, konnte sie jedoch auch nicht unter 48 Byte bringen. Ich dachte, dieser Weg sei am einfachsten zu verstehen, aber ich bin mir sicher, dass es jemandem gelingen wird, ihn abzuspielen!
Robin Ryder
47 Bytes durch Invertieren TRUEund FALSE...
Giuseppe
@ Giuseppe Ist das erlaubt? Die Regeln verlangen ausdrücklich die Wahrheit, wenn die Eingabe ein gültiger Präfixcode ist. (Auch Ihr Link ist auf die 48-Byte-Version, aber ich vermute, dass Ihr Vorschlag zu ersetzen ist == durch >. :-))
Robin Ryder
0

Ruby, 48 Bytes

Verwendet Argumente als Eingabe und stdout als Ausgabe.

p !$*.map{a,*b=$*.rotate!
a.start_with? *b}.any?
ezrast
quelle
0

Scala, 71 Bytes

(s:Seq[String])=>(for{x<-s;y<-s}yield x!=y&&x.startsWith(y)).forall(!_)
Jacob
quelle
0

Schläger 130 Bytes

(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

Ungolfed:

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

Testen:

(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"])

Ausgabe:

#t
#t
#t
#t
#t
#f
#f
#f
#f
#f
#f
rnso
quelle
0

C (gcc) 93 Bytes

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;}

Probieren Sie es online!

Einfache double for-Schleife, mit der strstr(a,b)==anach Präferenzen gesucht wird. Hauptsächlich hinzugefügt, da es noch keine C-Antwort zu geben scheint.

LambdaBeta
quelle
88 Bytes
Ceilingcat
0

05AB1E , 13 Bytes

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

Zu lange. Anfangs hatte ich eine 9-Byte-Lösung, die jedoch für den Testfall mit duplizierten Schlüsseln fehlgeschlagen ist.

Probieren Sie es online aus oder überprüfen Sie alle Testfälle .

Erläuterung:

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
quelle
0

Japt , 8 Bytes

á2 ËrbÃe

Versuch es

á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)
Zottelig
quelle
0

Stax , 6 Bytes

å·↑↑¶Ω

Führen Sie es aus und debuggen Sie es

Dies erzeugt für die Wahrheit einen Wert ungleich Null.

Die allgemeine Idee besteht darin, jedes Zeichenfolgenpaar in der Eingabe zu berücksichtigen. Wenn der Teilzeichenfolgenindex einer in der anderen jemals Null ist, ist dies kein gültiger Präfixcode. In stax ergibt sich der Index einer nicht vorhandenen Teilzeichenfolge-1 . Auf diese Weise können alle paarweisen Teilzeichenfolgenindizes miteinander multipliziert werden.

Dies ist derselbe Algorithmus wie die Pyth-Lösung von isaacg, aber ich habe ihn unabhängig entwickelt.

rekursiv
quelle