Uma frase da teoria dos números (para nossos propósitos) é uma sequência dos seguintes símbolos:
0
e'
(sucessor) - sucessor significa+1
, então0'''' = 0 + 1 + 1 + 1 + 1 = 4
+
(adição) e*
(multiplicação)=
(igual a)(
e)
(parênteses)- o operador lógico
nand
(a nand b
énot (a and b)
) forall
(o quantificador universal)v0
,v1
,v2
, Etc. (variáveis)Aqui está um exemplo de uma frase:
forall v1 (forall v2 (forall v3 (not (v1*v1*v1 + v2*v2*v2 = v3*v3*v3))))
Aqui not x
está uma abreviação de x nand x
- a frase real usaria (v1*v1*v1 + v2*v2*v2 = v3*v3*v3) nand (v1*v1*v1 + v2*v2*v2 = v3*v3*v3)
, porque x nand x = not (x and x) = not x
.
Isto indica que para cada combinação de três números naturais v1
, v2
e v3
, não é o caso que v1 3 + v2 3 = v3 3 (o que seria verdade, porque de último teorema de Fermat, exceto pelo fato de que ele iria ficar 0 ^ 3 + 0 ^ 3 = 0 ^ 3).
Infelizmente, como provado por Gödel, não é possível determinar se uma sentença na teoria dos números é verdadeira ou não.
Ele é possível, no entanto, se restringir o conjunto dos números naturais para um conjunto finito.
Portanto, esse desafio é determinar se uma sentença da teoria dos números é verdadeira ou não, quando usada no módulo n
, para um número inteiro positivo n
. Por exemplo, a frase
forall v0 (v0 * v0 * v0 = v0)
(a declaração de que, para todos os números x, x 3 = x)
Não é verdadeiro para aritmética comum (por exemplo, 2 3 = 8 ≠ 2), mas é verdadeiro quando usado no módulo 3:
0 * 0 * 0 ≡ 0 (mod 3)
1 * 1 * 1 ≡ 1 (mod 3)
2 * 2 * 2 ≡ 8 ≡ 2 (mod 3)
Formato de entrada e saída
A entrada é uma sentença e um número inteiro positivo n
em qualquer formato "razoável". Aqui estão alguns exemplos de formatos razoáveis para a frase forall v0 (v0 * v0 * v0 = v0)
no módulo de teoria dos números 3:
("forall v0 (v0 * v0 * v0 = v0)", 3)
"3:forall v0 (((v0 * v0) * v0) = v0)"
"(forall v0)(((v0 * v0) * v0) = v0) mod 3"
[3, "forall", "v0", "(", "(", "(", "v0", "*", "v0", ")", "*", "v0", ")", "=", "v0", ")"]
(3, [8, 9, 5, 5, 5, 9, 3, 9, 6, 3, 9, 6, 4, 9, 6]) (the sentence above, but with each symbol replaced with a unique number)
"f v0 = * * v0 v0 v0 v0"
[3, ["forall", "v0", ["=", ["*", "v0", ["*", "v0", "v0"]], "v0"]]]
"3.v0((v0 * (v0 * v0)) = v0)"
A entrada pode ser de stdin, um argumento de linha de comando, um arquivo etc.
O programa pode ter duas saídas distintas para saber se a sentença é verdadeira ou não, por exemplo, pode gerar yes
se for verdadeira e no
se não for.
Você não precisa suportar uma variável que é objeto de forall
duas vezes, por exemplo (forall v0 (v0 = 0)) nand (forall v0 (v0 = 0))
. Você pode assumir que sua entrada possui sintaxe válida.
Casos de teste
forall v0 (v0 * v0 * v0 = v0) mod 3
true
forall v0 (v0 * v0 * v0 = v0) mod 4
false (2 * 2 * 2 = 8 ≡ 0 mod 4)
forall v0 (v0 = 0) mod 1
true (all numbers are 0 modulo 1)
0 = 0 mod 8
true
0''' = 0 mod 3
true
0''' = 0 mod 4
false
forall v0 (v0' = v0') mod 1428374
true
forall v0 (v0 = 0) nand forall v1 (v1 = 0) mod 2
true (this is False nand False, which is true)
forall v0 ((v0 = 0 nand v0 = 0) nand ((forall v1 (v0 * v1 = 0' nand v0 * v1 = 0') nand forall v2 (v0 * v2 = 0' nand v0 * v2 = 0')) nand (forall v3 (v0 * v3 = 0' nand v0 * v3 = 0') nand forall v4 (v0 * v4 = 0' nand v0 * v4 = 0')))) mod 7
true
(equivalent to "forall v0 (v0 =/= 0 implies exists v1 (v0 * v1 = 0)), which states that every number has a multiplicative inverse modulo n, which is only true if n is 1 or prime)
forall v0 ((v0 = 0 nand v0 = 0) nand ((forall v1 (v0 * v1 = 0' nand v0 * v1 = 0') nand forall v2 (v0 * v2 = 0' nand v0 * v2 = 0')) nand (forall v3 (v0 * v3 = 0' nand v0 * v3 = 0') nand forall v4 (v0 * v4 = 0' nand v0 * v4 = 0')))) mod 4
false
Isso é código-golfe , então tente tornar o seu programa o mais curto possível!
fonte
v number
?var number
, ou mesmo apenas1 + number
(assim1
seriav0
,2
seriav1
, etc.)'v number
vez dev number'
escolhermos a opção prefixo-sintaxe?Respostas:
Python 2 ,
252236 bytesExperimente online!
Recebe a entrada como prefixo-sintaxe aninhada, com em
f
vez deforall
e emn
vez denand
:fonte
print(eval(g(*input())))
.APL (Dyalog Unicode) , 129 bytes SBCS
Experimente online!
Toma uma árvore de sintaxe de prefixo, como na resposta python do TFeld , mas usando uma codificação inteira. A codificação é
e a cada variável é atribuído um número a partir de 8. Essa codificação é um pouco diferente da usada na versão sem golf abaixo, porque eu a aprimorei enquanto jogava o código.
A tarefa envolve apenas duas entradas (o AST e o módulo), mas escrevê-lo como um operador em vez de uma função evita mencionar o módulo muitas vezes (como sempre é realizado em chamadas recursivas).
Ungolfed com comentários
Experimente online!
fonte