Esta pergunta é o primeiro de vários desafios de aniversário do Brain-flak, projetados para comemorar o primeiro aniversário do Brain-Flak! Você pode encontrar mais informações sobre o aniversário de Brain-Flak aqui

No verão passado, tivemos o Metagolf Inteiro do Brain-flak , e as respostas que ele gerou foram muito úteis para a comunidade do Brain-Flak desde então. A principal coisa que torna o Metagolf inteiro tão eficiente é uma técnica chamada Multiplication hardcoding.

No Brain-Flak, a multiplicação do tempo de execução é extremamente cara. O menor snippet de multiplicação conhecido é:

({}<>)({<({}[()])><>({})<>}{}<><{}>)

Descoberto pela Megatom

No entanto, existe uma maneira muito simples de criar a multiplicação do tempo de compilação. Por exemplo, o seguinte código será multiplicado por 5:

 (({})({})({})({}){})

Experimente online!

Isso funciona porque expressões consecutivas são adicionadas. Cada um deles ({})não faz nada na pilha ( {}abre e (..)empurra-a de volta) e avalia o que estiver no topo da pilha. Todas essas expressões juntas somam cinco vezes o que estava no topo da pilha.

Para qualquer uma ndas seguintes expressões de string, será criado um trecho que multiplicará a parte superior da pilha por n:

"("+"({})"*(n-1)+"{})"

Isso funciona criando nexpressões que são avaliadas no topo da pilha. O primeiro n-1não muda nada e o último remove o topo da pilha antes do push.

Para números compostos, você pode encadear várias expressões menores para salvar bytes. Por exemplo, você pode multiplicar por 25 multiplicando por 5 duas vezes:

(({})({})({})({}){})(({})({})({})({}){})

Isso é bastante simples e, para alguns números, funciona muito bem, no entanto, existem maneiras melhores de fazer isso. Por exemplo, um método que inventei usa a representação binária do número. ( Aqui está uma implementação em python ) Esse novo método é muito mais eficaz do que a expressão simples de string mostrada anteriormente, mas não é o fim, existem todos os tipos de maneiras interessantes de multiplicar o código por código e provavelmente uma tonelada que ninguém ainda descobriu.

Então, acho que é hora de ver como podemos melhorar.

Breve visão geral do Brain-Flak

Aqui está uma descrição de tudo o que você precisa saber sobre o Brain-Flak para este desafio.

Brain-Flak tem "niladas" e "mônadas". Nilads são parênteses que não têm nada dentro deles. Cada nilad faz uma coisa e retorna um valor. Para esse desafio, as duas niladas com as quais estamos preocupados são {}e <>. {}aparece o topo da pilha ativa e retorna seu valor. <>alterna a pilha ativa e a pilha ativa, para que a pilha ativa se torne inativa e a pilha inativa se torne ativa, ela retorna zero.

Mônadas são parênteses com coisas dentro delas. Eles usam um único argumento, a soma de tudo dentro deles, às vezes executam uma ação e, em seguida, retornam um valor. A três destes estamos preocupados com são (...), <...>e [...]. A mônada mais importante para esse desafio (...)pega o valor do interior e o empurra para a pilha ativa. Em seguida, retorna o argumento. <...>e [...]são mônadas "inertes", ou seja, não executam nenhuma ação, mas modificam o valor que recebem. <...>sempre retorna zero, independentemente do argumento passado. Enquanto isso, [...]sempre retorna os tempos de discussão -1.

Programas de exemplo com explicação

Se você nunca programou no Brain-Flak, pode ser uma boa ideia examinar alguns exemplos de programas usando as operações descritas

({}{})

Isso adiciona os dois principais números da pilha. Cada {}um retira um valor da pilha e (...)empurra sua soma de volta.

({}[{}])

Da mesma forma, isso subtrai o segundo item da pilha do primeiro. Como antes de cada {}um exibir um valor, mas o [..]próximo ao segundo faz com que ele seja adicionado. Mais uma vez, (...)empurra a soma.

({}<{}>)

Isso remove o segundo valor na pilha, mantendo intacto o valor superior. Funciona exatamente como os dois últimos, exceto que o segundo valor é silenciado pelo, <...>portanto, o push apenas empurra o primeiro valor de volta.

(({}))

Isso faz uma segunda cópia do valor na parte superior da pilha. Isso é feito ao abrir o topo da pilha com a {}obtenção de seu valor, o primeiro (..)empurra-o novamente para avaliar seu valor. O segundo (...)pega o valor retornado pelo primeiro e o envia para a pilha também. criando uma segunda cópia.

Tarefa

Dado um número inteiro, ncrie um snippet Brain-Flak limpo de pilha que multiplique o topo da pilha atual por n.

Você tem permissão para usar as seguintes operações do Brain-Flak

(...) -> Push Monad, Pushes the result of its contents
<...> -> Zero Monad, Returns zero
[...] -> Negative Monad, Returns the opposite of its contents result
{}    -> Pop nilad, Pops the TOS and returns its value
<>    -> Switch nilad, Switches the active and inactive stack

As outras operações são proibidas para os fins do desafio.

Pontuação

Sua pontuação será o comprimento acumulado de todos os programas de n=2até n=10000. Certifique-se de incluir um link para a saída do seu programa para verificação.

Ruby, 669856

$answers = Hash.new{|hash,n|
  valid = []
  2.upto(n**0.5){|i|
    valid.push("("+hash[n/i]+")"+"({})"*(i-2)+"{}") if n%i == 0
  }
  valid.push("({})"+hash[n-1])
  (hash[n] = valid.min_by{|s| s.length})
}
$answers[1] = "{}"

def full_answer n
  "("+$answers[n]+")"
end

Esta é uma resposta rápida da linha de base. Primeiros 1000 min-programas encontrados aqui . (Tentei postar todos eles, mas isso sobrecarregou o tamanho máximo de pastebin.) Posso adicionar uma explicação de código posteriormente.

Exemplos:

360:    ((((((({})(({}){}){})({}){})({}){}){}){}){})
4608:   (((((((((((({})({}){})({}){}){}){}){}){}){}){}){}){}){})
9991:   (({})((({})(((((((({})((({})({}){}){}){}){}){}){}){}){}){}){})({}){}){})