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>>=
function look_and_say(seed, reps)
  make next sequence
  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

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>>=
function look_and_say_pat(seed, reps)
  local seq = tostring(seed)
  local last = seq
  for i=2,reps do
    build next using patterns
    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>>=
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>>=
function test(expected, actual)
  return ((expected == actual) and "pass: "..expected or "fail: "..actual).."\n"
end

Download code