Most useful

Kimmo Fredriksson

Judges' comments:

To build:

make fredriksson

To run:

./fredriksson [-icvtnk#] regexp < file


./fredriksson -k1 -i POOT < /etc/group
ulimit -s unlimited
./fredriksson -k2 -t -n bofuskate < /usr/share/dict/words

Selected Judges Remarks:

The author of this entry was making sure that it does not win the “Best Short Program” award. On the outside, the program behaves as an approximate grep. On the inside, it is a Burrows-Wheeler transform decompressor that produces the source code of the actual obfuscated approximate grep program and calls it. As an exercise, try writing the compressor.

Author’s comments:

Approximate grep

Implements a variant of grep.


To search regexp from file, do:

./fredriksson [-icvtnk#] regexp < file

Pipes may not work, see the section Limitations. The options -i -c -v and -n are the classic ones:

This version of grep recognizes two more options, not present in normal grep implementations:

Of course, one could construct a standard regexp that matches the same patterns, but the problem is that such a regexp grows exponentially in size when the number of allowed edit operations is increased.

This version does not recognize all regular expressions, but the following are allowed:

The special characters must be escaped, if they are to be taken literally (i.e. use e.g. \. to match period). You might want to protect these with ', i.e. use 'foo\[bar' instead of foo\[bar. If you want to use the literal - in bracket expression, protect that too (\-), otherwise this is not needed. Note that the syntax differs from standard (?) grep a bit, i.e. in plain grep you can use ] and - in bracket expressions by putting ] as the first character, and putting - last.

Other uses

Other features

Limitations and remarks

Obfuscations (a.k.a. spoilers…)

Creative Commons License

© Copyright 1984-2012, Leo Broukhis, Simon Cooper, Landon Curt Noll - All rights reserved
This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.