Introdução: Lógica Combinatória
A lógica combinatória (CL) é baseada em coisas chamadas combinadores , que são basicamente funções. Existem dois combinadores "internos" básicos Se K, que serão explicados mais adiante.
Associatividade esquerda
CL é associativo à esquerda , o que significa que colchetes (que contêm material) que estão na extremidade esquerda do par de parêntesis que o contêm podem ser removidos, com o material liberado. Por exemplo, algo como isto:
((a b) c)
Pode ser reduzido para
(a b c)
Onde (a b)está na extremidade esquerda do suporte maior ((a b) c), para que possa ser removido.
Um exemplo muito maior de associação à esquerda (colchetes são explicações):
((a b) c ((d e) f (((g h) i) j)))
= (a b c ((d e) f (((g h) i) j))) [((a b) c...) = (a b c...)]
= (a b c (d e f (((g h) i) j))) [((d e) f...) = (d e f...)]
= (a b c (d e f ((g h i) j))) [((g h) i) = (g h i)]
= (a b c (d e f (g h i j))) [((g h i) j) = (g h i j)]
Os colchetes também podem ser reduzidos quando mais de um par envolve os mesmos objetos. Exemplos:
((((a)))) -> a
a ((((b)))) -> a b
a (((b c))) -> a (b c) [(b c) is still a group, and therefore need brackets.
Note that this doesn't reduce to `a b c`, because
`(b c)` is not on the left.]
Builtins
O CL possui dois combinadores "internos" Se K, que podem alternar objetos (combinadores únicos ou um grupo de combinadores / grupos entre colchetes) entre os seguintes:
K x y = x
S x y z = x z (y z)
Onde x, ye zpode ser stand-ins para qualquer coisa.
Um exemplo de Se Ksão os seguintes:
(S K K) x [x is a stand-in for anything]
= S K K x [left-associativity]
= K x (K x) [S combinator]
= x [K combinator]
Outro exemplo:
S a b c d
= a c (b c) d [combinators only work on the n objects to the right of it,
where n is the number of "arguments" n is defined to have -
S takes 3 arguments, so it only works on 3 terms]
Os exemplos acima são exemplos de instruções CL normais, nas quais a instrução não pode ser avaliada mais e alcança um resultado final em um período finito de tempo. Existem instruções não normais (que são declarações de CL que não terminam e continuarão sendo avaliadas para sempre), mas não estão no escopo do desafio e não precisam ser cobertas.
Se você quiser saber mais sobre CL, leia esta página da Wikipedia .
Tarefa:
Sua tarefa é criar combinadores extras, dado o número de argumentos e o que ele avalia como entrada, que é dada assim:
{amount_of_args} = {evaluated}
Onde {amount_of_args}é um número inteiro positivo igual ao número de args e {evaluated}consiste em:
- argumentos até a quantidade de argumentos,
1sendo o primeiro argumento,2o segundo, etc.- Você tem certeza de que os números dos argumentos acima da quantidade de args (portanto, somente
4quando ) não aparecerão .{amount_of_args}3{evaluated}
- Você tem certeza de que os números dos argumentos acima da quantidade de args (portanto, somente
- colchetes
()
Portanto, exemplos de entradas são:
3 = 2 3 1
4 = 1 (2 (3 4))
A primeira entrada está solicitando um combinador (digamos R) com três argumentos ( R 1 2 3), que é avaliado em:
R 1 2 3 -> 2 3 1
A segunda entrada solicita isso (com um nome combinador A):
A 1 2 3 4 -> 1 (2 (3 4))
Dada a entrada nesse formato, você deve retornar uma sequência de S, Ke ()que, quando substituída por um nome de combinador e executada com argumentos, retorna a mesma instrução avaliada que o {evaluated}bloco quando o bloco de comando é substituído novamente por esse nome de combinador.
A declaração do combinador de saída pode ter seu espaço em branco removido e os colchetes externos removidos, para que algo como (S K K (S S))possa ser transformado SKK(SS).
Se você quiser testar as saídas do seu programa, @aditsu fez um analisador lógica combinatória (que inclui S, K, Ie até mesmo outras gosto Be C) aqui .
Ponto:
Como esse é um metagolfo , o objetivo desse desafio é atingir a menor quantidade de bytes possível na saída, considerando esses 50 casos de teste . Coloque os resultados para os 50 casos de teste na resposta ou faça uma pastebin (ou algo semelhante) e poste um link para essa pastebin.
Em caso de empate, a solução mais antiga vence.
Regras:
- Sua resposta deve retornar a saída CORRETA - portanto, dada uma entrada, ela deve retornar a saída correta conforme a definição na tarefa.
- Sua resposta deve ser exibida dentro de uma hora em um laptop moderno para cada caso de teste.
- Qualquer codificação de soluções não é permitida. No entanto, você pode codificar até 10 combinadores.
- Seu programa deve retornar sempre a mesma solução para a mesma entrada.
- Seu programa deve retornar um resultado válido para qualquer entrada fornecida, não apenas para casos de teste.
fonte
1, você pode subtrair1tudo e, em seguida, agrupar a solução para essa respostaK(). Exemplo: Solução para2 -> 1éK, por conseguinte, para a solução3 -> 2éKK, solução para4 -> 3éK(KK)etcRespostas:
Haskell , pontuação 5017
Isso combina o algoritmo mais estúpido possível para a eliminação da abstração ((λ x . X ) = I; (λ x . Y ) = K y ; (λ x . M N ) = S (λ x . M ) (λ x . N ) ) com um otimizador de olho mágico usado após cada aplicação. A regra de otimização mais importante é S (K x ) (K y ) ↦ K ( xy ), que impede o algoritmo de explodir sempre exponencialmente.
O conjunto de regras é configurado como uma lista de pares de cordas, para que seja fácil brincar com novas regras. Como um bônus especial de reutilizar o analisador de entrada para esse fim, S, K e I também são aceitos nos combinadores de entrada.
Regras não são aplicadas incondicionalmente; em vez disso, as versões antiga e nova são mantidas, e as versões sub-ótimas são removidas apenas quando o comprimento excede o da melhor versão em mais do que uma constante (atualmente 3 bytes).
A pontuação é ligeiramente melhorada tratando I como um combinador fundamental até que o estágio de saída a reescreva para SKK. Dessa forma, KI = K (SKK) pode ser reduzido em 4 bytes para SK na saída sem confundir o restante das otimizações.
Experimente online!
Resultado
fonte
S (K x) (K y) = K (x y))?ruleStrings. Se não o fizéssemos, a saída seria exponencialmente maior: neste pequeno exemplo, teríamos obtido S (S (KS) (S (S (KS) (S (KK) (KS))) (S (S (KS) (S (KK) (KK))) (S (KK) (SKK))))) (S (S (KS) (S (S (KS) (S (KK) (KS))) ( S (S (KS) (S (KK) (KK))) (SK)))) (S (KK) (SK))) em vez de S (KS) K.Soma dos comprimentos da solução:
12945 85085872Código Haskell que recebe linhas de entrada do stdin e não se importa se o separador é
=ou->:Ele implementa a abstração de colchete aprimorada da seção 3.2 de John Tromp: Cálculo binário lambda e lógica combinatória, que está vinculada ao artigo da Wikipedia sobre lógica combinatória. Os casos especiais mais úteis usam apenas o
Scombinador para sufocar subtermos, a fim de evitar o agrupamento profundo de variáveis. O caso que verifica a igualdade de alguns subtermos não é necessário para nenhum dos casos de teste. Embora não haja um caso especial para lidar com oWcombinador (consulte a resposta de Peter), as regras trabalham juntas para encontrar aSS(SK)expressão mais curta . (Cometi um erro ao tentar otimizar as chamadas internas paraabstract, então essaWotimização não aconteceu e o resultado geral foi 16 bytes mais longo.)E aqui estão os resultados dos casos de teste:
fonte
8486 usando S, K, I, W
Explicação
O algoritmo de padrão (por exemplo, como descrito no capítulo 18 de Para Mock um Mockingbird ) utiliza quatro casos, correspondente aos combinadores
S,K,I = SKK, e deixou-simples associação. Eu acho que é isso que a resposta de Christian implementa. Isso é suficiente, mas não necessariamente ideal, e como podemos codificar até 10 combinadores, deixa 7 opções.Outros combinadores combinatórios bem conhecidos são
que, juntamente com
K, formam uma base completa . No SK, esses sãoe as
SKIregras derivam essas mesmas expressões paraBeC, mas paraWelas derivamS S (K (S K K)). Por isso, decidi implementarWcomo um caso especial.Programa (CJam)
Conjunto de testes online
Saídas geradas:
fonte