Inteiros são tediosos para representar no Brain-Flak . Existem 8 operadores:
() Evaluates to 1, but does not push anything on any stack
[] Evaluates to an indeterminate value for the purposes of this question
{} Removes the top of the stack and evaluates to it
<> Switches to or back from the alternate stack and evaluates to zero
(foo) Pushes the value of the expression foo to the stack and evaluates to it
[foo] Evaluates to the negation of foo
{foo} Evaluates the expression foo until the top of the stack is zero
<foo> Evaluates to zero but executes foo anyway
foo
pode consistir em vários operadores; nesse caso, eles são avaliados e somados. Por exemplo, (()())
empurra 2
para a pilha (e avalia 2
também).
Obviamente, o (()...())
mecanismo não é útil no Code Golf, pois grandes números levariam n*2+2
bytes para representar. Seu desafio é, portanto, escrever um programa ou função que produza o menor número de bytes possível de um programa Brain-Flak que enviará um número inteiro positivo n
à pilha ativa. Este programa não deve fazer suposições sobre o conteúdo existente das pilhas, portanto, não deve deixar as pilhas trocadas ou adicionar ou remover valores extras das pilhas.
Embora seu programa ou função deva ser capaz de retornar um programa Brain-Flak funcional para todas as entradas de 1 a 1.000.000, o vencedor será o programa ou função que gera o menor conjunto de programas Brain-Flak apropriados para todos os 1061 números primos entre 1.000 e 10.000 . Observe o tamanho total de suas saídas para essas 1061 entradas como parte de seu envio. Seu programa ou função pode aceitar o número inteiro e retornar o programa Brain-Flak (string) em qualquer um dos formatos de E / S aceitáveis usuais. Os laços serão quebrados usando o tamanho do seu programa ou função.
fonte
2n
é4^n catalan(n)
.(()()()...())
. Além disso, se você apenas usar números primos, isso poderá perder algumas otimizações possíveis para os compostos.[]
definido para esse desafio? Acho estranho implementar 7 dos 8 operadores. De qualquer maneira, desafio legal, estou honrado por alguém escrever um desafio inspirado na minha própria língua![]
em sua resposta.Respostas:
Python 2,
593945924458534584165839458250Ok, aqui está a minha solução.
A função relevante é
push(n)
. Para chamá-lo, basta chamar push no número inteiro que você deseja representar.Explicação
A principal otimização feita pelo programa é a codificação de multiplicação. A idéia de codificação codificada de multiplicação é bastante simples. Você pressiona o número e, em seguida, aparece e pressiona para criar um novo valor. Por exemplo, para multiplicar por dois, você pode usar o seguinte código em
((n){})
que n produz um número específico. Isso funciona porque ambos(n)
e{}
têm um valor de n.Essa idéia simples pode ser mais complexa para números maiores. Tomemos, por exemplo, 5 e foi descoberto há algum tempo que a melhor maneira de multiplicar por cinco era
(((n)){}){}{}
. Esse código faz duas cópias do n multiplica uma por 4 e adiciona as duas. Usando a mesma estratégia, faço cada multiplicação com base na representação binária de um número. Não vou entrar em detalhes de como isso funciona agora, mas faço isso cortando a primeira da representação binária e substituindo 0 por){}
e 1 por){}{}
. Ele garante que n seja pressionado o número apropriado de vezes e equilibra todos os parênteses. (Se você quiser saber como isso é feito, consulte meu código). Se você quer saber por que isso funciona, pergunte-me em um comentário. Eu não acho que alguém realmente leia todas as atualizações do meu post, então deixei a explicação de fora.Quando o algoritmo tenta encontrar um código rígido de multiplicação, ele tenta todos os fatores primos de um número. Ele ignora os fatores compostos porque, a certa altura, os fatores compostos sempre poderiam ser expressos de forma mais concisa, pois seus próprios fatores primários não são conhecidos se isso ainda é verdade.
O outro mecanismo de economia de bytes é um localizador de solução polinomial. Existem certas formas de polinômios que são fáceis de representar com loops decrescentes. Esses polinômios incluem, mas não estão limitados a, números poligonais. Essa otimização encontra polinômios que se ajustam ao formulário e cria o código que os cria.
Saída
colar-bin
fonte
n
é maior ou menor quen+1
if n % 3 == 2:
final dessa função em um nível.Flacidez Cerebral, 64664
Experimente Online!
Aqui está o meu código anotado
Explicação
Isso implementa apenas duas regras a partir de agora:
Se n é divisível por dois, retorne
(n/2){}
Se n não for divisível por dois, retorne
n-1()
Ele também codifica todos os números menores que 6.
fonte
Perl,
592225915658460 caracteresn()
(11322660 caracteres)(n){}()
(64664 caracteres)((n)){}{}
(63610 caracteres)((n)()){}{}
(63484 caracteres) - este é um novo cálculo(n){({}[()])}{}
(60748 caracteres)n[m]
(62800 caracteres)(n){m({}[l])}{}
(58460 caracteres) - este é um novo cálculoA fórmula para esse último cálculo é
n(n/l+1)/2+mn/l
. Eu tentei alguns outros cálculos, mas eles não são mais úteis para a saída fornecida. Na verdade, o programa gera todos os valores até 9999, mas lista os números primos fornecidos e seu comprimento total.fonte
&try($i * $i, "$numbers[$i]{({})({}[()])}{}");
, que desce para 58,032 quando eu também adicionar&try((3 * $i * $i - $i) / 2, "$numbers[$i]{({})({}[()])({})}{}");
(quadrados / números pentagonais) - é a partir daquiPython,
5913658676 caracteresFunção de golfe número Brainflak:
Iteração do número primo:
Saída:
Pastebin
Explicação:
Preenchemos previamente uma lista R da representação do Brain-flak avaliando números inteiros individuais em um intervalo maior que o necessário [1, m -1] para definir nossa função f . As representações são formadas pegando a menor representação não utilizada (indexada por l ) e formando muitas novas representações, mantendo apenas a mais curta. A representação mais baixa não utilizada assume que todos os números 1 a 1 foram atribuídos a uma representação e que essas representações já foram usadas para produzir novos números. Se um valor menor que l obtém uma representação mais curta, devemos voltar e reproduzir os números que começam nesse ponto. A função f produz um programa que salva o número na pilha adicionando parênteses.
Eu não conhecia nenhum Brainflak quando comecei isso, e aprecio muito a resposta de Eamon Olive por apontar a fórmula para os números dos triângulos. Eu geralmente generalizei a soma e fui implacável em verificar somas e diferenças. Adicionar muitos múltiplos de somas teve um grande efeito.
Para quem se importa, aqui está o código de rascunho que usei para ver quais fórmulas valiam a pena.
Fórmulas de representação:
(X){}
((X)){}{}
((((X)))){}{}{}{}
((((((X)))))){}{}{}{}{}{}
XY
X[Y]
(X){({}[Y])}{}
(X)({({}[Y])}{}){}
(X)(({({}[Y])}{})){}{}
(X)(({({}[Y])}{}){}){}
etc ...
fonte
Lua 5.3, 57522
Na verdade, comecei a trabalhar nisso quando a pergunta foi publicada, mas a esqueci até o aniversário do Brain-Flak.
Idéia semelhante às outras respostas em que funções úteis conhecidas são usadas para criar números maiores a partir de boas representações de números mais simples.
Uma diferença é que, em vez de resolver subproblemas em termos de números menores, estou resolvendo subproblemas em termos de números com representações mais curtas. Eu acho que isso torna mais elegante tirar proveito de números negativos, bem como lidar com o caso em que números menores são representados em termos de números maiores.
Além disso, tentar encontrar todos os números que podem ser representados em um determinado tamanho, ao invés de tentar representar um número específico o mais rápido possível, na verdade, simplifica certos cálculos. Em vez de trabalhar uma fórmula ao contrário para ver se ela pode ser aplicada a um número, a fórmula pode ser trabalhada para frente e aplicada a todos os números.
Outra diferença é que as soluções conhecidas são armazenadas em duas partes - um "prefixo" (opcional) e um "sufixo" (mais parecido com um infixo). Espera-se que a avaliação do prefixo seja ignorada ao calcular o número fornecido - o prefixo contém apenas o código que configura o sufixo a ser executado (geralmente empurrando uma ou mais coisas para a pilha). Portanto, dado um prefixo e um sufixo, o número correspondente pode ser colocado na pilha com
prefix(suffix)
.Essa divisão basicamente resolve o mesmo problema que a
unpack
função na resposta do Assistente de Trigo. Em vez de agrupar o código com<...>
apenas para desfazer isso posteriormente, esse código é simplesmente adicionado ao prefixo.Em alguns casos, o prefixo é realmente avaliado (principalmente para a operação de pseudo-exponenciação), portanto, sua avaliação também é armazenada. No entanto, isso realmente não causa um grande problema, pois o gerador não está tentando construir números específicos. Teoricamente, parece sugerir que poderia haver duas partes de código do mesmo comprimento e gerar o mesmo número que não seria redundante no cache devido a diferentes avaliações de prefixo. Eu não me incomodei em explicar isso, pois isso não parece importar muito (pelo menos nesse domínio).
Eu imagino que seria fácil diminuir a contagem de bytes apenas adicionando mais casos, mas eu já tive o suficiente no momento.
Eu corri para 1000000, mas apenas verifiquei a sanidade até 100000.
Pasta de saída da saída em números primos fornecidos.
fonte
k_limit
ek_max_len
fazer? Não sei se entendi o cabeçalho.k_max_len
. Poderia facilmente verificar se encontrou todos os números solicitados após o processamento de cada comprimento, mas foi útil para mim limitar o comprimento máximo durante o teste, para que o programa fosse executado mais rapidamente. (O processamento de comprimentos maiores pode ser muito lento.)k_limit
É basicamente o parâmetro de entrada - ele produzirá programas para números até esse ponto - assumindo quek_max_len
era grande o suficiente para encontrá-los.ruby, 60246 bytes
Eu uso um hash. Eu encontro o melhor golfe para um determinado número e usa os menores para encontrar os maiores.
Os hashes recursivos são muito divertidos!
fonte
Python, 64014 caracteres
Eu não sabia nada sobre o brainflak antes desse desafio e apenas brincava um pouco com o tryitonline, para que houvesse atalhos óbvios que eu perdesse. Essa é uma solução bastante entediante, apenas divide a entrada em
x=x/2+x%2
oux=x/3+x%3
, o que for menor.Chame assim:
b(42)
saída em pastebin
fonte
Lua, 64664 bytes
O programa imprime o comprimento total dos programas e o programa para o 203º prime (existe uma linha que você pode alterar para alterar qual deles é impresso ou descomentar uma linha para imprimir todos os programas)
No momento, a única otimização é x = 2 * n + 1
Espero ter tempo para adicionar mais otimizações para diminuir a pontuação.
fonte