Ce défi consiste à élever les esprits de notre mod Alex A. , qui a généralement tort .
Supposons que vous avez un ami nommé Alex qui a besoin d'aide pour la logique de base et les mathématiques, en particulier l'équivalent mathématique .
Il vous donne une liste d'équations de la forme [variable] = [variable]
où a [variable]
est toujours une simple lettre majuscule de A à Z (pas une lettre minuscule, ni un chiffre, ni rien d'autre). Il y a une équation par ligne dans la liste, à l'exception d'une seule ligne qui dit seulement therefore
.
Toutes les équations ci-dessus therefore
sont des prémisses , des faits supposés vrais. Toutes les équations ci-dessous therefore
sont des propositions non vérifiées, des faits qu'Alex tente de déduire des prémisses, et elles peuvent être vraies ou non.
Par exemple, dans cette liste d’équations, la proposition de conclusion unique A = C
est vraie:
A = B
B = C
therefore
A = C
C'est à vous de dire à Alex si toutes ses propositions découlent logiquement des prémisses données. Autrement dit, vous devez dire à Alex s’il a tort ou tort dans ses conclusions.
Écrivez un programme / une fonction qui prend une chaîne d'une liste d'équations telle que décrite et qui est imprimée / retournée
Alex is right
si toutes les conclusions découlent logiquement des locaux, et sinon sorties
Alex is wrong
si aucune conclusion ne découle logiquement des locaux.
Le code le plus court en octets gagne.
Assurez-vous de faire attention à ces cas:
La variable est toujours égale à elle-même. par exemple
B = A therefore A = A X = X
résultats en
Alex is right
.Les variables avec des relations inconnues ne peuvent pas être supposées égales. par exemple
P = Q therefore E = R
résultats en
Alex is wrong
.Quand il n'y a pas d'équations après le,
therefore
alors les conclusions sont vaines . par exempleD = C therefore
et
therefore
les deux résultent en
Alex is right
.Quand il n'y a pas d'équations avant le
therefore
seul alors égalité de soi peut être déduite. par exempletherefore R = R
résultats en
Alex is right
, maistherefore R = W
résultats en
Alex is wrong
.
Plus d'exemples
Alex a tort: (séparés par des lignes vides)
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 a raison:
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
Vérifie tous les cas de test.therefore\nTABS < SPACES
->Alex is right
Réponses:
CJam, 49 ans
Inspiré de la solution Ruby d'Histocrat. Essayez-le en ligne
3 octets oblitérés grâce à jimmy23013 :)
Explication:
Pour chaque prémisse, le programme remplace la première variable par la deuxième variable dans le reste du texte. Il vérifie ensuite s'il existe une conclusion avec différentes variables.
Ancienne version, 85
Ceci utilise un algorithme de recherche d'union. Essayez-le en ligne
la source
"Alex is "qN%S{f{)er}(_el-}h;{)#},"wrong""right"?
.Alex is * wrong * right * ?
Rubis,
8076 + 2 = 78Avec les indicateurs de ligne de commande
p0
, exécutezExplication:
Ceci utilise une manipulation de chaîne pure.
p0
lit l'entrée complète sous la forme d'une chaîne unique dans la variable$_
. Ensuite, nous associons à plusieurs reprises cette chaîne à l'expression régulière/(.) = (?!\1)(.)/
, qui trouve toutes les chaînes de la forme "X = Y" où X et Y ne sont pas la même lettre et affecte X à $ 1 et Y à $ 2. Lorsqu'une telle correspondance est trouvée,gsub$1,$2
remplace toutes les instances de X par Y dans la chaîne. Nous vérifions également si cette correspondance a eu lieu avant ou après le "donc" avecSi cela s'est produit après, c'est une demande injustifiée et Alex a tort. Nous vérifions si de tels événements se sont produits avec
p=
. L'utilisation dep
comme variable de suivi évite que les choses ne se brisent si la boucle ne frappe jamais une seule fois, car ellep
ne retournera rien si elle n'a jamais été affectée.A partir de cet article, la solution CJam est plus longue. Un moment de fierté, si ce n’est sans doute.
Edit: Ouais, rapidement détrôné. De plus, pour terminer l'explication, avec l'
p
indicateur, la valeur finale de$_
est sortie à la fin de l'exécution, la dernière ligne est donc la sortie.la source
String#format
faire en sorte que l’appel gsub et l’affectation en une seule expression soit une bonne idée, +1!CJam,
8375686764 octetsMerci à Dennis d'avoir sauvegardé 1 octet.
Suite de tests. Les cas de test sont trop longs pour un lien permanent, copiez-les simplement de la question. Notez que c'est assez lent - cela prend une minute ou deux dans l'interprète en ligne. Vous pouvez le faire beaucoup plus rapidement en changeant
5*
de2*
dans ce cas , il finira presque instantanément et de résoudre tous sauf un cas de test.Explication
(Légèrement dépassé.)
L'idée est de faire une sorte de "remplissage" des égalités possibles, puis de supprimer toutes les égalités que nous avons obtenues de la liste des conclusions. On peut montrer que nous n'avons pas besoin de plus de 5 étapes de remplissage, car celles-ci couvriraient une distance (dans le graphe initial des inégalités) de mais la distance maximale est de 25.
25 = 32
la source
R,
183192 octetsJ'ai modifié ma réponse pour répondre à une limitation signalée par l'utilisateur2357112. Il y a encore une très faible probabilité d'appeler Alex alors qu'il a raison (ce qui en soi ne semble pas se produire très souvent si je comprends le contexte du défi :-). J'espère que ça ne le dérangera pas.
J'ai besoin de dé-golfer un peu:
Par exemple, si l'entrée est
il va d'abord évaluer le
setup
:puis le
premises
sera exécuté 1000 fois chacun dans un ordre aléatoire. Ceci est pour vous assurer ("presque sûr") que toutes les égalités sont propagées. Enfin, il évaluera
propositions
:la source
A = B, B = C, C = A
, les valeurs simplement cycle pour toujours 26 tours d'évaluation ne suffisent pas.Haskell, 208 octets
Je délègue le travail au
Data.Equivalence.Persistent
module, qui fournit des fonctions pour manipuler des classes d'équivalence. Tout ce qui reste à faire est d’analyser les fonctions d’entrée et d’appel qui ont parfois des noms trop longs pour un golf correct.Exemple d'utilisation:
la source
Mathematica, 182
Fonctionne sur l'entrée de chaîne, selon le défi.
la source
f
une fonction pure, en remplaçantSimplify[#2,#1]
par#2~Simplify~#
et en remplaçantStringSplit[s,"\n"]
par#~StringSplit~"<actual newline>"
.q=StringSplit;
, puis s / StringSplit / q / pour 6 autres octets ou plus. Mais à la fin, ce n’est pas un bon défi pour Mathematica, même si le personnage logique semblait un ajustement parfait.a___
etb___
peut probablement être changé ena__
etb__
, ets=Symbol;
.a__
etb__
ne fonctionnera pas si les locaux, les propositions ou les deux sont videsRetina, 90 octets
Pour l'exécuter, placez les 12 lignes de code suivantes dans 12 fichiers distincts (+11 octets comptés pour chaque fichier au-delà du premier).
<empty>
désigne un fichier vide;\n
désigne une nouvelle ligne littérale. Autrement, conservez le\n
s tel quel, mettez toutes les lignes dans un seul fichier et utilisez l'-s
option. Assurez-vous que tous les fichiers utilisent des nouvelles lignes, pas Windows\r\n
, et notez l'espace à la fin de la dernière ligne.Comment ça fonctionne
Le premier remplacement correspond à la première prémisse de l'entrée, chaque fois que les lhs de la prémisse se produisent plus tard dans le fichier. Il remplace cette occurrence ultérieure par le rhs de la prémisse. Le
+
modificateur garantit que le remplacement est répété jusqu'à ce qu'il ne corresponde plus. Ainsi, si le premier principe estA = B
, tous lesA
s suivants du fichier sont transmutés enB
s.Le deuxième remplacement supprime le premier principe de l'entrée, puisque nous en avons terminé avec cela maintenant. Ensuite, le
)
modificateur revient en boucle au premier remplacement et se répète jusqu'à ce qu'il n'y ait plus de changement dans un passage complet de la boucle. Cela se produit lorsque tous les locaux ont été remplacés et supprimés et que l'entrée commence partherefore
.Le troisième remplacement correspond à la première ligne d'entrée (qui est
therefore
) ou à tout autre élément du formulaireA = A
et le supprime. Si toutes les propositions sont prises en charge par les prémisses, elles correspondront toutes à ce formulaire. Il ne reste donc que les nouvelles lignes. Le quatrième remplacement change cela enright
. Sinon, le cinquième remplacement remplace tout ce qui reste (ce qui ne contient pasr
depuistherefore
sa suppression)wrong
. Enfin, le dernier remplacement ajouteAlex is
au début.la source
Python 2, 264 octets
Il existe déjà une réponse remarquable à Python 3 de mbomb007 . Cette réponse vole de manière flagrante à celle-là (en particulier le truc "Alex est écrit").
Et cette réponse est aussi beaucoup plus longue que celle-là ...
Quoi qu’il en soit, l’idée dans cette réponse est de maintenir un dictionnaire de paires clé-valeur, où les clés sont les 26 caractères majuscules, et la valeur correspondante de chaque clé est l’ensemble des lettres qui sont équivalentes à la clé. (Si les 26 lettres étaient équivalentes, chaque touche aurait alors un ensemble de 26 lettres pour la valeur correspondante.)
(Pour économiser des octets, cette réponse mélange des espaces et des tabulations , ce qui est légal dans Python 2.)
Ce code est vraiment très efficace, car le dictionnaire est limité à une taille maximale possible (26 par 26 comme décrit ci-dessus), qui ne dépend pas du nombre de lignes d'entrée.
Alors que je jouais cette solution, je me suis rendu compte que je pouvais économiser quatre octets en utilisant des chaînes plutôt que des ensembles pour les valeurs du dictionnaire, en remplaçant
avec
Bien entendu, vous devez également remplacer (NOTE: NE LE FAITES PAS) les trois instances de l'opération d'union définie
|
avec la concaténation de chaînes+
, mais cela ne modifie pas la longueur du code. Le résultat est que tout devrait toujours fonctionner de la même manière, sauf que cela n'éliminera pas les doublons comme vous le faites avec des ensembles (cela ne fera que continuer d'ajouter des éléments à la fin de la chaîne). Cela semble correct - un peu moins efficace, bien sûr, mais 260 octets au lieu de 264.Eh bien, il s’avère que la version à 260 octets est tellement inefficace qu’elle a causé un problème
MemoryError
lorsque je l’ai testée avecC'était surprenant pour moi. Examinons la version "concaténation de chaînes" de 260 octets!
Bien sûr, cela commencerait par les paires clé-valeur
A:A
etB:B
(plus 24 autres qui importent peu). Nous écrironsd[A]
pour signifier la valeur du dictionnaire correspondant à la cléA
, donc nous aurions au débutd[A] = A
. Maintenant, étant donné la prémisseA = B
, il faudrait commencer par concaténer les valeursd[A]=A
etd[B]=B
obteniry = AB
. Ensuite, il bouclerait deux fois cette chaîne:for v in AB: for w in AB:
...Donc, la première fois dans la boucle, nous avons
v=A
etw=A
. Applicationd[v] += d[w]
etd[w] += d[v]
résultats dans la séquence de dictionnaires suivante:Ensuite, avec
v=A
etw=B
:Ensuite
v=B, w=A
:Et
v=B, w=B
:La séquence d'étapes ci-dessus implémenterait le principe unique
A = B
, avec la conclusionA
égale à chaque lettre de la chaîneAAAABBAAAABAAAAB
, etB
égale à chaque lettreBAAAABAAAABBAAAABAAAABBAAAABAAAABBAAAABAAAAB
.Maintenant, supposons que la prochaine prémisse soit à
A = B
nouveau . Vous calculez d'abordy = d[A] + d[B] = AAAABBAAAABAAAABBAAAABAAAABBAAAABAAAABBAAAABAAAABBAAAABAAAAB
.Ensuite, vous passez deux fois sur cette chaîne:
for v in y: for w in y:
...Ouais. Ce ne serait peut-être pas une implémentation très efficace.
la source
ES6, 128 octets
Librement inspiré de la version Ruby.
Recherche toute non-égalité devant le "par conséquent" et remplace la variable de manière récurrente tout au long de la chaîne à chaque fois (cela enregistre des octets sur une boucle while).
la source
C, 240 octets
Cela fonctionne en combinant des valeurs dans des arbres définis, donc toutes les valeurs équivalentes mènent à la même racine définie. Ungolfed, avec des types implicites rendus explicites.
180 octets
Cette version plus courte fonctionne pour tous les cas de l'OP, mais pour certaines autres entrées, Alex affirme à tort qu'il a tort. Il utilise une approche similaire, mais pour chaque prémisse, définit simplement la deuxième entrée sur la valeur actuelle de la première entrée. Lors de la comparaison, il ne regarde que les valeurs exactes au lieu de chercher dans un arbre.
Un exemple d'entrée pour lequel cela échoue:
la source
05AB1E , 32 octets
Inspiré par la réponse de CJad de @aditsu .
Essayez-le en ligne ou vérifiez tous les cas de test .
Explication:
Voir ce conseil 05AB1E (section Comment utiliser le dictionnaire? ) Pour comprendre pourquoi
…±º€ˆ
est"alex is "
et„–у©
est"wrong right"
.la source
bash + awk + SWI-Prolog , 167 octets
Essayez-le en ligne!
À l’origine, c’était une réponse de Prolog, mais les outils que j’ai pu trouver pour transformer le format d’entrée en quelque chose d’utilisable étaient suffisamment limités pour que j’ai décidé de le faire par bash, même si je n’avais pratiquement aucune expérience. faire n'importe quoi dans bash, et n'avait même jamais touché awk. J'ai fini par passer suffisamment d'heures dessus pour vouloir l'afficher même après qu'il soit devenu ce monstre de 167 octets, à peine golfé.
Essentiellement, le programme awk prend les entrées de stdin, efface la ligne avec
therefore
, remplace chaqueA = B
après avec?=(A,B)
, et ajoutewrite(\"Alex is right\");write(\"Alex is wrong\"). halt.
. Ensuite,paste -sd ,
remplace chaque virgule par une virgule, la transformant en deux requêtes valides au shell SWI-Prolog, qui sont ensuite exécutées avec le résultat imprimé tronqué à une ligne parhead -n1
, ce qui nécessite<(...)
un canal pour des raisons autres que ma compréhension. Tout cela, juste pour utiliser un Builtin !la source