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 wrangling 2.3 main loop 3 wrapping up

theory

This is a simple sed(1) script to generate look-and-say sequences such as the Conway sequence.

practice

looking and saying

Although it is possible in sed to count via a lookup table, here it is simpler to enumerate the possible digit groups.

<<count groups>>=
:B
s/@\(.\)\1\1/3\1@/;tB
s/@\(.\)\1/2\1@/;tB
s/@\(.\)/1\1@/;tB

Question: why does our implementation only support run lengths of 1, 2, and 3?

data wrangling

In the previous section, we used @ as a cursor to maintain context, separating the output (to say) from the input yet to be processed (to look at). Therefore we need to add a cursor before processing each line and then remove it afterwards.

<<transform line>>=
s/^/@/
count groups
s/@//

main loop

Finally, we wrap everything up in an infinite loop that prints its intermediate state at every iteration.

<<conway.sed>>=
:A
p
transform line
bA

wrapping up

All that remains is to test a few look-and-say sequences.

look and say:

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

conway:

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

sole degeneracy:

> echo 22 | sed -f conway.sed | head -10
22
22
22
22
22
22
22
22
22
22

Download code