fbpx

C++: Look-and-Say Sequence

Bjarne-stroustrup
 


The Look and say sequence is a recursively defined sequence of numbers studied most notably by John Conway.

Sequence Definition

  • Take a decimal number
  • Look at the number, visually grouping consecutive runs of the same digit.
  • Say the number, from left to right, group by group; as how many of that digit there are – followed by the digit grouped.
This becomes the next number of the sequence.

An example:

  • Starting with the number 1, you have one 1 which produces 11.
  • Starting with 11, you have two 1’s i.e. 21
  • Starting with 21, you have one 2, then one 1 i.e. (12)(11) which becomes 1211
  • Starting with 1211 you have one 1, one 2, then two 1’s i.e. (11)(12)(21) which becomes 111221

Task description

Write a program to generate successive members of the look-and-say sequence.

#include <string>
#include <sstream>
 
std::string lookandsay(const std::string &s)
{
  std::ostringstream r;
 
  for (unsigned int i = 0; i != s.length(); ) {
    unsigned int new_i = s.find_first_not_of(s[i], i+1);
    if (new_i == std::string::npos)
      new_i = s.length();
 
    r << new_i - i << s[i];
    i = new_i;
  }
  return r.str();
}
 
#include <iostream>
 
int main()
{
  std::string laf = "1";
 
  std::cout << laf << std::endl;
  for (int i = 0; i < 10; i++) {
    laf = lookandsay(laf);
    std::cout << laf << std::endl;
  }
 
  return 0;
}

SOURCE

Content is available under GNU Free Documentation License 1.2.