# Look and say sequence (dc)

### From LiteratePrograms

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

## Contents |

# 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 **n**umber of digits in each run, and the **v**alue 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 **c**ount
if it matches the current **d**igit,
or running **W**, a control-break routine
that pushes the current state onto
the number/count variables
then resets the **c**ount
and sets the current **d**igit 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 ?*

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

Download code |