xii.tex: Deciphering a TeX Puzzle

Updated 2016-09-28

xii.tex is a famous TeX puzzle by David Carlisle. The document source is terribly obfuscated. The following document is an attempt at deciphering the puzzle, i.e. an explanation of the various processes and TeX tricks.

The original puzzle can be found at CTAN/xii.

Here is a copy:

\let~\catcode~`76~`A13~`F1~`j00~`P2jdefA71F~`7113jdefPALLF
PA''FwPA;;FPAZZFLaLPA//71F71iPAHHFLPAzzFenPASSFthP;A$$FevP
A@@FfPARR717273F737271P;ADDFRgniPAWW71FPATTFvePA**FstRsamP
AGGFRruoPAqq71.72.F717271PAYY7172F727171PA??Fi*LmPA&&71jfi
Fjfi71PAVVFjbigskipRPWGAUU71727374 75,76Fjpar71727375Djifx
:76jelse&U76jfiPLAKK7172F71l7271PAXX71FVLnOSeL71SLRyadR@oL
RrhC?yLRurtKFeLPFovPgaTLtReRomL;PABB71 72,73:Fjif.73.jelse
B73:jfiXF71PU71 72,73:PWs;AMM71F71diPAJJFRdriPAQQFRsreLPAI
I71Fo71dPA!!FRgiePBt'el@ lTLqdrYmu.Q.,Ke;vz vzLqpip.Q.,tz;
;Lql.IrsZ.eap,qn.i. i.eLlMaesLdRcna,;!;h htLqm.MRasZ.ilk,%
s$;z zLqs'.ansZ.Ymi,/sx ;LYegseZRyal,@i;@ TLRlogdLrDsW,@;G
LcYlaDLbJsW,SWXJW ree @rzchLhzsW,;WERcesInW qt.'oL.Rtrul;e
doTsW,Wk;Rri@stW aHAHHFndZPpqar.tridgeLinZpe.LtYer.W,:jbye

Catcodes

The first step is to understand the TeX catcodes. It stands for category codes, i.e. the semantic of the various ASCII characters.

The first line

\let~\catcode~`76~`A13~`F1~`j00~`P2

applies the following catcodes:

Command defining commands

Next we have

jdefA71F~`7113jdefP

which, in proper TeX, would be

\def A #1{\catcode `#1=13 \def}

From then on, A will turn the first next character to an active character and define the second next character to what follows.

Example with the first application of A:

ALLF
P

(The linefeed matters.) It gets expanded to

\catcode `L=13 \def L {
}

So L is now a space.

The same process gets repeated throughout the following lines:

A''FwPA;;FPAZZFLaLPA//71F71iPAHHFLPAzzFenPASSFthP;A$$FevP
A@@FfPARR717273F737271P;ADDFRgniPAWW71FPATTFvePA**FstRsamP
AGGFRruoPAqq71.72.F717271PAYY7172F727171PA??Fi*LmPA&&71jfi
Fjfi71PAVVFjbigskipRPWGAUU71727374 75,76Fjpar71727375Djifx
:76jelse&U76jfiPLAKK7172F71l7271PAXX71FVLnOSeL71SLRyadR@oL
RrhC?yLRurtKFeLPFovPgaTLtReRomL;PABB71 72,73:Fjif.73.jelse
B73:jfiXF71PU71 72,73:PWs;AMM71F71diPAJJFRdriPAQQFRsreLPAI
I71Fo71dPA!!FRgieP

To sum up:

Core text

The above definitions did not produce any text, they merely served for laying down the foundations of the obfuscation.

The remaining text will generate the song:

Bt'el@ lTLqdrYmu.Q.,Ke;vz vzLqpip.Q.,tz;
;Lql.IrsZ.eap,qn.i. i.eLlMaesLdRcna,;!;h htLqm.MRasZ.ilk,%
s$;z zLqs'.ansZ.Ymi,/sx ;LYegseZRyal,@i;@ TLRlogdLrDsW,@;G
LcYlaDLbJsW,SWXJW ree @rzchLhzsW,;WERcesInW qt.'oL.Rtrul;e
doTsW,Wk;Rri@stW aHAHHFndZPpqar.tridgeLinZpe.LtYer.W,:jbye

Generative commands

The fundamental idea behind the text generation is that one command will loop over a list of sentences and run another command over each sentence.

The loop command is B. It recurses over the argument list using the , separator.

The sentence building command is X.

There is one last trick: the U command is used to propagate itself recursively on the #6 argument. Since there is no delimiter for #6, only one character is passed to U. The use of the & command shifts expands into another U called right after itself. Thus the rest of the #3 argument from B is successively passed to U .

Readable version

This version uses the same algorithm with human readable names.

% This is used to define active characters.
\catcode`@13
\def@#1{\catcode`#113\def}

% Nothing, useful to prevent globing.
@;;{}

% Space, used for last sentence shift from "a" to "and a".
@HH{\ }

% Character globing; used to glob extra commas, "ing" in some verses and "th"
% in ordinal numbers.
@WW#1{}

% Note that '#1' is everything from '&' to '\fi'. In our case, it is 'U#6'.
@&&#1\fi{\fi#1}

@UU#1#2#3#4 #5,#6{\par#1#2#3#5{ing}\if:#6\else &U#6\fi}

\def\day#1{\bigskip On the #1{th} day of Christmas my true love gave to me}

\def\gen#1 #2,#3:{\if.#3.\else \gen#3:\fi\day{#1}U#1 #2,#3:}

% Note that comments at the end of the lines are mandatory.
\gen
twelf lve drummers drumm,%
eleven ven pipers pip,%
ten ; lords a leap,%
nin e ladies danc,%
eigh ht maids a milk,%
seven en swans a swimm,%
six ; geese a lay,%
;fif ve gold ringsW,%
four r calling birdsW,%
;th{ird}W ree french hensW,%
;;;secondW two turtle dovesW,%
;;;firstW aH@HH{nd a }partridge in a pear tree.W,:

\bye

Simple version

This version uses an idea similar to the original, but without all the catcode intricacies.

\def\endverse{}

\def\verse#1 #2,#3:{\if.#3.\par #2{}\else\par#2\verse#3:\fi}

\def\day#1{\bigskip On the #1 day of Christmas my true love gave to me}

\def\gen#1 #2,#3:{\if.#3.\else \gen#3:\fi\day{#1}\verse#1 #2,#3:}

\gen
twelfth twelve drummers drumming,%
eleven eleven pipers piping,%
tenth ten lords a leaping,%
ninth nine ladies dancing,%
eighth eight maids a milk,%
seventh seven swans a swimm,%
sixth six geese a lay,%
fifth five gold rings,%
fourth fourr calling birds,%
third three french hens,%
second two turtle doves,%
first \endverse\def\endverse{and }a partridge in a pear tree.,:

\bye

References