16

Ваша задача - создать самую длинную итерацию периода , в которой длина каждой программы в последовательности ограничена 500 байтами.

То есть, если вы повторите следующие шаги:

Начните с вашей начальной программы
Запустите текущую программу
Вернитесь к шагу 2

В конечном итоге вы вернетесь к своей первоначальной программе. Количество программ в цикле - это ваш счет, который вы пытаетесь максимизировать.

Ни одна из программ не может вызвать каких-либо ошибок. Каждая программа должна также выполняться одинаково (например, без разных версий, реализаций, опций компилятора, платформ и т. Д.) (РЕДАКТИРОВАТЬ: Да, любое внешнее состояние, такое как состояние генератора псевдослучайных чисел, было включено в последний Заявление. Внешнее состояние должно быть «сброшено» после каждого запуска. Если вы используете истинные случайные числа, предполагается худший случай.)

Что отличает эту задачу от самой длинной итерации за период (кроме 100 против 500), так это то, что каждая программа в цикле также должна иметь размер 500 байт или меньше. Это означает, что самый длинный возможный цикл равен (256 ^ 501 - 1) / 255 или меньше. Это, конечно, большое число, но не такое большое с точки зрения того, сколько кода требуется для вычисления. Таким образом, задача состоит в том, чтобы использовать как можно больше (256 ^ 501 - 1) / 255 возможностей, а не занятие занятого бобра.

Программы не имеют доступа к своему исходному коду. Однако пустая программа будет разрешена , если вы хотите ( до тех пор , пока вы будете следовать другим правилам).

Так как проверять программы вручную было бы сложно, вы можете вычислить счет, используя теоретические методы. Вы должны включить объяснение оценки и правильности в вашу программу. Если вы не можете определить счет, вы можете вместо этого использовать нижнюю границу количества программ в цикле в качестве значения по умолчанию. Вам разрешается обновлять это по мере того, как вы находите лучшие нижние границы, или если вы находите точную фактическую оценку.

Это вызов кода , поэтому выигрывает самый высокий балл!

РЕДАКТИРОВАТЬ: Рекомендуется, чтобы вы написали, что ваш счет в научной записи, чтобы ответы были легче сопоставимы. Прекрасно иметь и другие формы партитуры, особенно если они более четко связаны с вашей программой. Также читателям предлагается отредактировать предыдущие ответы, чтобы соответствовать этому.

code-challenge quine code-generation PyRulez
источник

2

«самый длинный возможный цикл равен (256 ^ 501 - 1) / 255 или меньше» - это не обязательно так, программа может проходить через одно и то же состояние несколько раз, прежде чем вернуться к исходному состоянию, если она манипулирует внешним объектом ( такие как состояние ГСЧ или семя)

JDL

2

@JDL, который должен быть против правил, ИМХО - если он хранит состояние в другом месте, чем в исходном коде, то это не правильная итерирующая квинна.

Натаниэль

1

@Nathaniel Я бы не классифицировал это как сохранение состояния в другом месте, он просто использует точки входа, которые являются допустимой частью языка программирования, в котором он реализован. Возможно, все, что вызывает другую функцию в языке программирования, имеет доступ к состояниям, которые хранятся вне свой собственный исходный код.

JDL

1

@ JDL нет, это разные вещи. Любая программа на любом языке, очевидно, должна полагаться на вещи, которые реализованы вне исходного кода, но сохранение состояния вне исходного кода отличается. Это означало бы, что вывод программы не является детерминированной функцией ее исходного кода, а вместо этого зависит от некоторого другого внешнего контекста, который был изменен предыдущими запусками. Это не должно быть разрешено при вызове quine, ИМХО, и утверждение OP о максимальной длине цикла указывает на то, что оно было намерено запретить здесь.

Натаниэль

3

@JDL, как я уверен, вы знаете, что в детерминистском языке указатель инструкций сохраняет состояние только во время выполнения программы, а не между ее вызовами. Ваш пример с 5 состояниями невозможен, если вывод программы является детерминированной функцией ее источника.

Натаниэль

12

Perl 6 , $126^{398} \approx 8.86 \times 10^{835}$ итераций

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

Попробуйте онлайн!

Это повторяет все возможные комбинации первых 126 байтов длиной 398 и ниже (исключая строки с ведущими байтами NUL). Если вы хотите увидеть, что он действительно возвращается к первой итерации, вы можете уменьшить длину до 1, изменив ограничение следующим образом .

Объяснение:

Каждая итерация увеличивает строку, сохраненную в форме базы 126, а затем преобразует ее обратно в базу 126. Она делает это до тех пор, пока не достигнет строки длиной 399, а затем сбрасывает строку обратно до пустой снова. Если у вас возникли проблемы с концептуализацией числа, представьте вместо этого десять байтов. Начиная с 0, увеличивайте до 4 цифр 1000и сбрасывайте. Это $10^{4-1}$ итераций (включая 0или пустую строку в случае моей программы).

$!=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

Джо Кинг
источник

1

Вау, ты сделал это очень быстро, я почти закончил с моим, но я, вероятно, закончу это завтра (мой будет в Голе <<>)

KrystosTheOverlord

Этот расчет предполагает, что вы переоценили свой счет. Числитель - это количество строк длиной 397 с использованием 126 символов. (Я должен был распределить дробь в сумму, так как вольфрам альфа действовала странно.)

PyRulez

@PyRulez Я думаю, что мой номер правильный, так как он в основном повторяет базовый номер 126 до 399 цифр ... Я думаю, что мое объяснение было

Джо Кинг,

@ JoKing ах да, я думаю, что объяснение было проблемой. Вы изменили 397 на 398, что делает ваш счет больше не завышенным. Вы можете недооценивать его (поскольку вы включили в партитуру только строки длиной ровно 398), но это нормально.

PyRulez

2

Рунические чары , 64654 ¹⁰⁶ ; 122 ³⁸⁷ -1 ≈ 2,638 × 10 ⁸⁰⁷ итераций

"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]}@

Попробуйте онлайн!

_{Предупреждение: €неправильно отображается, оно должно быть `` (0x80).}

Вместо стека используйте строку и операторы стека, измененные с помощью, ͍чтобы изменить строку, а не стек (см. Предыдущую версию). Таким образом, каждый символ ограничен 1 байтом (диапазон 0-127, минус проблемные символы), но их более чем в 3 раза больше (из-за меньшего количества шаблонов обработки из-за отсутствия необходимости пропускать символы объединения Юникода, как а также некоторые другие байтовые сбережения) достигается большее количество итераций.

Если разрешено кодирование в качестве истинного байта с обратным порядком байтов (то есть, если байтовые значения выше 127 без пересекающихся 0x00байтов), это может обеспечить 251 ³⁸⁷ -1 ≈ 4,717 × 10 ⁹²⁸ итераций. Однако латинская кодировка TIO предотвращает это, как отметил Эрик Аутгольфер в своем ответе на Python 2. Мне нужно проверить, работает ли он локально, прежде чем претендовать на этот счет.

Должен быть в состоянии заменить f1+0Bна '0B(там есть распечатка 0x16), но он боролся со мной (вещи не хотели правильно разветвляться / пропускать / возвращаться), поэтому я оставил это в покое. Это поднимет структуру с прямым порядком байтов с 387 до 388.

Draco18s больше не доверяет SE
источник

1

DOS COM, 49 байтов, период 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                                                |.|

Оригинальная сборка для создания:

 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

Эта маленькая жемчужина записывает следующий этап в q.com, а не стандартный вывод из-за нулей и других вещей, которые терминал не может обработать. Техника корневых квин эквивалентна строковому форматированию, а комната полезной нагрузки используется как 3608-битный счетчик. Благодаря тому, как работает DOS, начальное состояние счетчика содержит мусор из того, что было в памяти до его первого выполнения.

Исходный 49-байтовый ввод недоступен, поэтому, если вы хотите набрать 500 байт, вы можете продолжить.

Джошуа
источник

1

C # (интерактивный компилятор Visual C #) , флаги: `/u:System.Numerics.BigInteger`и`/r:System.Numerics`

Оценка: 10 ³³²

Спасибо JoKing, который увеличил мой счет с 10 ²⁵⁵ * 2 - 1 до сих пор!

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);

Попробуйте онлайн!

объяснение

Увеличивает BigInteger каждую итерацию, пока его длина не станет слишком большой, что в этом случае мы немедленно возвращаем к исходной квине.

//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);

Воплощение невежества
источник

1

Python 2 , 500 байт, $252^{219}$

#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

Обратите внимание, что есть завершающий перевод строки. Это может быть удалено выше, если подсветка синтаксиса пробивается внутрь.

К сожалению, вы не можете выполнить эту программу в TIO, так как она закодирована в Latin-1.

Выше, sсодержит 219 0x01 байтов. После запуска программы печатается ее источник, за исключением одного отличия: sбыл увеличен как число с прямым порядком байтов в 252, поэтому его самый левый символ был «увеличен» до 0x02. Байты 0x00, 0x22, 0x25 и 0x5C исключаются, поэтому, если какой-либо символ строки становится одним из символов после увеличения, сам символ снова увеличивается.

0x00 (ноль): исходный файл Python не может содержать нулевые символы.
0x22 ( "): Существует опасность формирования трех байтов 0x22 в строке, т. Е. """Последнего символа строки, становящегося "так, что строка будет преждевременно закрыта.
0x25 ( %): Printf типа строки форматирования используется до завершения Куайна скелета, поэтому %не рядом с другим %ин sвызовут проблемы. К сожалению, невозможно изменить порядок форматирования, чтобы избежать этого предостережения.
0x5C ( \): существует вероятность того, что \вместо строки дословно используется escape-знак в строке, поэтому его избегают.

Таким образом, 252 из 256 байтов могут быть использованы. Если sсодержит 219 0xFF ( ÿ) байт, он просто возвращается к 219 0x01 байт, что завершает цикл.

Учитывая вышеизложенное, имеем $252^{219}$ возможные строки, следовательно, так много программ в целом.

$252^{219}=8067118401622543607173815381864126969021321378412714150085501148172\\081568355283332551767558738710128769977220628694979838777041634307806013053\\042518663967641130129748108465109552157004184441957823830340121790768004370\\530578658229253323149648902557120331892465175873053680188287802536817909195\\292338112618632542000472094347226540339409672851252596442228662174845397731\\175044304251123874046626291460659909127172435776359148724655575878680270692\\451120531744950544969860952702932354413767504109600742385916705785109741289\\800204288$

Эрик Outgolfer
источник

1

Чистый , $251^{226} \approx 2.1 \times 10^{542}$

~~251 ³⁹~~ убрал зависимость отText
~~251 ¹²²~~ функция приращения в гольфе
~~251 ¹²⁸~~ комбинированных исходных строк префикса и суффикса
~~251 ¹⁸⁸~~ убрал зависимость отGast.GenLibTest

Представлено в формате xxd из-за непечатных / недействительных UTF-8:

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="

Попробуйте онлайн!

Приращивает 226-байтовую строку через все значения байт за исключением \0, \n, \r, 'и \.

Причина, по которой мы избегаем этих символов:

\0 раздражает компилятор
\nи \rне может появиться в списках
' закончил бы чарлист
\ может вызвать проблемы, если он предшествует экранируемому символу

Как только строка становится все \377s, она оборачивается на все \001s, давая оригинальную программу.

Οurous
источник

Выход (по крайней мере, для TIO) - это символ с порядковым значением 128, но состоящий из двух байтов C2 80. Это то же самое, что и поведение на вашем локальном компьютере?

Джо Кинг,

1

@ JoKing О нет, я получил один байт на моей машине. TIO изменяет вывод, когда он не является допустимым UTF-8 (и входные файлы тоже).

Οurous

1

@JoKing Я изменил ответ на новый формат, который позволяет увидеть правильное поведение на TIO.

Οurous

0

Gol> <> , 70 байт, 39039000 итераций

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

Вау, это намного ниже, чем я думал, что будет ... Следующий шаг! У этого есть больше итераций !!!

Попробуйте онлайн!

KrystosTheOverlord
источник

кажется, что он ничего не удаляет, когда достигает 500, просто добавляет NUL-байт

Джо Кинг

Это вообще работает? Я не могу заставить "увеличивать последний символ" на работу

только ASCII

@ ASCII-only Теперь это работает, извините за ранее, я испортил раздел, работая над исправлением всего этого. Работает сейчас, извините за неудобства !!!

KrystosTheOverlord

@JoKing Байт NUL - это процесс удаления, теперь программа должна удалять, пока он почти не исчезает, затем удалять NUL и увеличивать последний символ, если он равен ~, тогда он будет преобразован в '#', возвращая обратно к нормальной жизни !!!

KrystosTheOverlord

Напишите самую длинную итерацию периода, ограниченную 500 байтами

Ответы:

Perl 6 , $126^{398} \approx 8.86 \times 10^{835}$ итераций

Объяснение:

Рунические чары , 64654 ¹⁰⁶ ; 122 ³⁸⁷ -1 ≈ 2,638 × 10 ⁸⁰⁷ итераций

DOS COM, 49 байтов, период 2 ^ 3608

C # (интерактивный компилятор Visual C #) , флаги: `/u:System.Numerics.BigInteger`и`/r:System.Numerics`

Оценка: 10 ³³²

объяснение

Python 2 , 500 байт, $252^{219}$

Чистый , $251^{226} \approx 2.1 \times 10^{542}$

Gol> <> , 70 байт, 39039000 итераций

Напишите самую длинную итерацию периода, ограниченную 500 байтами

Ответы:

Perl 6 , 126398≈ 8,86 × 10835126398≈8,86×10835126^{398} \approx 8.86 \times 10^{835} итераций

Объяснение:

Рунические чары , 64654 106 ; 122 387 -1 ≈ 2,638 × 10 807 итераций

DOS COM, 49 байтов, период 2 ^ 3608

C # (интерактивный компилятор Visual C #) , флаги: /u:System.Numerics.BigIntegerи/r:System.Numerics

Оценка: 10 332

объяснение

Python 2 , 500 байт,252219252219252^{219}

Чистый ,251226≈ 2,1 × 10542251226≈2,1×10542251^{226} \approx 2.1 \times 10^{542}

Gol> <> , 70 байт, 39039000 итераций

Perl 6 , $126^{398} \approx 8.86 \times 10^{835}$ итераций

Рунические чары , 64654 ¹⁰⁶ ; 122 ³⁸⁷ -1 ≈ 2,638 × 10 ⁸⁰⁷ итераций

C # (интерактивный компилятор Visual C #) , флаги: `/u:System.Numerics.BigInteger`и`/r:System.Numerics`

Оценка: 10 ³³²

Python 2 , 500 байт, $252^{219}$

Чистый , $251^{226} \approx 2.1 \times 10^{542}$