Similar to Fibonacci, a piece of code that enlightened me was the simple PEG implementation, which is represented as a pair of mutually recursive procedures. I used to think of parsers as really difficult to understand, and hard to write. But the simplicity of PEG was an eye opener.

def unify_key(key, text, at):
   if key not in grammar:
       return (True, at + len(key)) if text[at:].startswith(key) else (False, at)
   rules = grammar[key]
   for rule in rules:
       res, l = unify_rule(rule, text, at)
       if res: return (res, l)
   return (False, 0)

def unify_rule(rule, text, at):
    for token in rule:
          result, at = unify_key(token, text, at)
          if not result: return (False, at)
    return (True, at)

Given a grammar as below, we try to unify the input string with the starting key – here expr. If To unify a key with the given string (unify_key), we check if the key is in the grammar. If it was not, then it is a plain token match, and we do simple string match. If not, we get the production rules defined in the grammar corresponding to the key, and try each rule one by one using unify_rule. We return as soon as any rule succeeds. The unify_rule is also simple. It gets the parts of the rule, and tries to match them in sequence using unify_key. If any of these fails, then return failure.

grammar = {
    'expr': [
        ['term', 'add_op', 'expr'],
        ['term']],
    'term': [
        ['fact', 'mul_op', 'term'],
        ['fact']],
    'fact': [
        ['digits'],
        ['(','expr',')']],
    'digits': [
        ['digit','digits'],
        ['digit']],
    'digit': [[str(i)] for i in list(range(10))],
    'add_op': [['+'], ['-']],
    'mul_op': [['*'], ['/']]
}

A driver

import sys
res, till = unify_key('expr', sys.argv[1], 0)
assert(till == len(sys.argv[1]))
print(res)

Using it:

$ python3 peg.py '1+10/(3+2)'
True
$ python3 peg.py '1+10/x(3+2)'
Assertion failure

While this implementation can have really bad performance due to back tracking, all one needs to do to make it linear is to decorate the procedures with @functools.lru_cache(maxsize=None), which memoizes the parsing, and makes parsing linear. While this does not implement the complete PEG syntax, it implements enough to be complete in terms of the grammars that can be represented (see Ford 2004 for details).

Edit: Thanks @asrp for finding that the original had issues.

For me, the single piece of code that had the largest impact was the ddmin from Andreas Zeller which is used to isolate failure causing input from much larger input.

import random
import string

def complement(s, i, l): return s[:i] + s[i + l:]

def some_complement_is_failing(s, npartitions, testfn):
    subset_length = len(s) // npartitions
    items = range(0, len(s), subset_length)
    complements = (complement(s, i, subset_length) for i in items)
    return next((i for i in complements if testfn(i)), None)

def update_input(s, npartitions, fn):
    v = some_complement_is_failing(s, npartitions, fn)
    if v:  return v, max(npartitions - 1, 2)
    else:  return s, min(npartitions * 2, len(s))

def ddmin(s, fn):
    npartitions = 2
    while s:
        s, n1 = update_input(s, npartitions, fn)
        if npartitions == len(s): break
        npartitions = n1
return s

Given a failure causing input, it is able to narrow the string down to the simplest sequence of characters necessary to cause the same failure. It is not limited to just strings but to any set of input conditions, and has been extended numerous times – The same algorithm lies behind git bisect. However, the core is still just this much.

As an example, run the following code: The test succeeds if the input contains “()”. So, we progressively trim the input until we find the smallest input that can cause the test to succeed.

def test(s):
    print("%s %d" % (s, len(s)))
    return set('()') <= set(s)

def fuzzer(): return ''.join(random.choices(string.digits +
                                            string.ascii_letters +
                                            string.punctuation, k=1024))

mystr = fuzzer()
minimized = ddmin(mystr, test)
print("%s => %s" % (mystr, minimized))

Edit: here is a better ddmin code than the one above. The above is kind of mangled by me.

I can’t read that page. I see it as a purple background with a faint red texture on it. Does chrome on Android have a high contrast feature?

The APL one definitely blew my mind.

I did stop reading when I reached the common mis-attribution of who did the bulk of the work on the Apollo code.

I’ve never seen that one image in the Game of Life article. That looked wild. Do you have a link to that implementation and its parameters so we can replicate it?