Diese Herausforderung besteht darin, die Stimmung unseres Mods Alex A. zu heben , der normalerweise Unrecht hat .
Angenommen, Sie haben einen Freund namens Alex, der Hilfe bei der grundlegenden Logik und Mathematik benötigt, insbesondere bei der mathematischen Äquivalenz .
Er gibt Ihnen eine Liste von Gleichungen in der Form, [variable] = [variable]
in der a [variable]
immer ein einzelner Großbuchstabe von A bis Z ist (kein Kleinbuchstabe, keine Zahl oder etwas anderes). Es gibt eine Gleichung pro Zeile in der Liste mit Ausnahme einer einzelnen Zeile, die nur besagt therefore
.
Alle Gleichungen über dem therefore
sind Prämissen , Tatsachen, von denen angenommen wird, dass sie wahr sind. Alle nachstehenden Gleichungen therefore
sind unbestätigte Aussagen, Tatsachen, die Alex aus den Prämissen abzuleiten versucht, und sie können wahr sein oder auch nicht.
Zum Beispiel ist in dieser Gleichungsliste der einzige Schlusssatz A = C
zufällig wahr:
A = B
B = C
therefore
A = C
Es ist Ihre Aufgabe, Alex zu sagen, ob alle seine Vorschläge logisch aus den gegebenen Voraussetzungen folgen. Das heißt, Sie müssen Alex sagen, ob er in seinen Schlussfolgerungen falsch oder richtig ist.
Schreiben Sie ein Programm / eine Funktion, die eine Folge einer Liste von Gleichungen wie beschrieben aufnimmt und ausgibt / zurückgibt
Alex is right
wenn alle Schlussfolgerungen logisch aus den Räumlichkeiten folgen und ansonsten ausgegeben werden
Alex is wrong
wenn eine Schlussfolgerung nicht logisch aus den Räumlichkeiten folgt.
Der kürzeste Code in Bytes gewinnt.
Achten Sie auf folgende Fälle:
Variable ist immer gleich. z.B
B = A therefore A = A X = X
Ergebnisse in
Alex is right
.Variablen mit unbekannten Beziehungen können nicht als gleich angenommen werden. z.B
P = Q therefore E = R
Ergebnisse in
Alex is wrong
.Wenn es nach dem keine Gleichungen mehr gibt, sind
therefore
die Schlussfolgerungen nicht korrekt . z.BD = C therefore
und
therefore
beide ergeben
Alex is right
.Wenn es keine Gleichungen
therefore
gibt, kann nur auf die Selbstgleichheit geschlossen werden. z.Btherefore R = R
Ergebnisse in
Alex is right
, abertherefore R = W
Ergebnisse in
Alex is wrong
.
Mehr Beispiele
Alex ist in falschen Fällen: (durch Leerzeilen getrennt)
A = B
C = D
therefore
A = C
A = L
E = X
A = I
S = W
R = O
N = G
therefore
G = N
L = I
R = O
S = A
X = X
X = E
D = K
D = Q
L = P
O = L
M = O
therefore
K = L
A = B
therefore
B = C
Z = A
S = S
therefore
A = Z
A = A
S = A
A = S
Z = A
Z = A
K = L
K = X
therefore
X = P
L = X
L = P
therefore
A = B
B = C
A = C
therefore
A = A
B = B
C = C
D = D
E = E
F = F
G = G
H = H
I = I
J = J
K = K
T = I
L = L
M = M
N = N
O = O
P = P
Q = Q
R = R
S = S
T = T
U = U
V = V
W = W
X = X
Y = Y
Z = Z
A = B
B = C
C = D
D = E
E = F
F = G
G = H
H = I
I = J
J = K
K = L
L = M
M = N
N = O
O = P
P = O
Q = R
R = S
S = T
T = U
U = V
V = W
W = X
X = Y
Y = Z
therefore
A = Z
therefore
C = D
T = Y
A = Z
P = Q
therefore
E = R
therefore
R = W
Alex hat Recht:
H = J
therefore
J = H
K = L
K = X
therefore
L = X
C = B
B = A
therefore
A = B
K = L
K = X
K = P
therefore
L = X
L = P
X = P
A = Y
Y = Q
Q = O
therefore
O = Y
O = A
C = C
therefore
C = C
A = B
B = A
therefore
A = B
B = A
A = B
B = C
C = D
therefore
A = A
A = B
A = C
A = D
B = A
B = B
B = C
B = D
C = A
C = B
C = C
C = D
D = A
D = B
D = C
D = D
therefore
A = A
B = B
C = C
D = D
E = E
F = F
G = G
H = H
I = I
J = J
K = K
L = L
M = M
N = N
O = O
P = P
Q = Q
R = R
S = S
T = T
U = U
V = V
W = W
X = X
Y = Y
Z = Z
D = I
F = H
J = M
therefore
M = J
D = I
H = F
A = B
B = C
C = D
D = E
E = F
F = G
G = H
H = I
I = J
J = K
K = L
L = M
M = N
N = O
O = P
P = Q
Q = R
R = S
S = T
T = U
U = V
V = W
W = X
X = Y
Y = Z
therefore
Z = A
F = R
G = I
W = L
A = B
B = C
therefore
A = C
B = A
therefore
A = A
X = X
P = P
C = G
M = C
therefore
D = C
therefore
therefore
therefore
R = R
Alex is wrong
Überprüft alle Testfälle.therefore\nTABS < SPACES
->Alex is right
Antworten:
CJam, 49
Inspiriert von der Ruby-Lösung von Histocrat. Probieren Sie es online
3 Bytes ausgelöscht dank jimmy23013 :)
Erläuterung:
Für jede Prämisse ersetzt das Programm die erste Variable durch die zweite Variable im restlichen Text. Anschließend wird geprüft, ob Schlussfolgerungen mit unterschiedlichen Variablen vorliegen.
Alte Version, 85
Dies verwendet einen Union-Find-Algorithmus. Probieren Sie es online aus
quelle
"Alex is "qN%S{f{)er}(_el-}h;{)#},"wrong""right"?
.Alex is * wrong * right * ?
Ruby,
80,76 + 2 = 78p0
Führen Sie mit Befehlszeilenflags ausErläuterung:
Dies verwendet eine reine String-Manipulation.
p0
Liest die vollständige Eingabe als einzelne Zeichenfolge in die Variable$_
. Dann vergleichen wir diese Zeichenfolge wiederholt mit dem regulären Ausdruck/(.) = (?!\1)(.)/
, der alle Zeichenfolgen der Form "X = Y" findet, bei denen X und Y nicht der gleiche Buchstabe sind, und ordnet X $ 1 und Y $ 2 zu. Wenn eine solche Übereinstimmung gefunden wird, werdengsub$1,$2
alle Instanzen von X durch Y in der Zeichenfolge ersetzt. Wir prüfen auch, ob diese Übereinstimmung vor oder nach dem "deshalb" mit aufgetreten istWenn es danach passiert ist, ist es eine ungerechtfertigte Behauptung und Alex ist falsch. Wir verfolgen mithilfe von, ob solche Vorkommnisse aufgetreten sind
p=
. Die Verwendung vonp
als Tracking-Variable verhindert, dass die Schleife unterbrochenp
wird, wenn sie nicht ein einziges Mal ausgeführt wird.Ab diesem Beitrag ist die CJam-Lösung länger. Ein stolzer, zweifellos flüchtiger Moment.
Edit: Ja, schnell entthront. Um die Erklärung zu beenden, wird mit dem
p
Flag der Endwert von$_
am Ende der Ausführung ausgegeben, sodass die letzte Zeile die Ausgabe ist.quelle
String#format
, sowohl den gsub-Aufruf als auch die Zuweisung in einen Ausdruck zu bringen, ist eine ziemlich nette Idee, +1!CJam,
8375686764 BytesVielen Dank an Dennis für das Speichern von 1 Byte.
Testsuite. Die Testfälle sind zu lang für einen Permalink. Kopieren Sie sie einfach aus der Frage. Beachten Sie, dass dies ziemlich langsam ist - im Online-Dolmetscher dauert es ein oder zwei Minuten. Sie können es viel schneller machen , indem
5*
zu2*
in diesem Fall ist es fast sofort beenden wird und alle bis auf einen Testfall lösen.Erläuterung
(Etwas veraltet.)
Die Idee ist, eine Art "Überflutung" möglicher Gleichheiten durchzuführen und dann alle Gleichheiten, die wir erhalten haben, aus der Abschlussliste zu entfernen. Es kann gezeigt werden, dass wir nicht mehr als 5 Schritte der Überflutungsfüllung benötigen, da diese einen Abstand (in der anfänglichen Ungleichungsgrafik) von 25 zurücklegen würden, aber der maximale Abstand 25 beträgt.
25 = 32
quelle
R,
183192 BytesIch habe meine Antwort geändert, um eine Einschränkung zu beheben, auf die user2357112 hingewiesen hat. Es gibt immer noch eine äußerst geringe Wahrscheinlichkeit, Alex anzurufen, wenn er tatsächlich Recht hat (was anscheinend nicht sehr oft vorkommt, wenn ich den Kontext der Herausforderung verstehe :-). Ich hoffe, es wird ihm nichts ausmachen.
Ich muss das ein bisschen entgolfen:
Zum Beispiel, wenn die Eingabe ist
es wird zuerst ausgewertet
setup
:dann ist die
premises
werden jeweils 1.000-mal in zufälliger Reihenfolge ausgeführt. Dies soll sicherstellen ("fast sicher"), dass alle Gleichheiten weitergegeben werden. Abschließend wird Folgendes ausgewertet
propositions
:quelle
A = B, B = C, C = A
, zirkulieren die Werte für immer. 26 Bewertungsrunden reichen nicht aus.Haskell, 208 Bytes
Ich verlagere die Arbeit in das
Data.Equivalence.Persistent
Modul, das Funktionen zum Bearbeiten von Äquivalenzklassen bereitstellt. Sie müssen nur die Eingabe- und Aufruffunktionen analysieren, die manchmal zu lange Namen haben, um richtig Golf zu spielen.Anwendungsbeispiel:
quelle
Mathematica, 182
Funktioniert bei der Eingabe von Zeichenfolgen entsprechend der Herausforderung.
quelle
f
als reine Funktion und ersetztSimplify[#2,#1]
mit#2~Simplify~#
und ErsetzenStringSplit[s,"\n"]
mit#~StringSplit~"<actual newline>"
.q=StringSplit;
und dann s / StringSplit / q / für weitere 6 Bytes oder so gespeichert. Aber am Ende ist dies leider keine gute Herausforderung für Mathematica, auch wenn der logische Charakter perfekt zu mir passte.a___
undb___
können wahrscheinlich zua__
undb__
und geändert werdens=Symbol;
.a__
undb__
wird nicht funktionieren, wenn Räumlichkeiten, Vorschläge oder beides leer sindNetzhaut, 90 Bytes
Platzieren Sie zum Ausführen die folgenden 12 Codezeilen in 12 separaten Dateien (+11 Byte, die für jede Datei nach der ersten gezählt werden).
<empty>
bezeichnet eine leere Datei;\n
bezeichnet einen wörtlichen Zeilenumbruch. Alternativ können Sie das\n
s so lassen, wie es ist, alle Zeilen in eine einzige Datei einfügen und die-s
Option verwenden. Stellen Sie sicher, dass in allen Dateien Literal Newlines und nicht Windows verwendet werden\r\n
, und beachten Sie das Leerzeichen am Ende der letzten Zeile.Wie es funktioniert
Die erste Ersetzung entspricht der ersten Prämisse in der Eingabe, wenn die lhs der Prämisse später in der Datei auftreten. Es ersetzt dieses spätere Vorkommen durch das rechte der Prämisse. Der
+
Modifikator stellt sicher, dass das Ersetzen wiederholt wird, bis es nicht mehr übereinstimmt. Wenn also die erste Voraussetzung istA = B
, werden alle nachfolgendenA
s in der Datei inB
s umgewandelt.Die zweite Ersetzung entfernt die erste Prämisse aus der Eingabe, da wir jetzt damit fertig sind. Dann
)
kehrt der Modifikator zur ersten Ersetzung zurück und wiederholt sich, bis sich in einem gesamten Durchlauf durch die Schleife nichts geändert hat. Dies geschieht, wenn alle Räumlichkeiten ersetzt und entfernt wurden und die Eingabe mit beginnttherefore
.Die dritte Ersetzung stimmt mit der ersten Eingabezeile (die
therefore
) oder einer beliebigen Form übereinA = A
und löscht sie. Wenn alle Vorschläge von den Prämissen unterstützt werden, stimmen alle mit dieser Form überein. Was also übrig bleibt, sollte nur aus Zeilenumbrüchen bestehen. Die vierte Ersetzung ändert dies inright
. Ansonsten ändert die fünfte Ersetzung alles Übrige (wasr
seitdem nicht mehr enthalten isttherefore
) inwrong
. Schließlich fügt die letzte ErsetzungAlex is
zu Beginn hinzu.quelle
Python 2, 264 Bytes
Es gibt bereits eine bemerkenswerte Python 3-Antwort von mbomb007 . Diese Antwort stiehlt flagrant von diesem einen (insbesondere der "Alex ist Wrriognhgt" -Trick).
Und diese Antwort ist auch deutlich länger als diese ...
In dieser Antwort geht es jedenfalls darum, ein Wörterbuch mit Schlüssel-Wert-Paaren zu führen, in dem die Schlüssel aus 26 Großbuchstaben bestehen und der entsprechende Wert jedes Schlüssels der Menge der Buchstaben entspricht, die dem Schlüssel entsprechen. (Wenn alle 26 Buchstaben gleich wären, hätte jeder Schlüssel einen Satz von 26 Buchstaben für den entsprechenden Wert.)
(Um Bytes zu sparen, werden in dieser Antwort Leerzeichen und Tabulatoren gemischt , was in Python 2 zulässig ist.)
Dieser Code ist sehr effizient, da das Wörterbuch auf eine maximal mögliche Größe (26 mal 26, wie oben beschrieben) beschränkt ist, die nicht von der Anzahl der Eingabezeilen abhängt.
Als ich diese Lösung spielte, wurde mir klar, dass ich durch Ersetzen von Zeichenfolgen anstelle von Mengen für die Wörterbuchwerte vier Bytes einsparen konnte
mit
Natürlich müssen Sie dann auch die drei Instanzen der Mengenvereinigungsoperation
|
durch Zeichenfolgenverkettung ersetzen (HINWEIS: TUN SIE DAS NICHT)+
, aber das ändert nichts an der Codelänge. Das Ergebnis ist, dass alles immer noch genauso funktionieren sollte, außer dass Duplikate nicht beseitigt werden, wie dies bei Sets der Fall ist. Klingt in Ordnung - ein bisschen weniger effizient, aber 260 Bytes statt 264.Nun, es stellt sich heraus, dass die 260-Byte-Version so ineffizient ist, dass es einen Fehler verursachte,
MemoryError
als ich sie mit testeteDas hat mich überrascht. Untersuchen wir die 260-Byte-Version "String-Verkettung"!
Natürlich würde es mit den Schlüssel-Wert-Paaren beginnen
A:A
undB:B
(plus 24 andere, die keine Rolle spielen). Wir werden schreibend[A]
, um den Wörterbuchwert zu bezeichnen, der dem Schlüssel entsprichtA
, also hätten wir am Anfangd[A] = A
. Nun, unter der VoraussetzungA = B
, würde es damit beginnen, die Werte zu verkettend[A]=A
undd[B]=B
zu erhalteny = AB
. Dann würde es diese Zeichenfolge zweimal durchlaufen:for v in AB: for w in AB:
...Also, das erste Mal durch die Schleife, haben wir
v=A
undw=A
. Anwendungd[v] += d[w]
undd[w] += d[v]
Ergebnisse in der folgenden Reihenfolge der Wörterbücher:Weiter mit
v=A
undw=B
:Als nächstes
v=B, w=A
:Und
v=B, w=B
:Die obige Abfolge von Schritten würde die einzelne Prämisse implementieren
A = B
, mit der Schlussfolgerung, dassA
jeder Buchstabe in der ZeichenfolgeAAAABBAAAABAAAAB
und jeder Buchstabe in der ZeichenfolgeB
gleich istBAAAABAAAABBAAAABAAAABBAAAABAAAABBAAAABAAAAB
.Angenommen, die nächste Voraussetzung ist
A = B
wieder . Sie berechnen zuersty = d[A] + d[B] = AAAABBAAAABAAAABBAAAABAAAABBAAAABAAAABBAAAABAAAABBAAAABAAAAB
.Als nächstes durchlaufen Sie diese Zeichenfolge zweimal:
for v in y: for w in y:
...Ja. Vielleicht wäre das keine sehr effiziente Implementierung.
quelle
ES6, 128 Bytes
Lose basierend auf der Ruby-Version.
Sucht nach Ungleichheit vor dem "also" und ersetzt die Variable jedes Mal in der Zeichenfolge (dies spart Bytes über eine while-Schleife).
quelle
C 240 Bytes
Dies funktioniert, indem Werte in Mengenbäumen kombiniert werden, sodass alle äquivalenten Werte zur gleichen Mengenwurzel führen. Ungolfed, mit expliziten impliziten Typen.
180 Bytes
Diese kürzere Version funktioniert in allen Fällen vom OP aus, aber für einige andere Eingaben behauptet Alex fälschlicherweise, dass sie falsch sind. Es verwendet einen ähnlichen Ansatz, setzt jedoch für jede Prämisse einfach den zweiten Eintrag auf den aktuellen Wert des ersten Eintrags. Beim Vergleich werden nur exakte Werte angezeigt, anstatt einen Baum zu durchsuchen.
Eine Beispieleingabe, für die dies fehlschlägt:
quelle
05AB1E , 32 Bytes
Inspiriert von @aditsus CJam-Antwort .
Probieren Sie es online aus oder überprüfen Sie alle Testfälle .
Erläuterung:
Sehen Sie sich meinen Tipp 05AB1E (Abschnitt Wie verwende ich das Wörterbuch? ) An, um zu verstehen, warum es
…±º€ˆ
ist"alex is "
und„–у©
ist"wrong right"
.quelle
Bash + Awk + SWI-Prolog , 167 Bytes
Probieren Sie es online!
Ursprünglich war dies nur eine Prolog-Antwort, aber die Werkzeuge, die ich finden konnte, um das Eingabeformat tatsächlich in etwas Verwendbares zu verwandeln, waren so begrenzt, dass ich mich entschied, diesen Teil in bash zu machen, obwohl ich so gut wie keine Erfahrung hatte Ich tat irgendetwas in Bash und hatte noch nie Awk berührt. Am Ende habe ich genug Stunden damit verbracht, um es zu veröffentlichen, selbst nachdem es zu diesem 167-Byte-Monster herangewachsen war, das kaum Golf gespielt hat.
Im Grunde genommen übernimmt das awk-Programm die Eingabe von stdin, löscht die Zeile mit
therefore
, ersetztA = B
sie danach mit?=(A,B)
und hängt sie anwrite(\"Alex is right\");write(\"Alex is wrong\"). halt.
. Dannpaste -sd ,
ersetzt jede Neue - Zeile aber die letzte mit einem Komma, es in eine gültigen zwei Anfragen an die SWI-Prolog Schale Transformation, die dann mit dem Druckergebnis führen zu einer Linie abgeschnitten ist , durchhead -n1
, das erfordert<(...)
aus Gründen anstelle einem Rohr jenseits mein Verständnis. All dies, nur um ein eingebautes zu verwenden !quelle