# Look and say sequence (dc)

Other implementations: C++ | dc | J | Java | Lua | Ruby | Scala | sed | sh

# theory

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

# practice

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

## 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
```

## 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
```

## 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$?

## 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
```

# 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?

hijacker
hijacker
hijacker
hijacker