Este desafío es levantar el espíritu de nuestro mod Alex A. , que generalmente se equivoca .
Supongamos que tiene un amigo llamado Alex que necesita ayuda con la lógica básica y las matemáticas, específicamente la equivalencia matemática .
Te da una lista de ecuaciones de la forma [variable] = [variable]
en la que a [variable]
siempre es una letra mayúscula de la A a la Z (no una letra minúscula, ni un número, ni ninguna otra cosa). Hay una ecuación por línea en la lista, excepto por una sola línea que solo dice therefore
.
Todas las ecuaciones anteriores therefore
son premisas , hechos que se suponen verdaderos. Todas las ecuaciones a continuación therefore
son proposiciones no verificadas, hechos que Alex intenta inferir de las premisas, y pueden o no ser ciertas.
Por ejemplo, en esta lista de ecuaciones, la proposición concluyente única A = C
es verdadera:
A = B
B = C
therefore
A = C
Es su trabajo decirle a Alex si todas sus proposiciones se siguen lógicamente de las premisas dadas. Es decir, debe decirle a Alex si está equivocado o correcto en sus conclusiones.
Escriba un programa / función que tome una cadena de una lista de ecuaciones como se describe e imprime / devuelve
Alex is right
si todas las conclusiones se siguen lógicamente de las premisas y, de lo contrario, salen
Alex is wrong
si alguna conclusión no se deduce lógicamente de las premisas.
El código más corto en bytes gana.
Asegúrese de estar atento a estos casos:
La variable siempre se iguala a sí misma. p.ej
B = A therefore A = A X = X
resultados en
Alex is right
.No se puede suponer que las variables con relaciones desconocidas sean iguales. p.ej
P = Q therefore E = R
resultados en
Alex is wrong
.Cuando no hay ecuaciones después de
therefore
entonces, las conclusiones son vacías . p.ejD = C therefore
y
therefore
ambos resultan en
Alex is right
.Cuando no hay ecuaciones antes,
therefore
entonces solo se puede inferir la auto-igualdad. p.ejtherefore R = R
resulta en
Alex is right
, perotherefore R = W
resultados en
Alex is wrong
.
Más ejemplos
Alex tiene casos incorrectos: (separados por líneas vacías)
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 tiene razón casos:
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
Verifica todos los casos de prueba.therefore\nTABS < SPACES
->Alex is right
Respuestas:
CJam, 49
Inspirado en la solución Ruby de histocrat. Pruébelo en línea
3 bytes borrados gracias a jimmy23013 :)
Explicación:
Para cada premisa, el programa reemplaza la primera variable con la segunda variable en el resto del texto. Luego verifica si hay alguna conclusión con diferentes variables.
Versión anterior, 85
Esto utiliza un algoritmo de búsqueda de unión. Pruébalo en línea
fuente
"Alex is "qN%S{f{)er}(_el-}h;{)#},"wrong""right"?
.Alex is * wrong * right * ?
Rubí,
8076 + 2 = 78Con banderas de línea de comandos
p0
, ejecuteExplicación:
Esto utiliza la manipulación de cadenas pura.
p0
lee la entrada completa como una sola cadena en la variable$_
. Luego, repetidamente hacemos coincidir esa cadena con la expresión regular/(.) = (?!\1)(.)/
, que encuentra todas las cadenas de la forma "X = Y" donde X e Y no son la misma letra, y asigna X a $ 1 e Y a $ 2. Cuando se encuentra dicha coincidencia,gsub$1,$2
reemplaza todas las instancias de X con Y en la cadena. También verificamos si esta coincidencia ocurrió antes o después del "por lo tanto" conSi ocurrió después, es un reclamo injustificado y Alex está equivocado. Realizamos un seguimiento de si se han producido dichos sucesos utilizando
p=
. El uso dep
como una variable de seguimiento evita que las cosas se rompan si el bucle nunca golpea ni siquiera una vez, yap
que volverá nulo si nunca se le asignó.A partir de esta publicación, la solución CJam es más larga. Un momento orgulloso, sin duda fugaz.
Editar: Sí, rápidamente destronado. Además, para finalizar la explicación, con el
p
indicador, el valor final de$_
se emite al final de la ejecución, por lo que la última línea es la salida.fuente
String#format
obtener tanto la llamada gsub como la asignación en una sola expresión es una idea bastante clara, ¡+1!CJam,
8375686764 bytesGracias a Dennis por guardar 1 byte.
Banco de pruebas. Los casos de prueba son demasiado largos para un enlace permanente, así que simplemente cópielos de la pregunta. Tenga en cuenta que esto es bastante lento: lleva un minuto o dos en el intérprete en línea. Puede que sea mucho más rápido cambiando
5*
a2*
en cuyo caso se terminará casi al instante y resolver todos menos un caso de prueba.Explicación
(Ligeramente anticuado)
La idea es hacer una especie de "relleno de inundación" de posibles igualdades y luego eliminar todas las igualdades que obtuvimos de la lista de conclusiones. Se puede demostrar que no necesitamos más de 5 pasos del relleno de inundación, porque cubrirían una distancia (en el gráfico inicial de desigualdades) de pero la distancia máxima es 25.
25 = 32
fuente
R,
183192 bytesHe modificado mi respuesta para abordar una limitación señalada por el usuario2357112. Todavía hay una probabilidad extremadamente pequeña de llamar a Alex cuando en realidad tiene razón (lo que en sí mismo no parece suceder muy a menudo si entiendo el contexto del desafío :-). Espero que no le importe.
Necesito desempacar esto un poco:
Por ejemplo, si la entrada es
Primero evaluará
setup
:entonces la
premises
se ejecutará 1,000 veces cada uno en un orden aleatorio. Esto es para asegurarse ("casi seguro") de que todas las igualdades se propagan. Finalmente, evaluará
propositions
:fuente
A = B, B = C, C = A
, los valores simplemente cambian para siempre. 26 rondas de evaluación no son suficientes.Haskell, 208 bytes
Estoy descargando el trabajo al
Data.Equivalence.Persistent
módulo, que proporciona funciones para manipular clases de equivalencia. Todo lo que queda por hacer es analizar la entrada y las funciones de llamada que a veces tienen nombres demasiado largos para el golf adecuado.Ejemplo de uso:
fuente
Mathematica, 182
Funciona en la entrada de cadena, según el desafío.
fuente
f
como una función pura, reemplazandoSimplify[#2,#1]
con#2~Simplify~#
y reemplazandoStringSplit[s,"\n"]
con#~StringSplit~"<actual newline>"
.q=StringSplit;
y luego s / StringSplit / q / para otros 6 bytes más o menos guardados. Pero al final, este no es un buen desafío para Mathematica, me temo, a pesar de que el personaje lógico parecía encajar perfectamente.a___
yb___
probablemente se puede cambiar aa__
yb__
, ys=Symbol;
.a__
yb__
no funcionará si los locales, proposiciones o ambos están vacías aunqueRetina, 90 bytes
Para ejecutar, coloque las siguientes 12 líneas de código en 12 archivos separados (+11 bytes contados para cada archivo más allá del primero).
<empty>
designa un archivo vacío;\n
designa una nueva línea literal. Alternativamente, mantenga las\n
s como están, coloque todas las líneas en un solo archivo y use la-s
opción. Asegúrese de que todos los archivos usen nuevas líneas literales, no Windows\r\n
, y tenga en cuenta el espacio al final de la última línea.Cómo funciona
El primer reemplazo coincide con la primera premisa en la entrada, siempre que el lhs de la premisa ocurra más adelante en el archivo. Reemplaza esa ocurrencia posterior con la derecha de la premisa. El
+
modificador asegura que el reemplazo se repita hasta que ya no coincida. Por lo tanto, si la primera premisa esA = B
, todos losA
s posteriores en el archivo se transmutan enB
s.El segundo reemplazo elimina la primera premisa de la entrada, ya que hemos terminado con ella ahora. Luego, el
)
modificador regresa al primer reemplazo y se repite hasta que no haya cambios en un pase completo a través del ciclo. Esto sucede cuando todas las premisas han sido sustituidas y eliminadas, y la entrada comienza contherefore
.El tercer reemplazo coincide con la primera línea de entrada (que es
therefore
) o cualquier cosa del formularioA = A
, y lo elimina. Si todas las proposiciones son compatibles con las premisas, todas coincidirán con este formulario, por lo que lo que quede debe consistir únicamente en nuevas líneas. El cuarto reemplazo cambia esto aright
. De lo contrario, el quinto reemplazo cambia todo lo que queda (que no contiener
desde quetherefore
se eliminó)wrong
. Finalmente, el último reemplazo se agregaAlex is
al principio.fuente
Python 2, 264 bytes
Ya hay una notable respuesta de Python 3 por mbomb007 . Esta respuesta le roba flagrantemente a esa (en particular, el truco "Alex está escribiendo").
Y esta respuesta también es significativamente más larga que esa ...
Bueno, de todos modos, la idea en esta respuesta es mantener un diccionario de pares clave-valor, donde las claves son los 26 caracteres en mayúscula, y el valor correspondiente de cada clave es el conjunto de letras que son equivalentes a la clave. (Si las 26 letras fueran equivalentes, entonces cada tecla tendría un conjunto de 26 letras para su valor correspondiente).
(Para guardar bytes, esta respuesta mezcla espacios y pestañas , lo cual es legal en Python 2.)
Este código es realmente bastante eficiente, porque el diccionario está limitado a un tamaño máximo posible (26 por 26 como se describe anteriormente) que no depende del número de líneas de entrada.
Ahora, mientras jugaba esta solución, me di cuenta de que podía ahorrar cuatro bytes usando cadenas en lugar de conjuntos para los valores del diccionario, reemplazando
con
Por supuesto, también debe reemplazar (NOTA: NO HAGA ESTO) las tres instancias de la operación de unión de conjunto
|
con concatenación de cadenas+
, pero eso no cambia la longitud del código. El resultado es que todo debería funcionar igual, excepto que no eliminará duplicados como lo hace con los conjuntos (simplemente seguirá agregando al final de la cadena). Suena bien, un poco menos eficiente, claro, pero 260 bytes en lugar de 264.Bueno, resulta que la versión de 260 bytes es tan ineficiente que causó un
MemoryError
cuando la probé conEsto fue sorprendente para mí. ¡Investiguemos la versión de "concatenación de cadenas" de 260 bytes!
Por supuesto, comenzaría con los pares clave-valor
A:A
yB:B
(más otros 24 que no importan). Escribiremosd[A]
para significar el valor del diccionario correspondiente a la claveA
, por lo que al principio tendríamosd[A] = A
. Ahora, dada la premisaA = B
, comenzaría por concatenar los valoresd[A]=A
yd[B]=B
obtenery = AB
. Luego, pasaría por esta cadena dos veces:for v in AB: for w in AB:
...Entonces, la primera vez a través del ciclo, tenemos
v=A
yw=A
. Aplicaciónd[v] += d[w]
yd[w] += d[v]
resultados en la siguiente secuencia de diccionarios:A continuación, con
v=A
yw=B
:A continuación
v=B, w=A
:Y
v=B, w=B
:La secuencia de pasos anterior implementaría la premisa única
A = B
, con la conclusión de queA
es igual a cada letra en la cadenaAAAABBAAAABAAAAB
, mientras queB
es igual a cada letra enBAAAABAAAABBAAAABAAAABBAAAABAAAABBAAAABAAAAB
.Ahora, supongamos que la próxima premisa es
A = B
nuevamente . Primero calculasy = d[A] + d[B] = AAAABBAAAABAAAABBAAAABAAAABBAAAABAAAABBAAAABAAAABBAAAABAAAAB
.Luego, repite esta cadena dos veces:
for v in y: for w in y:
...Sí. Tal vez esa no sería una implementación muy eficiente.
fuente
ES6, 128 bytes
Basada en la versión Ruby.
Busca cualquier no auto-igualdad antes del "por lo tanto" y reemplaza repetidamente la variable a lo largo de la cadena cada vez (esto ahorra bytes en un ciclo while).
fuente
C, 240 bytes
Esto funciona combinando valores en árboles de conjunto, por lo que cualquier valor equivalente conduce a la misma raíz de conjunto. Sin golf, con tipos implícitos hechos explícitos.
180 bytes
Esta versión más corta funciona para todos los casos desde el OP, pero para algunas otras entradas afirma incorrectamente que Alex está equivocado. Utiliza un enfoque similar, pero para cada premisa simplemente establece la segunda entrada al valor actual de la primera entrada. Al comparar, solo busca valores exactos en lugar de buscar un árbol.
Un ejemplo de entrada para el que esto falla:
fuente
05AB1E , 32 bytes
Inspirado por @aditsu respuesta Cjam 's .
Pruébelo en línea o verifique todos los casos de prueba .
Explicación:
Vea esta sugerencia mía 05AB1E (sección ¿Cómo usar el diccionario? ) Para comprender por qué
…±º€ˆ
es"alex is "
y„–у©
es"wrong right"
.fuente
bash + awk + SWI-Prolog , 167 bytes
Pruébalo en línea!
Originalmente, esto solo iba a ser una respuesta de Prolog, pero las herramientas que pude encontrar para transformar realmente el formato de entrada en algo utilizable fueron lo suficientemente limitadas que decidí hacer esa parte en bash, a pesar de que casi no tenía experiencia haciendo cualquier cosa en bash, y nunca había tocado awk. Terminé pasando suficientes horas en él para querer publicarlo incluso después de que se convirtió en este 167 bytes, apenas golfizado en absoluto.
Esencialmente, lo que hace el programa awk es tomar la entrada de stdin, borrar la línea con
therefore
, reemplazar cadaA = B
después con?=(A,B)
y agregarwrite(\"Alex is right\");write(\"Alex is wrong\"). halt.
. Luego,paste -sd ,
reemplaza cada línea nueva pero la última con una coma, transformándola en dos consultas válidas para el shell SWI-Prolog, que luego se ejecutan con el resultado impreso truncado en una líneahead -n1
, lo que requiere en<(...)
lugar de una tubería por razones más allá mi punto de vista. Todo esto, solo para usar un incorporado !fuente