Escreva o período de iteração de período mais longo limitado por 500 bytes

16

Seu trabalho é criar o período de iteração de período mais longo , em que o comprimento de cada programa na sequência é limitado por 500 bytes.

Ou seja, se você repetir as seguintes etapas:

  1. Comece com seu programa inicial
  2. Execute o programa atual
  3. Volte ao passo 2

Você retornará ao seu programa original. O número de programas no ciclo é sua pontuação, que você está tentando maximizar.

Nenhum dos programas pode gerar erros. Cada programa também deve ser executado da mesma maneira (por exemplo, versões, implementações, opções de compilador, plataformas, etc ...) diferentes (EDIT: Sim, qualquer estado externo, como o de um gerador de números pseudo-aleatórios, foi incluído no último O estado externo deve ser "redefinido" após cada execução. Se você usar números aleatórios verdadeiros, o pior caso será assumido.)

O que separa esse desafio do período de iteração de período mais longo (que não seja 100 vs 500) é que todo programa no ciclo também deve ter 500 bytes ou menos. Isso significa que o ciclo mais longo possível é (256 ^ 501 - 1) / 255 ou menos. É claro que é um número grande, mas não tão grande em termos de quanto código é necessário para calcular. Portanto, o desafio é usar o maior número possível de possibilidades (256 ^ 501 - 1) / 255, não um desafio de castor ocupado.

Os programas não têm permissão para acessar seu próprio código-fonte. No entanto, um programa vazio é permitido se você desejar (desde que siga as outras regras).

Como a verificação manual dos programas seria difícil, você pode descobrir a pontuação usando métodos teóricos. Você deve incluir uma explicação da pontuação e correção no seu programa. Se você não conseguir descobrir a pontuação, use um limite inferior do número de programas no ciclo como uma pontuação defacto. Você pode atualizar isso à medida que encontrar melhores limites inferiores ou se encontrar a pontuação exata.

Este é , então a pontuação mais alta vence!

EDIT: Recomenda-se que você escreva qual é a sua pontuação em notação científica, para que as respostas sejam mais facilmente comparáveis. É perfeitamente bom ter outras formas de pontuação também, especialmente se elas estiverem mais claramente conectadas ao seu programa. Além disso, os leitores são incentivados a editar respostas anteriores para cumprir isso.

PyRulez
fonte
2
"o ciclo mais longo possível é (256 ^ 501 - 1) / 255 ou menos" --- isso não é necessariamente verdade, o programa pode passar pelo mesmo estado várias vezes antes de retornar ao original se manipular um objeto externo ( como o estado ou a semente do RNG)
JDL
2
@JDL que deve ser contra as regras, IMHO - se ele armazena o estado em outro lugar que não no código-fonte, então não é um quine de iteração adequado.
11119 Nathaniel
1
@ Nathaniel Eu não o categorizaria como estado de armazenamento em outro lugar, é simplesmente usar pontos de entrada que são uma parte válida da linguagem de programação em que é implementado. Provavelmente, qualquer coisa que chama outra função na linguagem de programação está acessando estados que são mantidos fora seu próprio código fonte.
JDL
1
@JDL não, essas são coisas diferentes. Qualquer programa em qualquer idioma obviamente precisa confiar em coisas que são implementadas fora do código fonte, mas o estado de armazenamento fora do código fonte é diferente. Isso significaria que a saída do programa não é uma função determinística do seu código-fonte, mas depende de algum outro contexto externo que foi alterado pelas execuções anteriores. Isso não deve ser permitido em um desafio de quine, IMHO, e a declaração do OP sobre a duração máxima do ciclo indica que ele deveria ser proibido aqui.
11119 Nathaniel
3
@JDL como tenho certeza de que você sabe, em uma linguagem determinística, o ponteiro de instrução armazena apenas o estado durante a execução de um programa, e não entre as invocações dele. Seu exemplo de 5 estados não é possível se a saída do programa for uma função determinística de sua fonte.
11139 Nathaniel

Respostas:

12

Perl 6 , 1263988,86×10835 iterações

$!=Q~~;<say "\$!=Q~{chrs(my@a=[R,] polymod :126[$!.ords]+1: 126 xx*)x?(@a-399)}~;<$_>~~.EVAL">~~.EVAL

Experimente online!

Isso itera através de todas as combinações possíveis dos primeiros 126 bytes de comprimento 398 e menos (excluindo cadeias com bytes NUL iniciais). Se quiser ver que ele realmente retorna à primeira iteração, você pode reduzir o comprimento para 1 alterando o limite dessa forma .

Explicação:

Cada iteração incrementa a string, armazenada no formato base 126 e, em seguida, a converte de volta na base 126. Isso é feito até atingir uma string com o comprimento 399 e, em seguida, redefine a string novamente para esvaziar. Se você está tendo problemas para conceber o número, imagine-o com dez bytes. A partir de 0, incremente até 4 dígitos 1000e redefina. Este é 104-1 iterações (incluindo 0ou string vazia no caso do meu programa).

$!=Q~~;         # Start with an empty string
< ... >~~.EVAL  # Set a string to $_ and EVAL it
  say "\$!=Q~{...}~;<$_>~~.EVAL"   # Print the program with the string replaced by
                       :126[$!.ords]   # The string converted from base 126
                                    +1 # Incremented
          [R,] polymod                : 126 xx*  # Back to base 126
chrs(                                )  # Back to a string
     my@a=                            x?(@a-399)  # Only if it isn't 399 characters
Brincadeira
fonte
1
Uau, você fez isso muito rápido, eu estou quase terminando o meu, mas provavelmente vou terminar amanhã (o meu será em Gol> <>) #
KrystosTheOverlord
Esse cálculo sugere que você superestime sua pontuação. O numerador é quantas cordas de comprimento 397 estão usando 126 símbolos. (I tido para distribuir a fracção na soma desde alfa volfrâmio foi agindo estranho.)
PyRulez
@PyRulez eu acho que o meu número está correto, uma vez que é basicamente repetindo um número base de 126 até 399 dígitos ... Acho que a minha explicação foi off
Jo rei
@ Joking ah sim, acho que a explicação foi o problema. Você alterou 397 para 398, o que faz com que sua pontuação não seja mais superestimada. Você pode estar subestimando (já que você incluiu apenas cordas de comprimento exatamente 398 na partitura), mas tudo bem.
PyRulez 11/02/19
2

Encantos Rúnicos , 64654 106 ; 122 387 -1 ≈ 2.638 × 10 807 iterações

"3X4+kSq'ƃZ,r{1?{1[:1Z%1+:a=+:d=+:3X4+=+:6X2+=+:'€(c*?~1-1kq}͍f1+0Bl1=6*?S1-Skql͗2=4*?{͍]}B͍l1=6*?kS1-Sq]}@

Experimente online!

Alerta: O é exibido incorretamente, deve ser `` (0x80).

Em vez da pilha, use uma sequência e os operadores da pilha modificados com ͍para modificar uma sequência em vez da pilha (consulte a revisão anterior). Como tal, cada caractere é limitado a 1 byte (intervalo de 0 a 127, menos os caracteres problemáticos), mas com mais de 3 vezes o número deles (devido a haver menos clichê de processamento devido à falta de ignorar caracteres combinados Unicode, como bem como outras economias de bytes), ele alcança um número maior de iterações.

Se a codificação como um verdadeiro big endian for permitida (ou seja, ter valores de bytes acima de 127 sem interpor 0x00bytes), isso poderá atingir 251 387 -1 ≈ 4,717 × 10 928 iterações. No entanto, a codificação latina do TIO impede isso, conforme observado por Erik, o Outgolfer, em sua resposta em Python 2. Eu precisaria verificar se funciona localmente antes de reivindicar essa pontuação.

Deve ser capaz de substituir f1+0Bcom '0B(há um unprinting 0x16lá), mas foi-me (coisas não queria filial / saltar / retorno corretamente) lutando, então eu deixei ele sozinho. Isso aumentaria a estrutura de big endian de 387 para 388.

Draco18s não confia mais no SE
fonte
1

DOS COM, 49 bytes, período 2 ^ 3608

00000000  be 31 01 89 f7 b9 f4 02  f9 ac 14 00 aa 39 ce 72  |.1...........9.r|
00000010  f8 31 c9 b4 3c ba 2b 01  cd 21 89 c3 b4 40 b9 f4  |.1..<.+..!...@..|
00000020  01 ba 00 01 cd 21 b4 3e  cd 21 c3 71 2e 63 6f 6d  |.....!.>.!.q.com|
00000030  00                                                |.|

Montagem original a ser criada:

 BITS 16
 ORG 0100h
   mov si, l
   mov di, si
   mov cx, 500 + 0100h
   stc
n: lodsb
   adc al, 0
   stosb
   cmp si, cx
   jb n
   xor cx, cx
   mov ah, 3ch
   mov dx, f
   int 21h
   mov bx, ax
   mov ah, 40h
   mov cx, 500
   mov dx, 0100h
   int 21h
   mov ah, 3eh
   int 21h
   ret
f: db "q.com", 0
l: db 0

Essa pequena joia grava a próxima fase no q.com, em vez da saída padrão, devido a nulos e outras coisas que o terminal não pode lidar. A técnica de root quine é equivalente à stringification e a sala de carga útil é usada como um contador de 3608 bits. Devido à maneira como o DOS funciona, o estado inicial do contador contém detritos do que estava na memória antes de sua primeira execução.

A entrada original de 49 bytes é inacessível; portanto, se você quiser pontuar isso como 500 bytes, vá em frente.

Joshua
fonte
1

C # (Compilador interativo do Visual C #) , sinalizadores: /u:System.Numerics.BigIntegere/r:System.Numerics

Pontuação: 10 332

Graças ao JoKing, que aumentou minha pontuação de 10 255 * 2 - 1 para agora!

var i=Parse("0");var s="var i=Parse({0}{2}{0});var s={0}{1}{0};Write(s,(char)34,s,(++i).ToString().Length<333?i:0);";Write(s,(char)34,s,(++i).ToString().Length<333?i:0);

Experimente online!

Explicação

Incrementa um BigInteger a cada iteração, até que o comprimento se torne muito grande, e nesse caso, instantaneamente voltamos ao quine original.

//The BigInteger that will be incremented
var i=Parse("0");
//The string that encodes the quine
var s="var i=Parse({0}{2}{0});var s={0}{1}{0};Write(s,(char)34,s,(++i).ToString().Length<333?i:0);";
//Print out the string, with every {0} replaced with quotes and the {1} replaced with the original string
Write(s,(char)34,s,
//And the {2} is replaced to the BigInteger+1 if the BigInteger wouldn't be too long, else 0
(++i).ToString().Length<333?i:0);
Modalidade de ignorância
fonte
1

252219

#coding=L1
s=""""""
for i in range(220-len(s.lstrip("ÿ")))[:219]:s=s[:i]+chr(ord(s[i])%255-~(s[i]in"!$&"))+s[i+1:]
S='#coding=L1\ns="""%s"""\nfor i in range(220-len(s.lstrip("\xff")))[:219]:s=s[:i]+chr(ord(s[i])%%%%255-~(s[i]in"!$&"))+s[i+1:]\nS=%%r;print S%%%%s%%%%S';print S%s%S

Observe que há uma nova linha à direita. Pode ser removido acima se o marcador de sintaxe forçar a entrada.

Infelizmente, você não pode executar este programa no TIO, pois está codificado no Latin-1.

Acima, scontém 219 0x01 bytes. Após a execução do programa, sua fonte é impressa, exceto por uma diferença: sfoi incrementada como um número big endian da base 252, portanto, seu caractere mais à esquerda foi "incrementado" para 0x02. Os bytes 0x00, 0x22, 0x25 e 0x5C são evitados; portanto, se algum caractere da sequência se tornar um desses após a incrementação, o próprio caractere será incrementado novamente.

  • 0x00 (nulo): um arquivo de origem Python não pode conter caracteres nulos.
  • 0x22 ( "): existe o risco de três bytes 0x22 se formarem em uma linha, ou seja """, ou o último caractere da cadeia se tornar ", para que a cadeia seja fechada prematuramente.
  • 0x25 ( %): a formatação de string do tipo printf é usada antes da conclusão do esqueleto quine, portanto, um %não adjacente a outro %in scausará problemas. Infelizmente, não é possível reordenar a formatação para evitar essa ressalva.
  • 0x5C ( \): existe a possibilidade de que ele \seja usado como uma marca de escape na string, em vez de literalmente, por isso é evitado.

Portanto, 252 de 256 bytes são utilizáveis. Se scontiver 219 0xFF ( ÿ) bytes, é simplesmente revertido para 219 0x01 bytes, concluindo assim o ciclo.

252219

252219=8067118401622543607173815381864126969021321378412714150085501148172081568355283332551767558738710128769977220628694979838777041634307806013053042518663967641130129748108465109552157004184441957823830340121790768004370530578658229253323149648902557120331892465175873053680188287802536817909195292338112618632542000472094347226540339409672851252596442228662174845397731175044304251123874046626291460659909127172435776359148724655575878680270692451120531744950544969860952702932354413767504109600742385916705785109741289800204288

Erik, o Outgolfer
fonte
1

2512262.1×10542

  • 251 39 dependência removida deText
  • 251 122 função incrementadora de golfe
  • 251 128 cadeias combinadas de origem de prefixo e sufixo
  • 251 188 dependência removida deGast.GenLibTest

Apresentado no formato xxd devido a UTF-8 não imprimível / inválido:

00000000: 6d6f 6475 6c65 2071 3b69 6d70 6f72 7420  module q;import 
00000010: 5374 6445 6e76 3b53 7461 7274 3d28 7325  StdEnv;Start=(s%
00000020: 2830 2c34 3129 2c3f 5b27 0101 0101 0101  (0,41),?['......
00000030: 0101 0101 0101 0101 0101 0101 0101 0101  ................
00000040: 0101 0101 0101 0101 0101 0101 0101 0101  ................
00000050: 0101 0101 0101 0101 0101 0101 0101 0101  ................
00000060: 0101 0101 0101 0101 0101 0101 0101 0101  ................
00000070: 0101 0101 0101 0101 0101 0101 0101 0101  ................
00000080: 0101 0101 0101 0101 0101 0101 0101 0101  ................
00000090: 0101 0101 0101 0101 0101 0101 0101 0101  ................
000000a0: 0101 0101 0101 0101 0101 0101 0101 0101  ................
000000b0: 0101 0101 0101 0101 0101 0101 0101 0101  ................
000000c0: 0101 0101 0101 0101 0101 0101 0101 0101  ................
000000d0: 0101 0101 0101 0101 0101 0101 0101 0101  ................
000000e0: 0101 0101 0101 0101 0101 0101 0101 0101  ................
000000f0: 0101 0101 0101 0101 0101 0101 0101 0101  ................
00000100: 0101 0101 0101 0101 0101 0101 275d 2c73  ............'],s
00000110: 2528 3432 2c39 3939 292c 712c 732c 7129  %(42,999),q,s,q)
00000120: 3b71 3d69 6e63 2721 273b 3f5b 683a 745d  ;q=inc'!';?[h:t]
00000130: 2363 3d68 2b69 6628 616e 7928 283d 3d29  #c=h+if(any((==)
00000140: 6829 5b27 ff09 0c26 5b27 5d29 2702 2727  h)['...&['])'.''
00000150: 0127 3d5b 633a 6966 2863 3e68 2969 643f  .'=[c:if(c>h)id?
00000160: 745d 3b3f 653d 653b 733d 226d 6f64 756c  t];?e=e;s="modul
00000170: 6520 713b 696d 706f 7274 2053 7464 456e  e q;import StdEn
00000180: 763b 5374 6172 743d 2873 2528 302c 3431  v;Start=(s%(0,41
00000190: 292c 3f5b 2727 5d2c 7325 2834 322c 3939  ),?[''],s%(42,99
000001a0: 3929 2c71 2c73 2c71 293b 713d 696e 6327  9),q,s,q);q=inc'
000001b0: 2127 3b3f 5b68 3a74 5d23 633d 682b 6966  !';?[h:t]#c=h+if
000001c0: 2861 6e79 2828 3d3d 2968 295b 27ff 090c  (any((==)h)['...
000001d0: 265b 275d 2927 0227 2701 273d 5b63 3a69  &['])'.''.'=[c:i
000001e0: 6628 633e 6829 6964 3f74 5d3b 3f65 3d65  f(c>h)id?t];?e=e
000001f0: 3b73 3d22                                ;s="

Experimente online!

Incrementa uma cadeia de 226-byte através de todos os valores de byte excluindo \0, \n, \r, 'e \.

A razão pela qual evitamos esses caracteres é:

  • \0 irrita o compilador
  • \ne \rnão pode aparecer nas listas
  • ' terminaria a lista
  • \ pode causar problemas se vier antes de um caractere escapável

Uma vez que a string é all \377s, ela se agrupa em todos os \001s, fornecendo o programa original.

Furioso
fonte
A saída (pelo menos no TIO) é o caractere com valor ordinal 128, mas composto pelos dois bytes C2 80. É o mesmo que o comportamento na sua máquina local?
Jo rei
1
@ JoKing Oh, não, recebo um único byte na minha máquina. O TIO gerencia a saída quando não é UTF-8 válido (e os arquivos de entrada também).
Οurous
1
@JoKing Alterei a resposta para um novo formato que torna possível ver o comportamento correto no TIO.
005 Οurous
0

Gol> <> , 70 bytes, 39039000 iterações

":1=l8:*6+=S&Q~:'~'=Q~~'H#'||lPaa*5*=?1:1=Q$~$~|:1)lPaa*5*(Q?:|r2ssH##

Uau, isso é muito menor do que eu pensava que seria ... Próximo passo! Fazendo com que tenha mais iterações !!!

Experimente online!

KrystosO Soberano
fonte
não parece excluir qualquer coisa uma vez que atinge 500, apenas acrescenta um byte NUL
Jo rei
Isso funciona mesmo? Eu não posso obter o "incrementar o último char" para o trabalho
ASCII-only
@ Somente ASCII Agora, isso funciona, desculpe antes, eu tinha estragado uma seção enquanto trabalhava na correção da coisa toda. Funciona agora, desculpe pela inconveniência !!!
KrystosTheOverlord 11/02/19
@JoKing O byte NUL é o processo de exclusão, agora o programa deve excluir até quase desaparecer, excluir o NUL e incrementar o último caractere, se for um ~, depois será convertido para um '#', retornando ao normal!!!
KrystosTheOverlord 11/02/19