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.
quelle
001
eindeutig entzifferbar? Es könnte entweder00, 1
oder sein0, 11
.0, 00, 1, 11
alle 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 also0, 10, 11
beispielsweise ein Präfixcode sind, der eindeutig entschlüsselbar ist.001
ist keine gültige Nachricht, aber0011
oder0010
eindeutig entschlüsselbar.Antworten:
Pyth, 8 Bytes
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).
quelle
Haskell, 37 Bytes
Jedes Element
x
vonl
wird 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üftx
, wodurch Elemente über die Länge von abgeschnitten werdenx
.quelle
Java,
128127126125124121 Byte(Vielen Dank, @Kenny Lau, @Maltysen, @Patrick Roberts, @Joba)
Ungolfed
Ausgabe
quelle
&
funktionieren, anstatt&&
?int
und return0
und ändern1
? Das würde mehrere Bytes einsparen. Ich vergesse auch, ob dies in Java gültig ist, aber wenn Sie deklariereni
,j
undl
innerhalb der äußerenfor
Schleife, die ein Byte von einem Semikolon weniger speichern würde.indexOf(a[i])==0
in diesem Fall keine Einsparungen geben.Python 2, 48
51BytesFür jedes Element
a
von ermitteltl
die Funktiona.find
den Index des ersten Vorkommensa
in der Eingabezeichenfolge und gibt-1
eine Abwesenheit an. Gibt also0
ein Präfix an. In einer Liste ohne Präfix gibt die Zuordnung dieser Funktion nur eine einzige0
füra
sich zurück. Die Funktion prüft, ob dies bei jedem der Fall ista
.51 Bytes:
Ersetzen Sie
~
durch ein Zeichen mit dem ASCII-Code 128 oder höher.Für jedes Element
a
inl
ist eine Kopie für jedes Element enthalten, das ein Präfix davon ist. Bei einer Liste ohne Präfix ist das einzige solche Elementa
selbst, sodass die ursprüngliche Liste erhalten wird.quelle
CJam, 14 Bytes
Testsuite.
Erläuterung
quelle
JavaScript ES6,
654340 BytesMeine vorherige Lösung, die String-Arrays aller UTF-8-Zeichen handhabte:
Ich konnte es vermeiden,
JSON.stringify
da die Aufforderung nur druckbare ASCII-Zeichen angibt.Prüfung
quelle
Haskell, 49 Bytes
Dies hat ein paar Teile:
Wenn die beiden Listen gleich sind, ist ein Element nur das Präfix von sich selbst und es ist gültig.
quelle
Retina , 19 Bytes
Die Anzahl der Bytes setzt die Kodierung nach ISO 8859-1 voraus.
Der Eingang sollte zeilenweise getrennt sein. Ausgabe ist
0
fü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
Sortieren Sie die Zeilen in der Eingabe. Wenn ein Präfix existiert, endet es direkt vor einer Zeichenfolge, die es enthält.
Versuchen Sie,
M
eine vollständige Zeile abzugleichen ( ), die sich auch am Anfang der nächsten Zeile befindet. Derm
aktiviert den Multiline-Modus so, dass er^
mit dem Zeilenanfang übereinstimmt, und1
stellt sicher, dass höchstens eine Übereinstimmung gezählt wird, sodass die Ausgabe0
oder ist1
.Zum Tauschen
0
und1
im Ergebnis zählen wir die Anzahl der0
s.quelle
Java, 97 Bytes
Verwendet die meisten Tricks aus @ Marvs Antwort aber auch die Gleichheit von foreach-Schleife und String-Referenz.
Nicht abgeschlossen:
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:
quelle
PostgreSQL,
186, 173 BytesAusgabe:
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:
y
LEFT OUTER JOIN
auf die gleiche abgeleitete Tabelle basierend auf der gleicheni
(id), aber mit unterschiedlichenoridinal
, die mit dem Präfix beginneny.z LIKE u.z||'%'
c
(anfängliches Array) und verwenden Sie dieEVERY
Gruppierungsfunktion. Wenn jede Zeile aus der zweiten TabelleIS NULL
keine Präfixe enthält.Eingabe bei Interesse:
BEARBEITEN:
SQL Server 2016+
Implementierung: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 ORDINALITY
könnte ersetzt werden:SqlFiddleDemo
quelle
Brachylog , 8 Bytes
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).Weniger trivial 9-Byte - Varianten als
¬(⊇Ċpa₀ᵈ)
der Lauf in angemessener Zeit sind¬(⊇o₁a₀ᵈ)
,¬(⊇o↔a₀ᵈ)
und¬(⊇oa₀ᵈ¹)
.quelle
Perl 6 , 24 Bytes
Probieren Sie es online!
Wow, überraschend kurz bei Verwendung eines langen eingebauten.
Erläuterung
quelle
Schläger, 70 Bytes
quelle
Python,
58-55Bytesquelle
a.index(b)==0
ist etwas kürzer. Alternativ könnten Sie tun0**sum(a.index(b)for a in l for b in l)
.index
eine Ausnahme ausgelöst wird, wenn sieb
nicht gefunden wird. Und weil es sein sollte==
, nicht>=
. Funktioniert jedochfind
. (Und es ist auch kürzer!)find
. Schläfriges Gehirn ist schläfrig. Die zweite Version sollte auch funktionierenfind
.len(l)
ist , dass es immer mindestens eine Übereinstimmung pro gibt, da wir alleb
s durchlaufen . Wir prüfen also, ob die Anzahl der Übereinstimmungen mit der Anzahl der Elemente übereinstimmt.a
a
JavaScript (ES6), 52
54Bearbeite 2 Bytes, die dank @Neil gespeichert wurden
Prüfung
quelle
!w.indexOf(v)
?Mathematica
75 6968 BytesLaut wie immer. Aber Martin B konnte den Code um 7 Bytes reduzieren.
Methode 1: Speichern der Ausgabe in einem
Array
(68 Bytes)
Methode 2: Speichern der Ausgabe in a
List
(69 Bytes)
quelle
a~Drop~{#}~StringStartsQ~a[[#]]
funktionieren. AußerdemArray
sollten Sie ein paar Bytes sparenLength
, vor allem, weil es Ihnen ermöglicht,Join@@
anstatt zu verwendenFlatten@
(vorausgesetzt, Sie verwendenFlatten
nur für eine einzelne Ebene).Array
später nachsehen .Mathematica, 41 Bytes
quelle
APL (Dyalog Unicode) , 13 Byte SBCS
-2 Bytes:
Probieren Sie es online!
Erläuterung:
quelle
~2∊+\⊃¨∘.⍷⍨⎕
J , 17 Bytes
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
Versuchen Sie einen anderen Ansatz. Diese Lösung sortiert und betrachtet benachbarte Paare.
Probieren Sie es online!
quelle
R , 48 Bytes
Probieren Sie es online!
Erläuterung:
outer(s,s,startsWith)
Gibt eine Matrix von Logiken aus, die prüfen, obs[i]
ein Präfix von ists[j]
. Wenns
es 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).quelle
function(s)all(colSums(outer(s,s,startsWith))<2)
aber es bleibtstartsWith
eine Funktion, die ich nicht kannte! Schöner Fund.TRUE
undFALSE
...==
durch>
. :-))Pyth -
1312 BytesProbieren Sie es hier online aus .
quelle
Ruby, 48 Bytes
Verwendet Argumente als Eingabe und stdout als Ausgabe.
quelle
Scala, 71 Bytes
quelle
Schläger 130 Bytes
Ungolfed:
Testen:
Ausgabe:
quelle
C (gcc) 93 Bytes
Probieren Sie es online!
Einfache double for-Schleife, mit der
strstr(a,b)==a
nach Präferenzen gesucht wird. Hauptsächlich hinzugefügt, da es noch keine C-Antwort zu geben scheint.quelle
05AB1E , 13 Bytes
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:
quelle
Japt , 8 Bytes
Versuch es
quelle
C # (Visual C # Interactive Compiler) , 70 Byte
Probieren Sie es online!
quelle
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.
quelle