Дано целое число nвыходных nитераций кривой Гильберта в ASCII с использованием символов _и |.

Вот первые 4 итерации:

n=1
 _ 
| |

n=2
 _   _ 
| |_| |
|_   _|
 _| |_

n=3
 _   _   _   _ 
| |_| | | |_| |
|_   _| |_   _|
 _| |_____| |_ 
|  ___   ___  |
|_|  _| |_  |_|
 _  |_   _|  _ 
| |___| |___| |

n=4
 _   _   _   _   _   _   _   _ 
| |_| | | |_| | | |_| | | |_| |
|_   _| |_   _| |_   _| |_   _|
 _| |_____| |_   _| |_____| |_ 
|  ___   ___  | |  ___   ___  |
|_|  _| |_  |_| |_|  _| |_  |_|
 _  |_   _|  _   _  |_   _|  _ 
| |___| |___| |_| |___| |___| |
|_   ___   ___   ___   ___   _|
 _| |_  |_|  _| |_  |_|  _| |_ 
|  _  |  _  |_   _|  _  |  _  |
|_| |_| | |___| |___| | |_| |_|
 _   _  |  ___   ___  |  _   _ 
| |_| | |_|  _| |_  |_| | |_| |
|_   _|  _  |_   _|  _  |_   _|
 _| |___| |___| |___| |___| |_ 

Разъяснения

• Мой вопрос похож на Рисование кривой Гильберта и Рисование кривой Гильберта с помощью косой черты .
• Преобразование между подчеркиванием ( _) и вертикальной чертой ( |) - это u=2*v-1где uчисло _s и vчисло |s.
• Чтобы сохранить соответствие с моим исходным постом, кривая должна начинаться и заканчиваться внизу.
• Вы можете иметь полную программу или функцию.
• Вывод на стандартный вывод (или что-то подобное).
• Вы можете иметь начальные или конечные пробелы, выходные данные просто должны выстроиться так, чтобы они выглядели как примеры.
• Это код-гольф, поэтому выигрывает самый короткий ответ в байтах.

Befunge, 444 368 323 байта

&1>\1-:v
0v^*2\<_$00p>
_>:10p\:20pv^_@#-*2g00:+1,+55$
^!-<v*2g000<>$#<0>>-\:v
g2*^>>10g20g+v \ ^*84g_$:88+g,89+g,\1+:00
v#*!-1g02!g01_4^2_
>::00g2*-!\1-:10g-\20g-++>v
87+#^\#p01#<<v!`g01/2\+76:_
vv1-^#1-g01:\_$:2/20g`!
_ 2/^>:10g#vv#`g02/4*3:\+77
v>0p^^/2:/2_
<^2-1-g02</2`#*3:
0g+10p2*:^*3_1
! "#%$
%$"#!
 !!##%
|||_
 _ __

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

Типичный подход к построению кривой Гильберта состоит в том, чтобы следовать по пути в виде последовательности штрихов и поворотов, визуализировать результат в растровое изображение или некоторую область памяти, а затем записывать этот рендеринг после завершения пути. Это просто невозможно в Befunge, когда у нас есть только 2000 байтов памяти для работы, и это включает в себя источник самой программы.

Таким образом, подход, который мы здесь использовали, заключается в том, чтобы придумать формулу, которая точно сообщает нам, какой символ вывести для данной координаты x, y. Чтобы понять , как это работает, это проще всего игнорировать ASCII рендеринга , чтобы начать с, и просто думать о кривой , как из коробки символов: ┌, ┐, └, ┘, │, и ─.

Когда мы смотрим на кривую таким образом, мы сразу видим, что правая сторона является точным зеркалом левой стороны. Символы справа можно просто определить, посмотрев на их партнера слева и отразив его горизонтально (т. Е. Вхождения ┌и ┐поменялись местами, как есть └и ┘).

Затем, глядя в левый нижний угол, мы снова видим, что нижняя половина является отражением верхней. Таким образом, символы внизу просто определяются путем поиска их партнера сверху и их отражения по вертикали (т. Е. Случаи ┌и └меняются местами, как ┐и ┘).

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

И левый блок может быть получен из вертикального отражения блока в самом верхнем левом углу полной кривой.

На данный момент все, что у нас осталось, это верхний левый угол, который является еще одной кривой Гильберта на одну итерацию ниже. Теоретически, теперь нам просто нужно повторить процесс снова, но есть некоторая хитрость - на этом уровне левая и правая половины блока не являются точными зеркалами друг друга.

Таким образом, на любом другом уровне, кроме верхнего уровня, символы нижнего угла должны обрабатываться как особый случай, когда ┌символ отображается как ─, а │символ - как └.

Но кроме этого, мы действительно можем просто повторить этот процесс рекурсивно. На последнем уровне мы жестко кодируем верхний левый символ как ┌, а символ под ним как │.

Теперь, когда у нас есть способ определить форму кривой по определенной координате x, y, как мы можем перевести это в рендеринг ASCII? На самом деле это просто простое отображение, которое переводит каждую возможную плитку в два символа ASCII.

• ┌становится  _(пробел плюс подчеркивание)
• ┐становится   (два пробела)
• └становится |_(вертикальная черта плюс подчеркивание)
• ┘становится | (вертикальная черта плюс пробел)
• │становится | (снова вертикальная черта плюс пробел)
• ─становится __(два подчеркивания)

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

И это в основном все, что нужно сделать. Фактически реализация этого алгоритма в Befunge - это еще одна проблема, но я оставлю это объяснение в другой раз.

C 267 байт

const n=4,s=1<<n,a[]={1,-s,-1,s};l,p,q;
t(d){d&=3;p-q||printf("%.2s",&"__|      _|       |___ _|_| | | "[l*8+d*2]);p+=a[l=d];}
h(d,r,n){n--&&(h(d+r,-r,n),t(d+r),h(d,r,n),t(d),h(d,r,n),t(d-r),h(d-r,-r,n));}
main(){for(;p=s*s-s,l=1,q<s*s;++q%s||putchar(10))h(0,1,n),t(3);}

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

h()использует рекурсию для генерации штрихов кривой Глиберта. t()Печатает символ обводки, только если позиция пера pравна текущей позиции вывода q.

Это неэффективно, но просто.

Если кривая начинается в верхнем левом углу, код может быть уменьшен до 256 байтов.