Look and say sequence (Lua)
- Other implementations: C++ | dc | Eiffel | Haskell | J | Java | Lua | OCaml | Perl | PHP | Python | Ruby | Scala | sed | sh
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>>= function look_and_say(seed, reps) local seq = tostring(seed) local last = seq for i=2,reps do local next = make_next(last) last = next seq = seq .. "," .. next end return seq end
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>>= local function make_next(s) local d = s:sub(1,1) local say = "" local count = 0 for i=1,s:len()+1 do if s:sub(i,i) ~= d then say = say .. count .. d count = 0 d = s:sub(i,i) end count = count + 1 end return say end
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>>= function look_and_say_pat(seed, reps) local seq = tostring(seed) local last = seq for i=2,reps do last = next seq = seq .. "," .. next end return seq end
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>>= local next = "" while last:len() > 0 do local c = last:sub(1, 1) local match = 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>>= 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>>= function test(expected, actual) return ((expected == actual) and "pass: "..expected or "fail: "..actual).."\n" end