🧩 29바이트로 인사하기: SuperHack에서 “Hello, World!” 코드 골프 도전기 🔗

hacker.org의 “Super Small Hello World” 챌린지 풀이 기록: 작동했던 솔루션들, 아깝게 실패한 시도들, 그리고 마침내 29바이트에 도달한 트릭을 소개합니다.

📑 목차 🔗

🎯 챌린지 소개 🔗

hacker.org에는 SuperHack이라는 작은 난해한 프로그래밍 언어(esoteric language)가 있습니다. 과제는 사소해 보입니다. Hello, World!를 출력하는 SuperHack 프로그램을 작성하는 것입니다.

함정은 점수 산정 방식에 있습니다. 점수는 코드를 둘러싸는 최소 직사각형(bounding rectangle)의 면적으로 매겨지며, 작을수록 좋습니다. 또한 프로그램은 !(종료, halt) 명령어를 실행하여 정상적으로 종료되어야 합니다. 텍스트를 출력한 뒤 VM 예외로 크래시가 나는 것은 인정되지 않으며, 불필요한 여분의 바이트를 출력하는 것도 허용되지 않습니다.

깨야 할 목표 기록은 29였습니다.

🧭 2분 만에 둘러보는 SuperHack 🔗

SuperHack은 Befunge와 기본 정신이 비슷한 2차원 스택 머신입니다:

• 코드는 단일 문자 명령어들로 이루어진 격자(grid)입니다. 프로그램 카운터(PC)는 왼쪽 위 모서리(또는 % 위치)에서 시작하여 오른쪽으로 이동합니다.
• 정수를 담는 하나의 데이터 스택과, 위치를 저장하는 별도의 **콜 스택(call stack)**이 있습니다.
• 이 글에서 사용된 명령어들:

여기서 파생되는 두 가지 결과가 이어지는 모든 과정을 결정짓습니다.

1. 문자는 곧 데이터다. g는 프로그램 자신의 코드를 읽으므로, Hello, World!라는 문자열을 그냥 격자 안에 넣어두고 한 번에 한 글자씩 읽어 들일 수 있습니다. 대부분의 글자(H e l o W r)는 실행될 때 아무 일도 하지 않는 no-op입니다. 하지만 세 글자는 예외입니다. ,는 0을 푸시하고, d는 나눗셈을 수행하며, !는 프로그램을 정지시킵니다.
2. @ / $는 루프를 만들며, 루프 횟수는 @들이 어디에 배치되느냐에 따라 달라진다. $는 되돌아간 @에서 두 칸 뒤부터 실행을 재개합니다. 그 위치에 다음 @가 있으면 다시 자기 자신을 푸시하게 되므로, 몇 개의 @만으로도 루프 본문을 여러 번 반복 실행할 수 있습니다:
   • 인접한 @@@@@는 피보나치 횟수를 만듭니다. 다섯 개를 붙이면 본문을 정확히 13번 실행합니다.
   • 두 칸 간격으로 떨어진 @들은 2의 거듭제곱 횟수를 만듭니다. 네 개를 배치하면 16번의 패스(반복)가 가능합니다.

13개의 문자, 13번의 패스. 이 점을 기억해 두세요.

면적은 가로 곱하기 세로이며, 29는 소수(prime)입니다. 따라서 29셀짜리 프로그램은 반드시 단일 행 또는 단일 열이어야 합니다.

1️⃣ 솔루션 1: 정직한 루프 (면적 32) 🔗

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

첫 번째 실제 솔루션은 페이로드(출력할 문자열)를 맨 앞에 두고 그 뒤에서부터 실행을 시작합니다:

정지 가젯. 첫 번째 @는 자신의 위치를 콜 스택 맨 아래에 넣고, s는 !를 건너뜁니다. 그런 다음 피보나치 체인이 13번의 패스를 수행합니다. 마침내 콜 스택이 모두 풀려 맨 처음의 @까지 내려오면, $는 그로부터 두 칸 뒤에서 실행을 재개하는데, 그 위치가 정확히 !입니다. 프로그램은 어디에도 문자열 끝(end-of-string) 검사 로직 없이 깔끔하게 정지합니다.

패딩. 인접한 @들을 사용할 때 마지막 @에서 복귀하면 두 칸 뒤에서 실행이 재개되므로 체인 바로 다음의 첫 번째 셀을 건너뛰게 됩니다. 따라서 그 셀에는 무해한 무언가가 들어가야 하므로 공백(space)을 넣었습니다.

결과: Hello, World!, 깔끔한 정지, 면적 32. 정확하게 작동하지만 여유 공간이 많습니다. 페이로드가 실행에 참여하지 않는 짐 덩어리이고, %와 패딩, 그리고 0이 합쳐서 세 개의 셀을 차지합니다.

2️⃣ 솔루션 2: 인터리빙(교차 배치) (면적 28, 하지만 무효) 🔗

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

다음 아이디어는 별도의 페이로드에 셀을 소비하는 것을 멈추고 문자열을 코드 사이사이에 엮어 넣는(interleave) 것입니다. Hello, World!의 문자들은 홀수 열(1, 3, …, 25)에 자리 잡고, 코드는 그 사이의 짝수 열을 채웁니다:

• 1은 인덱스를 1열(H)에서 시작하게 합니다.
• 두 칸 간격으로 배치된 네 개의 @(2, 4, 6, 8열)는 최대 16번의 패스를 허용합니다.
• 페이로드 자체의 ,(11열)가 g가 행 번호로 필요로 하는 0을 푸시합니다.
• 2+는 인덱스를 다음 홀수 열로 증가시킵니다.
• s 셀들은 페이로드의 d와 !가 코드로 실행되지 않도록 건너뛰게 해 줍니다.

문제는 16번의 패스가 13번보다 많다는 점입니다. 문자열을 모두 출력한 후에도 루프는 끝을 넘어 계속 문자를 가져와 $와 두 개의 NUL 바이트를 출력합니다. 그런 다음 $가 비어 있는 콜 스택을 만나면서 VM이 죽어버립니다:

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

크기는 작지만 유효한 솔루션이 아닙니다. 하지만 핵심적인 아이디어를 제시해 줍니다. 우연히 유용한 명령어이기도 한 페이로드 문자(,)가 데이터와 코드라는 두 가지 역할을 동시에 수행하게 하는 것입니다.

3️⃣ 솔루션 3: 세로로 세우기 (면적 27, 하지만 무효) 🔗

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

P
W
2
o
+
r
$
l

d

!

(한 줄에 한 글자씩입니다. 빈 줄은 데이터에 해당하는 단일 공백 문자입니다.)

프로그램을 옆으로 눕혀 세로로 세우면 뜻밖의 이점이 생깁니다. 단일 열에서는 g가 x좌표로 0을, 행 번호로 i를 필요로 합니다. 페이로드의 ,가 그 0을 공짜로 공급해 주므로, 문자를 가져오는 코드가 x , g(i 복제, 0 푸시, 가져오기)로 줄어듭니다. 대가는 맨 위에서 PC를 아래쪽으로 꺾어주는 \ 하나뿐입니다.

하지만 솔루션 2와 똑같은 결함을 가지고 있습니다. 루프가 목표를 지나쳐 NUL 바이트들을 출력하고 call stack underflow로 끝납니다. 면적 27로 이 글에서 가장 작은 프로그램이지만 정답으로 인정되지 않습니다.

솔루션 2와 3에서 얻은 교훈은 깔끔하게 멈추려면 셀을 지불해야 한다는 것입니다. 인터리빙은 루프를 저렴하게 만들어 주지만, 정확히 13번이 필요한 상황에서 16번의 패스를 제공합니다.

4️⃣ 솔루션 4: 종료를 위한 대가 지불하기 (면적 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으로 유지되므로, ?는 마지막 패스를 제외한 모든 패스에서 정지 명령어를 건너뜁니다. 마지막 패스에서는 실행 흐름이 페이로드의 !로 떨어지며, 이 !는 출력되는 마지막 문자임과 동시에 프로그램을 멈추는 명령어로 작동합니다.

페이로드의 ,, d, !가 모두 코드로 작동하는 아주 멋진 재사용 사례입니다. 하지만 테스트에 다섯 개의 셀이 소비되어 총면적은 30이 됩니다.

🧱 왜 29가 불가능해 보였는가 🔗

이 시점에서 저의 AI 파트너는 30이 최적해임을 증명하려고 시도했습니다. 모든 접근 방식이 똑같은 벽에 부딪히는 것처럼 보였습니다:

• 인터리빙은 저렴한 루프를 가로막는다. 13번의 패스를 만들려면 다섯 개의 인접한 @가 필요한데, 인터리빙 구조에는 인접한 코드 셀이 없습니다. 따라서 어쩔 수 없이 16번의 패스를 쓰고 셀을 지불하는 종료 테스트를 넣어야 합니다.
• 홀짝성(Parity)이 더 저렴한 탈출구를 가로막는다. 인터리빙 구조에서는 ?가 절대 $ 바로 앞에 위치할 수 없습니다. 둘 사이의 셀은 항상 페이로드 셀이기 때문입니다.
• 연속된 페이로드는 다른 설계를 가로막는다. 페이로드를 한 덩어리로 모으면 피보나치 루프가 다시 들어맞습니다. 하지만 ...d!를 코드로 실행하면 크래시가 나거나 정지해 버리기 때문에, 페이로드를 절대 실행되지 않는 곳에 두어야만 합니다(결국 %나 큰 시작 인덱스에 셀을 쓰게 됩니다).

더 작은 면적에 대한 완전 탐색(exhaustive search)에서도 아무것도 나오지 않았고, 면적 29에서 솔루션 4의 레이아웃 주변을 탐색해 봐도 아무것도 나오지 않았습니다. “30이 하한선이다"라는 말은 하나의 정리(theorem)처럼 보이기 시작했습니다.

하지만 그렇지 않았습니다.

🏆 솔루션 5: 29바이트 (면적 29) 🔗

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

돌파구는 채점기(judge)의 소스 코드를 다시 읽는 것에서 나왔습니다. 다음 두 줄이 핵심입니다:

case 'P':
  $output .= chr($this->Pop() & 0x7F); break;
...
default:
  break;   // 알 수 없는 모든 문자는 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은 아무 일도 하지 않습니다. 페이로드의 ,가 g가 행 번호로 필요로 하는 0을 푸시합니다. ä와 ¡는 아무 일도 하지 않습니다.
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로 데이터를 전송하면서 각 특수 문자를 2바이트로 변환해 버린 것입니다(ä → C3 A4, ¡ → C2 A1). 7비트로 마스킹되면서 0xC3은 C로, 0xA4는 $로 출력되었습니다.

해결책은 브라우저가 해당 문자들을 각각 1바이트로 표현하는 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으로, !는 정지 명령어로, 그리고 마침내 전체 페이로드가 루프 본문으로 작동했습니다.
• 불가능성 증명은 그 전제 조건만큼만 유효하다. “30이 하한선이다"라는 명제는 인터리빙된 출력 가능한 ASCII 레이아웃이라는 전제하에서만 참이었습니다. 하지만 규칙에는 그 두 가지 제한 중 어느 것도 없었습니다.
• 실제 소스를 읽어라. 고정된 설계 공간 안에서의 무차별 대입(brute-force) 탐색은 그 공간 밖에 있는 답을 찾을 수 없습니다. 채점기 PHP 코드의 두 줄(& 0x7F와 default: break)이 몇 시간의 탐색으로도 해내지 못한 일을 해냈습니다.
• 전송 과정을 주의하라. 프로그램이 아무리 정확하더라도 웹 폼이 채점기로 가는 도중에 바이트를 바꿔버리면 실패할 수 있습니다.