ASCII-Hilbert-Kurve

23

Bei einer ganzzahligen nAusgabe die nIteration der Hilbertkurve in ASCII mit den Zeichen _und |.

Hier sind die ersten 4 Iterationen:

n=1
 _ 
| |

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

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

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

Klarstellungen

  • Meine Frage ähnelt dem Zeichnen der Hilbert-Kurve und dem Zeichnen der Hilbert-Kurve mit Schrägstrichen .
  • Die Umwandlung zwischen Unterstrichen ( _) und vertikalen Stangen ( |) ist , u=2*v-1wo udie Anzahl der ist , _s und vist die Anzahl von |s.
  • Um die Konsistenz mit meinem ursprünglichen Beitrag zu gewährleisten, muss die Kurve unten beginnen und enden.
  • Sie können ein vollständiges Programm oder eine Funktion haben.
  • Ausgabe auf stdout (oder ähnliches).
  • Sie können führende oder nachfolgende Leerzeichen verwenden. Die Ausgabe muss nur so ausgerichtet sein, dass sie den Beispielen entspricht.
  • Dies ist Code-Golf, also gewinnt die kürzeste Antwort in Bytes.
Bobas_Pett
quelle
3
Könnten Sie bitte eine Definition der Hilbert-Kurve und die genauen Spezifikationen für den Aufbau der ASCII-Version in Ihren Beitrag aufnehmen?
Loovjo
@ Bobas_Pett: Nicht Kolmogorov-Komplexität
Shooqie
@shooqie es gibt einige Debatten darüber auf meta
trichoplax
@ Loovjo Ich habe in einem Punkt über die Länge der Unterstriche (_) und vertikalen Balken (|) unter "Erläuterungen" hinzugefügt. Wenn weitere Informationen oder eine strenge Definition erforderlich sind, teilen Sie mir dies bitte mit.
Bobas_Pett
@shooqie Ich habe den Tag entfernt
Bobas_Pett

Antworten:

5

Befunge, 444 368 323 Bytes

&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
! "#%$
%$"#!
 !!##%
|||_
 _ __

Probieren Sie es online!

Der typische Ansatz zum Zeichnen der Hilbert-Kurve besteht darin, dem Pfad als Folge von Strichen und Kurven zu folgen, das Ergebnis in eine Bitmap oder einen Speicherbereich zu rendern und dieses Rendern dann auszuschreiben, wenn der Pfad vollständig ist. Dies ist in Befunge einfach nicht möglich, wenn nur 2000 Byte Arbeitsspeicher zur Verfügung stehen und dies auch die Quelle des Programms selbst einschließt.

Wir haben uns hier also eine Formel ausgedacht, die genau angibt, welches Zeichen für eine bestimmte x, y-Koordinate ausgegeben werden soll. Um zu verstehen , wie dies funktioniert, ist es am einfachsten , das ASCII - Rendering zu ignorieren , mit zu beginnen, und man denke nur an der Kurve als Kasten Zeichen aus: , , , , , und .

Wenn wir die Kurve so betrachten, können wir sofort erkennen, dass die rechte Seite ein exakter Spiegel der linken Seite ist. Die Zeichen auf der rechten Seite können einfach bestimmt werden, indem der Partner auf der linken Seite nachgeschlagen und horizontal reflektiert wird (dh das Auftreten von und wird wie und vertauscht ).

Level 3 Hilbert-Kurve, die die Reflexion über die vertikale Achse zeigt

Wenn wir dann die untere linke Ecke betrachten, können wir wieder sehen, dass die untere Hälfte eine Reflexion der oberen Hälfte ist. So werden die Zeichen auf der Unterseite einfach dadurch bestimmt, dass ihr Partner oben nachgeschlagen und vertikal reflektiert wird (dh Vorkommen von und werden vertauscht, so wie und ).

Level 3 Hilbert-Kurve, die die Reflexion über die horizontale Achse in der unteren linken Ecke zeigt

Die verbleibende Hälfte dieser Ecke ist etwas weniger auffällig. Der rechte Block kann aus einer vertikalen Reflexion des diagonal angrenzenden Blocks abgeleitet werden.

Level 3 Hilbert-Kurve, die zeigt, wie der obere rechte Block der unteren linken Ecke abgeleitet werden kann

Der linke Block kann aus einer vertikalen Reflexion des Blocks ganz links oben in der vollständigen Kurve abgeleitet werden.

Level 3 Hilbert-Kurve, die zeigt, wie der obere linke Block der unteren linken Ecke abgeleitet werden kann

An diesem Punkt bleibt uns nur die obere linke Ecke, die nur eine weitere Hilbert-Kurve ist, die eine Iteration tiefer liegt. Theoretisch sollten wir den Vorgang jetzt nur noch einmal wiederholen müssen, aber es gibt einen kleinen Haken - auf dieser Ebene sind die linke und die rechte Hälfte des Blocks keine exakten Spiegel voneinander.

Auf allen anderen Ebenen als der obersten Ebene müssen die Zeichen in der unteren Ecke als Sonderfall behandelt werden, in dem das Zeichen als und das Zeichen als reflektiert wird .

Level 3 Hilbert-Kurve, die zeigt, wie der obere linke Block der unteren linken Ecke abgeleitet werden kann

Davon abgesehen können wir diesen Vorgang wirklich nur rekursiv wiederholen. Auf der letzten Ebene wird das Zeichen oben links als und das Zeichen darunter als fest codiert .

Folge von Bildern, die zeigen, wie die verbleibenden Teile der Kurve abgeleitet werden

Nachdem wir nun die Form der Kurve an einer bestimmten x, y-Koordinate bestimmen können, wie übersetzen wir das in das ASCII-Rendering? Es ist eigentlich nur eine einfache Zuordnung, die jede mögliche Kachel in zwei ASCII-Zeichen übersetzt.

  • wird  _(Leerzeichen plus Unterstrich)
  • wird   (zwei Leerzeichen)
  • wird |_(senkrechter Strich plus Unterstrich)
  • wird (senkrechter Strich plus Leerzeichen)
  • wird (wieder ein vertikaler Strich plus Leerzeichen)
  • wird __(zwei Unterstriche)

Dieses Mapping ist zunächst nicht intuitiv, aber Sie können sehen, wie es funktioniert, wenn Sie zwei entsprechende Renderings nebeneinander betrachten.

Hilbert-Kurve der Stufe 2, gerendert als ASCII-Grafik und mit Box-Zeichen

Und das ist im Grunde alles, was dazu gehört. Eigentlich ist die Implementierung dieses Algorithmus in Befunge ein weiteres Problem, aber ich werde diese Erklärung für ein anderes Mal belassen.

James Holderness
quelle
2

C 267 Bytes

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

Probieren Sie es online!

h()Verwendet die Rekursion, um die Striche der Hubert-Kurve zu erzeugen. t()druckt das Strichzeichen nur aus, wenn die Stiftposition pder aktuellen Ausgabeposition entspricht q.

Dies ist ineffizient, aber einfach.

Beginnt die Kurve oben links, kann der Code auf 256 Byte reduziert werden.

Milo Yip
quelle
Schlagen Sie puts("")anstelle von putchar(10)und "..."+l*8+d*2anstelle von &"..."[l*8+d*2]und n--?h(d+r...-r,n):0anstelle vonn--&&(h(d+r...-r,n))
Ceilingcat