Golunar / Unary é uma maneira de codificar todos os programas válidos do Brainfuck , mas não é uma enumeração, pois a maioria dos números naturais não corresponde a um programa válido.
Para o propósito deste desafio, assuma uma fita duplamente infinita e nenhum comentário, ou seja, um programa Brainfuck é válido se e somente se consistir apenas nos caracteres <>+-.,[]
e todos os colchetes esquerdo e direito coincidirem.
Por exemplo, o programa vazio, ,[+][-].
, [>+<[--].]
e +[+[+][+[+]+]+]+.
são programas Brainfuck válidos, enquanto que ][
, e a[]
não são.
Tarefa
Escreva um programa ou função que aceite um programa Brainfuck válido como entrada e retorne um número natural ( 1 , 2 , 3 ,…), com as seguintes restrições:
A saída gerada deve ser diferente para todos os programas válidos do Brainfuck.
Para todo número natural n , deve haver um programa Brainfuck válido que, quando fornecido como entrada, gere a saída n .
Regras adicionais
Dado um programa Brainfuck de 100 ou menos bytes, seu programa ou função deve terminar em um minuto.
Isso significa que você não pode repetir todos os programas válidos do Brainfuck até corresponder à entrada.
Aplicam-se as regras padrão de código de golfe .
fonte
Respostas:
Python 3,
443158155154134131128124117116115 bytesVários bytes graças ao Sp3000 e Mitch Schwartz: D
Como isso funciona:
Isso mapeia todos os programas válidos de BF em todos os programas possíveis, válidos ou inválidos de BF, que não começam com um
[
, na proporção de um para um. Depois disso, o novo programa é simplesmente convertido em octal.Aqui está a fórmula de mapeamento:
[
caracteres. A terceira parte é o maior postfix composto apenas por]
caracteres. A segunda parte é o meio.]
colchetes na terceira parte que correspondem aos[
colchetes na segunda parte. Estes também podem ser recalculados mais tarde.Se você não entender esta explicação, poderá encontrar uma explicação detalhada no chat, começando aqui .
Para referência, aqui estão os 20 primeiros programas:
Aqui estão os primeiros 1000 programas: http://pastebin.com/qykBWhmD
Aqui está o programa que eu usei para gerá-los: http://ideone.com/e8oTVl
Aqui está
Hello, World!
:fonte
Python 2, 157 bytes
Ainda parece bastante jogável, mas estou postando isso por enquanto. Ele usa recursão com um pouco de cache. Irritantemente,
D.get
não provoca um curto-circuito no cache, então não posso salvar 9 bytes dessa maneira ...O mapeamento prioriza primeiro o comprimento, depois a ordem lexicográfica sobre a ordem
"][><.-,+"
(veja exemplos de saída abaixo). A idéia principal é comparar prefixos.A variável
o
controla o número de[
colchetes ainda abertos para o prefixo atual, enquanto a variáveld
utiliza um dos três valores que indicam:d = 1
: O prefixo atual é lexicograficamente anterior as
. Adicione todos os programas com esse prefixo e comprimento<= s
,d = -1
: O prefixo atual é lexicograficamente posterior as
. Adicione todos os programas com esse prefixo e comprimento< s
.d = 0
: O prefixo atual é um prefixo des
, portanto, podemos mudard
para 1 ou -1 mais tarde.Por exemplo, se tivermos
s = "[-]"
e nosso prefixo atual forp = "+"
, uma vez quep
é posterior aos
lexicograficamente, sabemos apenas adicionar os programas iniciados com osp
quais são estritamente menores ques
.Para dar um exemplo mais detalhado, suponha que tenhamos um programa de entrada
s = "-[]"
. A primeira expansão recursiva faz isso:Nota como nós realmente não usar os prefixos na recursão - todos nós se preocupa com eles é capturada através das variáveis
d
,o
e o programa de entrada encolhendos
. Você notará muitas repetições acima - é aqui que entra o cache, permitindo que processemos programas de 100 caracteres bem dentro do prazo.Quando
s
está vazio, examinamos(d>=0 and o==0)
, que decide se deve retornar 1 (conte este programa porque é lexicograficamente precoce / igual e o programa é válido) ou 0 (não conte este programa).Qualquer situação com
o < 0
retorno imediato0
, pois qualquer programa com esse prefixo tem mais]
s que[
e, portanto, é inválido.As primeiras 20 saídas são:
Usando o mesmo exemplo do Hello World que a resposta do @ TheNumberOne:
fonte
Python 2, 505 (não jogado)
Eu gostei de desenvolver essa abordagem, mas talvez não me incomode em jogar golfe porque não é competitiva em comparação com outras abordagens. Estou publicando por causa da diversidade e possível interesse estético. Envolve recursão e um pouco de matemática.
A função
f(n)
conta o número de programas válidos de foda cerebraln
.h(x)
mapeia programas de comprimenton
para[0..f(n)-1]
eg(x)
é a função de classificação bijetiva em questão.A idéia principal é que um programa não vazio possa começar com
[
ou com um dos 6[]
caracteres não . No primeiro caso, podemos iterar sobre os possíveis locais da correspondência]
e recuar na parte fechada e na cauda (onde cauda significa a substring após a]
). No último caso, podemos recuar na cauda (onde cauda significa largar o primeiro caractere). Esse raciocínio pode ser usado tanto na contagem quanto na classificação da computação.Programas mais curtos sempre terão classificação mais baixa do que programas mais longos, e o padrão de colchetes é um fator determinante secundário. Os não
[]
caracteres são classificados de acordo com "+ - <>,". (que é arbitrário).Por exemplo, com
n=4
estes casos:onde
z
significa não[]
caractere ex
representa qualquer caractere, sob a restrição de que ele]
precisa corresponder à inicial[
. Os programas são classificados de acordo com essa ordem e recursivamente nasx
subseções, com a seção esquerda priorizada sobre a seção direita nos últimos casos. O cálculo da classificação é semelhante aos sistemas de números de mistura mista ef
é importante para calcular a "base" atual.fonte
Esta resposta é uma prova formal da resposta de TheNumberOne , Enumerate Brainf ** k programas válidos , onde pode ser um pouco difícil entender os pontos positivos da razão pela qual a enumeração está correta. Não é trivial entender por que não há algum programa inválido que mapeie para um número não coberto por um programa válido.
Em toda essa resposta, maiúsculas são usadas para denotar programas e variáveis em minúsculas são usadas para funções e números inteiros. ~ é o operador de concatenação.
Proposição 1:
Seja a função f o programa descrito nessa resposta. Então, para todo programa U existe um programa válido V tal que f (U) = f (V)
Definição 1:
Seja g (X) o número
[
que aparece no programa X e h (X) seja o número]
que aparece.Definição 2:
Defina P (x) para esta função:
Definição 3:
Dado um programa X, denote X1 como seu maior prefixo de
[
caracteres, X2 seu centro e X3 seu maior sufixo de]
caracteres.Prova da proposição 1:
Se g (U) = h (U), então U é um programa válido, e podemos usar V = U. (caso trivial).
Se g (U) <h (U), então podemos criar V acrescentando n = h (U) - g (U)
[
símbolos. Obviamente f (V) = f (U), pois todos os[
símbolos no prefixo são removidos.Agora considere g (U)> h (U). Defina T = U2 ~ U3. se g (T) <= h (T), então podemos construir V removendo n = g (U) - h (U)
[
símbolos.Portanto, podemos assumir que h (T) <g (T). Construa V = T ~ P (g (T) - h (T)).
Precisamos de três pequenos fatos para prosseguir:
Reivindicação 1: g (U2) = g (T)
U3 não contém nenhum
[
símbolo por sua definição. Como T = U2 ~ U3, seus[
símbolos estão todos na primeira parte.Reivindicação 2: h (U3) <g (T)
Isso resulta da observação de que h (T) <g (T) eh (U3) <h (U3 ~ U2) = h (T).
Reivindicação 3: h (V3) = g (U2) - h (U2)
Agora mostramos que f (V) = f (U).
Isso completa a prova. QED
Vamos fazer exclusividade também.
Proposição 2:
Seja U, V dois programas válidos diferentes. Então f (U)! = F (V)
Isso é bastante simples em comparação com a proposição anterior.
Vamos supor que U2 = V2. Mas a única maneira de U e V serem diferentes é adicionando ou removendo n
[
e]
símbolos a U1 e U3, respectivamente. No entanto, isso altera a saída de f, pois f contará o número de]
símbolos não correspondentes no sufixo.Assim U2! = V2.
Obviamente, isso leva a uma contradição. Como U2 e V2 estão literalmente contidos na saída de f (U) ef (V), respectivamente, eles não podem diferir, exceto na 'borda', o local em que U2 é concatenado com U3. Mas o primeiro e o último símbolo de U2 e V2 não podem ser
[
ou]
por definição, enquanto esses são os únicos símbolos permitidos em U1, U3, V1, V3, respectivamente e respectivamente novamente. Assim, temos U2 = V2. QEDfonte