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

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

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 переходит к представлению, которое использует наименьшее количество отдельных символов в своем текстовом блоке. Если все еще связаны, ответ опубликовал первые победы.

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

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

пит - 32 * 6 = 192

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

Вот вторая итерация:

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

> <> , 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 (поскольку> <> не имеет функции журнала). Нижний ноль используется для отслеживания счета.

Perl, 26

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

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

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

$n--or$n=3**$s++;
print$s-1if!$o++;

Perl, 30 (15 × 2)

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

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

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

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

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

Golfscript, 9 * 2 = 18

0+       
,3base,(}

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

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

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

С, 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//__

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

Python 2, 15 * 3 = 45

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

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

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

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

a+=1;          
l(a)/l(3);halt;

Golfscript, 7 * 2 = 14

1+~abs(
3base,}

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

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

С, 13х8

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

Perl, 76

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

$_++;                                 
if(not$_&$_-1){print log()/log 8;$_--}

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

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

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

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

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

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

Луа, 3 * 17 = 51

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

x=(x or 0)+1;    
y=math.log(x,3)  
print(y)os.exit()

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

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

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