Subprogramas Brainf *** com saídas únicas

19

Você deve escrever um programa BF (brainfuck de 100 bytes).

Um caractere removerá dele de todas as formas possíveis os 100 novos programas resultantes (99 bytes de comprimento). Por exemplo, para o programa ++.>.os 5 subprogramas são +.>., +.>., ++>., ++..e ++.>.

Sua pontuação será o número de saídas exclusivas que os 100 programas geram. Maior pontuação é melhor.

Detalhes

  • Seus programas serão encerrados após a saída do primeiro caractere.
  • Programas inválidos ou não termináveis ​​e programas que geram saídas vazias não são contabilizados para a pontuação.
  • As células BF são de 8 bits. (255 + 1 = 0, 0-1 = 255)
  • Seu programa não recebe nenhuma entrada. Se você usar ,o código, ele definirá a célula atual para 0.
  • Não há células no lado esquerdo da posição inicial. Por exemplo, <.é inválido, mas .<é válido, pois a execução é encerrada em .. A fita não tem limites na outra direção.
  • Programas com colchetes não balanceados ( [e ]) são inválidos.
  • Seu programa original pode ter menos de 100 bytes, pois é fácil estendê-lo para 100 bytes sem alterar a pontuação.
  • Seu programa original não precisa ser um código BF válido.

Você pode usar este programa python3 (link ideone) para determinar a pontuação da sua resposta. (Para programas de longa execução, pode ser necessário modificar a maxstepvariável.)

Exemplo

(Para simplificar, este programa tem menos de 100 bytes.)

Solution: ++,+[-]+><.-,-.

Score: 3

Explanation:

Subprogram     => Output

+,+[-]+><.-,-. => 1
+,+[-]+><.-,-. => 1
+++[-]+><.-,-. => 1
++,[-]+><.-,-. => 1
++,+-]+><.-,-. => None
++,+[]+><.-,-. => None
++,+[-+><.-,-. => None
++,+[-]><.-,-. => 0
++,+[-]+<.-,-. => None
++,+[-]+>.-,-. => 0
++,+[-]+><-,-. => 255
++,+[-]+><.,-. => 1
++,+[-]+><.--. => 1
++,+[-]+><.-,. => 1
++,+[-]+><.-,- => 1

Unique outputs are [0, 1, 255]    
Score is 3 for ++,+[-]+><.-,-. (length = 15)

Em caso de empate, o vencedor é aquele com o código mais curto. (Seu programa pode ter menos de 100 bytes, conforme indicado na seção Detalhes.) Se os códigos tiverem o mesmo comprimento, o vencedor será o pôster anterior.

Quebra-cabeça bônus: sem a restrição em negrito, você pode encontrar um programa com pontuação 100?

randomra
fonte
Eu resolvi o quebra-cabeça do bônus; a resposta é (censurada).
AJMansfield
@AJMansfield Você poderia editar seu comentário para que outros pudessem pensar no quebra-cabeça também? Por exemplo, altere sua solução para um link pastebin.com que contém a resposta.
randomra
3
Hmm. Eu escrevi um otimizador genético para esta pergunta para tentar encontrar micro-melhorias nas respostas existentes, mas até agora não é muito bem-sucedido. Eles estão ficando presos em 79 e 43, respectivamente. Ah, bem - valeu a pena tentar!
wchargin

Respostas:

12

Pontuação: 35 41 69 78 79 83

(Remova a nova linha.)

-->+>->+>->+>->+>->+>->+>->+>->+>->+>->+>->+>->+>-
>+>->+>->+>->+>->+>->+>->+>->+>++[>[-<+++>]<<++]>.

Experimente online!

Não sei exatamente por que isso funciona ...

Pontuação: 79

X->>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>
+>+>+>+>+>+>+>+>+>+>+>+[>[-<+>>+<]+>[-<+>]<<<+]>>.

Experimente online!

Era para somar 2 * mem [i] * i e adicionar o número de células (+ const) onde os endereços são contados da direita para a esquerda. O multiplicador 2 e o número de células podem tornar a remoção + e> com paridade diferente.

De fato, funcionou assim na versão de 69 pontos. Mas a versão mais recente quebrou isso e conseguiu outra coisa por coincidência. Ele calcula soma (mem [i] * i + i + 1) e remover + e> faz quase o mesmo, exceto a soma (i) que tem uma diferença no número de células, que também é o número de saídas diferentes para remover + e>.

Para o bônus:

+. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +.

jimmy23013
fonte
Nota: se você testar isso com o programa de pontuação fornecido, aumente o maxstepvalor (in def evaluate(r,maxstep=20000):), pois alguns subprogramas são executados por um longo período de tempo.
randomra
11
A pontuação pode realmente ser aumentada 79substituindo-a ->+>+> ...por->,>+> ...
BrainSteel 30/03
@BrainSteel Acabei de mudar para um no-op.
jimmy23013
9

Pontuação: 37 43

+>-,->,+-><->-[>---+-+<[--->>+><,+>>>++<><<<+<[>--]]><><+-+>+<<+<><+++<[[<[---->-<-]>++>],>,]<,]<+-.

EDIT: Agora meu programa permite alguns colchetes. Não vou ganhar nenhum prêmio com isso, mas é o que eu ganho por fazer alguns RNGs ponderados fazerem o trabalho ocupado para mim.

Isso foi gerado por um programa que escrevi em C.

Para cada Ncaractere removido, aqui estão as saídas:

N = 0 => 158
N = 1 => 158
N = 2 => 158
N = 3 => 187
N = 4 => 129
N = 5 => 100
N = 6 => 158
N = 7 => 13
N = 8 => 1
N = 9 => 211
N = 10 => 129
N = 11 => 1
N = 12 => 57
N = 13 => 255
N = 14 => Mismatched Braces
N = 15 => 59
N = 16 => 11
N = 17 => 11
N = 18 => 11
N = 19 => 117
N = 20 => 11
N = 21 => 117
N = 22 => 166
N = 23 => Mismatched Braces
N = 24 => 206
N = 25 => 206
N = 26 => 206
N = 27 => 147
N = 28 => 147
N = 29 => 158
N = 30 => 148
N = 31 => 188
N = 32 => 51
N = 33 => 17
N = 34 => 84
N = 35 => 84
N = 36 => 84
N = 37 => 158
N = 38 => 158
N = 39 => 94
N = 40 => 46
N = 41 => 94
N = 42 => 94
N = 43 => 94
N = 44 => 17
N = 45 => 196
N = 46 => Mismatched Braces
N = 47 => 149
N = 48 => No Termination
N = 49 => No Termination
N = 50 => Mismatched Braces
N = 51 => Mismatched Braces
N = 52 => 45
N = 53 => 77
N = 54 => 45
N = 55 => 77
N = 56 => 50
N = 57 => 209
N = 58 => 50
N = 59 => 251
N = 60 => 249
N = 61 => 99
N = 62 => 99
N = 63 => 117
N = 64 => 89
N = 65 => 207
N = 66 => 89
N = 67 => 115
N = 68 => 115
N = 69 => 115
N = 70 => 95
N = 71 => Mismatched Braces
N = 72 => Mismatched Braces
N = 73 => 104
N = 74 => Mismatched Braces
N = 75 => No Termination
N = 76 => No Termination
N = 77 => No Termination
N = 78 => No Termination
N = 79 => Left Overflow
N = 80 => 3
N = 81 => 2
N = 82 => No Termination
N = 83 => Mismatched Braces
N = 84 => No Termination
N = 85 => 133
N = 86 => 133
N = 87 => 0
N = 88 => Mismatched Braces
N = 89 => 158
N = 90 => 0
N = 91 => 4
N = 92 => Mismatched Braces
N = 93 => 0
N = 94 => 158
N = 95 => Mismatched Braces
N = 96 => 0
N = 97 => 157
N = 98 => 159
N = 99 => None

Há um total de 37 saídas exclusivas, que são (em ordem numérica):

0, 1, 2, 3, 4, 11, 13, 17, 45, 46, 50, 51, 57, 59, 77, 84, 89, 94, 95, 99,
100, 104, 115, 117, 129, 133, 147, 148, 149, 157, 158, 159, 166, 187, 188, 
196, 206, 207, 209, 211, 249, 251, 255

Estou 90% 100% certo de que esta solução não é ótima , mas provando que isso pode ser extremamente difícil . Existem algumas coisas que estão claras. Não ter .símbolos até o último caractere parecer ser o caminho a seguir , e colchetes ( []) parecem ser bastante inúteis . Pensei um pouco aqui, que gostaria de descrever:

Seja Lo comprimento do código em bytes (no desafio 100) e no número de saídas exclusivas dos subprogramas.

Pois L=3existem várias soluções ótimas do formulário +-., onde n=2(nesse caso, as saídas são 1 e 255 para +.e -., respectivamente.) Isso coloca a melhor proporção para L = 3em n/L = 66.67%. Observe que essa proporção não pode ser ultrapassada por pelo menos L<10.

Pois L=10as soluções são simples o suficiente para forçá-lo a força bruta. Aqui estão todas as melhores soluções em n = 6:

++>-->+<+. => 6
++>-->+<+. => 6
+++>->+<+. => 6
--->->+<+. => 6
++>---><+. => 6
+++>--><+. => 6
-->++>-<-. => 6
+++>+>-<-. => 6
--->+>-<-. => 6
-->+++><-. => 6
--->++><-. => 6

O que gera uma taxa de pontuação de n/L = 60%.

Como L->infinityé evidente, a razão deve se aproximar de 0, pois existem apenas 255 saídas possíveis para um potencial infinito L.

A proporção NÃO, no entanto, diminui uniformemente. Não é possível construir uma solução para n=6, L=9, então a melhor razão possível para L=9é 5/9 = 55.56% < 60%.

Isso levanta a questão: com que rapidez e de que maneira a proporção desce? Pois L = 100, e em 10^9 checks/second, levaria várias ordens de magnitude mais longas que a vida útil do universo para forçar uma solução ótima. Existe uma maneira elegante de fazer isso? Muito I dúvida de que é até 37%para L = 100.

A proporção realmente aumenta, até L=100. Veja outras respostas para confirmar.

Eu adoraria ouvir suas avaliações do que foi dito acima. Eu poderia estar atrozmente errado, afinal.

BrainSteel
fonte