Quine Mini-Flak mais rápido

26

Mini-Flak é um subconjunto do Brain-Flak linguagem, onde os <>, <...>e []operações não são permitidas. A rigor, ele não deve corresponder à seguinte expressão regular:

.*(<|>|\[])

Mini-Flak é o menor subconjunto completo de Turing conhecido por Brain-Flak.

Há pouco tempo, eu era capaz de fazer um Quine em Mini-Flak , mas era muito lento para funcionar durante a vida do universo.

Então, meu desafio para você é fazer um Quine mais rápido.

Pontuação

Para pontuar seu código, coloque um @cysinalizador no final do código e execute-o no interpretador Ruby ( Experimente online, use o intérprete ruby) usando o -dsinalizador. Sua pontuação deve ser impressa no STDERR da seguinte maneira:

@cy <score>

Esse é o número de ciclos que seu programa leva antes de terminar e é o mesmo entre as execuções. Como cada ciclo leva aproximadamente a mesma quantidade de tempo para ser executado, sua pontuação deve ser diretamente correlacionada ao tempo necessário para executar seu programa.

Se o seu Quine é muito longo para você executar razoavelmente no seu computador, você pode calcular o número de ciclos manualmente.

Calcular o número de ciclos não é muito difícil. O número de ciclos é equivalente a 2 vezes o número de mônadas executadas mais o número de niladas executadas. É o mesmo que substituir cada nilad por um único caractere e contar o número de caracteres executados no total.

Exemplo de pontuação

  • (()()()) pontua 5 porque possui 1 mônada e 3 niladas.

  • (()()()){({}[()])} pontua 29 porque a primeira parte é a mesma de antes e pontua 5 enquanto o loop contém 6 mônadas e 2 nilads com pontuação 8. O loop é executado 3 vezes, então contamos sua pontuação 3 vezes. 1*5 + 3*8 = 29

Exigências

Seu programa deve ...

  • Ter pelo menos 2 bytes

  • Imprima seu código-fonte quando executado no Brain-Flak usando a -Abandeira

  • Não corresponde à regex .*(<|>|\[])

Dicas

  • O intérprete Crane-Flak é categoricamente mais rápido que o intérprete ruby, mas carece de alguns dos recursos. Eu recomendaria testar seu código usando o Crane-Flak primeiro e depois pontuá-lo no interpretador de ruby ​​quando você souber que ele funciona. Eu também recomendo não executar o seu programa no TIO. O TIO não é apenas mais lento que o interpretador de desktop, mas também atingirá o tempo limite em cerca de um minuto. Seria extremamente impressionante se alguém conseguisse uma pontuação baixa o suficiente para executar seu programa antes que o tempo limite do TIO expirasse.

  • [(...)]{}e (...)[{}]funciona da mesma forma, <...>mas não quebra, o requisito de fonte restrita

  • Você pode conferir Quines Brain-Flak e Mini-Flak se quiser ter uma idéia de como enfrentar esse desafio.

restricted-source quine fastest-code brain-flak Assistente de Trigo
fonte
1
"melhor atual" -> "somente atual"
HyperNeutrino 24/17

Respostas:

33

Mini-Flak, 6851113 ciclos

O programa (literalmente)

Eu sei que a maioria das pessoas provavelmente não espera que um quine Mini-Flak use caracteres não imprimíveis e até caracteres de vários bytes (tornando a codificação relevante). No entanto, esse quine sim, e os não imprimíveis, combinados com o tamanho do quine (93919 caracteres codificados como 102646 bytes de UTF-8), tornam bastante difícil colocar o programa nesta postagem.

No entanto, o programa é muito repetitivo e, como tal, compacta muito bem. Para que todo o programa esteja disponível literalmente no Stack Exchange, existe um xxdhexdump reversível de uma gzipversão compactada do quine completo, oculta por trás do recolhível abaixo:

Mostrar snippet de código

(Sim, é tão repetitivo que você pode até ver as repetições depois de compactadas).

A pergunta diz: "Eu também recomendo não executar seu programa no TIO. O TIO não é apenas mais lento que o interpretador de desktop, mas também atingirá o tempo limite em cerca de um minuto. Seria extremamente impressionante se alguém conseguisse pontuar baixo o suficiente para executar o programa antes do tempo limite do TIO ". Eu posso fazer isso! Demora cerca de 20 segundos para executar no TIO, usando o intérprete Ruby: Experimente online!

O programa (facilmente)

Agora, eu forneci uma versão do programa que os computadores podem ler, vamos tentar uma versão que os humanos possam ler. Eu converti os bytes que compõem o quine na página de códigos 437 (se eles tiverem o conjunto de bits alto) ou imagens de controle Unicode (se forem códigos de controle ASCII), espaço em branco adicionado (qualquer espaço em branco pré-existente foi convertido para controlar imagens) ), codificado pelo comprimento da execução usando a sintaxe «string×length»e alguns bits pesados ​​de dados elididos:

␠
(((()()()()){}))
{{}
    (({})[(()()()())])
    (({})(
        {{}{}((()[()]))}{}
        (((((((({})){}){}{})){}{}){}){}())
        {
            ({}(
                (␀␀!S␠su! … many more comment characters … oq␝qoqoq)
                («()×35» («()×44» («()×44» («()×44» («()×44» («()×45»
                … much more data encoded the same way …
                («()×117»(«()×115»(«()×117»
                «000010101011┬â┬ … many more comment characters … ┬â0┬â┬à00␈␈
                )[({})(
                    ([({})]({}{}))
                    {
                        ((()[()]))
                    }{}
                    {
                        {
                            ({}(((({}())[()])))[{}()])
                        }{}
                        (({}))
                        ((()[()]))
                    }{}
                )]{}
                %Wwy$%Y%ywywy$wy$%%%WwyY%$$wy%$$%$%$%$%%wy%ywywy'×almost 241»
                ,444454545455┬ç┬ … many more comment characters … -a--┬ü␡┬ü-a␡┬ü
            )[{}()])
        }{}
        {}({}())
    )[{}])
    (({})(()()()()){})
}{}{}␊

(O "quase 241" ocorre porque a 241ª cópia está ausente no final ', mas é idêntica à outra 240.)

Explicação

Sobre os comentários

A primeira coisa a explicar é: o que há com caracteres não imprimíveis e outros itens indesejados que não são comandos do Mini-Flak? Você pode pensar que adicionar comentários ao quine apenas dificulta as coisas, mas isso é uma competição de velocidade (não uma competição de tamanho), o que significa que os comentários não prejudicam a velocidade do programa. Enquanto isso, o Brain-Flak e, portanto, o Mini-Flak, apenas despejam o conteúdo da pilha na saída padrão; se você tivesse que garantir que a pilha contivesse apenasos caracteres que compunham os comandos do seu programa, você teria que gastar ciclos limpando a pilha. Assim, o Brain-Flak ignora a maioria dos caracteres, desde que asseguremos que os elementos da pilha de lixo eletrônico não sejam comandos válidos para o Brain-Flak (tornando-o um poliglota do Brain-Flak / Mini-Flak) e não sejam negativos ou externos No intervalo Unicode, podemos apenas deixá-los na pilha, permitir que sejam exibidos e colocar o mesmo caractere em nosso programa no mesmo local para manter a propriedade quine.

Existe uma maneira particularmente importante de tirar vantagem disso. O quine funciona usando uma cadeia de dados longa e, basicamente, toda a saída do quine é produzida formatando a cadeia de dados de várias maneiras. Há apenas uma sequência de dados, apesar do programa ter várias partes; portanto, precisamos poder usar a mesma sequência de dados para imprimir diferentes partes do programa. O truque "dados indesejados não importa" nos permite fazer isso de uma maneira muito simples; armazenamos os caracteres que compõem o programa na cadeia de dados adicionando ou subtraindo um valor para ou de seu código ASCII. Especificamente, os caracteres que compõem o início do programa são armazenados como seu código ASCII + 4, os caracteres que compõem a seção repetida quase 241 vezes como seu código ASCII - 4,todos os caracteres da sequência de dados com um deslocamento; se, por exemplo, imprimi-lo com 4 adicionados a cada código de caractere, obtemos uma repetição da seção repetida, com alguns comentários antes e depois. (Esses comentários são simplesmente as outras seções do programa, com os códigos de caracteres alterados para que não formem nenhum comando válido do Brain-Flak, porque o deslocamento incorreto foi adicionado. Temos que desviar dos comandos do Brain-Flak, não apenas do Mini- Comandos Flak, para evitar violar a parte de origem restrita da questão; a escolha dos deslocamentos foi projetada para garantir isso.)

Devido a esse truque de comentário, na verdade, precisamos apenas produzir a sequência de dados formatada de duas maneiras diferentes: a) codificada da mesma maneira que na fonte, b) como códigos de caracteres com um deslocamento especificado adicionado a cada código. Essa é uma enorme simplificação que faz com que o comprimento adicionado valha totalmente a pena.

Estrutura do programa

Este programa consiste em quatro partes: a introdução, a sequência de dados, o formatador da sequência de dados e o outro. A introdução e o outro são basicamente responsáveis ​​por executar a sequência de dados e seu formatador em um loop, especificando o formato apropriado a cada vez (ou seja, se deseja codificar ou compensar e qual deslocamento usar). A sequência de dados é apenas dados, e é a única parte do quine para a qual os caracteres que a compõem não são especificados literalmente na sequência de dados (fazer isso seria obviamente impossível, pois teria que ser mais longo que ele); assim, é escrito de uma maneira particularmente fácil de se regenerar. O formatador de cadeia de dados é composto por 241 partes quase idênticas, cada uma das quais formata um dado específico dos 241 na cadeia de dados.

Cada parte do programa pode ser produzida através da cadeia de dados e seu formatador, da seguinte maneira:

  • Para produzir o outro, formate a sequência de dados com deslocamento +8
  • Para produzir o formatador de cadeia de dados, formate-a com deslocamento +4, 241 vezes
  • Para produzir a sequência de dados, formate a sequência de dados codificando-a no formato de origem
  • Para produzir a introdução, formate a sequência de dados com o deslocamento -4

Então, tudo o que precisamos fazer é observar como essas partes do programa funcionam.

A sequência de dados

(«()×35» («()×44» («()×44» («()×44» («()×44» («()×45» …

Precisamos de uma codificação simples para a sequência de dados, pois precisamos poder reverter a codificação no código Mini-Flak. Você não pode ficar muito mais simples que isso!

A idéia principal por trás desse quine (além do truque dos comentários) é observar que há basicamente apenas um lugar para armazenar grandes quantidades de dados: as "somas de comando retornam valores" nos vários níveis de aninhamento da fonte do programa. (Isso é comumente conhecido como a terceira pilha, embora o Mini-Flak não tenha uma segunda pilha, então "pilha de trabalho" provavelmente é um nome melhor no contexto do Mini-Flak.) As outras possibilidades de armazenamento de dados seriam a pilha principal / primeira (que não funciona porque é para onde nossa saída precisa ir e não podemos mover a saída além do armazenamento de maneira remotamente eficiente) e codificada em um bignum em um único elemento de pilha (o que não é adequado para esse problema, pois leva um tempo exponencial para extrair dados dele); quando você os elimina, a pilha de trabalho é o único local restante.

Para "armazenar" dados nessa pilha, usamos comandos desbalanceados (neste caso, a primeira metade de um (…)comando), que serão balanceados no formatador de sequência de dados posteriormente. Cada vez que fechamos um desses comandos no formatador, ele envia a soma de um dado retirado da sequência de dados e os valores de retorno de todos os comandos nesse nível de aninhamento no formatador; podemos garantir que este último seja zero, para que o formatador veja apenas valores únicos retirados da sequência de dados.

O formato é muito simples (:, seguido por n cópias de (), em que n é o número que queremos armazenar. (Observe que isso significa que podemos armazenar apenas números não negativos e o último elemento da sequência de dados precisa ser positivo.)

Um ponto pouco intuitivo sobre a sequência de dados é em qual ordem ela está. O "início" da sequência de dados é o fim mais próximo do início do programa, ou seja, o nível de aninhamento mais externo; essa parte é formatada por último (à medida que o formatador é executado dos níveis de aninhamento mais interno para mais externo). No entanto, apesar de ter sido formatado por último, ele é impresso primeiro, porque os valores inseridos na pilha primeiro são impressos por último pelo interpretador Mini-Flak. O mesmo princípio se aplica ao programa como um todo; primeiro precisamos formatar o outro, depois o formatador da sequência de dados, a sequência de dados e a introdução, ou seja, o inverso da ordem em que eles são armazenados no programa.

O formatador de cadeia de dados

)[({})(
    ([({})]({}{}))
    {
        ((()[()]))
    }{}
    {
        {
            ({}(((({}())[()])))[{}()])
        }{}
        (({}))
        ((()[()]))
    }{}
)]{}

O formatador da cadeia de dados é composto de 241 seções, cada uma com código idêntico (uma seção possui um comentário marginalmente diferente), cada uma das quais formata um caractere específico da cadeia de dados. (Não foi possível usar um loop aqui: precisamos de um desequilíbrio )para ler a sequência de dados através da correspondência do desequilibrado (, e não podemos colocar um desses dentro de um {…}loop, a única forma de loop que existe. Então, em vez disso, nós " desenrole "o formatador e simplesmente obtenha a introdução / outro para gerar a sequência de dados com o deslocamento do formatador 241 vezes.)

)[({})( … )]{}

A parte mais externa de um elemento do formatador lê um elemento da sequência de dados; a simplicidade da codificação da cadeia de dados leva a um pouco de complexidade na leitura. Começamos fechando o inigualável (…)na sequência de dados e depois negamos ( […]) dois valores: o dado que acabamos de ler da sequência de dados ( ({})) e o valor de retorno do restante do programa. Copiamos o valor de retorno do restante do elemento formatador com (…)e adicionamos a cópia à versão negada com {}. O resultado final é que o valor de retorno do elemento da string de dados e do elemento formatador juntos é o dado menos o dado menos o valor de retorno mais o valor de retorno, ou 0; isso é necessário para que o próximo elemento da cadeia de dados produza o valor correto.

([({})]({}{}))

O formatador usa o elemento da pilha superior para saber em qual modo ele está (0 = formato na formatação da cadeia de dados, qualquer outro valor = o deslocamento para saída). No entanto, depois de ler a sequência de dados, o dado está no topo do formato na pilha e queremos que seja o contrário. Este código é uma variante mais curta do código de permuta de cérebro-Flak, tendo um acima b a b acima um  +  b ; não apenas é mais curto, como também (nesse caso específico) é mais útil, porque o efeito colateral de adicionar b a a não é problemático quando b é 0 e quando b não é 0, ele faz o cálculo de deslocamento para nós.

{
    ((()[()]))
}{}
{
    …
    ((()[()]))
}{}

O Brain-Flak possui apenas uma estrutura de controle de fluxo; portanto, se queremos algo além de um whileloop, será preciso um pouco de trabalho. Essa é uma estrutura "negativa"; se houver um 0 no topo da pilha, ele o remove; caso contrário, coloca um 0 no topo da pilha. (Funciona de maneira bem simples: contanto que não haja um 0 no topo da pilha, pressione 1 - 1 para a pilha duas vezes; quando terminar, clique no elemento superior da pilha.)

É possível colocar o código dentro de uma estrutura negativa, como pode ser visto aqui. O código será executado apenas se a parte superior da pilha for diferente de zero; portanto, se tivermos duas estruturas negativas, supondo que os dois principais elementos da pilha não sejam zero, eles se cancelarão, mas qualquer código dentro da primeira estrutura será executado apenas se o elemento superior da pilha for diferente de zero e o código dentro a segunda estrutura será executada apenas se o elemento da pilha superior for zero. Em outras palavras, isso é equivalente a uma instrução if-then-else.

Na cláusula "then", que é executada se o formato for diferente de zero, na verdade não temos nada a fazer; o que queremos é enviar os dados + offset para a pilha principal (para que possam ser impressos no final do programa), mas já estão lá. Portanto, apenas temos que lidar com o caso de codificar o elemento da cadeia de dados no formato de origem.

{
    ({}(((({}())[()])))[{}()])
}{}
(({}))

Aqui está como fazemos isso. A {({}( … )[{}()])}{}estrutura deve estar familiarizada como um loop com um número específico de iterações (que funciona movendo o contador de loop para a pilha de trabalho e mantendo-o lá; estará seguro de qualquer outro código, porque o acesso à pilha de trabalho está vinculado a o nível de aninhamento do programa). O corpo do loop é ((({}())[()])), que faz três cópias do elemento da pilha superior e adiciona 1 à mais baixa. Em outras palavras, ele transforma um 40 no topo da pilha em 40 acima de 40 acima de 41, ou visto como ASCII, (em ((); executar isso repetidamente se (transformará (()em (()()into (()()()e assim por diante, e, portanto, é uma maneira simples de gerar nossa cadeia de dados (supondo que já esteja (no topo da pilha).

Quando terminarmos o loop, (({}))duplique a parte superior da pilha (para que agora comece ((()…ao invés de (()…. O líder (será usado pela próxima cópia do formatador de cadeia de dados para formatar o próximo caractere (ele será expandido para (()(()…então (()()(()…, e assim por diante, para que isso gere a separação (na sequência de dados).

%Wwy$%Y%ywywy$wy$%%%WwyY%$$wy%$$%$%$%$%%wy%ywywy'

Há um último interesse no formatador de cadeias de dados. OK, então este é apenas o outro deslocamento de 4 pontos de código para baixo; no entanto, esse apóstrofo no final pode parecer fora de lugar. '(ponto de código 39) mudaria para +(ponto de código 43), que não é um comando Brain-Flak, então você deve ter adivinhado que ele existe para algum outro propósito.

A razão pela qual isso está aqui é porque o formatador de cadeia de dados espera que já exista um (na pilha (ele não contém um literal 40 em lugar nenhum). o'na verdade, é o início do bloco que é repetido para compor o formatador de sequência de dados, não o final. Portanto, depois que os caracteres do formatador de sequência de dados foram inseridos na pilha (e o código está prestes a passar para a impressão da sequência de dados) próprio), o outro ajusta os 39 no topo da pilha em 40, prontos para o formatador (o formatador em execução desta vez, não sua representação na fonte) para usá-lo. É por isso que temos "quase 241" cópias do formatador; a primeira cópia está faltando seu primeiro caractere. E esse caractere, o apóstrofo, é um dos três únicos caracteres na sequência de dados que não correspondem ao código Mini-Flak em algum lugar do programa; está lá puramente como um método de fornecer uma constante.

A introdução e outro

(((()()()()){}))
{{}
    (({})[(()()()())])
    (({})(
        {{}{}((()[()]))}{}
        (((((((({})){}){}{})){}{}){}){}())
        {
            ({}(
                (␀␀!S␠su! … many more comment characters … oq␝qoqoq)
                …
            )[{}()])
        }{}
        {}({}())
    )[{}])
    (({})(()()()()){})
}{}{}␊

A introdução e o outro são conceitualmente a mesma parte do programa; a única razão pela qual fazemos uma distinção é que o outro precisa ser produzido antes da sequência de dados e seu formatador (para que seja impresso após eles), enquanto a introdução precisa ser produzida após eles (impressão antes deles).

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

Começamos colocando duas cópias de 8 na pilha. Esse é o deslocamento para a primeira iteração. A segunda cópia é porque o loop principal espera que exista um elemento indesejado no topo da pilha acima do deslocamento, deixado para trás no teste que decide se existe o loop principal e, portanto, precisamos colocar um elemento indesejado para que não joga fora o elemento que realmente queremos; uma cópia é a maneira mais rápida (portanto, mais rápida de gerar) de fazer isso.

Existem outras representações do número 8 que não são mais longas que esta. No entanto, ao optar pelo código mais rápido, essa é definitivamente a melhor opção. Por um lado, o uso ()()()()é mais rápido do que, digamos, (()()){}porque, apesar de ambos terem 8 caracteres, o primeiro é um ciclo mais rápido, porque (…)é contado como 2 ciclos, mas ()apenas como um. Porém, salvar um ciclo é insignificante em comparação com uma consideração muito maior para um quine : (e )possui pontos de código muito menores que {e }, portanto, gerar o fragmento de dados para eles será muito mais rápido (e o fragmento de dados ocupará menos espaço no código, também).

{{} … }{}{}

O loop principal. Isso não conta as iterações (é um whileloop, não um forloop e usa um teste para interromper). Depois que sai, descartamos os dois principais elementos da pilha; o elemento superior é um 0 inofensivo, mas o elemento abaixo será o "formato a ser usado na próxima iteração", que (sendo um deslocamento negativo) é um número negativo e se houver algum número negativo na pilha quando o Mini -Flak programa sai, o intérprete falha ao tentar produzi-los.

Como esse loop usa um teste explícito para interromper, o resultado desse teste será deixado na pilha, então o descartamos como a primeira coisa que fazemos (seu valor não é útil).

(({})[(()()()())])

Esse código empurra 4 e f  - 4 acima de um elemento de pilha f , enquanto deixa esse elemento no lugar. Estamos calculando o formato para a próxima iteração com antecedência (enquanto temos os 4 constantes à mão) e simultaneamente colocando a pilha na ordem correta para as próximas partes do programa: usaremos f como o formato para essa iteração e o 4 é necessário antes disso.

(({})( … )[{}])

Isso salva uma cópia do f  -4 na pilha de trabalho, para que possamos usá-lo na próxima iteração. (O valor de f ainda estará presente nesse ponto, mas ele estará em um lugar estranho na pilha, e mesmo se pudéssemos manobrar para o lugar correto, teríamos que gastar ciclos subtraindo 4 dele, e ciclos de impressão do código para fazer essa subtração. Muito mais fácil simplesmente armazená-lo agora.)

{{}{}((()[()]))}{}

Um teste para ver se o deslocamento é 4 (ou seja, f  - 4 é 0). Se estiver, estamos imprimindo o formatador de sequência de dados, portanto, precisamos executar a sequência de dados e seu formatador 241 vezes, em vez de apenas uma vez nesse deslocamento. O código é bastante simples: se f  -4 for diferente de zero, substitua f  -4 e o próprio 4 por um par de zeros; em ambos os casos, pop o elemento superior da pilha. Agora temos um número acima de f na pilha, 4 (se quisermos imprimir essa iteração 241 vezes) ou 0 (se quisermos imprimi-la apenas uma vez).

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

Esse é um tipo interessante de constante Brain-Flak / Mini-Flak; a fila longa aqui representa o número 60. Você pode estar confuso com a falta de (), que normalmente está em todo o lugar nas constantes Brain-Flak; esse não é um número regular, mas um numeral da igreja, que interpreta os números como uma operação de duplicação. Por exemplo, o número da Igreja para 60, visto aqui, faz 60 cópias de suas contribuições e as combina em um único valor; no Brain-Flak, as únicas coisas que podemos combinar são números regulares, além disso, por isso, acabamos adicionando 60 cópias do topo da pilha e multiplicando o topo da pilha por 60.

Como observação lateral, você pode usar um localizador de números Underload , que gera números de Igreja na sintaxe Underload, para encontrar também o número apropriado no Mini-Flak. Os números de subcarga (exceto zero) usam as operações "elemento duplicado da pilha superior" :e "combinar os dois principais elementos da pilha" *; ambos existem essas operações em Brain-Flak, então você apenas traduzir :para ), *para {}, incluir um {}, e adicione o suficiente (no início para o equilíbrio (isto é usando uma mistura estranha da pilha principal e pilha de trabalho, mas funciona).

Esse fragmento de código específico usa o número da igreja 60 (efetivamente um trecho "multiplique por 60"), junto com um incremento, para gerar a expressão 60 x  + 1. Portanto, se tivéssemos um 4 da etapa anterior, isso nos dará um valor de 241, ou se tivéssemos um 0, obtemos apenas o valor 1, ou seja, isso calcula corretamente o número de iterações necessárias.

A escolha de 241 não é coincidência; foi um valor escolhido para ser a) aproximadamente a duração em que o programa terminaria de qualquer maneira eb) 1 mais que 4 vezes o número da rodada. Os números redondos, 60 neste caso, tendem a ter representações mais curtas como números da Igreja, porque você tem mais flexibilidade nos fatores para copiar. O programa contém preenchimento posteriormente para elevar o comprimento até 241 exatamente.

{
    ({}(
        …
    )[{}()])
}{}

Este é um loop for, como o visto anteriormente, que simplesmente executa o código dentro dele várias vezes igual ao topo da pilha principal (que consome; o contador de loop é armazenado na pilha de trabalho, mas a visibilidade de isso está vinculado ao nível de aninhamento do programa e, portanto, é impossível que qualquer coisa, exceto o próprio loop for, interaja com ele). Na verdade, isso executa a sequência de dados e seu formatador 1 ou 241 vezes e, como agora exibimos todos os valores que estávamos usando para o cálculo do fluxo de controle da pilha principal, temos o formato a ser usado em cima dela, pronto para o formatador a ser usado.

(␀␀!S␠su! … many more comment characters … oq␝qoqoq)

O comentário aqui não é inteiramente sem interesse. Por um lado, existem alguns comandos do Brain-Flak; o )no final é gerado naturalmente como um efeito colateral da maneira como as transições entre os vários segmentos do programa funcionam; portanto, (no início foi adicionado manualmente para equilibrá-lo (e, apesar da duração do comentário, colocar um comentário no interior um ()comando ainda é um ()comando, então tudo o que faz é adicionar 1 ao valor de retorno da sequência de dados e de seu formatador, algo que o loop for ignora completamente).

Mais notavelmente, esses caracteres NUL no início do comentário claramente não são compensados ​​com nada (mesmo a diferença entre +8 e -4 não é suficiente para transformar um (em NUL). Esses são um puro preenchimento para elevar a cadeia de dados de 239 elementos até 241 elementos (que se pagam facilmente: seriam precisos muito mais que dois bytes para gerar 1 vs. 239 em vez de 1 vs. 241 ao calcular o número de iterações necessárias ) NUL foi usado como caractere de preenchimento porque possui o menor ponto de código possível (tornando o código-fonte da cadeia de dados mais curto e, portanto, mais rápido para a saída).

{}({}())

Solte o elemento da pilha superior (o formato que estamos usando), adicione 1 ao próximo (o último caractere a ser produzido, ou seja, o primeiro caractere a ser impresso, da seção do programa que acabamos de formatar). Não precisamos mais do formato antigo (o novo formato está oculto na pilha de trabalho); e o incremento é inofensivo na maioria dos casos, e altera a 'extremidade da representação de origem do formatador de cadeia de dados em um ((necessário na pilha para a próxima vez em que executar o formatador, para formatar a própria cadeia de dados). Precisamos de uma transformação como essa no outro ou na introdução, porque forçar o início de cada elemento formatador de cadeia de dados (o tornaria um pouco mais complexo (pois precisaríamos fechar o (e depois desfazer seu efeito posteriormente), ede alguma forma, precisamos gerar um extra em (algum lugar, porque só temos quase 241 cópias do formatador, não todas as 241 (por isso é melhor que um personagem inofensivo 'seja o que está faltando).

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

Finalmente, o teste de saída do loop. A parte superior atual da pilha principal é o formato necessário para a próxima iteração (que acabou de sair da pilha de trabalho). Isso o copia e adiciona 8 à cópia; o valor resultante será descartado na próxima vez em que ocorrer o loop. No entanto, se apenas imprimirmos a introdução, o deslocamento será -4, portanto o deslocamento para a "próxima iteração" será -8; -8 + 8 é 0, então o loop sairá em vez de continuar na iteração posteriormente.

conta temporária de ais523
fonte
16

128.673.515 ciclos

Experimente online

Explicação

O motivo pelo qual os miniflak quines estão destinados a ser lentos é a falta de acesso aleatório do Miniflak. Para contornar isso, crio um bloco de código que pega um número e retorna um dado. Cada dado representa um único caractere como antes e o código principal simplesmente consulta esse bloco por cada um de cada vez. Isso funciona essencialmente como um bloco de memória de acesso aleatório.

Este bloco de código tem dois requisitos.

  • Ele deve pegar um número e gerar apenas o código de caractere para esse caractere

  • Deve ser fácil reproduzir a tabela de pesquisa pouco a pouco no Brain-Flak

Para construir esse bloco, eu realmente reutilizei um método da minha prova de que o Miniflak é Turing completo. Para cada dado, existe um bloco de código que se parece com isso:

(({}[()])[(())]()){(([({}{})]{}))}{}{(([({}{}(%s))]{}))}{}

Isso subtrai um do número no topo da pilha e se zero empurra %so dado abaixo dela. Como cada peça diminui o tamanho em um se você começar com n na pilha, receberá de volta o enésimo dado.

Isso é agradável e modular, para que possa ser escrito por um programa facilmente.

Em seguida, precisamos configurar a máquina que realmente converte essa memória na fonte. Consiste em 3 partes, como tal:

(([()]())())
{({}[(
  -Look up table-
 )]{})
 1. (({}[()])[(())]()){(([({}{})]{}))}{}{([({}{}(([{}]))(()()()()()))]{})}{}

 2. (({}[()])[(())]()){(([({}{})]{}))}{}{([({}{}
      (({}[(
      ({}[()(((((()()()()()){}){}){}))]{}){({}[()(({}()))]{}){({}[()(({}((((()()()){}){}){}()){}))]{}){({}[()(({}()()))]{}){({}[()(({}(((()()()()())){}{}){}))]{}){([(({}{}()))]{})}}}}}{}
      (({}({}))[({}[{}])])
     )]{}({})[()]))
      ({[()]([({}({}[({})]))]{})}{}()()()()()[(({}({})))]{})
    )]{})}{}

 3. (({}[()])[(())]()){(([({}{})]{}))}{}{([({}{}
     (({}(({}({}))[({}[{}])][(
     ({}[()(
      ([()](((()()[(((((((()()()){})())){}{}){}){})]((((()()()()())){}{}){})([{}]([()()](({})(([{}](()()([()()](((((({}){}){}())){}){}{}))))))))))))
     )]{})
     {({}[()(((({})())[()]))]{})}{}
     (([(((((()()()()){}){}()))){}{}([({})]((({})){}{}))]()()([()()]({}(({})([()]([({}())](({})([({}[()])]()(({})(([()](([({}()())]()({}([()](([((((((()()()())()){}){}){}()){})]({}()(([(((((({})){}){}())){}{})]({}([((((({}())){}){}){}()){}()](([()()])(()()({}(((((({}())())){}{}){}){}([((((({}))){}()){}){}]([((({}[()])){}{}){}]([()()](((((({}())){}{}){}){})(([{}](()()([()()](()()(((((()()()()()){}){}){}()){}()(([((((((()()()())){}){}())){}{})]({}([((((({})()){}){}){}()){}()](([()()])(()()({}(((((({}){}){}())){}){}{}(({})))))))))))))))))))))))))))))))))))))))))))))))
     )]{})[()]))({()()()([({})]{})}{}())
    )]{})}{}

   ({}[()])
}{}{}{}
(([(((((()()()()){}){}())){}{})]((({}))([()]([({}())]({}()([()]((()([()]((()([({})((((()()()()){}){}()){})]()())([({})]({}([()()]({}({}((((()()()()()){}){}){}))))))))))))))))))

A máquina consiste em quatro partes que são executadas em ordem começando com 1 e terminando com 3. Eu as rotulei no código acima. Cada seção também usa o mesmo formato de tabela de pesquisa que eu uso para a codificação. Isso ocorre porque o programa inteiro está contido em um loop e não queremos executar todas as seções toda vez que executamos o loop, por isso colocamos na mesma estrutura de RA e consultamos a seção que desejamos a cada vez.

1

Seção 1 é uma seção de configuração simples.

O programa informa as primeiras consultas na seção 1 e no dado 0. O dado 0 não existe; portanto, em vez de retornar esse valor, ele simplesmente diminui a consulta uma vez para cada dado. Isso é útil porque podemos usar o resultado para determinar o número de dados, que se tornarão importantes nas próximas seções. A Seção 1 registra o número de dados negativizando o resultado e consulta a Seção 2 e o último dado. O único problema é que não podemos consultar a seção 2 diretamente. Como resta outro decréscimo, precisamos consultar uma seção inexistente 5. Na verdade, esse será o caso toda vez que consultarmos uma seção dentro de outra seção. Vou ignorar isso na minha explicação, no entanto, se você estiver procurando um código, lembre-se de que 5 significa voltar uma seção e 4 significa executar a mesma seção novamente.

2

A seção 2 decodifica os dados nos caracteres que compõem o código após o bloco de dados. Cada vez que espera que a pilha apareça da seguinte forma:

Previous query
Result of query
Number of data
Junk we shouldn't touch...

Ele mapeia cada resultado possível (um número de 1 a 6) para um dos seis caracteres válidos do Miniflak ( (){}[]) e o coloca abaixo do número de dados com o "Lixo eletrônico que não devemos tocar". Isso nos dá uma pilha como:

Previous query
Number of data
Junk we shouldn't touch...

A partir daqui, precisamos consultar o próximo dado ou, se tivermos consultado todos, vá para a seção 3. A consulta anterior não é realmente a consulta exata enviada, mas a consulta menos o número de dados no bloco. Isso ocorre porque cada dado diminui a consulta em um, para que a consulta saia bastante confusa. Para gerar a próxima consulta, adicionamos uma cópia do número de dados e subtraímos um. Agora nossa pilha se parece com:

Next query
Number of data
Junk we shouldn't touch...

Se nossa próxima consulta for zero, lemos toda a memória necessária na seção 3, então adicionamos o número de dados à consulta novamente e colocamos um 4 no topo da pilha para passar para a seção 3. Se a próxima consulta não for zero, coloque um 5 na pilha para executar a seção 2 novamente.

3

A seção 3 cria o bloco de dados consultando nossa RAM, assim como a seção 3.

Por uma questão de brevidade, omitirei a maioria dos detalhes de como a seção 3 funciona. É quase idêntico à seção 2, exceto que, em vez de converter cada dado em um caractere, ele converte cada um em um longo pedaço de código que representa sua entrada na RAM. Quando a seção 3 é concluída, ele diz ao programa para sair do loop.

Após a execução do loop, o programa precisa apenas pressionar o primeiro bit da solução ([()]())(()()()()){({}[(. Eu faço isso com o código a seguir implementando técnicas padrão de complexidade Kolmogorov.

(([(((((()()()()){}){}())){}{})]((({}))([()]([({}())]({}()([()]((()([()]((()([({})((((()()()()){}){}()){})]()())([({})]({}([()()]({}({}((((()()()()()){}){}){}))))))))))))))))))

Espero que isso esteja claro. Por favor, comente se você está confuso sobre alguma coisa.

Assistente de Trigo
fonte
Quanto tempo isso leva para ser executado? Cronometra no TIO.
Pavel
@ Pavel Eu não o executo no TIO porque isso seria incrivelmente lento, eu uso o mesmo intérprete que o TIO usa (o ruby ). Demora cerca de 20 minutos para executar em um servidor de rack antigo ao qual tenho acesso. Demora cerca de 15 minutos no Crain-Flak, mas o Crain-Flak não possui sinalizadores de depuração, portanto não posso pontuá-lo sem executá-lo no interpretador Ruby.
Assistente de trigo
@ Pavel Corri novamente e cronometrou. Demorou 30m45.284spara ser concluído em um servidor de extremidade inferior (aproximadamente o equivalente a uma área de trabalho moderna média) usando o intérprete ruby.
Assistente de trigo