🧩 Neunundzwanzig Bytes für ein Hallo: Code-Golfing von „Hello, World!" in SuperHack 🔗

Ein Erfahrungsbericht zur „Super Small Hello World"-Challenge auf hacker.org: die Lösungen, die funktionierten, die, die fast funktionierten, und der Trick, der schließlich die 29 knackte.

📑 Inhaltsverzeichnis 🔗

🎯 Die Herausforderung 🔗

Auf hacker.org gibt es eine kleine esoterische Programmiersprache namens SuperHack. Die Aufgabe klingt zunächst trivial: Schreibe ein SuperHack-Programm, das Hello, World! ausgibt.

Der Haken ist die Bewertung. Bewertet wird die Fläche des umschließenden Rechtecks deines Codes – je kleiner, desto besser. Außerdem muss sich das Programm sauber beenden, nämlich durch Ausführen der Anweisung ! (Halt). Ein Absturz mit einer VM-Exception nach der Textausgabe zählt ebenso wenig wie das Ausgeben überflüssiger Bytes.

Die zu schlagende Bestmarke lag bei 29.

🧭 Eine Zwei-Minuten-Tour durch SuperHack 🔗

SuperHack ist eine zweidimensionale Stack-Maschine, im Geiste ähnlich wie Befunge:

• Der Code besteht aus einem Gitter einzelner Zeichenanweisungen. Der Befehlszähler (PC) startet in der oberen linken Ecke (oder bei einem %) und bewegt sich nach rechts.
• Es gibt einen Daten-Stack für Ganzzahlen sowie einen separaten Call-Stack, der Positionen speichert.
• In diesem Beitrag verwendete Anweisungen:

Zwei Konsequenzen prägen alles Folgende:

1. Zeichen sind Daten. g liest den eigenen Programmcode, sodass die Zeichenkette Hello, World! einfach im Gitter liegen und Zeichen für Zeichen ausgelesen werden kann. Die meisten Buchstaben darin (H e l o W r) sind bei der Ausführung No-Ops. Drei jedoch nicht: , legt 0 auf den Stack, d dividiert und ! hält das Programm an.
2. @ / $ bilden Schleifen, und die Anzahl der Durchläufe hängt davon ab, wo die @-Zeichen stehen. $ setzt die Ausführung zwei Zellen nach dem @ fort, zu dem es zurückkehrt. Dort landet es auf dem nächsten @, das sich wiederum selbst auf den Call-Stack legt, sodass wenige @-Zeichen den Schleifenrumpf viele Male wiederholen können:
   • Nebeneinanderliegende @@@@@ liefern Fibonacci-Anzahlen. Fünf davon führen den Rumpf genau 13-mal aus.
   • @-Zeichen im Abstand von zwei Zellen liefern Zweierpotenzen. Vier davon ermöglichen 16 Durchläufe.

Dreizehn Zeichen, dreizehn Durchläufe. Behalten wir das im Hinterkopf.

Die Fläche ist Breite mal Höhe, und 29 ist eine Primzahl. Ein Programm mit 29 Zellen muss also zwingend eine einzelne Zeile oder eine einzelne Spalte sein.

1️⃣ Lösung 1: Die geradlinige Schleife (Fläche 32) 🔗

Hello, World!%0@s!@@@@@ 01^gP1+$

Die erste funktionierende Lösung platziert den Text (die Payload) ganz vorne und startet die Ausführung dahinter:

Das Halt-Gadget. Das erste @ legt seine eigene Position ganz unten auf dem Call-Stack ab, und s springt über das ! hinweg. Die Fibonacci-Kette absolviert dann ihre 13 Durchläufe. Wenn der Call-Stack schließlich bis zu diesem allerersten @ abgearbeitet ist, setzt $ die Ausführung zwei Zellen dahinter fort – und das ist genau das !. Das Programm hält sauber an, ganz ohne Prüfung auf das Ende der Zeichenkette.

Das Füllzeichen (Padding). Bei direkt benachbarten @-Zeichen setzt die Rückkehr vom letzten @ zwei Zellen weiter wieder an, wodurch die erste Zelle nach der Kette übersprungen wird. In dieser Zelle muss daher etwas Harmloses stehen – also ein Leerzeichen.

Ergebnis: Hello, World!, sauberer Halt, Fläche 32. Das Programm ist korrekt, aber verschwenderisch: Die Payload liegt als totes Gewicht herum, und das %, das Leerzeichen sowie die 0 kosten zusammen drei Zellen.

2️⃣ Lösung 2: Verschränkung (Fläche 28, aber ungültig) 🔗

1H@e@l@l@o ,1 ^WgoPr2lsds!+$

Die nächste Idee besteht darin, keine eigenen Zellen mehr für eine separate Payload zu verschwenden, sondern die Zeichenkette direkt mit dem Code zu verweben. Die Zeichen von Hello, World! sitzen in den ungeraden Spalten (1, 3, …, 25), und der Code füllt die geraden Spalten dazwischen:

• 1 startet den Index bei Spalte 1 (dem H).
• Vier @-Zeichen im Abstand von je zwei Zellen (Spalten 2, 4, 6, 8) erlauben bis zu 16 Durchläufe.
• Das , aus der Payload selbst (Spalte 11) legt die 0 auf den Stack, die g als Zeilennummer benötigt.
• 2+ erhöht den Index auf die nächste ungerade Spalte.
• s-Zellen springen über das d und das ! der Payload hinweg, damit sie nicht als Code ausgeführt werden.

Das Problem: 16 Durchläufe sind mehr als 13. Nachdem die Zeichenkette ausgegeben wurde, liest die Schleife hinter dem Ende weiter und gibt $ sowie zwei NUL-Bytes aus. Danach findet $ einen leeren Call-Stack vor und die VM stürzt ab:

output:  "Hello, World!$\0\0"
message: call stack underflow

Es ist zwar klein, aber keine gültige Lösung. Allerdings führt es die Schlüsselidee ein: Payload-Zeichen, die zufällig nützliche Anweisungen sind (,), übernehmen eine Doppelrolle als Daten und Code.

3️⃣ Lösung 3: Ab in die Vertikale (Fläche 27, aber ungültig) 🔗

\
2
H
@
e
@
l
@
l
@
o
x
,
g

P
W
2
o
+
r
$
l

d

!

(Ein Zeichen pro Zeile. Die Leerzeilen enthalten jeweils ein einzelnes Leerzeichen, das als Datum dient.)

Das Programm auf die Seite zu kippen, bringt einen unerwarteten Vorteil. In einer einzelnen Spalte benötigt g als x-Koordinate eine 0 und als Zeile den Index i. Das , der Payload liefert diese 0 kostenlos, sodass das Auslesen auf x , g schrumpft: i duplizieren, 0 auf den Stack legen, Zeichen holen. Die Kosten dafür betragen lediglich ein \ ganz oben, um den PC nach unten zu lenken.

Allerdings leidet dieser Ansatz unter demselben Fehler wie Lösung 2: Die Schleife schießt über das Ziel hinaus, gibt NUL-Bytes aus und endet mit einem call stack underflow. Mit Fläche 27 ist es das kleinste Programm in diesem Artikel – aber es zählt nicht.

Die Lektion aus den Lösungen 2 und 3 lautet: Sauberes Anhalten kostet Zellen. Das Verschränken macht die Schleife billig, liefert aber 16 Durchläufe, obwohl wir genau 13 brauchen.

4️⃣ Lösung 4: Den Preis für den Ausstieg zahlen (Fläche 30) 🔗

\
2
H
@
e
@
l
@
l
@
o
x
,
g
 
P
W
x
o
5
r
d
l
5
d
?
!
2
+
$

Lösung 4 behält die vertikale Verschränkung aus Lösung 3 bei und ergänzt eine reguläre Prüfung auf das Ende der Zeichenkette:

Der Index durchläuft die Werte 2, 4, …, 26. floor(i/25) bleibt 0 bis zum allerletzten Zeichen (i = 26), sodass ? den Halt bei jedem Durchlauf außer dem letzten überspringt. Beim letzten Durchlauf fällt die Ausführung direkt auf das ! der Payload, das damit gleichzeitig das letzte ausgegebene Zeichen und der Befehl zum Anhalten des Programms ist.

Eine wunderbare Mehrfachnutzung: ,, d und ! aus der Payload dienen alle zugleich als Code. Doch der Test kostet fünf Zellen, womit wir insgesamt bei 30 landen.

🧱 Warum 29 unmöglich erschien 🔗

An diesem Punkt versuchte mein KI-Begleiter zu beweisen, dass 30 das theoretische Optimum sei. Jeder Ansatz schien gegen dieselbe Wand zu laufen:

• Verschränkung blockiert die billige Schleife. Dreizehn Durchläufe erfordern fünf benachbarte @-Zeichen, und in einem verschränkten Layout gibt es keine direkt benachbarten Code-Zellen. Man sitzt also auf 16 Durchläufen und einem teuer erkauften Abbruchtest fest.
• Parität verhindert billigere Ausstiege. In einem verschränkten Layout kann ? niemals unmittelbar vor $ stehen. Die Zelle dazwischen ist immer eine Payload-Zelle.
• Eine zusammenhängende Payload blockiert das andere Design. Legt man die Payload in einen zusammenhängenden Block, passt zwar die Fibonacci-Schleife wieder. Dann muss die Payload aber an einem Ort liegen, der niemals ausgeführt wird (was ein % oder einen großen Startindex kostet), weil die Ausführung von ...d! als Code unweigerlich abstürzt oder zu früh anhält.

Erschöpfende Maschinensuchen über kleinere Flächen ergaben nichts, und auch Suchen rund um das Layout von Lösung 4 mit Fläche 29 blieben erfolglos. „30 ist die Untergrenze" sah immer mehr wie ein mathematischer Satz aus.

War es aber nicht.

🏆 Lösung 5: Neunundzwanzig (Fläche 29) 🔗

9@s!@@@@@Hello, Worlä¡1^gP1+$

Der Durchbruch kam beim erneuten Lesen des Quellcodes des Bewertungsservers (Judge). Zwei Zeilen sind entscheidend:

case 'P':
  $output .= chr($this->Pop() & 0x7F); break;
...
default:
  break;   // every unknown character is a no-op

• P gibt nur die unteren 7 Bits aus. Ein Byte mit gesetztem höchstem Bit, c + 128, wird exakt genauso ausgegeben wie c.
• Ein Byte zwischen 128 und 255 ist kein gültiger Befehl und wird daher als No-Op ausgeführt.
• PHP-Strings sind Byte-Arrays, sodass ein solches Byte genau eine Zelle belegt wie jedes andere Zeichen auch.

Jedes Payload-Zeichen besitzt somit zwei Kodierungen: Die normale Variante tut möglicherweise etwas, wenn sie ausgeführt wird. Die Variante c | 0x80 ist garantiert wirkungslos. Das ist die „Formel für die Daten": Speichere die gefährlichen Zeichen als c + 128 und lass P das höchste Bit kostenlos wieder abschneiden.

Nur zwei Zeichen in der Payload sind gefährlich: Aus d wird ä (0xE4) und aus ! wird ¡ (0xA1). Mit diesen beiden Änderungen kann die gesamte Payload problemlos durchlaufen werden. Damit löst sich das Hindernis aus dem dritten Punkt oben in Luft auf.

Jetzt nehmen wir Lösung 1 und verschieben die Payload mitten in die Schleife:

Gehen wir einen Durchlauf Schritt für Schritt durch:

1. Der PC landet irgendwo in der @-Kette und läuft mitten durch die Payload. H e l l o, das Leerzeichen und W o r l tun nichts. Das , der Payload legt die 0 auf den Stack, die g als Zeilennummer braucht. ä und ¡ tun nichts.
2. 1^ kopiert i über diese 0, und g liest Spalte i aus.
3. P gibt das Zeichen aus. Für die letzten beiden Zeichen berechnet es 0xE4 & 0x7F = 'd' und 0xA1 & 0x7F = '!'.
4. 1+ erhöht i, und $ springt zurück in die Kette.

Im Vergleich zu Lösung 1 verschwinden gleich drei Zellen:

• %: Die Payload muss nicht mehr vor der Ausführung geschützt werden.
• Das Füll-Leerzeichen: Die Zelle, die nach der Kette übersprungen wird, ist nun das H der Payload – ein No-Op.
• Die 0 vor 1^g: Das , der Payload liefert sie bei jedem Durchlauf frei Haus.

32 − 3 = 29. Nach dem 13. Durchlauf wird der Call-Stack bis zum Halt-Gadget abgebaut, und das Programm stoppt sauber auf dem ! in Spalte 3.

Ausgabe Hello, World!, keine VM-Fehlermeldung, 271 Zyklen, Fläche 29.

🌐 Die letzte Hürde: Die Bytes unbeschadet zum Judge bringen 🔗

Der erste Einreichungsversuch kam mit got: 'Hello, WorlC$' und einer Punktzahl von 31 zurück. Das Webformular hatte die Daten als UTF-8 gesendet, wodurch jedes Sonderzeichen in zwei Bytes umgewandelt wurde (ä → C3 A4, ¡ → C2 A1). Auf 7 Bit maskiert wird 0xC3 als C und 0xA4 als $ ausgegeben.

Die Lösung besteht darin, den Browser anzuweisen, Latin-1 zu senden, wo jedes dieser Zeichen genau ein Byte lang ist. Auf der Challenge-Seite musste ich dazu die DevTools-Konsole öffnen und Folgendes ausführen:

document.querySelectorAll('form').forEach(
  f => f.acceptCharset = 'ISO-8859-1');
document.querySelector('textarea').value =
  "9@s!@@@@@Hello, Worl\u00e4\u00a11^gP1+$";

Danach genügte ein Klick auf den normalen Absende-Button. Der Judge gibt Hello, World! aus, und der Bestwert liegt bei 29.

📊 Ergebnisübersicht 🔗

💡 Erkenntnisse 🔗

• Daten sind auch Code. Jeder entscheidende Fortschritt entstand dadurch, dass dieselben Zellen beide Aufgaben gleichzeitig übernahmen: das , der Payload als kostenloses push 0, ihr ! als Halt und schließlich die gesamte Payload als Teil des Schleifenrumpfs.
• Ein Unmöglichkeitsbeweis ist immer nur so gut wie seine Annahmen. „30 ist die Untergrenze" stimmte für verschränkte Layouts aus druckbaren ASCII-Zeichen. Keine dieser beiden Einschränkungen stand jedoch in den Regeln.
• Lies den echten Quellcode. Eine Brute-Force-Suche innerhalb eines fest gesteckten Designraums kann keine Antwort finden, die außerhalb davon liegt. Zwei Zeilen im PHP-Code des Judges (& 0x7F und default: break) leisteten, was stundenlange algorithmische Suche nicht schaffte.
• Achte auf den Transportweg. Selbst ein völlig korrektes Programm kann scheitern, wenn das Webformular seine Bytes auf dem Weg zum Server verändert.