Wednesday, March 23, 2011

Look and Say

There was a programming challenge a week ago that asked for solutions that create the Look and Say sequence. Below is an implementation in Factor.

The “Look and Say” sequence, Sloane number A005150, begins 1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, …. Each term is constructed from its predecessor by stating the frequency and number of each group of like digits. For instance, the term after 1211 is “one 1, one 2, and two 1s”, or 111221.

We can use the splitting.monotonic vocabulary to split a number, recombine it based on the length of intermediate sequences of digits, and produce the next value in a "Look and Say" sequence:

USING: formatting kernel math.parser sequences splitting.monotonic ;

: look-and-say ( n -- n' )
    number>string [ = ] monotonic-split [
        [ length ] [ first ] bi "%d%c" sprintf
    ] map concat string>number ;

You can try it out in the Listener to see the first 10 numbers in the sequence:

( scratchpad ) 1 10 [ dup . look-and-say ] times
1
11
21
1211
111221
312211
13112221
1113213211
31131211131221
13211311123113112211

No comments: