Look and say sequence (J)
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 J script to generate look-and-say sequences such as the Conway sequence.
practice
looking and saying
We simply count the multiplicity of the value in each run,
and — following functional programming tradition —
zip the results together so they interleave.
Here we take full advantage of J's facilities for tacit programming;
in this case the distributive law that makes
x (F G H) y equivalent to (x F y) G (x H y).
<<look and say>>= ((count zipto value) first)
ancillary definitions
In order to work on the runs,
first we must find the first element
of each run.
The expression 2=/\
compares each pair (2) of elements for equality (=).
As the first element is certainly not equal to its predecessor,
we prepend a boolean false to the result (0,).
Finally, as we have just computed every element in a run but the first,
we negate (-.) the entire result.
This function does throw information away, but
here we take advantage of another tacit programming definition:
(F G) y is equivalent to y F (G y),
allowing us to have both the processed and the original argument.
NB. x and y are canonical J for left and right arguments, respectively, in a function definition
<<defns>>= first=: monad : '-.0,2=/\y'
To count the multiplicity in each run, we first find the indices (I.) where first has indicated the beginning of a run. Similar to the verb train count zipto value, here we have the train I. , #, which concatenates (,) the previous result to the length of the entire list (#). Finally we take pairwise differences (2-~/\) to find the length of each run.
Question: why do we use flip (~) to reverse the sense of the subtraction?
<<defns>>= count=: dyad : '2-~/\(I.,#)y'
Extracting the values is dead simple: we repeat (#) each element of the left argument (our original array) with a multiplicity of the right argument (from first). Because first returns a boolean array, this results in a projection where we get either 0 or 1 copies of each element; in fact, the final result will be just one value per run. QEF
Exercise: rewrite the definition of value using flip (~)
Question: do you understand the difference between the monadic (length) and dyadic (repeat) uses of the # operator?
<<defns>>= value=: dyad : 'y#x'
zipto is equally trivial. Although the zip of an array is equivalent to the transpose, here we find it easier to simply use sideways composition (,.) to paste the arrays together as columns, and then ravel (,) the result back to a linear array.
<<defns>>= zipto=: dyad : ',x,.y'
wrapping up
J does have an operator for iterating expressions (and, given an argument of , it naturally produces a fixpoint) but here we know we have an arbitrary unfolding that never converges, so we use a simple tail-recursive definition instead, setting it to work on the numeric value (".) of the input as a character array (stdin ''). As echo is called purely for effect, we use the [ as a binary equivalent of the K combinator — it ignores its right argument.
<<conway.ijs>>= loop=: monad : 'loop look and say y [ echo y' defns loop ". stdin ''
of course, if one prefers combinator form, it's possible to precompose the functions, resulting in a nearly point-free, much terser, definition:
loop=: monad : 'loop,@(((2&(-~/\))@(I.,#)@],.#~)(1,-.@(2&(=/\))))y[echo y' loop".stdin''
Finally, we try a few test cases.
look and say:
> echo -n 1 | jconsole conway.ijs | head -10 1 1 1 2 1 1 2 1 1 1 1 1 2 2 1 3 1 2 2 1 1 1 3 1 1 2 2 2 1 1 1 1 3 2 1 3 2 1 1 3 1 1 3 1 2 1 1 1 3 1 2 2 1 1 3 2 1 1 3 1 1 1 2 3 1 1 3 1 1 2 2 1 1
conway:
> echo -n 3 | jconsole conway.ijs | head -10 3 1 3 1 1 1 3 3 1 1 3 1 3 2 1 1 3 1 1 1 3 1 2 2 1 1 3 3 1 1 3 1 1 2 2 2 1 1 3 1 3 2 1 1 3 2 1 3 2 2 1 1 3 1 1 1 3 1 2 2 1 1 3 1 2 1 1 1 3 2 2 2 1 1 3 3 1 1 3 1 1 2 2 2 1 1 3 1 1 1 2 3 1 1 3 3 2 2 1 1 3
sole degeneracy:
> echo -n 2 2 | jconsole conway.ijs | head -10 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
Exercise: this is a nondegenerate degeneracy. Can you find the degenerate degeneracy?
| Download code |