Esse desafio é elevar o ânimo do nosso mod Alex A. , que geralmente está errado .
Suponha que você tenha um amigo chamado Alex que precise de ajuda com lógica e matemática básicas, especificamente equivalência matemática .
Ele fornece uma lista de equações da forma em [variable] = [variable]
que a [variable]
é sempre uma única letra maiúscula de A a Z (nem uma letra minúscula, nem um número, nem qualquer outra coisa). Há uma equação por linha na lista, exceto por uma única linha que diz apenas therefore
.
Todas as equações acima therefore
são premissas , fatos que são assumidos como verdadeiros. Todas as equações abaixo therefore
são proposições não verificadas, fatos que Alex está tentando inferir a partir das premissas, e podem ou não ser verdadeiras.
Por exemplo, nesta lista de equações, a única proposição conclusiva A = C
é verdadeira:
A = B
B = C
therefore
A = C
É seu trabalho dizer a Alex se todas as suas proposições seguem logicamente a partir das premissas fornecidas. Ou seja, você precisa dizer a Alex se ele está certo ou errado em suas conclusões.
Escreva um programa / função que inclua uma sequência de uma lista de equações conforme descrito e imprima / retorne
Alex is right
se todas as conclusões derivam logicamente das premissas e, de outra forma, produzem
Alex is wrong
se alguma conclusão não resultar logicamente das premissas.
O código mais curto em bytes vence.
Cuidado com esses casos:
Variável sempre se iguala. por exemplo
B = A therefore A = A X = X
resulta em
Alex is right
.Variáveis com relacionamentos desconhecidos não podem ser consideradas iguais. por exemplo
P = Q therefore E = R
resulta em
Alex is wrong
.Quando não há equações após o
therefore
, as conclusões são vacuamente verdadeiras . por exemploD = C therefore
e
therefore
ambos resultam em
Alex is right
.Quando não existem equações antes
therefore
, apenas a auto-igualdade pode ser inferida. por exemplotherefore R = R
resulta em
Alex is right
, mastherefore R = W
resulta em
Alex is wrong
.
Mais exemplos
Alex está com casos errados: (separados por linhas vazias)
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 está certo:
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 os casos de teste.therefore\nTABS < SPACES
->Alex is right
Respostas:
CJam, 49
Inspirado na solução Ruby do histocrat. Experimente online
3 bytes eliminados graças a jimmy23013 :)
Explicação:
Para cada premissa, o programa substitui a primeira variável pela 2ª variável no restante do texto. Em seguida, verifica se há alguma conclusão com variáveis diferentes.
Versão antiga, 85
Isso usa um algoritmo de localização de união. Experimente online
fonte
"Alex is "qN%S{f{)er}(_el-}h;{)#},"wrong""right"?
.Alex is * wrong * right * ?
Ruby,
8076 + 2 = 78Com sinalizadores de linha de comando
p0
, executeExplicação:
Isso usa manipulação pura de strings.
p0
lê a entrada completa como uma única sequência na variável$_
. Em seguida, correspondemos repetidamente essa string à expressão regular/(.) = (?!\1)(.)/
, que encontra todas as strings do formato "X = Y" onde X e Y não são a mesma letra e atribui X a $ 1 e Y a $ 2. Quando essa correspondência é encontrada,gsub$1,$2
substitui todas as instâncias de X por Y na sequência. Também verificamos se essa correspondência ocorreu antes ou depois do "portanto" comSe ocorreu depois, é uma reivindicação injustificada e Alex está errado. Nós rastreamos se alguma dessas ocorrências aconteceu usando
p=
. O uso dep
como variável de rastreamento impede que as coisas quebrem se o loop nunca atingir uma única vez, poisp
retornará nulo se nunca tiver sido atribuído.Até o momento, a solução CJam é mais longa. Um momento orgulhoso, embora sem dúvida fugaz.
Edit: Sim, rapidamente destronado. Além disso, para finalizar a explicação, com o
p
sinalizador o valor final de$_
é emitido no final da execução, portanto a última linha é a saída.fonte
String#format
obter a chamada e a atribuição gsub em uma expressão é uma ideia muito interessante, +1!CJam,
8375686764 bytesAgradecemos a Dennis por economizar 1 byte.
Suíte de teste. Os casos de teste são muito longos para um link permanente, portanto, basta copiá-los da pergunta. Observe que isso é bastante lento - leva um ou dois minutos no intérprete online. Você pode torná-lo muito mais rápido, alterando
5*
para o2*
caso em que ele será concluído quase instantaneamente e resolverá todos, exceto um caso de teste.Explicação
(Um pouco desatualizado.)
A idéia é fazer uma espécie de "preenchimento" de possíveis igualdades e remover todas as igualidades que obtivemos da lista de conclusões. Pode-se mostrar que não precisamos de mais de 5 etapas do preenchimento da inundação, porque elas cobririam uma distância (no gráfico inicial de desigualdades), mas a distância máxima é 25.
25 = 32
fonte
R,
183192 bytesModifiquei minha resposta para resolver uma limitação apontada pelo usuário2357112. Ainda há uma probabilidade extremamente pequena de chamar Alex quando ele está certo (o que por si só não parece acontecer com muita frequência se eu entender o contexto do desafio :-). Espero que ele não se importe.
Eu preciso de-golf isso um pouco:
Por exemplo, se a entrada for
primeiro avaliará
setup
:então o
premises
será executado 1.000 vezes cada uma em uma ordem aleatória. Isso é para garantir ("quase com certeza") que todas as igualidades sejam propagadas. Por fim, avaliará
propositions
:fonte
A = B, B = C, C = A
, os valores circulam para sempre. 26 rodadas de avaliação não são suficientes.Haskell, 208 bytes
Estou transferindo o trabalho para o
Data.Equivalence.Persistent
módulo, que fornece funções para manipular classes de equivalência. Tudo o que resta fazer é analisar as funções de entrada e chamada, que às vezes têm nomes muito longos para o golfe adequado.Exemplo de uso:
fonte
Mathematica, 182
Funciona na entrada de string, conforme o desafio.
fonte
f
como uma função pura, substituindoSimplify[#2,#1]
por#2~Simplify~#
e substituindoStringSplit[s,"\n"]
por#~StringSplit~"<actual newline>"
.q=StringSplit;
, s / StringSplit / q / por mais 6 bytes salvos. Mas no final, esse não é um bom desafio para o Mathematica, embora o personagem lógico pareça perfeito.a___
eb___
provavelmente pode ser alterado paraa__
eb__
, es=Symbol;
.a__
eb__
não vai funcionar se instalações, proposições ou ambos estão vazios emboraRetina, 90 bytes
Para executar, coloque as 12 linhas de código a seguir em 12 arquivos separados (+11 bytes contados para cada arquivo além do primeiro).
<empty>
designa um arquivo vazio;\n
designa uma nova linha literal. Como alternativa, mantenha os\n
como estão, coloque todas as linhas em um único arquivo e use a-s
opção Verifique se todos os arquivos usam novas linhas literais, não o Windows\r\n
, e anote o espaço no final da última linha.Como funciona
A primeira substituição corresponde à primeira premissa na entrada, sempre que o lhs da premissa ocorrer posteriormente no arquivo. Ele substitui essa ocorrência posterior pelos rhs da premissa. O
+
modificador garante que a substituição seja repetida até que não corresponda mais. Assim, se a primeira premissa forA = B
, todos osA
s subsequentes no arquivo serão transmutados emB
s.A segunda substituição remove a primeira premissa da entrada, já que a terminamos agora. Em seguida, o
)
modificador volta para a primeira substituição e se repete até que não houve alterações em uma passagem completa do loop. Isso acontece quando todas as instalações foram substituídas e removidas e a entrada começa comtherefore
.A terceira substituição corresponde à primeira linha de entrada (que é
therefore
) ou qualquer coisa do formulárioA = A
e a exclui. Se todas as proposições forem suportadas pelas premissas, todas elas corresponderão a esse formulário; portanto, o que resta deve consistir apenas em novas linhas. A quarta substituição muda isso pararight
. Caso contrário, a quinta substituição altera tudo o que resta (que não contémr
desde quetherefore
foi excluído)wrong
. Finalmente, a última substituição é adicionadaAlex is
no início.fonte
Python 2, 264 bytes
Já existe uma resposta notável do Python 3 por mbomb007 . Essa resposta rouba flagrantemente aquela (em particular o truque "Alex is wrriognhgt").
E essa resposta também é significativamente mais longa do que aquela ...
Bem, de qualquer forma, a idéia nesta resposta é manter um dicionário de pares de valores-chave, onde as chaves são os 26 caracteres maiúsculos e o valor correspondente de cada chave é o conjunto de letras que são equivalentes à chave. (Se todas as 26 letras fossem equivalentes, cada chave teria um conjunto de 26 letras para o seu valor correspondente.)
(Para salvar bytes, esta resposta combina espaços e tabulações , o que é legal no Python 2.)
Esse código é realmente bastante eficiente, porque o dicionário é limitado ao tamanho máximo possível (26 por 26, conforme descrito acima), que não depende do número de linhas de entrada.
Agora, enquanto jogava essa solução, percebi que podia salvar quatro bytes usando cadeias de caracteres em vez de conjuntos para os valores do dicionário, substituindo
com
Obviamente, você também precisará substituir (OBSERVAÇÃO: NÃO FAÇA ISSO) as três instâncias da operação de união de conjuntos
|
com concatenação de cadeias+
, mas isso não altera o tamanho do código. O resultado é que tudo ainda deve funcionar da mesma forma, exceto que não eliminará duplicatas como você faz com os conjuntos (continuará adicionando no final da string). Parece OK - um pouco menos eficiente, com certeza, mas 260 bytes em vez de 264.Bem, acontece que a versão de 260 bytes é tão ineficiente que causou um
MemoryError
quando eu a testei comIsso foi surpreendente para mim. Vamos investigar a versão de "concatenação de string" de 260 bytes!
É claro que começaria com os pares de valores-chave
A:A
eB:B
(mais 24 outros que não importam). Escreveremosd[A]
para significar o valor do dicionário correspondente à chaveA
, portanto, no começo, teríamosd[A] = A
. Agora, dada a premissaA = B
, começaria concatenando os valoresd[A]=A
ed[B]=B
obtendoy = AB
. Em seguida, passaria duas vezes por essa sequência:for v in AB: for w in AB:
...Então, pela primeira vez no loop, temos
v=A
ew=A
. Aplicaçãod[v] += d[w]
ed[w] += d[v]
resultados na seguinte sequência de dicionários:Em seguida, com
v=A
ew=B
:Em seguida
v=B, w=A
:E
v=B, w=B
:A sequência de etapas acima implementaria a única premissa
A = B
, com a conclusão de queA
é igual a todas as letras da stringAAAABBAAAABAAAAB
, enquantoB
é igual a todas as letras deBAAAABAAAABBAAAABAAAABBAAAABAAAABBAAAABAAAAB
.Agora, suponha que a próxima premissa seja
A = B
novamente . Você calcula primeiroy = d[A] + d[B] = AAAABBAAAABAAAABBAAAABAAAABBAAAABAAAABBAAAABAAAABBAAAABAAAAB
.Em seguida, você faz um loop sobre essa sequência duas vezes:
for v in y: for w in y:
...Sim. Talvez isso não seja uma implementação muito eficiente.
fonte
ES6, 128 bytes
Vagamente baseado na versão Ruby.
Procura qualquer não-auto-igualdade antes do "portanto" e recurtavelmente substitui a variável por toda a cadeia de caracteres a cada vez (isso salva bytes em um loop while).
fonte
C, 240 bytes
Isso funciona combinando valores em árvores definidas, para que quaisquer valores equivalentes levem à mesma raiz definida. Ungolfed, com tipos implícitos explicitados.
180 bytes
Esta versão mais curta funciona para todos os casos do OP, mas para algumas outras entradas afirma incorretamente que Alex está errado. Ele usa uma abordagem semelhante, mas para cada premissa simplesmente define a segunda entrada para o valor atual da primeira entrada. Ao comparar, ele analisa apenas os valores exatos em vez de pesquisar uma árvore.
Um exemplo de entrada para o qual isso falha:
fonte
05AB1E , 32 bytes
Inspirado por @aditsu resposta CJam 's .
Experimente online ou verifique todos os casos de teste .
Explicação:
Veja esta dica 05AB1E (seção Como usar o dicionário? ) Para entender por que
…±º€ˆ
é"alex is "
e„–у©
é"wrong right"
.fonte
bash + awk + SWI-Prolog , 167 bytes
Experimente online!
Originalmente, essa seria apenas uma resposta do Prolog, mas as ferramentas que eu pude encontrar para transformar o formato de entrada em algo utilizável eram limitadas o suficiente para que eu decidisse fazer essa parte dele no bash, mesmo que eu tivesse quase nenhuma experiência fazendo qualquer coisa no bash, e nunca tinha tocado awk. Acabei gastando horas suficientes nele para querer publicá-lo, mesmo depois que ele se transformou em um monstro de 167 bytes, que mal jogava golfe.
Essencialmente, o que o programa awk faz é pegar a entrada do stdin, apagar a linha com
therefore
, substituir todas asA = B
depois por?=(A,B)
e anexarwrite(\"Alex is right\");write(\"Alex is wrong\"). halt.
. Em seguida,paste -sd ,
substitui cada nova linha, exceto a última, por vírgula, transformando-a em duas consultas válidas para o shell SWI-Prolog, que são executadas com o resultado impresso sendo truncado em uma linha porhead -n1
, o que requer, em<(...)
vez de um canal, por outras razões. meu entendimento. Tudo isso, apenas para usar um builtin !fonte