🧩 हैलो कहने के लिए उनतीस बाइट्स: SuperHack में “Hello, World!” की कोड गोल्फिंग 🔗

hacker.org के “Super Small Hello World” चैलेंज का एक विस्तृत विवरण: वे समाधान जिन्होंने काम किया, वे जो लगभग सफल रहे, और वह ट्रिक जिसने अंततः 29 का आँकड़ा छुआ।

📑 विषय-सूची 🔗

🎯 चुनौती (The challenge) 🔗

hacker.org पर SuperHack नाम की एक छोटी सी गूढ़ (esoteric) प्रोग्रामिंग भाषा है। कार्य सुनने में बहुत मामूली लगता है: एक ऐसा SuperHack प्रोग्राम लिखें जो Hello, World! प्रिंट करे।

असली पेच स्कोर में है। आपको आपके कोड के बाउंडिंग रेक्टेंगल (आयत) के क्षेत्रफल (area) के आधार पर स्कोर दिया जाता है, और यह जितना छोटा हो उतना बेहतर है। प्रोग्राम को सही तरीके से समाप्त भी होना चाहिए: ! (halt) निर्देश को निष्पादित करके। टेक्स्ट प्रिंट होने के बाद VM एक्सेप्शन के साथ क्रैश होने की गिनती नहीं होती, और न ही अनावश्यक बाइट्स प्रिंट करने की अनुमति है।

हराने के लिए लक्ष्य संख्या 29 थी।

🧭 SuperHack का दो मिनट का परिचय 🔗

SuperHack एक 2-D स्टैक मशीन है, जो भावना में Befunge के समान है:

• कोड एकल-अक्षर (single-character) निर्देशों का एक ग्रिड है। प्रोग्राम काउंटर (PC) ऊपरी-बाएँ कोने से (या % से) शुरू होता है और दाईं ओर बढ़ता है।
• पूर्णांकों (integers) का एक डेटा स्टैक होता है, और साथ ही एक अलग कॉल स्टैक (call stack) होता है जो पोजीशन (स्थितियों) को रखता है।
• इस पोस्ट में उपयोग किए गए निर्देश:

दो परिणाम आगे आने वाली हर चीज़ को आकार देते हैं:

1. अक्षर ही डेटा हैं। g प्रोग्राम के अपने कोड को पढ़ता है, इसलिए स्ट्रिंग Hello, World! सीधे ग्रिड में रह सकती है और एक समय में एक अक्षर करके वापस पढ़ी जा सकती है। निष्पादित होने पर इसके अधिकांश अक्षर (H e l o W r) no-op होते हैं। तीन नहीं हैं: , 0 पुश करता है, d विभाजित करता है, और ! प्रोग्राम को रोक देता है।
2. @ / $ लूप बनाते हैं, और लूप की गिनती इस बात पर निर्भर करती है कि @ कहाँ हैं। $ जिस @ पर लौटता है, उसके दो सेल बाद से काम शुरू करता है। वह अगले @ पर उतरता है, जो खुद को फिर से पुश करता है, इसलिए कुछ @ लूप बॉडी को कई बार चला सकते हैं:
   • आसन्न (Adjacent) @@@@@ फिबोनाची (Fibonacci) गिनती देते हैं। उनमें से पाँच बॉडी को ठीक 13 बार चलाते हैं।
   • दो सेल की दूरी पर रखे गए @ दो की घात (powers of two) देते हैं। उनमें से चार 16 राउंड (passes) की अनुमति देते हैं।

तेरह अक्षर, तेरह राउंड। इसे ध्यान में रखें।

क्षेत्रफल चौड़ाई गुणा ऊँचाई है, और 29 एक अभाज्य संख्या (prime number) है। इसलिए 29-सेल का प्रोग्राम एक एकल पंक्ति (row) या एक एकल कॉलम (column) ही होना चाहिए।

1️⃣ समाधान 1: सीधा-सादा लूप (क्षेत्रफल 32) 🔗

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

पहला वास्तविक समाधान पेलोड (डेटा) को सामने रखता है और उसके बाद निष्पादन (execution) शुरू करता है:

हॉल्ट गैजेट। पहला @ कॉल स्टैक के सबसे निचले हिस्से में अपनी पोजीशन रखता है, और s, ! के ऊपर से जंप कर जाता है। फिर फिबोनाची श्रृंखला अपने 13 राउंड पूरे करती है। जब कॉल स्टैक अंततः खुलते हुए उस पहले @ तक पहुँचता है, तो $ उसके दो सेल बाद फिर से शुरू होता है, जो कि ठीक ! है। प्रोग्राम साफ-सुथरे ढंग से रुक जाता है, और कहीं भी स्ट्रिंग के अंत की जाँच (end-of-string test) करने की ज़रूरत नहीं पड़ती।

पैडिंग। आसन्न @ के साथ, अंतिम @ से लौटने पर निष्पादन दो सेल बाद शुरू होता है, जो श्रृंखला के बाद पहली सेल को छोड़ देता है। इसलिए वह सेल कुछ हानिरहित होनी चाहिए, इसीलिए वहाँ एक स्पेस (खाली जगह) है।

परिणाम: Hello, World!, साफ-सुथरा हॉल्ट, क्षेत्रफल 32। यह सही है लेकिन बड़ा है: पेलोड निष्क्रिय भार की तरह है, और %, पैडिंग तथा 0 मिलकर तीन सेल खर्च करते हैं।

2️⃣ समाधान 2: इंटरलीविंग (क्षेत्रफल 28, लेकिन अमान्य) 🔗

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

अगला विचार अलग पेलोड पर सेल खर्च करना बंद करना और स्ट्रिंग को कोड के बीच में बुनना (interleave करना) है। Hello, World! के अक्षर विषम (odd) कॉलम (1, 3, …, 25) में बैठते हैं, और कोड उनके बीच के सम (even) कॉलम को भरता है:

• 1 इंडेक्स को कॉलम 1 (H) से शुरू करता है।
• दो की दूरी पर रखे गए चार @ (कॉलम 2, 4, 6, 8) 16 राउंड तक की अनुमति देते हैं।
• पेलोड का अपना , (कॉलम 11) वह 0 पुश करता है जिसकी g को अपनी पंक्ति (row) के रूप में आवश्यकता होती है।
• 2+ इंडेक्स को अगले विषम कॉलम पर ले जाता है।
• s सेल्स पेलोड के d और ! के ऊपर से जंप कर जाती हैं, ताकि वे कोड के रूप में न चलें।

समस्या यह है कि 16 राउंड 13 से अधिक हैं। स्ट्रिंग को प्रिंट करने के बाद, लूप अंत के आगे भी अक्षर लाता रहता है और $ तथा दो NUL बाइट्स प्रिंट कर देता है। फिर $ कॉल स्टैक को खाली पाता है और VM क्रैश हो जाता है:

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

यह छोटा है, लेकिन यह कोई मान्य समाधान नहीं है। हालांकि, यह एक मुख्य विचार पेश करता है: पेलोड के वे अक्षर जो उपयोगी निर्देश भी हैं (,), डेटा और कोड दोनों के रूप में दोहरा काम करते हैं।

3️⃣ समाधान 3: लंबवत (Vertical) जाना (क्षेत्रफल 27, लेकिन अमान्य) 🔗

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

P
W
2
o
+
r
$
l

d

!

(प्रति पंक्ति एक अक्षर। खाली पंक्तियाँ सिंगल स्पेस हैं, जो डेटा हैं।)

प्रोग्राम को घुमाकर खड़ा (लंबवत) करने का एक अप्रत्याशित लाभ होता है। एक एकल कॉलम में, g को x-कोऑर्डिनेट के 0 होने और पंक्ति (row) के i होने की आवश्यकता होती है। पेलोड का , वह 0 मुफ्त में प्रदान करता है, इसलिए अक्षर लाने का काम सिकुड़कर x , g रह जाता है: i की प्रतिलिपि बनाएँ, 0 पुश करें, प्राप्त करें। इसकी कीमत PC को नीचे की ओर मोड़ने के लिए सबसे ऊपर लगाया गया एक \ है।

हालांकि, इसमें भी समाधान 2 वाली ही खामी है। लूप आगे निकल जाता है, NUL बाइट्स प्रिंट करता है, और call stack underflow में समाप्त होता है। क्षेत्रफल 27 पर यह इस पोस्ट का सबसे छोटा प्रोग्राम है, लेकिन यह मान्य नहीं है।

समाधान 2 और 3 से सबक यह मिलता है कि साफ-सुथरे ढंग से रुकने में सेल्स खर्च होती हैं। इंटरलीविंग लूप को सस्ता बनाती है, लेकिन यह आपको 16 राउंड देती है जबकि आपको ठीक 13 की आवश्यकता होती है।

4️⃣ समाधान 4: बाहर निकलने (Exit) की कीमत चुकाना (क्षेत्रफल 30) 🔗

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

समाधान 4, समाधान 3 के लंबवत इंटरलीव को बनाए रखता है और एक वास्तविक एंड-ऑफ-स्ट्रिंग टेस्ट जोड़ता है:

इंडेक्स 2, 4, …, 26 तक चलता है। floor(i/25) बिल्कुल अंतिम अक्षर (i = 26) तक 0 रहता है, इसलिए ? अंतिम को छोड़कर हर राउंड में हॉल्ट को छोड़ देता है। अंतिम राउंड में, निष्पादन पेलोड के ! पर पड़ता है, जो एक साथ प्रिंट किया गया अंतिम अक्षर भी है और प्रोग्राम को रोकने वाला निर्देश भी।

यह पुन: उपयोग (reuse) का एक शानदार नमूना है: पेलोड के ,, d और ! सभी कोड के रूप में काम करते हैं। लेकिन टेस्ट में पाँच सेल खर्च होते हैं, और कुल योग 30 होता है।

🧱 29 असंभव क्यों लग रहा था 🔗

इस बिंदु पर मेरे AI साथी ने यह साबित करने की कोशिश की कि 30 ही सर्वोत्तम (optimal) है। हर तरीका एक ही दीवार से टकराता हुआ प्रतीत हो रहा था:

• इंटरलीविंग सस्ते लूप को रोकती है। तेरह राउंड के लिए पाँच आसन्न (adjacent) @ की आवश्यकता होती है, और इंटरलीव में कोई आसन्न कोड सेल नहीं होती। इसलिए आप 16 राउंड और कीमत चुकाकर किए जाने वाले टेस्ट के साथ फँस जाते हैं।
• सम-विषम (Parity) की बाध्यता सस्ते एग्जिट को रोकती है। इंटरलीव में, ? कभी भी सीधे $ के सामने नहीं बैठ सकता। उनके बीच की सेल हमेशा एक पेलोड सेल होती है।
• एक साथ जुड़ा हुआ (contiguous) पेलोड दूसरे डिज़ाइन को रोकता है। पेलोड को एक ब्लॉक में रखें तो फिबोनाची लूप फिर से फिट हो जाता है। लेकिन तब पेलोड को ऐसी जगह रहना होगा जो कभी निष्पादित न हो (जिसमें एक % या बड़ा स्टार्ट इंडेक्स खर्च होगा), क्योंकि ...d! को कोड के रूप में चलाने से प्रोग्राम क्रैश या हॉल्ट हो जाता है।

छोटे क्षेत्रफलों की गहन मशीन खोजों में कुछ नहीं मिला, और क्षेत्रफल 29 पर समाधान 4 के लेआउट के आसपास की खोजों में भी कुछ नहीं मिला। “30 ही न्यूनतम सीमा है” एक प्रमेय (theorem) की तरह दिखने लगा।

लेकिन ऐसा नहीं था।

🏆 समाधान 5: उनतीस (क्षेत्रफल 29) 🔗

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

सफलता जज (judge) के सोर्स कोड को दोबारा पढ़ने से मिली। दो पंक्तियाँ मायने रखती हैं:

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

• P केवल निचले 7 बिट्स को प्रिंट करता है। एक बाइट जिसका शीर्ष बिट सेट है, यानी c + 128, बिल्कुल c की तरह प्रिंट होता है।
• 128 से 255 तक का बाइट कोई निर्देश नहीं है, इसलिए यह no-op के रूप में निष्पादित होता है।
• PHP स्ट्रिंग्स बाइट्स होती हैं, इसलिए ऐसा बाइट किसी भी अन्य की तरह एक सेल ही होता है।

इसलिए प्रत्येक पेलोड अक्षर की दो एनकोडिंग होती हैं। साधारण एनकोडिंग निष्पादित होने पर कुछ कर सकती है। जबकि c | 0x80 वाली एनकोडिंग के निष्क्रिय (inert) होने की गारंटी है। यही “डेटा का फ़ॉर्मूला” है: खतरनाक अक्षरों को c + 128 के रूप में स्टोर करें, और P को मुफ्त में हाई बिट हटाने दें।

केवल दो पेलोड अक्षर खतरनाक हैं: d बन जाता है ä (0xE4) और ! बन जाता है ¡ (0xA1)। उन दोनों के बदलने के साथ, पूरे पेलोड को निष्पादित किया जा सकता है। यह ऊपर दिए गए तीसरे बिंदु की बाधा को दूर कर देता है।

अब समाधान 1 लें और पेलोड को लूप के अंदर ले जाएँ:

एक राउंड की प्रक्रिया को समझें:

1. PC @ श्रृंखला में कहीं उतरता है और पेलोड से होकर गुज़रता है। H e l l o, स्पेस और W o r l कुछ नहीं करते। पेलोड का , वह 0 पुश करता है जिसकी g को अपनी पंक्ति के रूप में आवश्यकता होती है। ä और ¡ कुछ नहीं करते।
2. 1^ उस 0 के ऊपर i की प्रतिलिपि बनाता है, और g कॉलम i को प्राप्त करता है।
3. P इसे प्रिंट करता है। अंतिम दो अक्षरों के लिए यह 0xE4 & 0x7F = 'd' और 0xA1 & 0x7F = '!' प्रिंट करता है।
4. 1+, i को आगे बढ़ाता है, और $ श्रृंखला में वापस लौटता है।

समाधान 1 की तुलना में, तीन सेल गायब हो जाते हैं:

• %: पेलोड को अब निष्पादन से बचाने की आवश्यकता नहीं है।
• पैडिंग स्पेस: श्रृंखला के बाद छोड़ी जाने वाली सेल अब पेलोड का H है, जो एक no-op है।
• 1^g से पहले का 0: पेलोड का , हर राउंड में इसकी आपूर्ति करता है।

32 − 3 = 29। 13वें राउंड के बाद, कॉल स्टैक खुलकर गैजेट तक पहुँचता है और प्रोग्राम कॉलम 3 में स्थित ! पर रुक जाता है।

आउटपुट Hello, World!, कोई VM संदेश नहीं, 271 साइकिल, क्षेत्रफल 29।

🌐 अंतिम बाधा: जज तक बाइट्स पहुँचाना 🔗

पहला सबमिशन got: 'Hello, WorlC$' और 31 के स्कोर के साथ वापस आया। वेब फ़ॉर्म ने UTF-8 पोस्ट किया था, जिसने प्रत्येक विशेष अक्षर को दो बाइट्स (ä → C3 A4, ¡ → C2 A1) में बदल दिया था। 7 बिट्स में मास्क किए जाने पर, 0xC3 प्रिंट होता है C के रूप में और 0xA4 प्रिंट होता है $ के रूप में।

इसका समाधान ब्राउज़र से Latin-1 भिजवाना है, जहाँ इनमें से प्रत्येक अक्षर एक बाइट का होता है। चैलेंज पेज पर, मुझे DevTools कंसोल खोलना पड़ा और यह चलाना पड़ा:

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

फिर सामान्य सबमिट बटन दबाएँ। जज Hello, World! प्रिंट करता है, और King of the Hill स्कोर 29 हो जाता है।

📊 स्कोरबोर्ड 🔗

💡 मुख्य निष्कर्ष 🔗

• डेटा ही कोड भी है। हर विजयी कदम उन्हीं सेल्स को दोनों भूमिकाएँ निभाने देने से आया: पेलोड का , एक मुफ्त push 0 के रूप में, उसका ! हॉल्ट के रूप में, और अंततः पूरा पेलोड लूप बॉडी के रूप में।
• असंभवता का प्रमाण केवल उतना ही अच्छा होता है जितनी उसकी मान्यताएँ (assumptions)। “30 ही न्यूनतम सीमा है” इंटरलीव्ड, प्रिंटेबल-ASCII लेआउट के लिए सच था। लेकिन इनमें से कोई भी प्रतिबंध नियमों में नहीं था।
• असली सोर्स कोड पढ़ें। एक निश्चित डिज़ाइन स्पेस के भीतर ब्रूट-फ़ोर्स खोज ऐसा उत्तर नहीं ढूँढ सकती जो उसके बाहर स्थित हो। जज के PHP की दो पंक्तियों (& 0x7F और default: break) ने वह कर दिखाया जो घंटों की खोज नहीं कर सकी।
• ट्रांसपोर्ट का ध्यान रखें। एक सही प्रोग्राम भी तब विफल हो सकता है जब वेब फ़ॉर्म जज तक जाने के रास्ते में उसके बाइट्स को बदल देता है।