Look and say sequence (sed)

From LiteratePrograms
Jump to: navigation, search
Other implementations: C++ | dc | J | Java | Lua | Ruby | Scala | sed | sh

Contents

[edit] theory

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

[edit] practice

[edit] 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?

[edit] 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/@//

[edit] 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

[edit] 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
hijacker
hijacker
hijacker
hijacker