GWEB 예제

GWEB은 Go를 위한 문학적 프로그래밍 시스템이다. 크누스와 레비의 CWEB을 가까이 본떴다. 확장자 .w 파일 하나에 TeX 산문과 Go 코드를 엮어 두면, 도구 둘이 그것을 서로 반대 방향으로 읽는다. 도구 gtangle은 기계가 읽을 .go를 뽑아내고, gweave는 사람이 읽을 상호 참조 문서를 조판한다. 프로그램과 그것을 설명하는 글은 따로 맞춰 두는 두 산출물이 아니다. 하나의 파일이다.

이 저장소는 그렇게 쓴 프로그램을 모은 것이다. 범위는 일부러 넓게 잡았다. 크누스의 CWEB 프로그램을 옮긴 것이 가장 많고, 알아 둘 만한 알고리즘의 해설(짚트리, FFT, 리차오 트리, CDQ 분할 정복)이 있고, 터미널 생명 게임이나 기타 튜너처럼 그 자체로 돌아가는 프로그램도 있다. 문서는 모두 한글로 썼다.

이것들은 GWEB을 실제로 쓰면 어떤 모습인지 보이려고 있고, 바라건대 그 자체로도 읽을 만하려고 있다. 파일 .w가 짜 내는 PDF부터 보기를 권한다. 그쪽이 사람의 눈을 위한 면이다.

빌드

Makefile은 예제를 이름(.w의 기본 이름)으로 빌드한다.

make ziptree   # ziptree.w -> ziptree.go (+ @( ) 로 뽑는 파일들) + ziptree.pdf
make           # 사용법 보기
make clean     # .w/.ch 원본만 남기고 생성물 삭제

예제는 한 번에 하나씩 빌드한다(make all은 없다). 짜 낸 .go는 거의 모두 저마다 main()을 가진 package main이라, 한 디렉터리에 한꺼번에 풀면 Go가 main 중복으로 컴파일을 거부한다.

조판은 그림이 있든 없든 모두 luatex으로 한다. 한글 문서(\input kotexgweb.tex, 아래 참조)와 그림 있는 문서(\input luamplib.sty)가 luatex을 요구하고, 여기 있는 문서는 모두 그 둘 가운데 하나다.

그림에는 따로 빌드 단계가 필요 없다. luamplib이 문서를 조판하는 동안 MetaPost를 그 자리에서 돌린다. 따로 도는 mpost 단계도, 중간 PDF도 없고, 그림의 라벨은 문서 자신의 글꼴로 짜인다. MetaPost는 몇 장이든 .w 안에 그대로 담는다. 남은 .mp는 넷뿐이고 저마다 까닭이 있다. tarjan-strong.mp와 wordcube.mp는 문서 둘이 나눠 쓰는 도우미이고, hyperbolic-arcs.mp는 hyperbolic.w의 프로그램이 뱉는 좌표이며, skew-ternary/skew-ternary-calc.mp는 크누스가 발표한 파일을 고친 것이라 원본과 한 줄씩 견줄 수 있게 그대로 두었다. 모두 \everymplib{input <이름>;}으로 읽어들인다.

추적하는 것은 원본과 자료뿐이다. 원본은 .w/.ch 프로그램과 남은 MetaPost 파일(*.mp)이고, 자료는 wordcube.w와 word-cube-dlx.w가 읽는 낱말 목록 sgb-words.txt, 그리고 enigmatic-puzzle.w가 5-그램 계수에 쓰는 크누스의 원문 VOL1TEXT.txt다. 여기 있는 .go와 PDF는 모두 생성물이니, 빌드하기 전에는 없다.

목록에 없는 types.w는 예제가 아니라 모든 문서가 @i로 읽어들이는 공용 포함 파일이다. @d와 @s 지시자만 들어 있어 혼자서는 tangle 할 것이 없다.

아래 목록에서 .w가 아니라 디렉터리를 가리키는 항목은 저마다 README.md, Makefile, go.mod를 갖춘 별개의 프로젝트다. 이 저장소의 Makefile은 그 안으로 들어가지 않으니, 그것들은 안에서 빌드한다(cd life-game && make).

• 15puzzle-korf1.w — 15 퍼즐의 최소 수 풀이를 코르프의 반복 깊이 증가로 찾는다. 맨해튼 하한을 써서 먼저 "행복한" 수만으로 해 보고, 안 되면 "슬픈" 수를 하나씩 늘려 간다. 안쪽 반복문은 손으로 펼친 경우 152가지 (r,c,d,p)의 유한 상태 오토마톤이다. 빈칸이 (r,c)에 있고, 방향 p에서 들어왔으며, 이제 d로 가 본다는 뜻이고, 경우들은 goto로 이어지며 되짚어 갈 곳은 부호를 쌓는 스택이 기억한다. Go는 case 블록 안으로 뛰어들 수 없으므로, 이름표 152개를 한 블록에 나란히 두고 switch는 분기만 한다. 부호는 16진수 0xrcdp라서 분기표와 이름표를 눈으로 바로 맞대어 볼 수 있다. 전이 152가지를 모두 기계로 크누스의 원문과 맞춰 보았고, 틀린 것은 하나도 없었다. 결함은 하나, 처음 배치가 이미 목표일 때 1970년부터의 초를 찍는 것이다. 배치 1800개에서 C판과 출력이 바이트까지 같고, 풀이는 한 걸음씩 검사했다. 처음 옮긴 Go판은 C보다 25% 느렸다. 경우 152가지를 모두 품은 main을 Go의 인라이너가 '큰' 함수로 보아 비용 20 이하의 함수만 끼워 넣는데, 값 둘을 돌려주는 east(r,c)는 비용이 26이라 경우마다 진짜 호출이 일어나고 s와 t가 메모리로 밀려났다. 조각은 그 자리에서 읽고 값 하나짜리 happy(x)(비용 8)만 남기자 해결되었다. 코르프의 가장 어려운 예 ca6098dfb73254e1이 C의 24초에 맞서 Go에서 22초다.
• back-20q.w — 돈 우즈의 스무 문제를 푼다. 스무 개의 객관식 문항이 모두 자기가 인쇄된 답안지를 두고 하는 말이다("답이 A인 첫 문항은…", "이 시험에서 얻을 수 있는 최고 점수는…"). 다섯 비트 후보 집합 위의 백트래킹인데, 문항마다 그 자리에서 판정할 수 있는 부분과 스무 글자가 다 정해져야 알 수 있는 부분으로 갈라 두고, 강제된 글자 하나가 이웃한 문항들로 줄줄이 번져 간다. 문서는 스무 문항을 모두 인용하고(더 읽기 전에 직접 풀어 보시라) 절 하나에 문항 하나씩 코드로 옮긴다. 그 과정에서 발표된 CWEB의 잘못 둘을 찾아 고쳤다. 닿을 수 없는 줄 때문에 18번을 틀릴 수가 없었던 것과, 뒤집힌 검사 때문에 15번이 사실은 맞는데도 틀린 것으로 매겨질 수 있었던 것이다. 그 탓에 원본은 옳은 답안지 14장을 잃고 그른 답안지 5장을 얻었다. 퍼즐 자체의 답은 그대로다. 최고 점수는 19점이고, 20번을 맞히면서 그 점수에 닿는 답안지는 정확히 하나다. 고친 원본과 거짓 패턴 211가지 모두에서 맞춰 보았고, 영문 문제에서 새로 쓴 독립 채점기와도, 탐색 순서를 열두 가지로 바꾼 것과도 맞춰 보았다. 크누스의 변경 파일 둘도 GWEB 변경 파일로 함께 옮겼다(back-20q-backmod9,15.ch, back-20q-backmod9,15-indet.ch). 저마다 문항 두엇을 고쳐 쓰고 제 답을 보고하는데, 그 가운데 첫째는 15번 결함이 어디서 왔는지 짐작하게 한다. 그 문구대로라면 다섯 선택지가 가지런히 늘어서서 문제의 경우가 사라지기 때문이다. 적용은 CWEB에서 하던 대로 gtangle back-20q.w back-20q-backmod9,15.ch. MetaPost 그림 셋.
• back-dissect.w — 정사각형을 칸 단위로 d개의 조각으로 잘라, 돌리고 밀어서 주어진 다른 모양을 채우는 방법을 모두 찾는다. 조각마다 옮김과 회전을 하나씩 정해 두면 남는 것은 이분 매칭이다. 옮김들이 모양을 덮는지부터 걸러 내고, 강제된 짝을 먼저 짓고, 그래도 남는 문제는 크누스가 DANCE에서 뜯어 온 춤추는 링크로 푼다. 4×9 직사각형의 계단 자르기가 두 조각으로 나오고, 4×4와 3×3을 나란히 놓은 모양을 5×5로 만들려면 조각이 이어져 있기를 바랄 때 네 조각이 든다는 것도 셈해 본다. 옮기다가 결함 둘을 만났다. 칸 하나짜리 모양에서 배열 밖 s[-1]을 읽고 죽는 것과, fgets의 37바이트 버퍼가 긴 줄을 쪼개 모양을 소리 없이 바꾸는 것이다. 원본과 무작위 모양 697개, 가장자리 32가지에서 출력과 종료 부호가 바이트까지 같고, 결함이 걸리는 9가지는 두 결함만 고친 원본과 같다. MetaPost 그림 둘.
• back-graceful.w — 스탠퍼드 그래프베이스 파일에서 읽은 그래프(go-sgb의 gbsave를 쓴다)의 우아한 이름표를 모두 찾는다. 꼭짓점 이름표는 0..m에서 서로 다르고, 변의 차이가 정확히 1..m이어야 하며, VERTEX=label로 이름표 몇 개를 미리 정해 둘 수도 있다. 워커의 백트래킹(알고리즘 7.2.2W)은 층마다 아직 없는 가장 큰 변 이름표를 겨냥하고, 쓴 이름표와 안 쓴 이름표를 64비트 맵에 담고, 고를 것이 하나로 줄어든 꼭짓점은 강제하고, 미리 정한 이름표가 없으면 "정규" 이름표만 세어 여집합으로 일을 절반으로 줄인다. 옮기다가 흠 셋을 만나 모두 고치고 적어 두었다. 변수 bad가 int라서 32 이상인 변 이름표의 중복을 놓친다. 답에는 해가 없지만(찍힌 이름표가 모두 옳다는 것은 popcount 논증으로 보인다) 빽빽한 그래프에서 마디를 최대 8.9배까지 더 훑는다. 2층에서 강제된 수가 정규 조건을 건너뛰어 P₃의 정규 이름표를 2개가 아니라 4개로 센다. 그리고 두 꼭짓점에 같은 이름표를 미리 정해 두어도 막지 않아 엉뚱한 답이 나온다. 고친 C판과 382번의 실행에서 마디 수까지 바이트 하나 다르지 않고, 답은 무차별 계수기로 확인했다.
• back-pdi.w — 차수 m의 완전 자릿수 불변수를 모두 찾는다. 곧 제 자릿수의 m제곱 합과 같은 정수인데, 153 = 1³ + 5³ + 3³ 같은 것이다. 자릿수를 내림차순으로 고르는 백트래킹이고, 날카로운 상하한으로 가지를 세게 쳐 낸다. 큰 수는 덧셈만 있으면 되는 2진화 10진법으로 다룬다(+6 / −6 올림 요령을 그림으로 풀어 두었다). 크누스의 CWEB 프로그램을 Go/GWEB으로 옮긴 것이고, 마디 수가 원본과 정확히 같다. MetaPost 그림 하나.
• back-pi-day.w — 요한 더라위터르가 2018년 파이 데이에 낸 퍼즐을 다룬다. 10×10 격자의 칸마다 동서남북 가운데 한 방향을 가리키고, 각 칸에는 그 칸이 가리키는 칸들의 이름표 가운데 서로 다른 것의 개수가 들어가야 한다. 주어진 이름표 32개는 π의 첫 32자리다. 후보 이름표는 비트맵에 담고, 꼭짓점을 "안정"하게 만드는 일은 뒤따르는 칸들의 이름표 위에서 작은 백트래킹을 하되 ν(popcount)로 셈한 goal 마스크로 쳐 낸다. 사실상 일반화된 호 일관성이다. 활성 목록이 회마다 가장 불안정한 꼭짓점을 고르고, 여섯 회에 걸친 301번의 검사 끝에 모든 비트맵이 홑원소가 된다. 크누스의 낙관이 들어맞아 경우를 가를 일이 없다. 옮긴 판은 C와 출력이 바이트까지 같다. 디버깅 흔적 197,802줄과 mems 6,865,501까지 같고, 답이 하나뿐이라는 것은 따로 만든 풀이기로 확인했다. MetaPost 그림 하나가 주어진 이름표와 이끌어 낸 이름표를 함께 보인다.
• back-skeleton.w — 타케 준야가 고안한 곱셈 뼈대 퍼즐을 짓는다. 별표 무늬가 주어지면, 곱해지는 수와 곱하는 수와 특별한 숫자 d를 찾되, 곱하는 수의 0들이 줄을 밀어 놓는 모든 경우에 대해 d가 부분 곱과 곱에서 무늬가 말하는 자리에 정확히 나타나야 한다. 곱해지는 수의 자릿수를 오른쪽부터 고르는 백트래킹이고, 제약마다 둔 선택 목록이 곱하는 수의 자릿수를 그때그때 강제하며, 살아남은 m짝들 위의 안쪽 반복문이 맨 아랫줄을 검사한다. 옮기다가 결함을 하나 만났다. 식 o,tt=(constr[k][0]<=l? 0: o,constr[k][l+1])에서 쉼표가 ?:보다 느슨하게 묶여 길이 검사가 사라지고, 앞선 밀림이 남긴 낡은 자릿수가 "d이면 안 된다"를 "d여야 한다"로 뒤집는다. 그래서 원본은 들어가며에 나오는 타케 자신의 퍼즐(2208068 × 357029)을 놓치고, O 무늬에서 68151개인 답을 4707개만 찾는다. 옮긴 판은 고친 C와 마디와 mems까지 바이트 하나 다르지 않고, 가지치기 장치를 전혀 함께 쓰지 않는 독립 검사기도 같은 68151개를 찾는다.
• back-warnsdorf.w — 나이트 투어를 찾는 바른스도르프 규칙(늘 덮이지 않은 이웃이 가장 적은 이웃으로 간다)을 따라 걸을 수 있는 길을 동률의 갈림까지 모두 훑는다. 그래프는 go-sgb의 gbsave로 읽는다. 길마다 동률을 무작위로 깨는 걸음이 거기 닿을 확률을 셈하니, 이를테면 8×8 판에서는 어느 칸에서 떠나든 97–99퍼센트의 확률로 투어를 얻는다는 것을 알 수 있다. 바라는 끝 꼭짓점을 적어 닫힌 투어를 노릴 수도 있고, 같은 꼭짓점을 두 번 적으면 그것은 막다른 마지막 칸으로만 들어갈 수 있게 된다. 옮기다가 결함을 하나 만났다. 후보 스택이 1000칸으로 고정이라 꼭짓점이 1000개에 가까운 그래프에서 넘치는데(3×330 격자는 멀쩡히 끝나면서 1319칸을 쓴다), 옮긴 판은 스택을 호의 수만큼 잡는다. 원본과 450가지 경우에서 출력과 종료 부호가 바이트까지 같다.
• baxter-to-floorplan.w — 백스터 순열에서 플로어플랜을 만든다. 크누스의 2021년 삼부작의 셋째 편으로, 출력은 첫째 편 floorplan-to-twintree.w의 입력 형식이다. 방의 대각선 순서는 1…n, 반대각선 순서는 순열 그대로이고, Ackerman–Barequet–Pinter의 방법으로 오른쪽에서 왼쪽으로 본 최솟값과 최댓값의 스택 둘을 유지하며 선형 시간에 경계를 채운다. 3142에 "방 2.5"를 더한 바람개비 플로어플랜 그림 하나. 옮기며 원본의 결함 둘을 고쳤다. 원소가 1024개를 넘으면 배열 밖에 쓰는 것과, fscanf가 넘치는 수를 2³²로 나눈 나머지로 읽는 것이다. 크기 8까지의 순열 46234개에서 원본과 바이트까지 같고, 받아들인 플로어플랜은 모두 좌표를 주어 확인한 올바른 타일링이다. 세 편을 모두 GWEB 판으로 엮어 백스터 순열 13373개가 한 바퀴 돌아 제자리로 온다.
• canonize-bidigraph.w — 양방향 그래프(변의 양 끝에 방향 기호 <나 >가 붙는 그래프)의 꼭짓점 몇 개를 뒤집어, 인접 행렬의 대각선과 그 위를 네 비트 부호로 늘어놓은 열이 사전식으로 가장 크게 되도록 하는 정규형을 구한다. 그래프는 go-sgb의 gbsave로 읽고 쓴다. 옮기다가 원본(2026년 1월)의 알고리즘에서 결함 둘을 찾았다. 두 가지가 동률인 무늬 넷에서 j와 k가 뒤바뀌어 있고, 자유롭지 않은 꼭짓점을 자유롭다며 앞질러 정한다. 그래서 뒤집기로 오가는 두 그래프가 다른 "정규형"을 얻는다. 옮긴 판은 앞의 것을 바로잡고, 뒤의 것은 따름 관계를 짝을 기억하는 합집합-찾기로 행을 넘겨 들고 가서 고친다. 결함이 걸리지 않는 1045가지에서는 원본과 표준 오류까지 바이트가 같고, 걸리는 것에서는 출력이 전수 탐색의 사전식 최댓값과 같다. 유향 그래프의 정규형이 유향이라는 크누스의 주장은 네 꼭짓점 반례로 틀렸음을 보인다. 이름이 150자를 넘으면 sprintf가 넘치는 결함도 적었다. 그 김에 go-sgb의 SaveGraph가 154자를 넘는 이름을 자르지 않아 C SGB가 읽지 못하는 파일을 쓰던 것도 go-sgb 쪽에서 고쳤다. MetaPost 그림 하나.
• celtic-paths.w — 켈트 매듭을 찍는다. 정사각형 타일마다 모퉁이와 변의 가운데, 여덟 점을 잇는 선분을 하나나 둘 두어 고리를 짜면, 프로그램이 크누스의 전용 글꼴 CELTICA/CELTICB로 조판할 TeX 파일을 내놓는다. 흑백은 한 번 훑어 칠하고, 그림 바깥은 스택을 배열 안에 엮은 깊이 우선 탐색으로 찾는다. 엇갈리지 않는 두 선분의 가운데 영역은 둘레에서 두 토막으로 갈리므로 "마법의 표"로 건너뛴다. 크누스의 2010년 CWEB 프로그램을 옮기며 codetable[0x1425]를 두 번 대입한 오타를 고쳤다. 원본은 그 때문에 규칙에 맞는 타일 1427을 거절한다. 꼭 100행·100열인 그림에서 배열 밖을 찍던 곳도 고쳤다. 글꼴 자체에도 결함이 둘 있다(0514와 0527이 이웃 글자와 똑같이 그려져 끈이 끊긴다). 프로그램으로는 고칠 수 없으니 문서에 .mf의 고칠 줄을 적었다. 이 문서를 조판하려면 크누스 누리집의 celtica.mf, celticb.mf, celtica13.mf, celticb13.mf를 TeX이 찾는 곳에 두어야 한다. 원본의 결함만 고친 C 판과 그림 4580개에서 바이트까지 같고, 안팎 칠하기는 합집합-찾기로 따로 구한 것과 302개에서 같다. MetaPost 그림 하나.
• commafree-eastman.w — 이스트먼의 1965년 알고리즘을 반복문으로 쓴 것이다. 길이가 홀수이고 제 순환 이동 가운데 어느 것과도 같지 않은 수열이 주어지면, 고른 이동들이 쉼표 없는 부호를 이루도록 이동 하나를 고른다. 골롬과 고든과 웰치의 추측을 매듭지은 구성이다. 낱말은 경계 표시로 부분 낱말로 잘리고, 단계마다 이웃한 분지(네바다에서 온 용어는 크누스의 것이다) 사이의 길이가 홀수인 구간마다 표시를 딱 하나만 남긴다. 그래서 ⌊log₃ n⌋ 단계면 넉넉하다. CWEB 원본과 26830번의 실행에서 맞춰 보았다. 두세 글자 알파벳 위의 길이 3, 5, 7, 9인 수열 모두와 길이 105까지의 무작위 수열 4000개인데, 일부러 다르게 한 것이 하나 있다. 함수 strconv.Atoi는 sscanf("%d")가 조용히 받아들이던 뒤쪽 쓰레기를 거절한다. MetaPost 그림 하나.
• dlx-pre.w — 정확한 덮개 연작의 전처리기다. 입력 .dlx 문제를 읽어 쓸데없는 선택지와 항목을 덜어 낸 같은 값의 문제를 써 낸다. 규칙 둘이 일을 한다. 주 항목 p를 담은 선택지가 모두 색 없는 c도 담고 있으면 c와, p 없이 c를 담은 선택지를 모두 버릴 수 있다. 그리고 p를 담은 선택지가 모두 선택지 r과 부딪히면 r을 버릴 수 있다. 이것을 춤추는 링크 구조에서 항목을 하나씩 숨기며 적용하는데, 보조 표는 없어도 된다. 이중 연결 목록에서 빠져나온 마디는 제 이웃을 여전히 기억하기 때문이다. 옮길 때 매듭은 크누스가 자랑스러워한 goto다. 막힌 항목을 만나면 숨기는 반복문에서 빠져나와 되돌리는 반복문의 한가운데로 뛰어드는데, 그가 "goto 문을 쓰는 구조적 프로그래밍"(1974)에서 옹호한 바로 그 기법이다. Go는 블록 안으로 뛰어들 수 없으므로 blocked 플래그와 이름표 붙은 break로 흐름을 그대로 되살렸다. CWEB 원본과 맞춰 보았고(표준 출력이 바이트까지 같고 mems와 자세한 기록도 같다), 생성한 문제 612개에 대한 2496번의 실행과 dancing-cells의 펜토미노·필로미노 판, 그리고 패닉으로 끝나는 모든 길을 해 보았다. 문서는 원본 §3의 미끄러짐 둘도 적어 둔다. 보기 출력이 E 자리에 C를 보이고, 프로그램이 찍지 않는 |가 들어 있다.
• dragon-calc.w — 데킹의 일반화된 용 곡선과, 그의 다이아몬드와 용 노트에 나오는 타일 계산을 위한 대화형 계산기다. 글자 D와 U로 된 접기 수열, 곡선을 두 배(또는 다섯 배)로 만드는 접기 곱, 좌표의 합이 홀수인 가우스 정수로서의 타일, 허수부에 유클리드를 돌려 얻은 에르미트 표준형 기저로 나눈 (2+2i)z에 대한 합동류, 평면을 채우는 경로 위에서의 타일 인수분해, 그리고 MetaPost 출력. 크누스의 2010년 CWEB 프로그램을 Go/GWEB으로 옮긴 것으로, 답이 원본과 줄 단위로 같다. 원본에서 goto의 거미줄은 이름표 붙은 반복문이 되었고, 134 MB짜리 정적 표는 필요한 만큼만 잡는 것이 되었고, 닫힌 경로에서 나던 0으로 나누기는 이제 걸러 낸다. MetaPost 그림 둘.
• dynabidiham.w — dynaham.w의 양방향 그래프판으로, 처음 m개 마디로 된 유도 부분그래프마다 해밀턴 회로의 수를 센다. Weigel이 쓰고 크누스가 다듬은 것으로, dynadiham.w의 바탕이다. 변의 가지는 호 길이 mod 4로 읽고 빠진 짝 호만 채운다. 한 부분경로의 두 끝이 같은 종류일 수 있어 트라이가 끝점마다 샘과 싱크 두 칸을 둔다. dynadiham.w와 같은 결함 둘(oldmem 넘침 검사, 마디 없는 그래프)을 고쳤고, 같은 가지의 변을 두 번 적으면 적은 쪽에 따라 셈이 달라지는 명세 밖의 틈을 적어 두었다. 고친 CWEB 원본과 그래프 82개에서 바이트까지 같다.
• dynadiham.w — dynaham.w의 유향판으로, 처음 m개 마디로 된 유도 부분그래프마다 유향 해밀턴 회로의 수를 센다. Weigel과 크누스의 DYNABIDIHAM에서 왔다. 호마다 반대 방향의 짝 호를 길이 표시(4l+1, 4l+3)로 넣어 양방향 그래프로 바꾸고, 바깥 마디를 샘과 싱크로 갈라 부호 2j+[샘]으로 적는다. 원본은 제 고리를 거절하고 호가 셋 붙는 경우도 걸러서, dynaham.w의 결함 넷 가운데 둘(oldmem 넘침 검사, 마디 없는 그래프)만 남아 고쳤다. 전수 셈과 그래프 37개에서 맞춰 보았고, 고친 CWEB 원본과 그래프 114개에서 바이트까지 같다.
• dynaham.w — 그래프의 처음 m개 마디로 된 유도 부분그래프마다 해밀턴 회로의 수를 m=1, 2, …, n에 걸쳐 한꺼번에 센다. ss*ham 연작과 달리 되추적으로 회로를 늘어놓지 않는다. 경계의 모양으로 묶은 부분 경로 짜임의 동치류마다 수만 들고 가는 동적 계획법이다. 동치류는 몇 비트로 압축하는 트라이에 담는다. 나이트 판을 열 순서로 매기면 3×40, 5×16, 6×12, 7×8 판의 닫힌 투어 수가 OEIS와 맞는다. 원본의 결함 넷을 고쳤다. 겹친 변과 제 고리가 있으면 틀린 수를 내거나 죽는 것, 압축 트라이 넘침을 바이트와 낱말을 헷갈려 놓치는 것, 마디 없는 그래프에서 죽는 것이다. 전수 셈과 그래프 107개에서 맞춰 보았고, 고친 CWEB 원본과는 그래프 194개에서 바이트까지 같다. MetaPost 그림 하나.
• dynahamp.w — dynaham.w의 경로판으로, 처음 m개 마디로 된 유도 부분그래프마다 해밀턴 경로의 수를 센다. 모든 마디에 이웃한 새 마디 !를 보탠 G⁺의 해밀턴 회로로 바꾸어 센다. 나이트 판을 열 순서로 매기면 열린 투어 수가 나온다(6×6 판에서 3318960, 방향까지 센 6637920의 절반). dynaham.w에서 고친 원본의 결함 넷이 그대로 있어 똑같이 고쳤다. 전수 셈과 그래프 105개에서 맞춰 보았고, 고친 CWEB 원본과 그래프 193개에서 바이트까지 같다. MetaPost 그림 하나.
• enigmatic-puzzle.w — TAOCP 7.2.2.8에 나오는 125글자짜리 에니그마 암호문을 깬다. 암호문과 크립 낱말 하나(ENIGMATICALLY)만 가지고 회전자의 선택과 순서, 링 설정, 시작 위치, 플러그판, 그리고 평문을 되찾는다. 크누스의 프로그램 다섯 개를 여기서 하나의 파이프라인으로 엮었으므로 문서는 그것들을 모두 훑는다. 기계 자체(다섯 가운데 회전자 셋, 반사기 B, 이중 전진의 버릇, 그리고 어떤 글자도 자기 자신으로 암호화되지 않는 치명적 흠 — 이 한 줄이 크립 위치 113개 가운데 50개를 죽인다), 회전자가 얼마나 돌았는지만 좇아 모르는 링 설정을 비껴가고 k층에 마디가 정확히 2k+1개인 델타 나무, 순서 없는 글자 쌍 351개 위의 유니온 파인드인 봄베(쌍을 순서 없이 다루는 것이 곧 웰치먼의 대각 판이다), 강제된 류를 모두 하나의 거대한 류로 합치는 개선된 거르개, 살아남은 류와 어긋나지 않는 플러그판을 모두 늘어놓는 간추린 감시 리터럴 SAT 풀이기, 델타 경로를 다시 시작 위치와 링 설정으로 바꾸는 산술, 그리고 마지막으로 후보 3,331,188개 가운데 진짜 영어인 하나를 고르는 5-그램 통계다. 영어가 맞고, 1653년의 연금술 책에서 왔다. 크누스의 C 원본과 백만 가지 설정을 모두 훑어 줄 단위로 맞춰 보았다. 원본에 숨어 있던 버퍼 문제 셋을 고치고 설명해 두었다. 배열 move[64]는 변수 개수만큼 첨자가 붙는데, 그것이 64를 넘을 수 있다고 크누스 자신이 적어 두었고, 전체 실행이 정말 그렇다는 것을 보인다(max vars 79). 배열 plugs[…][26]은 플러그가 하나도 없는 플러그판에서 보초를 둘 자리가 없다. 그리고 리터럴이 없는 "적어도 하나" 절이 쓰지 않은 칸을 읽는다. 역사도 함께 엮었다. 셰르비우스, 레예프스키와 폴란드의 봄바, 피리, 튜링, 웰치먼이다. 전체 훑기는 고루틴으로 나누었다. 프로파일을 떠 보니 시간의 72%가 봄베의 유니온 단계에 있었는데, 경로 압축도 더 좁은 배열도 필드 구조체 배치도 모두 오히려 느렸다. 그러나 설정들은 서로 아무것도 나누어 쓰지 않으므로, 일꾼 열이 M1 Max에서 2시간 4분 26초 걸리던 것을 16분 10초로 줄였다. 출력은 바이트까지 그대로이고, 여전히 흘러나온다. 무엇을 찍을지가 그 앞의 모든 것에 달려 있어서 한 단위의 줄은 앞선 단위가 모두 끝나야 정해지므로, 일꾼마다 찍힐 수 있는 것을 넉넉히 모아 두었다가 끝난 앞부분을 차례로 내보낸다. 훑기를 60단위가 아니라 1560단위로 잘랐더니 첫 줄이 6.4초 만에 나오고, 단위마다 회전자 표를 다시 짓는데도 전체가 오히려 더 빠르다(꼬리가 짧다). 표준 오류로 나가는 진행 표시 13줄까지 그대로다. MetaPost 그림 둘. 5-그램 계수에는 크누스의 원문이 필요한데, 저장소에 VOL1TEXT.txt로 들어 있다(프로그램의 기본 파일 이름은 VOL1TEXT이므로 셋째 인자로 넘기면 된다).
• floorplan-to-twintree.w — 플로어플랜(직사각형을 방들로 나눈 것)에서 쌍둥이 나무를 계산한다. 플로어플랜, 쌍둥이 나무, 백스터 순열 사이의 전단사를 다루는 크누스의 2021년 삼부작의 첫 편이다. 방마다 위·아래·왼쪽·오른쪽 경계의 이름을 받아, 오른쪽 아래 모퉁이에서부터 ⊣와 ⊥ 교차점을 따라 경계를 하나씩 처리하며 모든 T자 교차점을 찾고, Yao–Chen–Cheng–Graham의 방법으로 방의 두 모퉁이에서 두 나무의 링크를 읽는다. 변경 파일 floorplan-to-twintree-ttform.ch는 출력을 둘째 편 TWINTREE-TO-BAXTER가 읽는 형식으로 바꾼다. 옮기며 원본의 결함 다섯을 고쳤다. 가장 큰 것은 잘못된 명세를 다 알아채지 못해, 쌍둥이 나무가 아닌 것이나 다른 플로어플랜의 쌍둥이 나무를 조용히 내놓거나 고리 때문에 스택이 넘쳐 죽는 것이다. 이 판은 같은 경계가 두 번 출발하면 멈추고, 찍기 전에 결과가 쌍둥이 나무인지와 링크마다 입력의 경계와 맞는지를 확인한다. 이 확인이 충분하다는 증명도 실었다. 그 밖에 오류 메시지가 엉뚱한 이름을 찍는 것 둘과 방 수의 한도를 살피지 않는 것을 고쳤다. 크기 8까지의 백스터 순열 13373개가 삼부작을 한 바퀴 돌아 제자리로 오고, 원본과 바이트까지 같으며, 잘못된 입력 60000개에서 플로어플랜만 받아들인다. MetaPost 그림 둘.
• floyd.w — 플로이드의 분할 문제. 크누스가 *장난감 문제는 쓸모 있는가?*에서 다룬 고전적인 "장난감 문제"다. √1…√50을 거의 같은 두 몫으로 가른다. 문학적으로 푼 풀이(중간에서 만나기 탐색, 그레이 부호 열거, 보정 덧셈, 그리고 math/big 검증)다.
• grayspan.w — 그래프의 신장 나무를 모두 만들되, 이웃한 두 나무가 변 하나만 다르게 늘어놓는다. 맬컴 스미스의 석사 논문(1997)을 바탕으로 크누스가 "조금 서둘러" 짠 것이다. 거의 나무의 첫 변을 줄여 되부르고, 끝나면 그 변을 지워(다리가 아닐 때만) 다시 되부른다. 줄이기와 펴기는 이중 연결 리스트 위의 춤추는 고리로 하고, 다리는 차수 1과 나란한 변이라는 어림 둘에 이어 너비 우선 탐색으로 가린다. 한 반복문에서 다른 반복문 몸통으로 뛰어드는 goto는 첫 반복문을 이름표로 펴서 옮겼다. 덩치 큰 go-sgb 레코드 대신 작은 꼭짓점·호 구조체로 옮겨 담는다. 원본의 결함 하나, 꼭짓점이 없는 그래프에서 세그폴트로 죽는 것을 고쳤다. 그래프 396개에서 세 가지 자세함으로 원본과 출력·mems가 바이트까지 같고, 행렬 나무 정리와 그레이 성질로 따로 검사했다. 전역이던 mems를 지역 변수로 옮기자 1.4배 느리던 것이 원본보다 1.4배 빨라졌다.
• ham-euler.w — 오일러가 1759년에 쓴 요령 넷(경로 늘이기, 뒤집기, 순환 돌리기, 끝에서 앞쪽으로 변을 걸어 꼬리 뒤집기)으로 해밀턴 순환을 찾는다. 정규형으로 만든 경로를 "초꼭짓점"으로 삼아 거대한 그래프에서 너비 우선 탐색을 하고, 경로가 길어지면 다 잊고 다시 시작한다. 초꼭짓점은 꼭짓점 번호를 10비트씩 담아 1기가바이트 순환 대기열에 두고, 변마다 붙인 난수의 합을 해시 부호로 쓴다. 블록 안의 이름표로 뛰는 goto memoverflow는 함수로, 삼항 연산자는 나머지 셈으로 옮겼다. 원본의 결함 다섯을 고쳤다. 처음 경로에 같은 꼭짓점이 두 번 나오면 "꼭짓점 일곱 개짜리 경로"를 꼭짓점 여섯인 그래프에서 찾는 것, 다중 그래프에서 꼭짓점 배열 밖을 쓰는 것(AddressSanitizer로 확인), 고리가 있으면 끝없이 도는 것, 빈 그래프에서 끝없이 도는 것, 첫 꼭짓점이 고립되면 초기화하지 않은 포인터를 쓰는 것이다. 원본과 2028가지, 고친 C판과 2080가지가 바이트까지 같고, 32×32 격자에서는 메모리가 넘칠 때까지 찍은 5.1GB가 같다. 8×8 나이트 그래프에서는 눈 깜짝할 새에 닫힌 투어를 찾는다.
• hopcroft-karp.w — 이분 그래프의 최대 매칭을 O((t+n)·sqrt(m))에 찾는다. 회마다 경로를 하나씩 늘리는 대신, 꼭짓점이 겹치지 않는 최단 증가 경로의 극대 집합을 한꺼번에 찾는다. 문서의 절반은 증명이다. 두 매칭의 대칭차가 순환과 경로로 갈라진다는 데서 베르주의 보조정리가 나오고, 증가는 성분 하나를 없애면서 더 짧은 것을 만들지 않으므로 경로 길이가 엄격히 늘고, r회가 지나면 매칭이 이미 최적의 r/(r+1)이므로 회수는 2·sqrt(s)로 묶인다. 크누스의 goto enter_level과 goto advance는 continue가 곧 전진인 반복문 하나가 되었다. 원본에 둘을 덧붙였다. 크누스는 길이 2k-1인 경로의 등급을 k로 정의해 놓고는 그보다 하나 작은 final_level을 찍고 (나중에 그것을 두고 논하는데), 옮긴 판은 정의를 하나 골라 그렇다고 밝힌다. 그리고 마지막으로 실패한 너비 우선 탐색이 교대로 닿을 수 있는 집합을 이미 셈해 두었으므로, 프로그램은 매칭과 크기가 같은 최소 꼭짓점 덮개를 함께 내놓을 수 있다. 답이 최적임을 눈으로 확인할 수 있는 쾨니그 증서다. C 원본과 무작위 1200개에서 맞춰 보았다. 매칭과 회수와 dag의 호가 모두 같고, 따로 구현한 것과도 교차 확인했으며, 덮개는 모두 옳고 크기도 정확하다. 마지막 장은 크누스가 끝에 남긴 연습 문제, 곧 1회는 따로 빠르게 구현할 만하다는 이야기를 다룬다. 정말 그렇고, 까닭은 1회에서 final_level이 반드시 0이라 깊이 우선 탐색이 내려가지 않고, 그래서 그 회 전체가 호 t개짜리 dag를 썼다가 곧바로 되읽는 먼 길을 돌아 욕심쟁이 극대 매칭을 짓는 것이기 때문이다. 이것을 욕심쟁이 여덟 줄로 바꾸면 1회가 4배쯤 빨라지고(실행 시간의 69%를 차지하던 것이 41%로) 매칭 전체가 1.6~2.3배 빨라진다. 대신 시작 매칭이 달라져 다섯에 하나쯤은 회수가 이리저리 바뀐다. 플래그 뒤에 두었으니 기본값은 크누스의 출력을 그대로 되살린다. MetaPost 그림 셋.
• hyperbolic.w — 36°-45°-90° 삼각형으로 쌍곡 평면을 덮는 유일한 타일링을 셈한다. 점은 상반 평면에 있고, "직선"은 실축에 중심을 둔 반원이며, 타일링 전체는 삼각형 하나에서 꼭짓점을 맞은편 변에 거듭 비추어(원에 대한 반전) 자라난다. 일을 사분 고리 하나로 줄이면 평면 전체에 삼각형 301개면 넉넉한데, 그 제한을 공짜로 만드는 요령은 중심이 0인 수직 "원"을 두고 알고리즘이 그것을 넘지 않도록 하는 것이다. 이 삼각형 열 개가 정오각형을 이루니 마르겐슈테른의 오각 격자가 모습을 바꾼 것이고, 시작 좌표에 황금비가 마땅히 나타난다. 크누스가 이웃 셈을 세 번 따로 쓰고 호 667개를 손으로 .mp 파일에 옮겨 적은 자리에서, 옮긴 Go판은 셋을 첨자 붙은 반복문 하나로 접고 MetaPost를 스스로 뽑아낸다. 호 667개가 모두 그의 것과 찍힌 마지막 자리까지 같다. 바탕 좌표는 컴파일러가 곱셈과 덧셈을 다르게 융합하는 탓에 3.3e-13까지 다른데도 그렇다. 그런데도 똑같은 타일링이 나오는 것이야말로 어름한 이진 탐색 사전을 둔 까닭이다. MetaPost 그림 넷.
• infty-queens.w — 끝없는 체스판의 가로줄마다 앞의 여왕들에게 잡히지 않는 가장 왼쪽 칸에 여왕을 놓아 가는 탐욕 수열(OEIS A065188)을 계산한다. Sloane과 Shallit이 밝힌 황금비 구조 덕에 비트 벡터 셋에서 몇 칸만 보면 되고, nφ의 분수 부분을 음 피보나치 표현의 비트 무늬로 들고 다니며 어긋남을 정확히 잰다. 크누스의 2017년 CWEB 프로그램을 옮겼다. 원본 첫 문단의 정의는 수열을 q₀부터 세어 프로그램과 첨자가 하나 어긋나고, 9φ의 예시 식은 첨자와 부호가 틀려 적힌 대로 셈하면 5.51이 나오는데, 둘 다 고쳤다. 음수 n은 거절하고, 13억쯤을 넘으면 int가 넘치던 배열 크기는 64비트로 셈한다. 원본과 인자 317가지 가운데 일부러 고친 음수 둘만 빼고 바이트까지 같다. MetaPost 그림 하나.
• koda-ruskey.w — 숲 포셋의 이상을 모두 만들어 낸다. 곧 부모가 1일 때만 자식이 1일 수 있는 비트열 모두를, 한 걸음에 비트 하나만 바뀌는 일반화된 반사 그레이 부호로 늘어놓는다. 같은 수열을 두 가지로 구현해 나란히 둔다. 하나는 마디마다 코루틴 하나를 두는 것이고, 다른 하나는 한 걸음이 언제나 네 고리짜리 변두리에 대한 정해진 수의 연산인 무반복 구현이다. CWEB 원본이 열 가지 상태의 switch로 코루틴을 손수 흉내 내는 자리에서, 옮긴 판은 그것을 버퍼 없는 채널에서 만나는 고루틴으로 적는다. 그래서 여섯 줄짜리 코루틴 몸통이 그대로 살아남는다. MetaPost 그림 셋.
• li-ruskey.w — 앞의 koda-ruskey의 속편이다. 이제 제약에 방향이 있으므로 입력은 숲 포셋이 아니라 완전 비순환인 방향 그래프 아무것이나 되고, 할 일은 x → y ⟹ 비트 x ≤ 비트 y를 지키는 0/1 라벨링을 모두, 뿌리 비트가 딱 한 번 뒤집히는 그레이 경로로 늘어놓는 것이다. 준양·준음 꼭짓점 집합, 반쪽 경로 둘을 하나로 잇는 혼합 기수 반사 부호, 딸림들과 전이 문자열, 그리고 돌아다니는 플래그 뒤에 낡은 고리를 남겨 두는 것으로 무반복을 지키는 변두리가 나온다. 크누스는 코루틴 판을 연습 문제로 남기며 부모 포인터가 동적이어야 할 것이라고 했는데, 옮긴 판은 그 연습 문제를 고루틴으로 푼다. 거기서는 어려움이 증발한다(호출 스택이 곧 부모 포인터다). 코루틴마다 처음 깨어날 때 제 비트를 읽어 들어갈 자리를 고른다. 두 구현이 한 프로그램 안에서 돌고, -v 출력까지 CWEB 원본과 줄 단위로 같다. MetaPost 그림 넷.
• lp.w — 크누스가 심플렉스 알고리즘을 몸으로 익히려고 짠 선형 계획 프로그램(2005)이다. 여유 변수를 넣은 표에서 0행이 모두 음 아닌 수가 될 때까지 피벗하고, 피벗 행은 사전순으로 가장 작은 r_i/a_ij로 골라 되풀이를 피한다. 정수 표(열마다 배율을 두어 분수를 피함)와 부동소수점 표를 나란히 돌려 서로 확인하고, 쌍대 문제의 해도 함께 읽는다. 원본의 결함을 고쳤다. 음수 상수항 검사가 엉뚱한 칸을 읽어 해 없는 문제에 엉터리 답을 내는 것, 숫자가 아닌 글자에서 끝없이 돌며 배열 밖에 쓰는 것, 줄바꿈 없는 마지막 줄을 거절하는 것, long을 %d로 찍어 2³¹ 이상이 잘리는 것, 정수 방법의 64비트 넘침을 모르는 것이다. 설명에 있던 표와 식의 잘못 여럿도 바로잡았다. 무작위 문제 1000개에서 최적해 418개를 쌍대성 증명서로 확인했고, 넘치지 않은 839개는 원본과 바이트까지 같다.
• matula.w — 자유 나무 S가 자유 나무 T의 부분 나무와 동형인가? 부분 그래프 동형은 일반적으로 NP-완전이지만(클릭과 해밀턴 경로가 특수한 경우다), 나무에 대해서는 데이비드 마툴라의 1978년 알고리즘이 O(mn·sqrt(최대 내부 차수))에 매듭짓는다. 이것을 hopcroft-karp.w 바로 다음에 읽을 까닭은, 안쪽 반복문이 곧 이분 매칭이기 때문이다. S의 마디 p가 T의 v에 박히는 것은 정확히 p의 자식들을 v의 서로 다른 이웃에 짝지을 수 있을 때이고, 마툴라의 통찰은 그 부분 문제의 s+1가지 판(어느 이웃이 부모 노릇을 하는가에 따라)이 하나로 무너져 n배를 아낀다는 것이다. 크누스는 매칭 코드를 HOPCROFT-KARP에서 훔쳐 왔다고 적었는데, 우리는 그것을 막 옮긴 참이었다. 절정은 마툴라의 정리 3.4다. 완전 매칭에서 풀려날 수 있는 처녀들은 정확히 HK가 멈출 때 너비 우선 큐에 남아 있는 것들이므로, 답은 이미 dag 안에 놓여 있다. 크누스의 mems를 달아 두었고, 옮긴 판은 그 수를 정확히 되살린다. 그 자신의 예에서 1917+14760, 그리고 무작위 나무 쌍 1100개에서 답과 찍힌 박음과 mem 수가 모두 같다. 거기 닿기까지 조심할 것이 있었다. C의 쉼표 연산자는 앞에 붙인 mems++가 되거나 mems, k = mems+1, next[k] 같은 다중 대입이 되고, && 안에 놓인 o는 두 조건 가운데 하나에만 매겨진다. 그것을 놓쳐 유령 mems 119를 얻은 적이 있다. 옮겨 온 판에는 진짜 결함도 있었다. 배열 thresh는 maxn개로 선언되었는데 T의 최대 차수가 61일 때 첨자 maxn으로 읽히고, 그것을 채우는 반복문은 T의 최대 차수가 S의 마디 수에 이를 때마다 solve()가 필요로 하는 칸에 미치지 못한 채 멈춘다. 이것이 탈 없이 지나간 것은 이웃한 낱말이 마침 0을 담고 있기 때문이다. 거기에 값을 심어 두면 옛 코드는 61이 옳은 자리에서 62라고 답한다. 크누스는 이 글을 쓰는 동안인 2026-08-21에 파일을 고쳤고, 바로 그 두 곳을 손보았다. 배열은 여기서처럼 한 칸 늘었고, 빠진 자리는 같은 비용의 다른 방법으로 채워져, 이제 시험한 모든 입력에서 mem 수가 그의 것과 같다. 크누스는 제 프로그램 곁에 변경 파일 셋을 두는데, 셋 모두 여기에 옮겨 두었다. matula-big.ch는 명령줄의 부모 포인터 문자열을 rectree 파일로 바꾸어 maxn을 62에서 2000으로 키운다. 그 형식은 S의 뿌리가 잎이라고 약속하지 않으므로 S를 다시 뿌리내리고 안에서 번호를 새로 매긴 뒤, 사용자에게는 그의 번호로 돌려준다. matula-big-planted.ch는 T만 받아 거기서 무작위로 잎 d개를 지워 S를 기른다. SGB의 gb_flip을 go-sgb로 쓰므로 같은 씨앗이면 크누스의 C와 같은 잎을 지운다. 그러면 S는 반드시 부분 나무이고, 물음은 알고리즘이 그것을 얼마나 빨리 찾느냐가 된다. 적용은 CWEB에서 하던 대로 gtangle matula.w matula-big.ch. 둘 다 크누스의 C와 mem까지 같다. 그의 예에서 3221+14939와 5750+36561이고, 무작위 나무 쌍 660개와 무작위 나무 500개에서 답과 종료 코드와 mem 수가 모두 같다. 심은 판의 산문은 그것이 고스란히 물려받은 결함도 적어 둔다. 뿌리 자신이 지워지면 아직 고치지 않은 child 포인터가 이미 지워진 마디를 가리킬 수 있고, 그러면 두 프로그램 모두 "I'm confused!"로 멈춘다. 마디 127개 가운데 124개를 지울 때 씨앗 200개 가운데 134개가 그렇다. matula-exhaustive.ch는 명령줄의 나무 둘을 개수 둘로 바꾸어, 마디가 m개인 자유 나무와 n개인 자유 나무의 모든 쌍을 돌린다. 그래서 maxn이 62에서 16으로 내려간다. 자유 나무를 정확히 한 번씩 얻는 것이 재미있는 대목이다. 방향 있는 숲의 정규 층 수열로 만든 트라이(TAOCP 연습 문제 7.2.1.6–90)가 중심 나무를 주고, 절반 크기 숲의 쌍이 이중 중심 나무를 준다. 크누스는 그 장치를 S용과 T용으로 두 번 쓰는데, 여기서는 first/next/nth를 갖춘 family 타입 하나이고, 그 덕에 그의 make_?string 둘도 하나로 합쳐진다. 쌍마다 mems의 웰퍼드 평균과 분산, 가장 어려운 쌍, 그리고 가장 많이 또 가장 적게 박히는 나무를 보고한다. 나무 개수의 곱이 200000 이하인 (m, n) 쌍 79가지 모두에서 C와 맞춰 보았고, 출력과 종료 코드와 mems가 같다. 이를테면 m = n = 8에서 2407+426125다. MetaPost 그림 셋.
• maxcliques.w — 마디가 64개 이하인 그래프의 극대 클리크를 모두 찾는다. Moody와 Hollis의 알고리즘으로, 인접 행렬의 행 ρ_v와 자리 v만 끈 δ_v를 마디마다 골라 비트별로 교차한 것 가운데 극대인 것만 작업 공간에 들고 간다. 가장 낮은 켜진 비트는 드 브라윈 곱으로 찾는다. 크누스의 2008년 CWEB 프로그램을 옮기며 원본의 결함 넷을 고쳤다. 마디 없는 그래프에서 음수만큼 밀어 없는 마디 이름 64개를 읽는 것, 흡수하는 가지에서 작업 공간 사용량을 적게 재는 것, 작업 공간이 넘치면 두 무리가 서로 덮어써 틀린 답을 조용히 내는 것(마디 33개짜리 문–모저 그래프에서 177147개 대신 87499개), mems가 32비트에서 한 바퀴 도는 것이다. Bron–Kerbosch와 그래프 75개에서 맞춰 보았고, 고친 CWEB 원본과 그래프 85개에서 바이트까지 같다.
• nqueens-somers.w — N 여왕 문제의 해를 세는 제프 소머즈의 기법(2002)을 옮기면서 하나하나 풀어 설명한다. 판의 한 줄을 N비트 정수로 나타내고, 대각선의 위협을 줄마다 한 칸씩 밀어 비트 자리가 곧 막힌 칸이 되게 하고, 놓아 볼 칸을 -x & x로 뽑고, 거울 대칭으로 일을 절반으로 줄이되 홀수 판의 가운데 칸은 따로 다루고, 재귀 대신 명시적 스택을 쓴다. MetaPost 그림 셋. 원본 nq.c와 N=18까지 해의 수가 같고, -p로 찍는 판은 원본과 바이트까지 같다. 원본을 그대로 옮기면 Go에서 30% 느린데, 방금 배열에 적은 값을 도로 읽는 한 곳이 원인이라 고쳤다. 그러고 나면 명시적 스택과 재귀가 거의 비긴다. 짝이 되는 변경 파일 nqueens-somers-par.ch(gtangle nqueens-somers.w nqueens-somers-par.ch)는 첫 두 줄의 여왕 짝을 작업으로 삼아 고루틴들에 나눠 준다. 결정적인 반복문은 한 글자도 바꾸지 않고, 코어 10개에서 N=18이 186초에서 27초로 준다.
• ntt.w — 고속 푸리에 변환과 그 정수 사촌인 수론 변환으로 가는 친절한 길잡이. 값매김–곱셈–보간이라는 우회로, 제곱이 1의 거듭제곱근을 접어 문제를 절반으로 만드는 까닭, 비트 뒤집기와 나비 회로, 역변환, NTT가 환에 정말로 요구하는 것(그리고 998244353 = 119·2²³+1인 까닭), 그리고 가우스(1805)에서 하비와 판데르후번(2021)에 이르는 뜻밖의 역사를 다룬다. MetaPost 그림 셋. 이 글이 향해 가는 프로그램은 Library Checker의 Convolution (mod 998244353), 곧 O(n log n)의 다항식 곱셈을 푼다.
• othello.w — m×n 판에서 p명이 두는 일반화한 오델로(리버시)를 대화형으로 진행한다. 표준 입력으로 칸 이름(d3)을 받고, 뒤에 !를 붙이면 판을 찍는다. 처음 p²수가 뒤집기 없는 첫 배치이고, 판에 빈 테두리를 둘러 여덟 방향으로 훑을 때 경계 검사가 필요 없다. 크누스의 2024년 CWEB 프로그램을 옮기며 서술의 오타(표준 판이 "m=n=9")를 고쳤다. 원본은 void main이라 게임이 제대로 끝나도 종료 부호가 정해지지 않는다(clang -O2에서 10). 이 판은 0을 돌려준다. 판 크기와 경기자 수를 열두 가지로 바꾼 원본과 무작위 입력 7200개에서 표준 출력과 표준 오류가 바이트까지 같고, 표준 첫 배치에서의 perft 4, 12, 56, 244, 1396이 그대로 나온다. MetaPost 그림 하나.
• pairsums.w — 모든 부분 배열에 대한 쌍 곱의 합 가운데 가장 큰 것을 찾는다. 항등식 value = (S²−Q)/2와 누적합 비틀기가 이것을 직선 가족의 위 포락선 문제로 바꾸고, 리차오 트리로 O(n log n)에 푼다.
• perec.w — 조르주 페렉의 인생 사용법을 그 두 제약에서 다시 짓는다. 소설의 99개 장은 방 10×10 격자의 나이트 투어를 따라가는데, (1,10)의 지하실만 빠진다. 페렉이 일부러 낸 흠인 클리나멘이고, 그 때문에 65장과 66장 사이에 규칙에 어긋나는 대각 걸음이 하나 생긴다. 프로그램은 SGB의 Board로 나이트 판을 짓고, 옮겨 적은 것을 믿는 대신 판 자신의 호에 견주어 페렉의 순서를 확인한다. 견주어 볼 흠 없는 투어를 얻으려고 바른스도르프 규칙도 돌리고, 장마다 무엇이 담기는지 정하는 10차 그레코라틴 방진도 되짚어 짓는다(그 100쌍 가운데 99쌍이 쓰이고, 빠진 하나가 클리나멘의 몫이다). go-sgb를 쓴다. 그 자리에서 luamplib이 그리는 MetaPost 그림 셋.
• perfect-partition-square.w — 마이클 켈러의 퍼즐을 다룬다. 7을 일곱 개, …, 1을 일곱 개를 7×7 정사각형에 놓아, 그 14개 행과 열이 7을 둘 이상으로 나눈 분할 14가지를 모두 보이게 하라. 크누스는 답이 있을지 의심하면서 무차별 탐색을 "할 수 있는 한 빠르게" 써서 30885개를 보고했다. 옮기다가 답을 바꾸는 결함을 만났다. 안쪽 반복문의 한계 1<<(7*l-m)이 32비트 int를 42까지 미는데, 이것은 C에서 정의되지 않은 동작이고 실제 기계에서는 42 mod 32 = 10만큼 민다. 그래서 남은 자릿수의 놓임새가 거의 다 시도 조차 되지 않는다. Go의 int는 64비트이므로 같은 줄이 공간을 다 훑고, 그 결과 이 정사각형에는 답이 16,492,083개 있다. 크누스가 센 것은 그 0.19%다. 그 탐색은 코어 기준 57시간이라, 옮긴 판은 부분 문제 1716개를 고루틴에 나눠 주고 저마다의 답을 모아 두어 찍히는 차례를 크누스의 것과 똑같이 지킨다(벽시계로 6시간 26분). 세 가지로 확인했다. 밀기를 다시 32비트로 자르면 원본 C와 바이트까지 같고(출력 308줄, 진행 1716줄, 답 30885개), 부분 문제 38개는 64비트로 고친 C와 정확히 같으며, 찍힌 답 164,920개가 모두 독립 검사기를 통과한다. 크누스 자신의 무작위 탐침 어림잡기는 일의 크기를 미리 재는데, 21% 낮게 잡았다.
• perm.w — 플로이드의 무작위 뽑기 알고리즘(벤틀리의 More Programming Pearls에서). 1…N에서 서로 다른 정수 M개를 균등하게 O(M)에 뽑는다. 모든 부분집합이 같은 확률이고, 순진한 방법이 겪는 충돌 재시도가 없다. 작은 perm 라이브러리(와 채널 기반 생성기)를 짓는 한글 문학적 에세이이고, 성질·재현성·분포·벤치마크를 다루는 넉넉한 @(perm_test.go@> 묶음이 딸려 있다.
• polynum.w — 고정 다항체(폴리오미노)를 세는 Jensen의 전이 행렬 방법을 크누스가 구현한 것(2017)이다. h×w 직사각형을 칸마다 훑으며, 줄 끝의 점유와 연결 성분을 0 1 ( ) - 다섯 글자 짜임으로 묶고, 최소-합 행렬 곱셈으로 셈한 연결 비용으로 쓸모없는 짜임을 잘라 낸다. 셈 자체는 하지 않고 짝 프로그램 POLYSLAVE가 해석할 이진 명령어 파일을 내놓는다. 짜임 풀을 위아래로 번갈아 굴리며 구멍까지 다시 쓴다. 한 반복문에서 다른 반복문 몸통으로 뛰어드는 goto는 case 몸통을 함수 바깥 수준의 이름표로 펴서 옮겼다. 원본의 결함 셋을 고쳤다. n≥127이면 char 지수가 넘쳐 버스 오류로 죽는 것, confsize가 0이면 배열 밖을 읽는 것, slavesize가 2³⁰을 넘으면 명령어의 주소가 깨지는 것이다. 파이썬 슬레이브로 세어 20칸까지 OEIS A001168과 맞았고, 원본과 실행 스무 가지에서 명령어 파일까지 바이트가 같다. MetaPost 그림 하나(크누스의 polyomino.mp).
• prime-sieve.w — 에라토스테네스의 체를 구간마다 홀수만 비트로 담아 돌리며 256 이상인 소수 간격의 기록을 찾는다. 두 소수 사이에 모두 1인 64비트 낱말이 있어야만 간격을 자세히 보고, 32보다 작은 소수는 낱말마다 비트 무늬를 돌려 찍는다. 크누스의 2017년 CWEB 프로그램을 옮겼다. 크누스가 미심쩍어한 구간 경계의 간격 논리는 구간 크기를 128까지 줄여 시험해 보니 옳았다. 명령줄 검사의 결함 둘을 고쳤다. s₀²이 64비트에서 넘쳐 2³²의 배수인 출발점을 거절하는 것과, 음수 t에서 0으로 나누고 배열 밖을 읽는 것이다. 이진 로그 표는 math/bits로 바꾸었다. 원본은 파이썬 구간 체와 1197건에서 맞았고, 이 판은 원본과 621건에서 고친 두 경우만 빼고 바이트까지 같다. MetaPost 그림 하나.
• prjeuler152.w — Project Euler 152번 문제. 핵심이자 재미는 합을 부동소수점으로 견줄 수 없다는 데 있다. $1/n^2$ 항을 더할 때는 정확한 유리수 연산이 필요하고, $2^{79}$개의 부분집합을 모두 도는 무차별 방법은 불가능하다.
• queenon-partition.w — 마이클 심킨이 n×n 격자를 다이아몬드로 자르고 45° 돌린 2N×2N 격자로 보내는 묘한 사상을 다루는데, 2021년에 그가 n-퀸 개수의 점근을 얻을 때 쓴 칸 나누기다. 규칙, 곧 *(ij)*와 넓이가 양수인 부분을 나누는 칸 가운데 가장 작은 I를 잡고 비기면 더 큰 J를 잡는다는 규칙은, 쌍을 I<<16 - J로 담아 최소를 지키면 저절로 나온다. 넓이 자체는 nN×nN 픽셀 격자 위의 무차별 셈으로 정한다. 프로그램은 그 배정을 그리는 MetaPost 파일을 뽑아내는데, Go의 날문자열이 fprintf 스물 몇 개를 대신하니 MetaPost를 MetaPost로 읽을 수 있다. CWEB 원본과 (N, n) 쌍 649가지에서 표준 출력과 뽑아낸 .mp와 종료 코드가 바이트까지 같다. 글 안에 담긴 luamplib 그림 둘.
• sliding.w — 미닫이 블록 퍼즐을 두루 푸는 엔진이다. 0/1 무늬로 주는 조각이 15종류까지, 죽은 칸이 있는 판, 그리고 이동 방식이 여섯이다. 조각 하나를 한 칸, 조각 하나를 곧게 아무 거리나, 조각 하나를 아무 길로나, 그리고 저마다의 "초조각" 판으로 블록 몇 개가 함께 미끄러지는 것이다. 너비 우선 탐색은 거리 층을 마지막 셋만 들고 있는데, 크기가 제각각인 꾸러미를 상대 해시 사슬 고리로 엮은 순환 표에 담고, 이기는 수순도 되찾는다. 표가 처음을 잊었으면 더 가까운 목표로 다시 시작한다. 초조각은 "부딪힌다" 방향 그래프의 이상이고, 말끔한 백트래킹이 그것을 만들어 낸다. 옮기다가 진짜 결함을 만났다. 방식 5에서 크누스는 같은 앞 배치에서 이미 닿은 배치를 만나면 더 나아가지 않는데, 근거는 조각 하나만 움직였다는 것이다. 조각 하나에는 맞지만 초조각에는 틀리다. 모양이 같은 조각이 있으면 서로 다른 초조각이 같은 배치에 이를 수 있기 때문이다. 원본은 배치를 한 층 늦게 놓고(무작위 1800번 가운데 8번), 4수면 되는 것을 5수라고 답할 수 있다. 초조각마다 도장을 찍어 고친다. 함께 고친 것은 꾸린 배치를 찍을 때의 부호 확장 오류와, 정의하지 않은 조각 이름을 막지 않아 off[-1]을 읽는 것이다. 64비트 hi/lo 포인터 쌍은 그냥 uint64가 되었는데, 훗날의 독자가 이 대목에서 웃으리라고 크누스가 미리 적어 둔 바다. 고친 C와 2178번의 실행(여섯 방식, 모든 자세히 찍기 단계)에서 바이트까지 같고, 따로 짠 파이썬 너비 우선 탐색기가 층마다 확인해 준다.
• spiders.w — 삼부작을 닫으며 koda-ruskey와 li-ruskey를 낡은 것으로 만든다. 같은 문제, 곧 완전 비순환 방향 그래프의 x → y ⟹ 비트 x ≤ 비트 y를 지키는 0/1 라벨링을 뿌리 비트가 한 번 뒤집히는 그레이 경로로 늘어놓는 일을 다른 쪽에서 푼다. 준집합 U_k/V_k를 조상 사슬에 암묵적으로 실어 O(n²)어치 집합 전부를 선형 시간과 공간에 담고, 반사 부호의 홀짝을 n비트 산술 대신 ueven/veven 표 하나에서 읽어 내며, 깨어 있는 마디와 잠든 마디가 번갈아 있는 활성 목록의 블록이 미룬 플래그를 남기며 드나들어 참으로 무반복인 생성기가 된다. 삽입 자리에 대한 크누스의 원래 점화식은 스물다섯 해 동안 틀린 채였고 꼭짓점 다섯 개짜리 거미가 그것을 깨뜨리는데, 이 문서는 그 실패와 고침을 그림과 함께 짚어 간다 (크누스가 2026년 6월에 받아들이고 이 저장소 지은이의 공으로 적었다). CWEB 원본과 꼭짓점 7개 이하인 연결된 거미 10,067개 모두에서 -v 출력까지 맞춰 보았다. MetaPost 그림 넷.
• squint.w — 게으른 거듭제곱 급수를 요구에 따라 움직이는 채널 그물로 본다(합, 곱, 합성, 역수, 함수의 역, 그리고 exp 같은 미분 방정식). 매킬로이의 Squinting at Power Series를 따른다.
• ssbidiham.w — ssdiham.w를 양방향 그래프로 넓혀 해밀턴 회로를 모두 찾는다. 변 하나의 두 끝에 <나 >가 붙어 u<<v, u<>v, u><v, u>>v 네 가지가 있고, 이것들은 각각 변 u⁻—v⁺, u⁻—v⁻, u⁺—v⁺, v⁻—u⁺가 된다. SGB 파일에서는 호 길이를 4로 나눈 나머지로 가지를 적는다. 원본과 그래프 80개, 선택항 조합 26가지로 모두 2132번을 바이트까지 견주었다. 원본이 센 해의 수도 전수 탐색과 63개 그래프에서 맞춰 보았다. 원본이 마디 없는 그래프에서 죽는 것은 고쳤다. 같은 부호끼리 잇는 변이 생기므로 원본의 "g는 이분 그래프" 문장이 틀렸다는 것도 적었다. MetaPost 그림 하나.
• ssdiham.w — ssham.w의 유향판으로, 유향 그래프의 해밀턴 회로를 모두 찾는다. 카프(1972)의 바꿈을 좇아 마디 v를 v⁻와 v⁺로 쪼개고 호 u→v를 변 u⁻—v⁺로 삼으면, 그래프는 이분 그래프가 되고 해밀턴 회로는 v⁻—v⁺ n개를 보태면 회로 하나가 되는 완전 매칭이 된다. 이제는 차수가 1인 맨몸 마디가 방아쇠를 당긴다. 입력은 SGB .gb 파일이고 go-sgb의 gbsave.RestoreGraph로 읽는다. ssham.w와 달리 말과 종료 부호를 원본 그대로 두어, CWEB 원본과 그래프 75개, 선택항 조합 26가지로 모두 1962번을 바이트까지 견주었다. 해, 자세한 기록, 옆모습, 진행 보고, mem 수, gb_flip 무작위화가 모두 같다. 6×6 나이트 그래프에서는 ssham.w가 센 9862의 꼭 두 배인 회로 19724개를 찾는다. MetaPost 그림 하나.
• ssham.w — 그래프의 해밀턴 순환을 모두 찾는데, 부분 경로의 변을 그것이 마지막 순환의 어디에 놓일지 모른 채 고르는 알고리즘을 쓴다. 셀비의 1970년 착상이고, 크누스가 2001년에 모든 부분 경로의 지위가 같은 더 대칭적인 꼴로 다시 발견했다. 크누스의 SGB 시연 프로그램 SHAM과 헷갈리지 마시라. 세 글자가 같을 뿐 전혀 다른 알고리즘이다. 줄어드는 그래프는 성긴 집합(nbr/adj, adj는 인접 행렬 노릇도 겸한다)에 담기고, 꼭짓점은 맨, 바깥, 안 가운데 하나이며, 차수가 2인 맨 꼭짓점은 trigger 목록에 올라 제 변 둘을 강제한다. 입력은 SGB .gb 파일이고 go-sgb의 gbsave.RestoreGraph로 읽는다. 또 go-sgb의 gbbasic.Board와 gbsave.SaveGraph는 C SGB와 바이트까지 같은 파일을 쓴다. 원본에서 goto의 거미줄은 그대로 옮겨 오고, 이름표 하나만 더 있으면 된다(Go는 블록 안으로 뛰어들 수 없다). CWEB 원본과 그래프·선택지 쌍 845가지에서 맞춰 보았다. 답과 자세한 기록과 프로파일과 진행 문자열과 mem 수가 모두 같고 gb_flip 무작위화까지 같다. 6×6 나이트 그래프는 양쪽 모두 2265+4671495 mems에 순환 9862개를 준다.
• tarjan-strong-and-weak.w — 알고리즘 7.4.1.2T를 다시 다루되 이번에는 알고리즘 7.4.1.2W를 나란히 싣는다. 크누스의 약한 성분은 흔히 말하는 약연결 성분이 아니다. 호가 없는 방향 그래프에는 하나뿐이고, 꼭짓점 k개짜리 경로에는 k개다. 흔한 쪽은 그가 무향 성분이라 부른다. 약한 동치는 "서로 닿을 수 있거나 서로 닿을 수 없다"의 추이 폐포이고(그레이엄, 크누스, 모츠킨, 1972), 응축 그래프 위에서는 정확히 비교 불가능 그래프의 연결성이다. 곧 닿음 포셋의 가장 잘게 나눈 서수 분해 P₁ ⊕ P₂ ⊕ ⋯ ⊕ Pₘ의 한 블록이고, 크누스의 색인은 이것을 포셋의 직렬 분해라 부른다. (정의는 프로그램에서 거꾸로 알아낸 뒤 약한 성분이 1개에서 20개인 방향 그래프 2500개에 무차별 셈으로 맞춰 보고, 프리패시클 12a로 확인했다.) 그 관점이 알고리즘을 읽을 수 있게 만든다. 블록은 타잔이 내놓는 차례에서 잇닿은 구간이므로, W는 잘린 자리가 가장 새 성분 위에 맞는지만 물으면 된다. 구체적으로는 위 블록의 원천이 모두 맞았는지 묻는데, 타잔의 HIT/WHIT 게으른 삭제가 정확하게 지켜 주는 원천 목록을 따라 걷는다. C가 쓸모 필드 다섯 개를 더 긁어모으려고 그림자 꼭짓점 n+1개를 잡아야 하는 자리에서, Go의 레코드는 아홉 개에 그냥 이름을 붙인다. C 원본과 출력과 mems가 바이트까지 같다. SGB의 로제 그래프와 무작위 방향 그래프 2230개에서 맞춰 보았는데, W의 병합 반복문과 경로 압축된 src 걷기를 굴리려고 지은 사슬과 추이 토너먼트와 층진 그래프도 함께 넣었다. go-sgb를 쓴다. MetaPost 그림 둘은 tarjan-strong.mp의 도우미를 함께 쓴다.
• tarjan-strong.w — 타잔의 강한 성분. 크누스의 CWEB tarjan-strong.w(곧 나올 프리패시클 12a의 알고리즘 7.4.1.2T)를 따른다. 깊이 우선 한 번으로 강한 성분을 모두 찾고, 증서도 함께 내놓는다. 성분마다 강한 연결을 지켜 주는 tree와 inner 호, 그리고 응축 그래프의 호마다 link 하나다. 크누스 자신의 노트에는 그가 처음에 잘못 잡았던 규칙, 곧 나무 자식이 LOW를 비길 때 부모의 안쪽 호를 버리는 규칙이 적혀 있는데, 이 문서는 그 틀린 판을 지어 그의 다섯 호짜리 반례에 돌려 실패를 되살린다. 여기서 LOW는 패시클이 내리막 경로와 호의 성숙으로 정의하는 이브–쿠르키수오니오 판이지 타잔의 1972년 lowlink가 아니다. 나무가 아닌 호 v→u는 PRE(u)가 아니라 LOW(u)를 돌려준다. 그래서 "LOW가 같으면 성분도 같다"는 거짓이고(무작위 방향 그래프 500개 가운데 168개에서 깨졌다), 그 때문에 꺼내기 검사가 ≥다. 옮긴 판은 C의 low/rep 합집합을 책이 정한 부호화(한 필드 안의 SENT + v′)로 바꾸는데, 그래야 mem 수가 맞고 원본의 포인터 주소 검사 exit(-666)도 지울 수 있다. C 원본과 출력과 mems가 바이트까지 같다. SGB의 로제 그래프(꼭짓점 1022개, 성분 77개)와 무작위 방향 그래프 1615개에서 맞춰 보았고, 증서는 다시 1500개에서 뜻이 맞는지 따로 검사했다. go-sgb를 쓴다. MetaPost 그림 셋.
• topswops.w — 콘웨이의 톱스왑스 놀이를 페퍼다인의 거꾸로 탐색(끝난 자리에서 놀이를 거꾸로 돌린다)으로 푼다. 크누스의 CWEB topswops.w를 다시 풀어 쓴 한글 문학적 에세이이고, MetaPost 그림(놀이 한 판과 n=3의 거꾸로 탐색 나무 전체)과 콘웨이의 멈춤 논증에 대한 증명이 딸려 있다.
• topswops_fwd.w — 같은 놀이를 앞으로 푼다. 자리 표시 카드와 f(m) 가지치기 한계를 쓰는 분기 한정 탐색이고, goto 상태 기계로 썼다. 크누스의 CWEB topswops-fwd.w를 다시 풀어 쓴 한글 문학적 에세이이고, MetaPost 그림(이름표 다섯 개짜리 상태 기계와 가지치기 한계)이 딸려 있다.
• twintree-to-baxter.w — 쌍둥이 나무에서 그것을 낳는 백스터 순열을 찾는다. 크누스의 2021년 삼부작의 둘째 편으로, floorplan-to-twintree.w에 ttform 변경 파일을 적용한 출력을 그대로 읽는다. 입력이 쌍둥이 나무의 다섯 조건을 만족하는지 살핀 뒤, Dulucq과 Guibert의 보조정리에 따라 T₀의 뿌리를 하나씩 떼어 내며 순열을 찍는다. 문서의 절반은 백스터 순열의 성질(뒤집기, 여순열, 역순열과의 관계, n을 끼울 수 있는 자리)이다. 옮기며 원본의 결함 둘을 고쳤다. 뿌리 번호의 범위를 살피지 않아 배열 밖을 읽는 것과, fscanf가 넘치는 수를 2³²로 나눈 나머지로 읽어 4294967297을 마디 1로 받아들이는 것이다. 서술의 오타 둘도 고쳤다. 크기 8까지의 쌍둥이 나무 13373개 모두에서 내놓는 순열이 백스터 순열이고 입력을 그대로 낳으며, 잘못된 입력 30000개에서 원본과 같은 말을 한다. 첫째 편의 Go 판과 엮어 백스터 순열 13373개가 한 바퀴 돌아 제자리로 온다. MetaPost 그림 하나.
• ulam-gibbs.w — 울람 수(1, 2, 3, 4, 6, 8, 11, … — 저마다 앞선 두 수의 합으로 나타나는 방법이 꼭 하나인 가장 작은 수)를 필립 깁스의 방법으로 수십억 개 셈한다. 슈타이너베르거는 λ ≈ 2.443443에 대해 U_n/λ mod 1이 거의 언제나 [1/3..2/3]에 떨어지는 것을 알아챘고, 깁스는 그것을 O(N) 알고리즘으로 바꾸었다. 후보마다 최근 울람 수의 창 위에서 짧은 무차별 탐색을 하거나 짧게 정렬된 이상값 목록에 기대어 판정하고, 바이트당 18비트 부호화가 울람 여부 표를 .778N 바이트에 꾸린다. 옮기다가 CWEB 원본의 진짜 결함을 만났다. 줄 else @<outlier tests@>;가 중괄호 없이 짜이는 탓에 else가 첫 문장만 다스리고, 표현을 찾지 못한 무차별 탐색 뒤에는 언제나 낡은 한계를 단 채 닻 반복문까지 돌아간다. 기본 λ에서는 그런 일이 한 번(u = 25) 일어나고 탈이 없지만, 성긴 근삿값에서는 C 프로그램이 틀린 울람 수를 찍는다. 선택지 p22 q9는 U₇₀₀부터 어긋난다. 중괄호가 반드시 있어야 하는 Go판은 곧이곧대로 센 것과 맞는다. 중괄호를 되살린 C 원본과 선택지 조합 47가지에서 맞춰 보았고, 표준 출력과 표준 오류와 mems와 METAPOST 히스토그램이 모두 같다. N = 10⁶에 대해 프로그램이 그리는 히스토그램을 문서의 그림으로 실었다.
• whirlpool-count.w — m×n 행렬의 2×2 부분행렬마다 네 원소가 가장 작은 것에서 가장 큰 것까지 한 바퀴 도는 소용돌이 순열의 수를 센다. 원소 n+1개의 부분 순열을 반전 수로 뺀 좌표 x_j로 나타내고, t마다 다른 메모리 사상 μ_t로 옛 셈을 덮어쓰지 않고 제자리에서 새 셈을 적는 동적 계획법이다. n-변이는 알고리즘 7.2.1.2X 모양의 되추적으로 훑는다. 크누스의 2020년 CWEB 프로그램을 옮겼다. 원본은 8×4와 7×5에서 셈이 64비트를 넘어 틀린 답을 내므로 (8×4의 참값은 278588168022148184390533120), 이 판은 올림을 살펴 멈춘다. 부분 순열 표현의 예와 λ_t의 식 등 설명의 잘못도 고쳤다. 전수 탐색과 열한 가지에서 맞춰 보았고, 원본과 크기 29가지에서 바이트까지 같다. MetaPost 그림 하나.
• word-cube-dlx.w — 앞의 wordcube.w와 똑같은 대칭 낱말 정육면체를 남에게 맡긴다. 이쪽은 문제 전체를 정확한 덮개(XCC) 사례 하나로 옮겨 DLX 파일로 써 낸다. 크누스의 word-rect-dlx.w ("BACK-MXN-WORDS-NEW와 겨루라고 만든 것")가 하던 방식이다. 옮겨 놓고 보면 놀랄 만큼 작다. 주 항목 15개(i <= j인 줄들), 부 항목 35개(칸들, 정렬한 첨자 세짝으로 이름을 짓는다), 그리고 줄과 낱말의 쌍마다 선택지 하나인데, 그 다섯 색 항목이 어느 글자가 어디에 놓이는지 말한다. 이름을 정렬하는 것이 대칭 장치의 전부이고, 그것을 검사하는 코드는 한 줄도 없다. 덤이 공짜로 따라온다. 낱말마다 색 없는 부 항목을 하나 두면 "열다섯 낱말이 모두 다르다"가 코드가 아니라 플래그(-d) 하나가 된다. 잘라 낸 사전 위에서 wordcube와 맞춰 보았고(낱말 3000개에서 3 대 3, 3500개에서 83 대 83, -d로 60 대 60), 뽑아낸 답마다 5×5×5 배열로 되짚어 지어 세 축을 따라 다시 검사했으며, 전체 목록도 끝까지 돌려 같은 83,576개를 얻었다. 마지막 장은 둘을 겨루게 한다. 춤추는 칸이 더 나은 나무를 쳐 내는데(마디 5710만 개 대 9800만 개) 시계로는 진다. 칸 항목 하나가 3·|W|개의 선택지에 들어 있어서, 색칠 한 번이 수천 개를 걷는 자리에서 백트래킹은 이진 탐색 한 번을 하기 때문이다. 규모가 커지면 덮인 항목이 목록을 줄여 차이가 좁아지기는 한다(낱말 2000개에서 92배, 3500개에서 39배, 전체 목록에서 16배로 26분 36초 대 1분 41초). 그 자리에서 그리는 MetaPost 그림 하나와 wordcube.mp에서 빌려 온 그림 하나.
• wordcube.w — 스탠퍼드 그래프베이스의 다섯 글자 낱말 5757개로 대칭 5×5×5 낱말 정육면체를 몇 개나 지을 수 있는가? 완전히 대칭인 정육면체는 세 축 어느 쪽으로 읽어도 같은 낱말이 나온다. 말끔한 백트래킹이 열다섯 줄을 행 우선으로 채우는데, 새 낱말마다 이미 놓인 글자가 접두사를 이루니 나머지는 사전 찾기가 해 준다. 답은 83,576개다(열다섯 낱말이 모두 달라야 하면 75,130개). 기본 프로그램은 배제(전방 검사)를 더한다. 낱말을 놓을 때마다 아직 채우지 않은 줄이 사전으로 채워질 수 있는지 확인해, 탐색 마디를 46억 개에서 9800만 개로 쳐 낸다(차례로 돌려 1분 30초쯤). 한글 문학적 에세이이고 MetaPost 그림이 딸려 있다. 짝이 되는 변경 파일 wordcube-par.ch(gtangle wordcube.w wordcube-par.ch)는 고루틴으로 병렬 빌드를 갈라 낸다. 첫 낱말의 서로 독립인 선택이 일꾼들로 퍼져 나가, 코어 10개에서 13초쯤에 같은 답을 준다.
• ziptree.w — 타잔과 레비와 팀멜의 짚트리. 기하 분포 난수 등급으로 최대 힙 순서를 지키는 무작위 이진 탐색 트리이고(비기면 키가 작은 쪽을 민다), 회전 대신 탐색 경로를 지퍼처럼 열고 닫아 갱신한다. 논문의 재귀적 insert, zip, delete를 라이브러리로 구현한 뒤 메모리를 아끼는 두 가지를 이끌어 낸다. 아레나(첨자 기반, 등급 1바이트, 빈칸 목록)는 마디 크기를 절반으로 줄이고 백만 마디 빌드의 할당을 100만 번쯤에서 40번쯤으로 줄인다. 의사 난수 등급 판은 등급 필드를 아예 없앤다(키에서 셈한다). 명령 go test로 돌리는 @(zip_test.go@> 시험 파일은 논문의 그림 1을 정확히 되살리고, 세 표현을 교차 확인하고, BST와 힙 불변식을 퍼징으로 검사하고, 할당을 벤치마크한다.
• cdq-dc/ — CDQ 분할 정복. 문제가 아니라 쌍의 집합을 가르는 오프라인 기법으로, 앞쪽 절반이 뒤쪽 절반에 제 몫을 미리 치르게 한다. 무기 하나에 축 하나다. 정렬, 분할 정복, 펜윅 트리.
  • flower/ — 뤄구 P3810, 3차원 부분 순서. 기법 일반을 다룬다. 무엇이고, 언제 쓰이고, O(n log n log k)이고, 무엇을 내주어야 하는지.
  • inv/ — 뤄구 P3157, 동적 역위. 시간을 축으로 올린다.
  • stars/ — POJ 2352, 별의 등급. 축이 둘뿐이라 입력이 정렬을 대신하고 펜윅 트리마저 사라진다. 기법의 가장 헐벗은 모습이다.
  • robin/ — LightOJ 1112. 다른 셋의 말 없는 셋째 축인 펜윅 트리에게 무대를 내주는 곁가지다.
• cht/ — 볼록 껍질 요령. 이차 DP 전이를 직선으로 다시 읽고, 그 직선들의 아래 포락선을 본다. 디렉터리 cdq-dc/의 짝으로, 단조성을 한 칸씩 빼앗기며 같은 사다리를 내려간다.
  • frog/ — 앳코더 EDPC Z, Frog 3. 기법 일반을 다룬다. 기울기와 질의가 모두 단조라 덱이 껍질을 들고 전체가 O(n)이다.
  • bridge/ — CEOI 2017 Building Bridges. 단조성이 둘 다 깨져 덱 대신 리차오 트리가 들어서고, 교점 대신 값을 견주니 128비트 산술이 물러난다.
  • cash/ — NOI 2007 Cash. CDQ 분할 정복이 세상에 나올 때 함께 온 문제다. 두 갈래가 여기서 만난다. 시간에 대한 재귀, 위로 올라가며 x에 대해 병합, 아래로 내려가는 기울기.
  • segment/ — HEOI 2013 Segment. 온라인이 강제되어(좌표가 앞선 답으로 암호화되어 온다) CDQ도 좌표 압축도 막히고, 리차오 트리만 제 집인 선분 삽입 문제에 홀로 선다.
• guitar-tuner/ — 맥의 마이크를 읽어 음높이를 바늘 계기로 실시간에 보이는 기타 튜너. 음높이 검출은 DSP 라이브러리 없이 YIN 알고리즘을 맨손으로 구현한 것이다. 차이 함수, 누적 평균 정규화, 절대 문턱값, 포물선 보간을 하고, 그 둘레에 고역 통과 전처리와 어택 과도 억제와 중앙값 평활화와 옥타브 오류 보정을 두른다. 소리 잡기는 malgo(miniaudio)로 한다. 자세한 것은 제 README에 있다. 위의 두 모음과 달리 이것은 프로그램 하나를 문서 셋으로 자른 것이다.
  • pitch/ — 마이크도 화면도 모르는 순수한 핵심. 곧 pitch.Stream 뒤의 검출 파이프라인과 개방현 음악 이론이다.
  • tuner.w — 콘솔 프런트엔드. 터미널에 그리는 반음계 계기다.
  • gui/ — Gio 네이티브 창으로 만든 둘째 프런트엔드. 같은 핵심을 함께 쓴다.
• life-game/ — 터미널에서 도는 콘웨이의 생명 게임. 그래픽 라이브러리는 전혀 쓰지 않는다. 콘웨이에게 바둑판으로 넉넉했다면 우리에게는 ANSI 이스케이프 부호로 넉넉하다. 우주는 원환면이라 한쪽 끝으로 걸어 나간 글라이더가 다른 쪽에서 돌아오고, 고스퍼의 글라이더 총도 끝내 제가 쏜 줄기에 맞아 떨어진다. 파일 .w 하나가 프로그램이자 에세이이고, 제목은 노자의 천지불인에서 왔다. 찻상 위에 돌을 놓아 가며 규칙을 다듬던 콘웨이, 글라이더 총이 매듭지은 50달러 내기, 그리고 말년의 "나는 생명 게임이 싫다"는 말을 담았다. 디렉터리 demos/에는 vhs로 찍은 기록이 있다.
• skew-ternary/ — 크누스의 skew-ternary-calc와, 누군가 만들어 주기를 그가 바랐던 대화형 장난감. 삼진 나무의 빈자리마다 싹이 돋고, 마디와 싹 저마다 등급이 있다(왼쪽 자식 −1, 가운데는 그대로, 오른쪽 +1). 등급이 한 번도 음수가 되지 않으면 그 나무는 비스듬하다. 어여쁜 정리는 그런 나무 2n+2개로 된 순환 가족마다 비스듬한 것이 정확히 넷이라는 것인데, 개미를 둘레로 기어가게 해 싹은 올리고 호는 내리며 세면 증명된다. 프로그램은 나무의 세 켤레를 셈한 뒤 대응하는 평면 지도를 두 가지로 짓는다. 자카르와 셰페르의 대응으로 한 번, 델룽고와 델리스토로와 페노의 대응으로 한 번인데, 기바스–스톨피 쿼드에지 구조 위에서 하며, 크누스 자신의 놀라움이 사는 곳도 거기다. 네 켤레가 네 개의 쌍대 지도를 준다는 추측인데, 질 셰페르가 자기 1998년 학위 논문에서 설명해 주었다. CWEB 원본과 씨앗마다 6333가지에서 차이 없이 맞춰 보았고, 크누스의 MetaPost 그림 68개도 모두 함께 옮겼다. 그러면서 mpost의 한 번 훑기 모형(그림이 앞선 그림의 상태를 물려받는다)에서 luamplib의 그림별 모형으로 바꾸었다.
  • app/ — 크누스가 들어가며에서 손수 밝힌 바람, 곧 누군가 이 나무들을 대화형으로 다루고 그 무늬를 색으로 드러내 주기를 바란 것에 답하는 HTML 한 쪽. 개미를 둘레로 한 걸음씩 옮기며 싹이 쌓이고 짝지어 사라지는 것을 보다가, 끝내 짝을 찾지 못한 넷만 남으면 그것들이 가리키는 네 켤레를 돌려 본다. 셈은 .w 자신의 파싱과 상태표 장을 자바스크립트로 옮긴 것이고, 무작위 비스듬 나무 3510개에서 Go 프로그램과 맞춰 보았다.