# Look and say sequence (Lua)

### From LiteratePrograms

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

This article demonstrates a couple of different ways to generate look-and-say sequences (such as the Conway sequence) in Lua.

Look-and-say sequences are created by repeatedly applying the basic look-and-say algorithm to a string of digits. Each of the two look-and-say functions takes as arguments a `seed`

number (the starting point for the sequence), and a number of reps `reps`

which defines how many iterations of the generating algorithm should be carried out. The difference between the two functions is that one figures out what to "say" by explicitly counting the number of occurrences of a digit in a group, while the other uses the pattern-matching features of Lua's string library.

## Explicit counting

The look-and-say function starts from the seed digit, and applies the look-and-say algorithm to generate the next chunk of the sequence. The last sequence generated is fed into the generating algorithm to create the next version of the sequence, and the process is repeated for as many iterations as the user requests. Thus, the basic structure of the function is iterative in nature. The output of the function is a comma-delimited list of the results of each iteration.

<<explicit counting>>=functionlook_and_say(seed, reps)make next sequencelocalseq = tostring(seed)locallast = seqfori=2,repsdolocalnext = make_next(last)last = next seq = seq .. "," .. nextendreturnseqend

The actual generation of the next iteration of the sequence is carried out in the `make_next`

function. In this function, we start with the first digit in the string, and begin marching through the string counting the number of consecutive occurrences of that digit. As soon as we find a digit other than the one we're counting we append the count and the digit to the sequence we're generating, and then start counting occurrences of the newly found digit.

<<make next sequence>>=localfunctionmake_next(s)locald = s:sub(1,1)localsay = ""localcount = 0fori=1,s:len()+1doifs:sub(i,i)~= dthensay = say .. count .. d count = 0 d = s:sub(i,i)endcount = count + 1endreturnsayend

## Pattern-matching

The pattern-matching version of the look-and-say generator has the same signature as the previous version, and uses the same iterative structure to build up the sequence.

<<pattern-matched>>=functionlook_and_say_pat(seed, reps)localseq = tostring(seed)locallast = seqfori=2,repsdobuild next using patterns last = next seq = seq .. "," .. nextendreturnseqend

The difference lies in the way in which counting is done. In this case, we use the `string.match()`

function to find a group of consecutive identical digits. The length of the match immediately gives us the count to "say". The we continue on to process the remainder of the string following the group that was just matched. The code to implement this is so compact, we don't even bother to abstract it out into a separate function.

<<build next using patterns>>=localnext = ""whilelast:len()> 0dolocalc = last:sub(1, 1)localmatch = last:match(c.."+")next = next .. match:len().. c last = last:sub(match:len()+1, -1)end

## A few quick tests

We use two different look-and-say sequences to test both implementations of the look-and-say generators. One sequence comes from the Wikipedia page on look-and-say sequences. The other from the Wikipedia page on Conway sequences (which are a particular kind of look-and-say sequence).

<<look_and_say.lua>>=explicit counting pattern-matched test report io.write(test("1,11,21,1211,111221,312211,13112221,1113213211", look_and_say(1,8)))io.write(test("3,13,1113,3113,132113,1113122113,311311222113", look_and_say(3,7)))io.write(test("1,11,21,1211,111221,312211,13112221,1113213211", look_and_say_pat(1,8)))io.write(test("3,13,1113,3113,132113,1113122113,311311222113", look_and_say_pat(3,7)))

The results of running these tests are:

$ lua look_and_say.lua pass: 1,11,21,1211,111221,312211,13112221,1113213211 pass: 3,13,1113,3113,132113,1113122113,311311222113 pass: 1,11,21,1211,111221,312211,13112221,1113213211 pass: 3,13,1113,3113,132113,1113122113,311311222113

Note that the tests above make use of an auxiliary function that checks the test results and generates a simple message:

<<test report>>=functiontest(expected, actual)return((expected == actual)and"pass: "..expectedor"fail: "..actual).."\n"end

Download code |