메아리

Tour de IOCCC: 2006/toledo1

char    *e,t    [366    ],*f
,*g,    *h,*    i;d,    m  ;
    main    (c,b)   char    **b;{
    for(    ;d[t]   =d%3    ?60<d
&300    >d&6    <d %    30?0
:32:    d%30    ?32:    10 ,
    366>    ++d;)   ;for    (g=3*
    atoi    (*++    b) +    34+t;
i=f=    "\1"    "\7"    "(d"
"\177"  "yX"    "\34"   ,e=g
    ;  )    for(    *e++    =++m/
    10 +    48,g    =c=0    ,*e =
48+m    %10;    h=e-    65+*
i,d=    *h,*    i++;    f-=8
    ,g=d    <c?c    =d,h:   g)for
    (; d    -=!!    h[*f    ++-64
    ],*f    ;) ;    puts    (t);}

눈에 확 들어 오는 프로그램만큼 좋은 건 없습니다. 물론 체스판으로 뭘 할 거냐는 여러 가지 답이 있지만요.

뭘 하는 프로그램인가?

이 프로그램은 체스판에서 지정한 위치에 나이트(knight)를 놓은 뒤 나머지 예순 세 개의 칸을 나이트의 규칙에 맞게 모두 방문합니다. 나이트의 이동 규칙은 상하좌우로 한 칸 움직인 뒤 방금 전 움직인 방향과 직각이 되는 방향으로 두 칸 움직이는 것입니다. (흔히 "L"자 모양으로 움직인다고 합니다.)

이 문제는 적어도 9세기에 알려진 아주 유명한 문제로 "나이트의 여행"이라고 부릅니다. 나이트의 여행은 몇 가지 분류가 있어서 모든 칸을 채운 뒤 처음 시작했던 칸으로 다시 돌아 올 수 있으면 "닫혔다"고 하는데, 이 프로그램은 (아쉽게도) 닫힌 경로를 만들어 내는 건 아닙니다.

프로그램을 실행해 봅시다. 프로그램은 하나의 인자를 받는데 십의 자리가 행 번호(1부터 8까지)고 일의 자리가 열 번호(마찬가지)인 시작 위치입니다. 이 프로그램은 각 칸이 몇 번째로 방문되는지 출력합니다.

$ gcc toledo1.c -o toledo1
$ ./toledo1 11



      01 16 27 22 03 18 47 52
      26 23 02 17 46 51 04 19
      15 28 25 50 21 48 53 56
      24 35 30 45 62 55 20 05
      29 14 61 34 49 44 57 54
      36 31 38 41 60 63 06 09
      13 40 33 64 11 08 43 58
      32 37 12 39 42 59 10 07



$ ./toledo1 73



      33 20 31 06 35 10 41 08
      30 05 34 21 40 07 36 11
      19 32 39 54 37 62 09 42
      04 29 22 63 56 43 12 49
      23 18 55 38 53 48 61 44
      28 03 26 47 64 57 50 13
      17 24 01 58 15 52 45 60
      02 27 16 25 46 59 14 51



$

가끔씩 엉뚱한 인자를 줬을 때 동작하는 경우도 있습니다. 예를 들어 아래에서 "9행 0열"이라는 건 실제로 존재하지 않지만 잘 동작하지요. 하지만 0행 4열 같은 건 또 동작하지 않습니다.

$ ./toledo1 90



      56 49 16 45 64 43 14 11
      17 46 55 60 15 12 35 42
      50 57 48 63 44 65 10 13
      47 18 61 54 59 34 41 36
      28 51 58 33 62 53 24 09
      19 04 29 52 25 32 37 40
      02 27 06 21 30 39 08 23
      05 20 03 26 07 22 31 38
   01                        


$ ./toledo 04
Bus error

어떻게 동작하는가?

먼저 원래 모양을 좀 그럴듯한 코드로 정리합시다. 문자열 상수도 하나로 합치도록 하겠습니다.

char *e, t[366], *f, *g, *h, *i;
d, m;

main(c, b)
    char **b;
{
    for (; d[t] = d%3 ? 60<d & 300>d & 6<d%30 ? 0 : 32 : d%30 ? 32 : 10, 366 > ++d; );
    for (g = 3*atoi(*++b)+34+t; i = f = "\1\7(d\177yX\34", e = g; )
        for (*e++ = ++m/10+48, g = c = 0, *e = 48+m%10; h = e-65+*i, d = *h, *i++;
                f -= 8, g = d<c ? c=d,h : g)
            for (; d -= !!h[*f++-64], *f; );
    puts(t);
}

dm은 형이 지정되지 않아 int 형으로 자동 지정됩니다. K&R 문법으로 쓰여진 main 함수의 인자들 역시 b는 뒤에 명시적으로 타입이 정해지지만 cint이지요. 지금은 K&R 시대가 아니니 현대적인 코드로 옮깁시다.

char *e, t[366], *f, *g, *h, *i;
int d, m;

int main(int c, char **b)
{
    for (; d[t] = d%3 ? 60<d & 300>d & 6<d%30 ? 0 : 32 : d%30 ? 32 : 10, 366 > ++d; );
    for (g = 3*atoi(*++b)+34+t; i = f = "\1\7(d\177yX\34", e = g; )
        for (*e++ = ++m/10+48, g = c = 0, *e = 48+m%10; h = e-65+*i, d = *h, *i++;
                f -= 8, g = d<c ? c=d,h : g)
            for (; d -= !!h[*f++-64], *f; );
    puts(t);
    return 0;
}

이 프로그램에는 for 문이 무려 네 개나 있는데다가 모든 문장이 그 안에 박혀 있습니다. 이 때 다음과 같은 for 문이 있다 치면,

for (A, B, C; D, E; F, G) H;

이건 다음과 같은 while 문과 같습니다.

A;
B;
C;
D; /* 조건에는 영향을 미치지 않지만 조건 직전에 평가됨 */
while (E) {
    H;
    F;
    G;
    D; /* 마찬가지 */
}

이 점에 유념해서 for 문에 박혀 있는 문장들을 정리하면 다음과 같겠습니다.

char *e, t[366], *f, *g, *h, *i;
int d, m;

int main(int c, char **b)
{
    do {
        d[t] = d%3 ? 60<d & 300>d & 6<d%30 ? 0 : 32 : d%30 ? 32 : 10;
    } while (366 > ++d);

    g = 3 * atoi(*++b) + 34 + t;
    i = f = "\1\7(d\177yX\34"; /* 중복 */
    while (e = g) {
        *e++ = ++m / 10 + 48;
        g = c = 0;
        *e = 48 + m % 10;
        h = e - 65 + *i;
        d = *h; /* 중복 */
        while (*i++) {
            do {
                d -= !!h[*f++-64];
            } while (*f);
            f -= 8;
            g = d<c ? c=d,h : g;
            h = e - 65 + *i;
            d = *h; /* 중복 */
        }
        i = f = "\1\7(d\177yX\34"; /* 중복 */
    }

    puts(t);
    return 0;
}

"중복"이라고 표시해 놓은 줄들은 위에서 for를 while로 고치면서 같은 문장이 두 개가 되어 버리는 부분을 나타낸 것입니다. 그런데 잘 보면, 첫 문장은 조건문이 실행된 뒤 초기화를 해도 되는 것이니 (if는 조건문에 안 들어 있으니) 하나로 바꿀 수 있겠지요. 두번째 문장도 마찬가지입니다.

char *e, t[366], *f, *g, *h, *i;
int d, m;

int main(int c, char **b)
{
    do {
        d[t] = d%3 ? 60<d & 300>d & 6<d%30 ? 0 : 32 : d%30 ? 32 : 10;
    } while (366 > ++d);

    g = 3 * atoi(*++b) + 34 + t;
    while (e = g) {
        i = f = "\1\7(d\177yX\34"; /* 하나로 합침 */
        *e++ = ++m / 10 + 48;
        g = c = 0;
        *e = 48 + m % 10;
        h = e - 65 + *i;
        while (*i++) {
            d = *h; /* 하나로 합침 */
            do {
                d -= !!h[*f++-64];
            } while (*f);
            f -= 8;
            g = d<c ? c=d,h : g;
            h = e - 65 + *i;
        }
    }

    puts(t);
    return 0;
}

또 하나 눈여겨 볼 점은 첫 do-while 문은 단순히 t 배열을 초기화하는 역할을 한다는 것입니다. (d[t]t[d]와 같습니다!) 아무래도 미리 설정해 두는 게 좋겠죠? 안의 삼항 연산자에 따라서 배열을 초기화하면 다음과 같은 결과가 나옵니다.

char t[366] = {
    '\n',
    ' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','\n',
    ' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','\n',
    ' ',' ',' ',' ',' ',' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,'\n',
    ' ',' ',' ',' ',' ',' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,'\n',
    ' ',' ',' ',' ',' ',' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,'\n',
    ' ',' ',' ',' ',' ',' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,'\n',
    ' ',' ',' ',' ',' ',' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,'\n',
    ' ',' ',' ',' ',' ',' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,'\n',
    ' ',' ',' ',' ',' ',' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,'\n',
    ' ',' ',' ',' ',' ',' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,' ', 0 , 0 ,'\n',
    ' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','\n',
    ' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','\n',
    ' ',' ',' ',' ',' '};

(ASCII에서 ' '은 32, '\n'은 10입니다. 따라서 이 프로그램은 ASCII에 종속적입니다만 어차피 거의 모든 컴퓨터가 ASCII를 쓰니 이 정도야 괜찮겠죠.)

보는 것과 같이, 프로그램은 이 배열을 미리 만들어 둔 뒤 널 문자로 채워 둔 곳에만 숫자를 채워 넣어서 결과를 출력하는 것 같습니다. (맨 마지막의 puts(t)가 바로 그 역할이겠죠?) 보기 쉽게 문자열로 고치면 정리된 코드는 다음과 같이 됩니다.

char t[366] =
    "\n"
    "                             \n"
    "                             \n"
    "      \0\0 \0\0 \0\0 \0\0 \0\0 \0\0 \0\0 \0\0\n"
    "      \0\0 \0\0 \0\0 \0\0 \0\0 \0\0 \0\0 \0\0\n"
    "      \0\0 \0\0 \0\0 \0\0 \0\0 \0\0 \0\0 \0\0\n"
    "      \0\0 \0\0 \0\0 \0\0 \0\0 \0\0 \0\0 \0\0\n"
    "      \0\0 \0\0 \0\0 \0\0 \0\0 \0\0 \0\0 \0\0\n"
    "      \0\0 \0\0 \0\0 \0\0 \0\0 \0\0 \0\0 \0\0\n"
    "      \0\0 \0\0 \0\0 \0\0 \0\0 \0\0 \0\0 \0\0\n"
    "      \0\0 \0\0 \0\0 \0\0 \0\0 \0\0 \0\0 \0\0\n"
    "                             \n"
    "                             \n"
    "     ";

char *e, *f, *g, *h, *i;
int d, m;

int main(int c, char **b)
{
    g = 3 * atoi(*++b) + 34 + t;
    while (e = g) {
        i = f = "\1\7(d\177yX\34";
        *e++ = ++m / 10 + 48;
        g = c = 0;
        *e = 48 + m % 10;
        h = e - 65 + *i;
        while (*i++) {
            d = *h;
            do {
                d -= !!h[*f++-64];
            } while (*f);
            f -= 8;
            g = d<c ? c=d,h : g;
            h = e - 65 + *i;
        }
    }

    puts(t);
    return 0;
}

앞으로는 t 배열은 지면을 절약하기 위해 생략하겠습니다.

이제 방금 사라진 do-while 문 다음 문장을 봅시다. g는 영 그렇게 생기지는 않았지만 결과적으로 문자 배열인 t에 인덱스를 더한 것이라 포인터 맞습니다. b는 이 문장에서 단 한 번만 사용되는데 *++bb 포인터를 다음으로 옮긴 뒤 참조하는 것이므로 b[1]과 동일하겠습니다. 이 부분만 고치면,

g = &t[3 * atoi(b[1]) + 34];

이 됩니다. t는 출력할 내용의 템플릿으로 현재 초기화되어 있는데, 34라는 위치는 사실 여기를 가리킵니다. (편의상 널문자는 _로 표시했습니다.)

"\n"
"                             \n"
"   *                         \n"
"      __ __ __ __ __ __ __ __\n"
"      __ __ __ __ __ __ __ __\n"
"      __ __ __ __ __ __ __ __\n"
"      __ __ __ __ __ __ __ __\n"
"      __ __ __ __ __ __ __ __\n"
"      __ __ __ __ __ __ __ __\n"
"      __ __ __ __ __ __ __ __\n"
"      __ __ __ __ __ __ __ __\n"
"                             \n"
"                             \n"
"     "

각 줄은 개행 문자를 포함해서 30바이트로 이루어져 있고, 한 행의 숫자들 사이의 간격은 3바이트입니다. 1행 1열을 11로 입력받고 2행 1열을 21로 입력받으니 한 행에 숫자 열 개가 들어 간다고 가정해도 무리는 없겠습니다.

이제 그 다음 문장들을 살펴 봅시다.

while (e = g) {
    i = f = "\1\7(d\177yX\34";
    *e++ = ++m / 10 + 48;
    g = c = 0;
    *e = 48 + m % 10;
    h = e - 65 + *i;
    while (*i++) ...
}

이 루프의 조건문은 대입문입니다만 그냥 대입문을 안쪽으로 옮겨 놓는다고 문제는 안 되겠지요.

while (g) {
    e = g;
    i = f = "\1\7(d\177yX\34";
    *e++ = ++m / 10 + 48;
    g = c = 0;
    *e = 48 + m % 10;
    h = e - 65 + *i;
    while (*i++) ...
}

잠시 e를 사용하는 부분만 순서대로 모아 봅시다. 다만 g가 널이 되기 전에 e에 대입될 필요는 있겠고요.

while (g) {
    i = f = "\1\7(d\177yX\34";
    e = g;
    g = c = 0;
    *e++ = ++m / 10 + 48;
    *e = 48 + m % 10;
    h = e - 65 + *i;
    while (*i++) ...
}

중간에 나오는 48은, IOCCC를 열심히 들여다 보신 분은 눈치 채셨겠지만 ASCII 환경에서 '0'입니다. 따라서 이 시점에서 문자열에 숫자가 삽입되는 것이지요. 이 부분만 조금 더 예쁘게 고치면,

while (g) {
    i = f = "\1\7(d\177yX\34";
    e = g;
    g = c = 0;

    ++m;
    *e++ = '0' + m / 10;
    *e = '0' + m % 10;

    h = e - 65 + *i;
    while (*i++) ...
}

이제 남은 문장들만 다시 살펴 봅시다.

while (g) {
    ...
    h = e - 65 + *i;
    while (*i++) {
        d = *h;
        do {
            d -= !!h[*f++-64];
        } while (*f);
        f -= 8;
        g = d<c ? c=d,h : g;
        h = e - 65 + *i;
    }
}

e가 포인터이므로 h도 포인터이고, e - 65 + *ie + (*i - 65)로 쓰는 게 더 알아 보기 쉽겠습니다.

while (g) {
    ...
    h = e + (*i - 65);
    while (*i++) {
        d = *h;
        do {
            d -= !!h[*f++-64];
        } while (*f);
        f -= 8;
        g = d<c ? c=d,h : g;
        h = e + (*i - 65);
    }
}

안쪽에 있는 g에 대한 대입을 if 문으로 고치면,

if (d < c) {
    g = (c=d, h);
} else {
    g = g;
}

가 되는데, g = g 같은 문장은 아무 일도 하지 않고, c = dg에 대입될 값에 영향을 미치지 않으니 간단하게 고칠 수 있습니다. 고친 문장을 끼워 넣으면 이렇게 됩니다.

while (g) {
    ...
    h = e + (*i - 65);
    while (*i++) {
        d = *h;
        do {
            d -= !!h[*f++-64];
        } while (*f);
        f -= 8;
        if (d < c) {
            c = d;
            g = h;
        }
        h = e + (*i - 65);
    }
}

TODO


Copyright © 1999–2009, Kang Seonghoon.