./getwords.sh en | grep .. | ./prog aeiouvwxyz
./getwords.sh en | grep .. | ./prog aeiouhjklmnvwxyz
./getwords.sh en | grep .. | ./prog mrjocktvquizphdbagsfewlynx
A few letters, one at a time, with no repeats. How many different ways can this be done?
While a quick brown fox might jump over the lazy dog, it has too many repeat letters to allow this entry to repeat. It is better that Mr Jock, TV quiz PhD, bags few lynx.
Speaking of jumping, can you rewrite the code to remote all of the goto jumps in this code?
This entry reads from standard input a list of words in any language written with an alphabet and outputs perfect pangrams composed of these words. A perfect pangram is a series of words that contains every letter of the alphabet exactly once.
$ grep .. /usr/share/dict/words | ./prog abcdefghijklmnopqrstuvwxyz
qualm fjord wiz pyx vs beg kc nth
quartz jinx vs fed kc womb glyph
quid jamb fez vs pyx kc growl nth
quiz fjord pyx vs bag kc mewl nth
quiz fjord pyx vs gab kc mewl nth
quiz fjord pyx vs gem bawl kc nth
quiz fjord pyx vs meg bawl kc nth
quiz fjord vex bawl kc gyp ms nth
quiz jamb flex vs kc gyp word nth
quiz jamb pyx vs kc flog drew nth
quiz jamb pyx vs kc frog lewd nth
quiz jamb pyx vs kc frog weld nth
quiz jamb pyx vs kc golf drew nth
quiz jamb pyx vs kc grew fold nth
quiz jamb pyx vs kc grow nth fled
quiz jamb pyx vs kc growl fed nth
Rearranging the words into more or less meaningful expressions is the user’s duty.
This entry implements Algorithm X (Exact cover via dancing links) from Section 220.127.116.11 in fascicle 5C of The Art of Computer Programming by Donald E. Knuth. As of June 2019, you can download an incomplete draft of the fascicle from Knuth’s website.
prog LETTERS [N]
reads allowed words from standard input and writes perfect pangrams
with at most N words composed of LETTERS to standard output, one
per line. If N is not given, the number of words in the pangrams is
unlimited. The characters in LETTERS must not repeat. The length of
LETTERS must not exceed 97 characters.
The exit status is 0 if no error occurred, 1 if the input word list is too long, and 2 if the command-line arguments are missing.
outputs a sorted list of unique words in a given language, one per
line. It requires
aspell with a dictionary for LANGUAGE_CODE.
wrapprog.py LETTERS [N]
works similarly to
prog LETTERS [N] except that it merges
anagrams before passing them to
prog and expands them in
prog’s output. This way, it finishes the job faster than
prog when there are millions of perfect pangrams. It requires a
ru.sh output German, English, French, Italian, Polish,
and Russian perfect pangrams, respectively. They require a UTF-8
I dare submit this entry to categories algorithms,
internationalization (I have not found active use of
among the programs that won IOCCC in the past), and obscure bugs (see
the questions about Linux core dumps below).
To a casual eye, this entry may look similar to
prog is internationalized and way faster. On my machine,
./klausler abcdefghijklmnopqrstuvwxyz printed only 3,965 perfect
pangrams until I killed it after 144 hours running, while the
tr A-Z a-z < /usr/share/dict/words | egrep -v '^[^ais]$' | ./prog abcdefghijklmnopqrstuvwxyz | wc -l
finished in 62 minutes, reporting 1,640,569,315 perfect pangrams, and
the example from section What is this? finished in 1.35
seconds. On the other hand,
prog can only output series of words
with nonrepeating characters, unlike
In contrast to
prog.c does not call
fflush(stdout) after outputting each line, thus running faster.
I am grateful to Witold Jarnicki for suggesting this change.
prog finished the example above in 100 minutes
instead of 62 minutes.
If your word list contains meaningless one-letter words, pipe
grep .. [FILE] through
prog to eliminate the pangrams that
aspell, some languages, e.g. Spanish,
have no perfect pangrams.
yes | ./prog y hang on Linux? Change
static int to
static wchar_t to
wchar_t, and recompile
prog. Why does
yes | ./prog y dump core now? Change the line
#define P 9<<23^1 to
#define P 9<<23 and recompile
prog. Why does
yes | ./prog y exit gracefully?
Answer: Nf bs Whar 2019, guhf znavsrfg ohtf va
The source code uses
goto three times. While it could easily get
goto M and
goto H, I challenge the adherents of
structured programming to refactor
goto T, which jumps back into a
With the supplied
prog.c without warnings in C11 and C99 mode. For a clean
gcc -std=c90, add
© Copyright 1984-2019,
Leo Broukhis, Simon Cooper, Landon Curt Noll
- All rights reserved