From LiteratePrograms

Other implementations: C++ | dc | Eiffel | Haskell | J | Java | Lua | OCaml | Perl | PHP | Python | Ruby | Scala | sed | sh

Contents 1 theory 2 practice 2.1 looking and saying 2.2 data mangling 2.3 lather, rinse, repeat 3 wrapping up

theory

This is a simple shell script to generate look-and-say sequences such as the Conway sequence. As is common for shell scripts, we will (ab)use standard utilities to do almost all the work; however we will have the equivalent of a loop and a structured variable in an anamorphic unfold which must roundtrip between data representations.

practice

looking and saying

Fortunately, there is already a unix utility, uniq, that when given the -c option (for Conway?) performs the heavy lifting of counting runs.

<<count runs>>=
uniq -c

data mangling

Unfortunately, we expect to operate on strings of digits, while uniq expects lines of text.

The conv=unblock option to dd, meant for taking fixed-width files (such as Forth blocks or punch card datasets) and producing line-oriented files, can also expand strings character-by-character if a trivial blocksize (cbs=1) is specified.

<<inject>>=
dd cbs=1 conv=unblock 2>/dev/null

Similarly, the tr program is capable, not only of character isomorphisms, but also, given the -d option, of mapping input (here, extraneous whitespace, whether the newlines introduced by our line-oriented injection, or the spaces introduced by uniq in counting) onto the trivial, null, output.

<<project>>=
tr -d " \n"

The two are not, strictly speaking, inverses — but they are close enough for our purposes here.

Excercise: can you spot the adjunction and its resulting monoid?

lather, rinse, repeat

finally we set up a small tail-recursive function to yield each value in the sequence and calculate the next one

<<conway.sh>>=
function looknsay() {
  echo $1
  looknsay $(echo -n $1|inject|count runs|project)
}

wrapping up

now all we need to do is provide an initial state (here taken from the command line, or defaulting to the conway sequence seed of "3")

<<conway.sh>>=
looknsay ${1:-3}

and we can test various sequences, such as look and say:

> sh conway.sh 1 | head -10
1
11
21
1211
111221
312211
13112221
1113213211
31131211131221
13211311123113112211

conway:

> sh conway.sh | head -10
3
13
1113
3113
132113
1113122113
311311222113
13211321322113
1113122113121113222113
31131122211311123113322113

and the sole degeneracy:

> sh conway.sh 22| head -10
22
22
22
22
22
22
22
22
22
22

Excercise: this is a nondegenerate degeneracy. can you find the degenerate degeneracy?

Download code