 C++: Look-and-Say Sequence

Posted in C++ 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

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.