(This is an entry for the "Most Beautiful Hack" prize)
sed is a unix utility for transforming text. It provides a simple programming language for matching and replacing text. Given its limited features, it was never designed as a general purpose programming language. However, it is an extremely versatile tool and can be used to solve problems way beyond the domain of simple text transformation. This is a proof-of-concept implementation of a maze solver written in sed.
How it works
The algorithm is a breadth-first search expressed as a cellular automaton. The rules of this automaton are simulated using sed's substitution command.
That's the high level overview. The actual implementation is challenging and ended up messier than I would have liked. The main difficulty lies in the lack of the luxuries usually provided in a regular programming language such as:
- data types other than strings
- more than 2 "variables"
Also, sed regex lacks features present in other regex systems such as PCRE (non-greedy matching, lookaheads, etc).