Look-and-say Sequence With Python

Solve a trivial game using the power of groupBy method

Photo by Cyrus Lopes on Unsplash

Patterns… are everywhere and our species has evolved to recognize them. Last week I saw an interesting post on Twitter:

I have a challenge for you! Here is a sequence of numbers:
1–11–21–1211–111221–312211
Can you guess the next number?

Usually, patterns or sequences are visual, but not this one. Just by looking at it you can tell there’s a progression of numbers, but what’s the order?

This is a tricky one because you have to say it out loud to find the answer! To decipher the next element one has to count how many times a digit exists in the given state of the sequence. Let’s see how it goes:

1. 1 — “One” one (which becomes the next number in the series).
2. 11 — “Two” one
3. 21 — “One” two, “one” one
4. 1211 — “One” one, “one” two, “two” one
5. 111221 — and so on and so forth…

The numbers in quotations mark are the number of times a number is present in the sequence.

Then, in the same tweet, there was a bonus:

Can you write a program that computes the next term of the sequence?

After several attempts using dictionaries, list comprehensions, and NumPy arrays I found the right module to solve this problem: itertools. The premise is this: you need to count how many times a number shows up in the sequence before the next number. This can be done using thegroupby method.

According to the itertools documentation, groupby returns an iterator with multiple keys and groups from an iterable (list, tuple, dictionary). Let’s take a look at a itertools example:

>>>[key for key, group in groupby('AAAABBBCCDAABBB')]
[A, B, C, D, A, B]

As you can see, the keys are the letters each group is made of. When groupby finds a new letter distinct from the last one, it creates a new key. For example, it returns two keys for ‘A’ and ‘B’ because even if they are the same letters, these are separated by groups of other letters.

Now we’ll get the group. In this case, group is an iterable of grouped items. Thus, we’ll unpack its elements as a list.

>>>[list(group) for key, group in groupby('AAAABBBCCDAABBB')]
[['A', 'A', 'A', 'A'], ['B', 'B', 'B'], ['C', 'C'], ['D'], ['A', 'A'], ['B', 'B', 'B']]

The next step is to get the number of items for each group:

>>>[len(list(group)) for key, group in groupby('AAAABBBCCDAABBB')]
[4, 3, 2, 1, 2, 3]

Can you see how we can accomplish the Look-and-say sequence using groupby ? If it’s not clear yet, let’s go another step further and combine each group’s count and its key:

>>>[(len(list(group)),key) for key, group in groupby('AAAABBBCCDAABBB')]
[(4, 'A'), (3, 'B'), (2, 'C'), (1, 'D'), (2, 'A'), (3, 'B')]

As you can see, we know have tuples with the count of each group and the value that represents it. We can use the logic above to compute the Look-and-say sequence with Python!

I’ll use a recursive method that begins with the first element of the sequence, in this case 1, calculates the next element, and adds it as a string to a list called arr . This method repeats again, until the number of iterations is 0.

The answer final_sequence, with iterator = 15 , looks something like this:

And that’s it! This is a trivial game, but it demonstrates how powerful groupby method is.