Серпинский кодекс

47

Напишите прямоугольный блок текста, который при размещении в ковре Серпинского , используя блоки одинакового размера для пустых порций, создает программу, которая выводит номер итерации ковра.

Например, если ваш текстовый блок

TXT
BLK

затем запустить программу

TXTTXTTXT
BLKBLKBLK
TXT   TXT
BLK   BLK
TXTTXTTXT
BLKBLKBLK

должен выводить, 1потому что форма программы представляет первую итерацию ковра Серпинского.

Точно так же работает

TXTTXTTXTTXTTXTTXTTXTTXTTXT
BLKBLKBLKBLKBLKBLKBLKBLKBLK
TXT   TXTTXT   TXTTXT   TXT
BLK   BLKBLK   BLKBLK   BLK
TXTTXTTXTTXTTXTTXTTXTTXTTXT
BLKBLKBLKBLKBLKBLKBLKBLKBLK
TXTTXTTXT         TXTTXTTXT
BLKBLKBLK         BLKBLKBLK
TXT   TXT         TXT   TXT
BLK   BLK         BLK   BLK
TXTTXTTXT         TXTTXTTXT
BLKBLKBLK         BLKBLKBLK
TXTTXTTXTTXTTXTTXTTXTTXTTXT
BLKBLKBLKBLKBLKBLKBLKBLKBLK
TXT   TXTTXT   TXTTXT   TXT
BLK   BLKBLK   BLKBLK   BLK
TXTTXTTXTTXTTXTTXTTXTTXTTXT
BLKBLKBLKBLKBLKBLKBLKBLKBLK

должен вывести 2, потому что это форма второй итерации Серпинского ковра.

Запуск текстового блока как есть

TXT
BLK

должен выводить, 0потому что это можно считать нулевой итерацией.

Это должно работать для всех дальнейших итераций. (По крайней мере, теоретически, если на компьютере есть память и все.)

подробности

  • Программы не могут читать или получать доступ к информации об их исходном коде. Относитесь к этому как к строгой проблеме Куайна.
  • Вывод идет в стандартный вывод или подобную альтернативу. Выведите только число и дополнительный завершающий перевод строки. Там нет ввода.
  • Текстовый блок может содержать любые символы, которые не считаются символами конца строки . Текстовый блок может содержать пробелы.
  • «Пустое пространство» в ковре должно состоять исключительно из символов пробела .
  • При желании вы можете предположить, что все программы имеют завершающий перевод строки.

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

<style>#o,#i{font-family:monospace;}</style><script>function c(e){e=e.split("\n");for(var n=new Array(3*e.length),t=0;t<n.length;t++){var l=t%e.length;n[t]=e[l]+(t>=e.length&&t<2*e.length?e[l].replace(/./g," "):e[l])+e[l]}return n.join("\n")}function f(){for(i=document.getElementById("i").value,n=parseInt(document.getElementById("n").value);n>0;)i=c(i),n--;document.getElementById("o").value=i}</script><textarea id='i'placeholder='code block...'rows='8'cols='32'></textarea><br>Iterations <input id='n'type='text' value='1'><br><br><button type='button'onclick='f()'>Generate</button><br><br><textarea id='o'placeholder='output...'rows='8'cols='32'style='background-color:#eee'readonly></textarea>

счет

Представление, начальный текстовый блок которого наименьший по площади (ширина умножается на высоту), является победителем. TXT\nBLKПример 3 на 2 на балл 6. ( в основном короткие выигрыши коды, поэтому кодовое поле для тега.)

Tiebreaker переходит к представлению, которое использует наименьшее количество отдельных символов в своем текстовом блоке. Если все еще связаны, ответ опубликовал первые победы.

Кальвин Хобби
источник

Ответы:

23

CJam, 9 байт

Я думаю, что это может быть улучшено, но сейчас давайте пойдем с этим ...

];U):U8mL

Как это работает :

];             "Wrap everything on stack in an array and discard it";
               "Before this point, the only thing on array can be the log 8 result of";
               "last updated value of U, or nothing, if its the first code";
  U):U         "Increment by 1 and update the value of U (which is pre initialized to 0)";
      8mL      "Take log base 8 of U. This is the property of Sierpinski carpet that";
               "the occurrence of the code is 8 to the power iteration count, indexed 0";

Попробуйте онлайн здесь

оптимизатор
источник
35

пит - 32 * 6 = 192

введите описание изображения здесь

Я заполнил пустое пространство шаблоном проверки. Я думаю, что это делает Серпинского немного более трогательным.

Вот вторая итерация: введите описание изображения здесь

оригинал: 32 * 7

введите описание изображения здесь

captncraig
источник
19

> <> , 11 * 2 = 22

";n"00pbi1v
+$3*:@3-0.>

Здесь мы применяем другой подход, используя функциональность прыжка / телепортации> <>.

Программа выполняет только блоки в верхнем ряду, выполняя 1-й / 2-й блок, затем 3-й / 4-й блоки, 9-й / 10-й блоки, 27-й / 28-й блоки и т. Д. (Возрастая в степени 3). Поскольку в верхней строке есть 3^nблоки, только nблоки выполняются до того, как программа вернется к началу, выведет верх стека и остановится (из-за nинструкции, размещенной через p).

Программа использует правило «Нет ввода.», Так как iкоманда помещает -1 в стек, если выполняется EOF. Таким образом, чтобы проверить это, вам нужно передать в пустой файл.


Предыдущее представление, 7 * 4 = 28

l"v"10p
v>:1=?v
3  ;n{<
<^}+1{,

Первая строка непрерывно увеличивает длину стека для каждого блока и изменяет первую "кавычку на стрелку вниз, vиспользуя команду pput. К моменту окончания первой строки стек выглядит так:

[0, 1, 2, .., 3^n]

(Обратите внимание, что инициал lиспользуется дважды.)

Последние три строки подсчитывают, сколько раз нам нужно разделить на 3, прежде чем мы нажмем 1 (поскольку> <> не имеет функции журнала). Нижний ноль используется для отслеживания счета.

Sp3000
источник
13

Perl, 26

$_+=.91/++$n;
die int."\n";

При этом используется ряд гармоник для аппроксимации логарифма основания 3. Я думаю, что это работает, но я только попробовал это для небольших чисел. Спасибо брезгливому ossifrage за идею использования die.

Старая версия (34):

$n--or$n=3**$s++;
print$s-1if!$o++;
GRC
источник
Это очень аккуратно!
брезгливое оссифраж
10

Perl, 30 (15 × 2)

Прежде всего, я собираюсь утверждать, что 10 итераций - разумный предел, а не 2 32 . После 10 итераций программа, состоящая из N байтов, будет расширена до ( N × 3 20 ) байтов (плюс разрывы строк), что превышает 3 гигабайта даже для N = 1. 32-битная архитектура была бы полностью неспособна обрабатывать 11 итераций. (И, очевидно, во Вселенной не хватает частиц для 2 32 итераций).

Итак, вот мое решение:

$n++; $_=log$n;
print int;exit;

Это работает путем увеличения переменной $nв первой строке и вычисления ее логарифма на каждом шаге. Вторая строка печатает целую часть этого логарифма и выходит.

Простой логарифм с основанием e (2.718 ..) достаточно близок, чтобы дать правильные результаты для первых 10 итераций.

брезгливый оссифраж
источник
2
Согласно ОП, теоретически он должен работать для всех итераций.
Натан Меррилл
2
@NathanMerrill Хорошо, хорошо. Но чтобы соответствовать оригинальной спецификации, он также должен был работать в альтернативных вселенных. Вопрос был отредактирован с тех пор.
брезгливое оссифраж
Я изменил вопрос из-за хороших замечаний, высказанных здесь. Я согласен, что использование натурального бревна - это скорее серая область, но, честно говоря, я не слишком обеспокоен, поскольку это не победа.
Увлечения Кальвина
Большинство из этих представлений сохраняют контроль только в верхнем ряду 3 ^ nx 1 плиток. Если вы просто сгенерируете этот сегмент ковра, вы можете масштабироваться немного дальше. Почти наверняка, где ошибки округления сломают вас.
captncraig
1
Как я уже упоминал, в первоначальном вопросе был задан код, который можно масштабировать до «разумного» числа итераций (до 2 ^ 32) . Если вы выполните математику, то обнаружите, что даже один байт расширится до 10 ^ 4098440370 байт после такого количества итераций. Я предложил ответ, который мне показался более разумным, но с тех пор слово «разумный» исчезло из вопроса: - /. Смотри, я сделал здесь Просто понизьте этот ответ, если он вам не нравится.
брезгливое оссифраж
9

Golfscript, 9 * 2 = 18

0+       
,3base,(}

(Обратите внимание, что в первой строке есть пробелы, чтобы сделать ее прямоугольной)

Я не мог найти функцию журнала для Golfscript, поэтому baseпришлось сделать.

Golfscript начинается с пустой строки, поэтому 0+просто увеличивает длину строки на 1 (по приведению). К тому времени, когда первая строка закончится, в стеке будет строка длины 3^n, которую мы возьмем за основу журнала 3, прежде чем будем суперкомментировать. nзатем автоматически печатается.

Sp3000
источник
Вы можете сохранить 2 символа, используя целое число вместо строки и, следовательно, сохранив ,во второй строке. Первая строка 0or):; вторая линия 3base,(}. Другая очевидная цель - (вторая строка. Это сложнее, но также можно удалить, заменив первую строку 1+~abs(на прямоугольник 7 * 2.
Питер Тейлор
8

С, 12х8 = 96

Вдохновленный @ciamej, я уменьшил его. Он использует это деление на 3 трюка, плюс понимание того, что ковер эффективно преобразует if в цикл while.

Код был протестирован на gcc / Ubuntu для итераций до 3.

#ifndef A //
#define A //
x;main(a){//
a++;/*    */
if(a/=3)x++;
printf(   //
"%d",x);} //
#endif    //

Предыдущее решение: C, 11x12

Не победитель размера, но эй, это C.

Он находит log2 числа блоков путем сдвига битов, затем использует некоторые магические числа и усечение int для оценки log3. Математика должна работать до 26 итераций (42-битное число).

#ifndef A//
#define A//
int n=0;//_
int main//_
(v,c){//___
n+=1;/*..*/
while(n//__
>>=1)v++;//
n=.3+.62*v;
printf(//__
"%d",n);}//
#endif//__
AShelly
источник
Привет, я опубликовал сокращенную версию вашего решения.
ciamej
Хороший трюк с этим, если! ;)
ciamej
6

CJam, 9 байт

Идея использования ]исходит от Оптимизатора, но он использует совершенно другой метод для подсчета.

X~]:X,8mL

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

Как это устроено:

X~          "push X and dump its contents.  On the zeroth iteration, X is a single number, but later is it an array.";
  ]         "wrap everything into an array.  The stack would contain the contents of X plus the result of the previous instance of the code";
   :X       "store this array back into X.  X is now 1 element longer";
     ,      "take the length of X";
      8mL   "do a base-8 logarithm of it";

Два других 9-байтовых решения

]X+:X,8mL

],X+:X8mL
PhiNotPi
источник
Это на самом деле связывает Оптимизатор даже с тай-брейком. : P Tiebreakerbreaker: ранний пост побеждает.
Увлечения Кэлвина
Я думаю, что это хорошее решение. Я не смог побить 9 символов.
PhiNotPi
Я думаю, что общий подход один и тот же (и который является единственным подходом, который имеет смысл) - есть переменная, как-то увеличить ее на 1.
Оптимизатор
4

Python 2, 15 * 3 = 45

m=n=0;E=exit  ;
m+=1;n+=m>3**n;
print n;E()   ;

Еще одна реализация идеи «счесть первый ряд-потом-журнал-три-и-выйти». Вероятно, еще можно играть в гольф чуть больше.

Sp3000
источник
2

до н.э., 2 * 16 + 1 = 33

Дополнительные +1 в счете, потому что -lтребуется опция bc:

a+=1;          
l(a)/l(3);halt;
Цифровая травма
источник
2

Golfscript, 7 * 2 = 14

1+~abs(
3base,}

Это вдохновляет Sp3000 в ответ , и , в частности , стремлением оптимизировать длинную вторую линию. 3base,настолько короток, насколько логарифм с базой 3 попадет в GS, и супер-комментарий }явно оптимален.

Для первой строки требуется отобразить пустую строку ''из исходного stdin в 0, а затем отобразить каждое неотрицательное целое число в его преемнике. Таким образом, мы заканчиваем первую строку 3^n - 1в стеке и 3base,не требуем никакого уменьшения.

Питер Тейлор
источник
2

С, 13х8

#ifndef A//__
#define A//__
x;a;main(){//
a++;;;;;;;;;;
while(a/=3)//
x++;printf(//
"%d",x);}//__
#endif//_____
ciamej
источник
1

Perl, 76

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

$_++;                                 
if(not$_&$_-1){print log()/log 8;$_--}
PhiNotPi
источник
@ Алекс Это не работает, даже на 1-й итерации.
PhiNotPi
Да, работает как есть. Вы проверяли свой метод?
PhiNotPi
Мой работает на ideone: ideone.com/othumP .
PhiNotPi
Попался. Я пропустил важную деталь, которая помешала ему работать раньше. Вы правы, мое предложение неверно.
Алекс А.
1

> <> (Рыба), 12 * 3 = 36

Более простое> <> решение:

'v'00p0l1+  
>  :2-?v$1+v
^$+1$,3< ;n<

Сначала мы запускаем верхний ряд верхних блоков. 'v'00pставит vна самую первую позицию всей программы, направляя указатель программы вниз, когда он возвращается к началу после достижения конца строки. Перед этим каждый блок помещает в него 0 и длину стека + 1. (стек будет 0 2 0 4 0 6 ...)

В первой половине второй и третьей мы подсчитываем, сколько раз мы можем разделить верхний элемент стека, прежде чем получим 2 (мы сохраняем это во втором-верхнем элементе).

В конце мы выводим второй в верхний элемент стека.

randomra
источник
1

Луа, 3 * 17 = 51

Та же стратегия, что и у большинства людей:

x=(x or 0)+1;    
y=math.log(x,3)  
print(y)os.exit()
Омар
источник
1

PHP, 22 × 2 = 44 27 × 2 = 54

<?php $i++          ?>
<?php die(log($i,3))?>

Просто еще один пример - count-log3-out. Не очень маленький, но мой первый гольф;)

Ларс Эберт
источник
На PCG.SE, как и везде, пожалуйста, проверьте документацию перед публикацией :).
Blackhole
@ Blackhole Хорошая добыча! Спасибо
Ларс Эберт