2011년 7월 16일 Spelt Number to Decimal: 제작 일기
이번 주 초에 올린 Spelt Number to Decimal, 즉 “a hundred” 같은 걸 “100”으로 바꿔 주는 프로그램은 개인적으로는 나쁘지 않은 코드 골프였다고 생각한다. 사람들 반응도 이전 Brainfuck 인터프리터 때보다 더 좋고(음… 설명을 써 놓아서 그런 건가?) 이번에는 내가 직접 레딧에 올렸기 때문에 카르마도 적절히 획득하고(…) 코드에 대한 피드백도 이전보다는 좀 더 활발한 게 괜찮았다. 하나 아까운 점은, 처음 공개 뒤에 십 수 바이트를 줄일 수 있다는 걸 발견해서 후다닥 고쳐야 했다는 것이랄까.
보통 코드 골프 글은 (영어 아는 사람이라면 누구나 볼 수 있도록) 영어로 쓰는 경우가 많은데, 이번 프로그램의 경우 여러 가지로 삽질을 했기 때문에 글 하나로는 약간 부족한 감이 있다. 그러하니 2개 국어 저널이라는 이름에 걸맞도록 하나는 영어, 하나는 한국어로 쓰고, 한국어 글은 영어 글에 없는 새로운 내용을 넣어서 한국어 독자에게 좀 더 보너스(?)를 주도록 하겠다. 코드 골프를 어떻게 하는지 궁금한 사람에게 괜찮은 내용이 될 것이다. 아, 코드를 다 이해해야 할 필요는 없지만 코드를 이해하고 싶다면 기본적인 코드 골프 테크닉은 알고 있을 필요는 있다.
시작
개인적인 얘기를 좀 하자면, 쓰고 있던 논문 자체는 6월 말에 끝을 내긴 했지만 논문이 12페이지 제한이 있었기 때문에 넘치는 세부 내용을 technical report로 따로 내야 했다. 이 technical report는 수식 및 코드 지옥으로, 이런 저런 최종 확인 작업을 다시 거쳐야 했기 때문에 7월 5일에서야 비로소 모든 일이 끝이 났다. 모든 일이 끝나고 나서 지금껏 못 하고 있던 온갖 취미 생활(…대부분은 리듬게임이지만)을 하다가, 오랜만에 삽질이나 한 번 해 볼까 하고 주말을 잡고 했던 일이 하필이면 코드 골프였던 것이다.
프로그램 주제는 순전히 우연하게 잡았는데, 골프에 쓸 언어를 자바스크립트로 할까 C로 할까 하다가 Brainfuck 인터프리터도 C였으니까 이번에도 C를 하자, 그런데 C라면 텍스트 프로세싱을 하는게 낫지 않을까?1 라고 생각하면서 나온 것이 “a hundred”를 “100”으로 바꿔 주는 프로그램이었다. 펄 코드 골프 등에 비슷한 문제가 있다는 건 나중에 확인했으나 애초에 언어가 달라서 별 소용은 없었다.
프로그램의 기본적인 아이디어는 처음부터 존재했다. 즉, 입력을 낱말 단위로 처리하면서 적절한 변수(accumulator)에 계속 더해 나가다가, “hundred” 같은 특수한 경우에만 accumulator를 어떻게 잘 변경한다. 아주 맨 처음에는 변수를 여러 개 두고(ones, hundreds, thousands 등등) 할 생각도 했지만 변수를 하나만 두어도 올바른 입력이 들어 온다면 자리가 서로 겹칠 수 없기 때문에 잘 동작한다는 걸 깨닫고 설계가 바뀌었다. 전체 형태소를 모두 저장하기에는 코드 공간이 적기 때문에 필터링을 하는 아이디어도 맨 처음에 나온 것이다. 7월 8일 0시 경, 나는 다음과 같은 첫 코드를 IRC에 뿌렸다. (설명의 편의를 위해 이 글에서는 코드를 제대로 들여쓰기하도록 하겠다. 코드 크기는 공백이 없는 버전을 기준으로 한다.)
v;w[]={
18,14,663,658,210,6,19,622,7,462,654,398,21228,466,674862,12686
};
main(a,b,c,d){
for(b=0;(a=getchar())>45;)
if((43798722>>a&31)&1)b=b<<5|a&31;
for(c=b&1023;b;b>>=5)
for(d=0;d<16;++d)
if(w[d]==b){
if(d<10)d=c-654?c-665?d:d*10:d+10;
v+=d-15?d-14?d-13?d:v%100*99:v%1000*999:v%1000000*999999;
b=0;
break;
}
a<0?printf("%d",v):main();
}
이 325바이트 코드는 현재 코드와 비교했을 때 아이디어는 같지만 상당한 차이가 있는데, 필터링을 위해 비트 벡터를 쓰고 있으며(43798722는 afglnrstwy에 해당한다) 각 글자를 32진법으로 저장하고 있다는 점이 첫번째이다. 필터링할 문자에 b가 없는 이유는 원래는 million을 넘는 숫자를 처리할 생각이 없었기 때문이다(용법에 따라 다른 수를 가리킬 수 있다는 좋은 핑계가 있기는 하지만, 사실 그냥 코드를 줄이려고 그랬던 거다). 그리고 첫 버전에는 a와 and를 위한 지원이 딱히 없었다(당시에는 어떻게 처리해야 할 지조차 몰랐다).
처음에는 으레 그렇듯 코드 크기가 급속하게 줄어들었다. 우선 굳이 break을 쓰지 않아도, d와 b를 적절한 숫자로 설정하면 루프를 자연스럽게 종료시키는 것이 가능하기 때문에 블록을 쓸 이유가 없었다. 굳이 d<10을 if 문으로 빼낼 필요 없이 삼항연산자로 합쳐도 된다는 것도 자명했다. 무엇보다, hundred, thousand 등등에 대해 경우를 모두 나눠서 짤 필요 없이 100, 1000, 1000000을 어디엔가 저장하고 그걸 가지고 수식을 만들어도 된다는 걸 눈치챈 게 컸다. 이 때문에 굳이 million까지로 입력을 제한할 이유가 사라졌기 때문에 trillion까지의 지원이 새로 추가되었고, 얼마 안 지나 코드는 다음과 같이 바뀌었다.
long long v,w[]={
18,14,663,658,210,6,19,622,7,462,654,398,21228,466,659,12,76,21068,
100,1e3,1e6,1e9,1e12
};
main(a,b,c,d){
for(b=0;(a=getchar())>45;)
if((43798726>>a&31)&1)b=b<<5|a&31;
for(c=b&1023;b;b>>=5)
for(d=18;d--;w[d]-b||
(v+=d>12?v%w[d+5]*~-w[d+5]:d>9?d:c-654?c-665?d:d*10:d+10,b=d=0));
a<0?printf("%lld",v):main();
}
이 코드는 316바이트이다(대응되는 짧은 버전의 코드는 286바이트였다). 낱말 테이블로만 쓰이던 w에 100, 1000 등을 함께 넣어서 인덱스에 5만 더하면 해당하는 값을 얻을 수 있도록 하여 코드를 줄였다. 또한 형태소 분석기는 첫 몇 글자만 맞으면 되기 때문에 674862(“tsan”)와 12686(“lln”)를 659(“ts”)와 12(“l”)로 변경한 것도 이 때이다. 21228(“twl”)과 21068(“trl”)은 어떻게 해도 줄일 수 없었는데, 이 두 엔트리는 이후에도 온갖 문제를 유발했다.
이 시점에서 보통 드는 생각은 “어떻게 하면 테이블을 최소화할 수 있을까?”인데, 가장 이상적인 경우는 깔끔하게 탈출열(escape sequence)이 전혀 안 들어 있는 문자열 리터럴 하나로 끝나는 경우이다. 하지만 대부분의 엔트리가 128은 커녕 256을 훌쩍 넘기고 있기 때문에 먼저 테이블에 들어 가는 숫자를 최대한 줄일 필요가 있었다.
조금 생각한 끝에, 다음과 같은 방법을 고안해 냈다. 우선 각 글자가 5비트로 저장되기는 하지만 가능한 글자 수는 11개 밖에 없다는 걸 생각해 보면, 다음과 같은 그림을 그릴 수 있다. (처음에 하나 비어 있는 자리는 ASCII에서 0x40에 해당하는 @이다.)
.ab...fg....l.n...rst..w.y.
이제 각 자리에 해당하는 숫자들을 서로 겹치지 않게 하면서 최대한 작은 숫자로 변경할 수 있는지 알아 본다. 놀랍게도, 각 숫자를 15로 나눈 나머지를 구하면 다음과 같이 전혀 겹치지 않는다는 걸 알 수 있다.
.ab...fg....l.n
...rst..w.y.
따라서 32진법 대신 15진법을 쓰는 것이 가능하고(!), 아까 전에 말했던 “twl”과 “trl”을 제외한 모든 엔트리가 256 아래로 내려가는 걸 볼 수 있다. 코드는 다음과 같이 바뀌었다.
long long v,w[]={
3,14,83,78,93,6,4,74,7,224,89,194,1257,213,79,12,42,1182,
100,1e3,1e6,1e9,1e12
};
main(a,b,c,d){
for(b=0;(a=getchar())>45;)
if(a%=32,43798726>>a&1)b=b*15+a%15;
for(c=b%225;b;b/=15)
for(d=18;d--;w[d]-b||
(v+=d>12?v%w[d+5]*~-w[d+5]:d>9?d:c-89?c-85?d:d*10:d+10,b=d=0));
a<0?printf("%lld",v):main();
}
이 방법을 쓰자 코드는 302바이트(짧은 버전은 273바이트)가 되었다. 숫자가 꽤 줄어 들긴 했지만 여전히 “twl”과 “trl”이 버티고 있기 때문에, 처음에는 문자열을 두 개 써야 했다.
long long u,v;
main(a,b,c,d){
for(b=0;(a=getchar())>45;b=43798726>>a&1?b*15+a%15:b)a%=32;
for(c=b%225;b;b/=15)
for(d=18;d--;"CNSN]FDJG`YBiUOLj^"[d]+"@@AAA@@A@CACSCA@@R"[d]*64-4160-b||
(v+=d>12?v%u*~-u:d>9?d+6:c-89?c-85?d:d*16:d+16,b=d=0))
u=1ll<<"XdpHL"[d%5]-64;
a<0?printf("%llx",v):main();
}
이 버전은 289바이트(짧은 버전은 264바이트)이다. 각 엔트리는 문자열 두 개로 표현되었으며, 첫 문자열이 하위 6비트, 둘째 문자열이 상위 5비트를 표현하도록 매핑이 되어 있다. 그 밖에도 잘 보면 첫 루프에서 if 문이 사라지고 삼항 연산자로 바뀐 것을 알 수 있다.
이 버전에서는 또 하나 중요한 차이가 있는데, 바로 본래 쓰던 w[] 배열을 완전히 날렸다는 점이다. 본래대로라면 10의 거듭제곱을 쉽게 계산할 방법이 없어서 배열을 써야 했지만, 출력할 때 10진법이 아니라 16진법을 써도 된다는 중요한 관찰 덕분에 10의 거듭제곱 대신 16의 거듭제곱을 쓸 수 있게 된 것이다. 16의 거듭제곱은 비트 시프트로 쉽게 구현할 수 있기 때문에 시프트할 크기(아무리 커도 trillion의 48이 최대이다)만 잘 저장하면 충분한 것이다. 16진법을 쓴다는 아이디어가 어디서 나왔는지 궁금하신 분은 이걸로 궁금증이 풀리셨으리라 믿는다.
덤으로, 이 시점부터 긴 버전과 짧은 버전을 따로 관리하기 시작했다. 물론 시프트 크기를 나타내는 문자열을 더 이상 눈에 보기 쉽게 편집할 수 없기 때문이기도 하지만, 짧은 버전은 1바이트 더 줄일 수 있기 때문이기도 했다. 루프 몸체를 다음과 같이 바꾸면 된다.
u=1<<"` 0"[d%3]/4
최대값이 million에 대응하는 24였기 때문에, 뺄셈 대신 나눗셈을 써서 1바이트를 더 절약할 수 있다. 이 시점이 대략 8일 밤 2시 반 정도였다.
간단한 접근이 옳은 접근
코드 골프를 많이들 복잡하고 손댈 수 없는 코드를 짜는 일로 인식하는 경우가 많은데, 후자는 아마도 참이겠지만 전자는 생각 외로 참이 아닌 경우가 많다. 복잡한 코드일수록 더 짧게 줄이기가 힘들다. 앞에서 나는 32진법을 15진법으로 줄이는 아이디어를 생각하고 흐뭇해하긴 했지만, 테이블 크기가 슬슬 진짜 문제로 부상하면서 그냥 문자 11개에 대응하는 11진법을 쓸 수는 없을까 하는 생각을 하게 되었다. 그리고…
long long u,v;
main(a,b,c,d){
for(b=0;(a=getchar()|32)>45;)
for(c=11;c--;b="rtabsfgwyln"[c]-a?b:b*11+c);
for(c=b%121;b;b/=11)
for(d=18;d--;"@JRKwEDvF8U-\217.OIj\302"[d]&255^64^b||
(v+=d>12?v%u*~-u:d>9?d+6:c-21?c-19?d:d*16:d+16,b=d=0))
u=1ll<<"XdpHL"[d%5]-64;
a<0?printf("%llx",v):main();
}
이런 280바이트 코드가 탄생했다. 굳이 필터링을 위해서 비트 벡터를 쓸 필요 없이, 그냥 문자열에서 한 글자씩 비교해서 맞으면 인덱스를 더하고 아니면 마는 코드를 짜는 게 더 짧았다! 11개의 글자를 11개의 자리로 표현할 수 있으니 최적의 접근이 아닐 수 없었다(물론 당연히 이 생각 또한 틀렸다).
이 접근의 또 다른 장점은, 각 글자에 대응하는 인덱스를 원하는 대로 수정하면서 최적의 결과를 찾아 낼 수 있다는 것이다. 잘 보면 t가 자리 1에 대응되는데, “twl”과 “trl”을 256 아래로 낮추기 위해서 필요한 조건이었다(t가 3 이상이면 아예 t로 시작하는 세 자리 숫자가 모두 256을 넘겨 버린다). 또한 64와 XOR하는 부분을 64 대신 다른 숫자로 바꾸면 테이블에서 탈출열을 최대한 제거해서 더 짧은 문자열을 만들 가능성도 있었기 때문에, 이 시점부터는 테이블 자동 생성 코드가 필수가 되었다. 실제로 위 코드에서 a와 l을 맞바꾸면, “trl”이 130에서 123으로 바뀌기 때문에 탈출열을 하나 더 제거하는 게 가능했다.
원래 접근에서는 ASCII 코드의 하위 5비트만을 사용해서 대소문자 구분 없이 글자를 인식했지만, 여기서는 문자열에 들어 있는 문자와 비교해야 했기 때문에 아예 문자를 항상 소문자로 변환하는(32와 OR) 방법을 썼다. 2의 보수 표현을 가정하면 음수에는 어떤 숫자를 OR시켜도 음수이기 때문에, 아무 변경 없이 EOF를 그대로 처리할 수도 있다.
이 코드에 다다른 것이 대략 7월 9일 자정 쯤이었던 것 같다. 앞에서 말한 대로 탈출열을 하나 더 제거하면 짧은 버전이 정확히 256바이트가 되었기 때문에 본래의 목표는 달성했다고 볼 수 있었지만, 아무래도 여전히 길어 보이는 건 어쩔 수 없었다. 그래서 코드를 줄이는 걸 잠시 멈추고, 이왕 길게 짤 거면 기능을 좀 더 추가하는 게 낫지 않을까? 하면서 생각한 게 a와 and를 제대로 처리하게 하는 것이었다.
당시 코드에서 a는 테이블에 없는 낱말이라 0으로 처리되었기 때문에 “a hundred”는 “zero hundred”처럼 인식이 되는 문제가 있었다. 이 문제를 해결하려면 “a”와 “one”(필터링하면 “n”)를 같은 인덱스에 집어 넣거나 어느 한 쪽을 특수 처리해야 하는데, 특수 처리하자니 코드가 길어질 게 뻔하기 때문에(10보다 작은 숫자는 인덱스가 곧 그 낱말의 값이니까) 코드를 최대한 키우지 않으면서 둘을 똑같은 날말로 인식하게 할 방법을 생각해야 했다. 그리고 11진법 대신 10진법을 쓴다는 아이디어가 나온 때가 바로 이 때였다.
long long u,v;
main(a,b,c,d){
for(b=c=0;c++||(a=getchar()|32)>45;b="wntrfslygba"[c]-a?b:b*10+c)c%=11;
for(c=b%100;b;b/=10)
for(d=19;d--;"CATWkDEsHKM%ZF \254U}\216"[d]&255^64^b||
(v+=d>15?d:d>9?v%u*~-u:c-21?c-27?d:d*16:d+16,b=d=0))
u=1ll<<"LXdpH"[d%6]%64;
a<0?printf("%llx",v):main();
}
이미 낱말을 숫자와 비슷하게 처리하고 있기 때문에, a를 (1에 대응하는 문자)(0에 대응하는 문자)로 바꾸는 것이 가능한 것이다. a가 쓰이는 곳은 그렇게 많지 않기 때문에 1에 대응하는 문자를 n으로 하고 0에 대응하는 문자를 겹치지 않게 해서 형태소 분석 과정에서 첫 글자 n만 인식하도록 하는 게 가능했다. 0에 대응하는 문자로는 w 또는 y가 가능했는데, 당시에는 그냥 편의상 w를 골랐다.
“a”를 이런 식으로 “one”과 같이 취급하면 한 가지 문제가 새로 생기는데, “and”(필터링하면 “an”)도 1로 취급되어 잘못된 결과가 나오는 것이다. 다행히도 100, 1000 등을 처리하는 코드에 1을 집어 넣으면 변수에 아무 변화도 일어나지 않는다는 걸 알고 있었기 때문에, 시프트 크기 0을 어딘가에 잘 끼워 넣어서 문제를 해결할 수 있다. 실제로 시프트 크기를 나타내는 문자열에는 변화가 없지만, 코드를 잘 들여다 보면 문자열 맨 끝에 붙어 있는 널 문자가 바로 이 “and”에 대응하는 엔트리라는 걸 확인할 수 있다.
이 접근은 필연적으로 엔트리 하나를 더 추가해야 했고, 시프트 크기 테이블에는 변화가 없지만 낱말 테이블에서 다시 나타난 탈출열 하나를 제거할 방법을 찾지 못 했기 때문에 원래2보다 4바이트 늘어난 276바이트(짧은 버전은 253바이트)였다. 참고로 낱말 테이블의 시작부에 있는 "CATWk...는 테이블 검색 과정에서 내가 고른 게 맞고, 짧은 버전에도 비슷한 문구가 있다(이 쪽이 더 신기하게 생겼다):
u,v;
main(a,b,c,d){
for(b=c=0;c++||(a=getchar()|32)>45;b="yntwgfrsla"[c]-a?b:b*9+c)c%=10;
for(c=b%81-18;b;b/=9)
for(d=17;d--;"fauxSeg djs)\245oz2h"[d]&255^96^b||
(v+=d>12?v%u*~-u:d>9?d+6:c-1?c?d:d*16:d+16,b=d=0))
u=1<<"` 0"[d%4]/4;
a<0?printf("%x",v):main();
}
…당연히 이 쪽에는 “trl”이 없으므로 탈출열은 하나 밖에 나오지 않는다.
짧은 버전의 경우 b가 없으니까 이미 9진법으로 내려가서 탈출열 하나만 제거하면 테이블 최적화는 정말로 끝이 나지만, 긴 버전의 경우 10진법이기 때문에 탈출열 말고도 숫자가 좀 큼지막하다는 문제는 여전히 남아 있었다. 9진법으로 내려가기만 해도 마지막 두 글자를 계산하는 수식에서 100 대신에 81을 쓸 수 있기 때문에 도합 3바이트가 줄어들고, 낱말 테이블에서 탈출열이 아예 안 나오게 만들 수 있는 가능성도 높아질 것이었다. 그래서 몇 가지 시도를 하다가, 급기야는 8진법도 가능하겠다는 결론을 내리게 되었다.
8진법을 생각한 이유는 이렇다. 일단 “a”를 “n”으로 변환시켜야 하기 때문에 n은 항상 인덱스 1에 존재해야 한다. 그런데 n으로 시작하는 엔트리는 “one”(“n”), “nine”(“nn”), “hundred”(“nr”) 정도 밖에 없고, 그러면 다른 것들을 n으로 시작하는 문자로 변환시켜서 나머지 가능성을 채울 수도 있지 않는가? 실제로 “g”(“eight”에 한 번 나옴)와 “b”(“billion”에 한 번 나옴)는 다른 곳에서 전혀 나오지 않기 때문에, 아예 이 둘을 모두 날려 버리면 8진법이 가능한 것이다. 실제로는 한 가지 제약 사항이 더 있으니, a, g, b 중 하나는 nn에 대응되어야 할텐데 “nine”이 이미 이 엔트리를 쓰고 있기 때문에 뒤에 한 글자가 더 붙어서 구분을 할 필요가 있었다. “billion”을 예제로 들면, b가 nn에 대응된다고 치면 “nnlln”이 되니 저장할 때는 “nnl”이라고 써야 한다. g가 nn에 대응되었다면 마찬가지로 “nnt”를 저장했어야 할 것이고, 어떤 경우라도 a를 nn에 대응시킬 수는 없다(“a”가 “one”이 아닌 “nine”에 대응될 것이다). 이 접근법을 토대로 탐색한 결과, 드디어 탈출열이 아예 없는 문자열을 얻을 수 있었다:
long long u,v;
main(a,b,c,d){
for(b=c=0;c++||(a=getchar()|32)>45;b="ynwtsflrabg"[c]-a?b:b*8+c)c%=11;
for(c=b%64-24;b;b/=8)
for(d=19;d--;"1+DIY/.K439kG0x(C["[d]-42&255^b||
(v+=d>15?d:d>9?v%u*~-u:c-1?c?d:d*16:d+16,b=d=0))
u=1ll<<"LXdpH"[d%6]%64;
a<0?printf("%llx",v):main();
}
이 코드는 266바이트로, 낱말 테이블은 정확히 18바이트(19바이트가 아닌 이유는 맨 뒤에 널문자도 포함되어 있기 때문에)이고 더 이상 줄일 수는 없다. 문자열의 첫머리에 있는 "1+DIY... 또한 앞에서와 비슷한 이유로 내가 선택한 것이다. 또 다른 변경점으로는, 본래는 “ten”, “eleven”, “twelve”가 인덱스 10, 11, 12에 있었지만 코드를 2바이트 더 줄이기 위해 16, 17, 18로 옮겼다는 것이다. 짧은 코드에서는 (일단 인덱스 16, 17, 18을 쓸 수 없기 때문에) 이런 식으로 코드를 줄일 수는 없었지만, 비슷한 방법으로 탈출열이 없는 문자열을 발견해 250바이트 코드를 만들 수 있었다.
10진법에 다다를 때까지 하루3, 8진법에 다다를 때까지 다시 하루가 걸렸으니, 이 시점에서 이미 주말 프로젝트(…)는 물건너가고 화요일 자정이 되어 버렸다. 긴 버전을 256바이트에서 10바이트 밖에 안 남았기 때문에 이왕 하는 김에 긴 버전을 256바이트까지만 줄이고 공개하기로 마음을 먹고 코드를 좀 더 들여다 보다가, 옛날에 residue number system라는 글을 쓴 걸 생각해 내고 열심히 고민한 끝에 다음과 같은 코드에 다다랐다.
long long u,v;
main(a,b,c,d){
for(b=c=0;c++||(a=getchar()|32)>46;b="ynwtsflrabg"[c]-a?b:b*8+c)c%=11;
for(c=b%64-24;b;b/=8)
for(d=19;d;"1+DIY/.K430x9G(kC["[d]-42&255^b||
(v+=d>15?d:d>9?v%u*~-u:c-1?c?d:d*16:d+16,b=d=0))
u=1ll<<6177%d--*4;
a<0?printf("%llx",v):main();
}
그러니까, 어떤 식으로는 인덱스 10부터 15까지에 0, 8, 12, 24, 36, 48을 유일하게 매핑시킬 수만 있으면 되기 때문에 적절한 상수를 골라서 나머지 값을 이와 같이 되도록 하는 게 가능한 것이다. (실제로는 나머지로 48이 나올 수는 없으니 4로 나눴다.) 본래 상수는 42였지만 안타깝게도 d가 0이면 나눗셈을 할 수 없기 때문에(…) d--의 위치를 살짝 바꿔서 인덱스 11부터 16까지를 해당하는 값으로 대응시키는 상수 6177을 찾아 냈다. 이 숫자는 확장 유클리드 호제법을 여러 번 돌려서 찾아 낼 수도 있지만(나는 이렇게 했다), 그냥 0부터 11, 12, …, 16의 최소공배수까지 하나 하나 테스트하면서 적절한 것을 찾아 내도 사실 상관은 없다. 지금 생각하면 왜 호제법을 일일이 손으로 짰는지 모르겠다….
이 코드는 261바이트였지만, 막판에 정리를 하던 도중에 최적화를 몇 가지 더 찾아 냈다. 일단 테이블에서 겹치는 엔트리가 존재하지 않기 때문에 한 번 낱말을 찾아 냈다고 안쪽 루프를 바로 빠져 나갈 필요가 없고, 따라서 d를 0으로 설정할 필요가 없다. 또한 원래 코드에서는 마지막 두 글자가 24(“-tn”)이면 d+16, 25(“-ty”)이면 d*16, 아니면 d를 더하도록 되어 있었지만, 마지막 두 글자가 24일 때 c가 0이 되도록 하면 첫번째와 세번째 경우를 d+16*!c와 같이 합칠 수 있다. 이 최적화를 적용하면 코드는 정확히 256바이트로 줄어 든다.
long long u,v;
main(a,b,c,d){
for(b=c=0;c++||(a=getchar()|32)>46;b="ynwtsflrabg"[c]-a?b:b*8+c)c%=11;
for(c=b%64-25;b;b/=8)
for(d=19;d;"1+DIY/.K430x9G(kC["[d]-42&255^b||
(v+=d>15?d:d>9?v%u*~-u:c+1?d+!c*16:d*16,b=0))
u=1ll<<6177%d--*4;
a<0?printf("%llx",v):main();
}
대응되는 짧은 버전은 240바이트가 되었다.
u,v;
main(a,b,c,d){
for(b=c=0;c++||(a=getchar()|32)>46;b="yntfgwslra"[c]-a?b:b*9+c)c%=10;
for(c=b%81-19;b;b/=9)
for(d=17;d;"2+ADM-0a.4|1C;=j"[d]-42&255^b||
(v+=d>13?d+2:d>9?v%u*~-u:c+1?d+!c*16:d*16,b=0))
u=1<<198%d--*4;
a<0?printf("%x",v):main();
}
이 코드에 다다른 시점은 대략 11일 밤 2시 경이었고, 설명글을 모두 쓴 뒤에 저널에 공개한 것은 4시 경이었다.
놓치고 지나가는 것들
4시 경에 글을 공개하고, 레딧과 해커 뉴스에 링크를 올렸을 때 처음 받은 반응은 황당하게도 “spoken number”라는 표현이 틀렸다는 지적이었다. 숫자를 영문으로 쓴 것을 바꿔 주는 거니까 “spelt number”가 맞다는 것이다. 그래서 곧바로 내 구릿구릿한 영어 실력을 탓하면서 표현을 고쳤으나, 해커 뉴스는 한 번 댓글이 올라 오면 제목 수정이 안 되어서(레딧은 아예 안 된다) 안타깝게도 그 쪽은 고칠 수 없었다.
코드로 넘어 가면, 글을 IRC에 공개했을 때 leonid 님께서 코드를 보시더니 곧바로 2바이트 더 줄여 버리셨다. 크흑.
long long u,v;
main(a,b,c,d){
for(b=c=0;c++||(a=getchar()|32)>46;b="ynwtsflrabg"[c%=11]-a?b:b*8+c);
for(c=b%64-25;b;b/=8)
for(d=19;d;"1+DIY/.K430x9G(kC["[d]-42&255^b||
(v+=d>15?d:d>9?v%u*~-u:~c?d+!c*16:d*16,b=0))
u=1ll<<6177%d--*4;
a<0?printf("%llx",v):main();
}
그러니까 c%=11을 대괄호 안에 넣고, c+1이 0인지 비교하는 대신 ~c가 0인지 비교하는 것인데 둘 다 당연한 것인데도 256바이트 되면 손 털고 올리자(…)라는 신념 때문에 미처 보지 못 한 것이었다. 하지만 이미 글은 다 써서 레딧에서 upvote가 쏟아지고 있는 상황이고, 굳이 2바이트 줄인 것 때문에 글을 바꿀 필요성은 느끼지 못 해서 “더 줄일 수는 있지만 그 쪽은 알아서 해 보세요”라는 취지의 FAQ를 올려 놓고 다시 일상으로 돌아 갔다. 아니, 일상으로 돌아 갔어야 했는데…
11일 저녁에 전산동 옥상에서 광란의 고기 파티(첫 고기가 구워지자마자 비가 왔기 때문에 아주 개판이 되었지만)를 한 뒤 연구실에서 잠깐 놀다가, 오후 8시 쯤에 지금껏 귀찮아서 한 번도 손을 대지 않은 코드 구조를 한 번 들여다 보기 시작했다. 그리고 20분만에 다음과 같은 코드를 찾아 냈다!
long long n,u,m,b;
main(e,r){
for(;n++||(e=getchar()|32)>46;b="ynwtsflrabg"[n%=11]-e?b:b*8+n);
for(r=b%64-25;b;b/=8)
for(n=19;n;"1+DIY/.K430x9G(kC["[n]-42&255^b||
(m+=n>15?n:n>9?m%u*~-u:~r?n+!r*16:n*16,b=0))
u=1ll<<6177%n--*4;
e<0?printf("%llx",m):main();
}
그러니까, 첫번째 루프는 루프 시작 전에 b(현재 입력되고 있는 낱말의 숫자 표현)와 c(현재 입력된 문자, 바뀐 코드에서는 e)가 0일 것을 가정하고, 두번째 루프는 루프가 끝나고 나면 b와 d(낱말 테이블을 검색할 때 사용하는 인덱스, 바뀐 코드에서는 n)가 0이 된다. 그런데 d와 c는 둘 다 임시 변수이기 때문에, 두번째 루프에서 c와 d의 사용을 뒤집으면 d는 항상 두번째 루프가 끝날 때 0이 되어 다시 0으로 초기화할 필요가 없어진다! 물론 맨 처음에는 아무튼 0이어야 하긴 하는데 이건 변수를 전역으로 밀어 넣으면 해결된다. 따라서 초기화 코드 5바이트가 통째로 사라지는 것이다.
코드 크기에 영향은 전혀 주지 않지만, 이 시점에서 사용하는 변수 6개를 각각 n, u, m, b, e, r로 바꾼 것도 이 시점이다(진즉에 이 생각을 못 했는지…). 다만 main에 인자가 적어도 하나는 있어야지 1바이트 절약이 가능하고, 반대로 초기화와 타입 문제 때문에 모든 변수를 main 인자로 밀어 넣을 수도 없기 때문에 numb와 er이 나뉜 것은 좀 아쉬운 일이긴 하다. 뭐 IRC에서는 “long, long numb-main-er”라고 농을 치긴 했다만.
삽질은 여기에서 그치지 않았다. 한 시간 뒤 코드는 이렇게 변해 있었다.
long long n,u,m,b;
main(e,r){
for(;n++||(e=getchar()|32)>=0;b="ynwtsflrabg"[n%=11]-e?b:b*8+n)
for(r=b%64-25;e<47&&b;b/=8)
for(n=19;n;"1+DIY/.K430x9G(kC["[n]-42&255^b||
(m+=n>15?n:n>9?m%u*~-u:~r?n+!r*16:n*16,b=0))
u=1ll<<6177%n--*4;
printf("%llx",m);
}
본래 재귀호출을 쓴 이유는, 재귀호출을 쓰지 않으면 for(;조건;) 같은 형태의 굉장히 비효율적인(빈 문장이 두 개나 남는데 채워 넣을 문장이 없었다) 코드가 나와서 원래보다 길어지기 때문이었다. 그런데 자세히 생각해 보니, 첫번째 루프와 두번째·세번째 루프를 완전히 합치는 것이 불가능하지는 않아 보였다. 즉, 첫번째 루프에서는 e가 0 이상인지 체크하고(EOF이면 곧바로 빠져 나가야 하니까), 두번째 루프에서는 본래 하던 대로 b가 0인지 체크함과 동시에 e가 낱말의 끝인지 함께 체크하는 것이다. e는 낱말을 처리하는 과정에서는 EOF 체크 때문에 항상 유지를 해야 했기 때문에 루프를 돌 때마다 매 번 체크를 한다 해도 큰 문제는 없는 것이다. 이렇게 하여 코드는 6바이트 더 줄어 들었다.
최적화는 여기에서 그치지 않았다. 코드가 13바이트씩이나 줄어든 것은 분명 글을 갱신할 만한 이유에 해당하기 때문에 오후 10시 경에 새 243바이트 코드(짧은 버전은 227바이트)를 올리긴 했지만, 사실 레딧에서 코드를 잘 살펴 보던 사람이 한 가지 최적화를 더 찾아 냈다.
long long n,u,m,b;
main(e,r){
for(;n++||(e=getchar()|32)>0;b="ynwtsflrabg"[n%=11]-e?b:b*8+n)
for(r=b%64-25;e<47&&b;b/=8)
for(n=19;n;"1+DIY/.K430x9G(kC["[n]-42&255^b||
(m+=n>15?n:n>9?m%u*~-u:~r?n+!r*16:n*16,b=0))
u=1ll<<6177%n--*4;
printf("%llx",m);
}
즉, 널 문자가 입력되었다 하더라도(이 경우 프로그램이 끝나면 안 된다) 어차피 32로 OR되는 과정에서 e가 0보다 커지기 때문에 e가 0과 같은지 체크하는 것은 의미가 없다. 이렇게 하면 1바이트 더 줄어서 242바이트 코드(짧은 버전은 226바이트)가 된다. 이 코드는 현재 내가 알고 있는 최소 크기 코드이다. 다만 글을 고치긴 귀찮았기 때문에 글에 별도로 올라가 있지는 않은데, 이것보다 좀 더 획기적으로 코드가 줄어드는 방법을 알아낸다면 적용해서 글에 올릴 작정이다.
포스트 모템(post-mortem)
처음의 “million”까지만 처리할 수 있는 325바이트 코드로부터 같은 일을 하는 226바이트 코드에 다다를 때까지는 대략 나흘의 시간이 걸렸다. 예전에 올렸던 Brainfuck 인터프리터가 주말에 정확히 24시간 써서 나온 걸 생각하면 생각보다 오래 걸린 셈이다. (물론 중간에 홈커밍이 있어서 36시간 정도 날리긴 했지만…)
개인적으로는 이 작업을 하면서 느낀 것이 많은데, 일단 코드 골프의 제 1 덕목인 근성(…) 면에서 좀 반성하고 있다. 항상 새로운 접근을 생각할 때마다 그보다 더 간단하고 짧은 접근이 존재하는지 생각해 봐야 하는데 그런 면에서 약간 서둘렀던 감이 없지 않다. 실제로 나는 비트 벡터 접근을 포기할 때까지 한동안 필터링할 문자를 더 늘려서(h를 추가한다거나…) 테이블 크기를 줄어들게 하는 것만 생각하고 있었고, 최적화를 덜 한 채 코드를 공개해 버려서 나중에 부랴부랴 수정하는 삽질을 해야 했다.
한편으로는 이번 코드에 대한 자세한 설명을 영문으로 써 낸 것에 대해서는 상당히 만족하고 있다. Brainfuck 인터프리터 같은 경우에도 사실 몇몇 사람에게 말로 설명을 해 주기는 했는데, 말로 하는 거랑 글로 쓰는 건 확실히 차이가 크더라. 글로 쓸 경우 저자의 시간과 독자의 시간이 서로 분리되어 있기 때문에 독자에게 “내 코드가 왜 이렇게 만들어졌는가”를 설득시키는 게 중요하고, 그런 면에서 좀 더 잘 정리된 설명을 쓸 수 있지 않나 싶다. 실제로 레딧 댓글 같은 곳을 봐도 설명을 마음에 들어하는 사람들이 꽤 있었던 것 같다. Brainfuck 인터프리터 설명은… 음 언젠가는 하겠지.
마지막으로, 상당한 수의 사람들이 처음에 “spoken number”라고 쓴 걸 보고 음성인식인가 착각을 했는데(…) 어쩌면 이 쪽도 한 번 파 볼 가치가 있을 지도 모르겠다는 생각이 든다. 아 물론 정말로 말로 “one hundred” 하면 100이 나오는 걸 만들겠다는 소리는 아니고, 특정한 종류의 사운드를 인식한다거나 하는 건 어느 정도 가능하지 않을까 싶다. Goertzel 알고리즘 같은 걸 구현해서 DTMF를 인식한다거나(그 집전화에서 버튼 누르면 나는 그 소리 얘기다)… 내가 아는 바로 이런 류의 코드로 obfuscated code를 짠 사람은 없을텐데(사운드를 생성하는 것은 IOCCC에 나온 적이 있다) 나쁘지 않은 방향 같아 보인다.
