Кривая Гильберта ASCII

23

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

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

n=1
 _ 
| |

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

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

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

Разъяснения

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

Ответы:

5

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 рендеринга , чтобы начать с, и просто думать о кривой , как из коробки символов: , , , , , и .

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

Кривая Гильберта 3-го уровня, отражающая отражение по вертикальной оси

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

Уровень 3 Кривая Гильберта, показывающая отражение по горизонтальной оси в левом нижнем углу

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

Уровень 3 Кривая Гильберта, показывающая, как можно получить верхний правый блок нижнего левого угла

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

Уровень 3 Кривая Гильберта, показывающая, как можно получить верхний левый блок нижнего левого угла

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

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

Уровень 3 Кривая Гильберта, показывающая, как можно получить верхний левый блок нижнего левого угла

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

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

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

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

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

Кривая Гильберта 2-го уровня, отрисованная как ASCII-арт и с символами коробки

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

Джеймс Холдернесс
источник
2

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 байтов.

Мило Йип
источник
Предложите puts("")вместо putchar(10)и "..."+l*8+d*2вместо &"..."[l*8+d*2]и n--?h(d+r...-r,n):0вместоn--&&(h(d+r...-r,n))
потолок кошка