Look and say sequence (dc)

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

Contents

[edit] theory

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

[edit] practice

We will use the arbitrary-precision integers that dc provides as stacks of digits.

[edit] data structures

First, we provide methods to A) pop and B) push digits on the "stack" implemented by the number on the top of the dc stack.

<<conway.dc>>=
[10~ sx]sA
[r 10 * +]sB

Next, we provide parallel methods for two variables, the number of digits in each run, and the value of the digits forming the runs.

<<conway.dc>>=
[ln 10 * lc + sn]sC
[lv 10 * ld + sv]sD
[ln 10~ r sn]sE
[lv 10~ r sv]sF

[edit] counting runs

Counting the runs is a fairly standard control-break problem. We steadily pop digits until running out of input, either incrementing the count if it matches the current digit, or running W, a control-break routine that pushes the current state onto the number/count variables then resets the count and sets the current digit appropriately.

<<conway.dc>>=
[lCx lDx 0sc lxsd]sW
[lAx lxld!=W lc1+sc d0!=X]sX

[edit] interleaving output

Once all the digits have been processed, we go back the other direction, popping lengths and values, pushing them back onto the input.

<<conway.dc>>=
[lEx lBx lFx lBx ln0!=Y]sY

Question: why is it useful here that rev \circ rev = id?

[edit] main loop

Finally we set up an infinite loop and invoke it after having queried the user for an initial state.

<<conway.dc>>=
[0sc0sd0sn0sv]sZ
[f lZx lXx lWx lYx lLx]sL
c ? lLx

[edit] wrapping up

Now all that remains is to try various look-and-say sequences.

look and say:

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

conway:

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

sole degeneracy:

> echo 22 | dc conway.dc | head -10
22
22
22
22
22
22
22
22
22
22

Exercise: this is a nondegenerate degeneracy. Can you find the degenerate degeneracy?

Download code
hijacker
hijacker
hijacker
hijacker