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