This thread goes over a possible Python implementation for the look-and-say sequence.
The Python 🐍 problem-solving bootcamp is starting soon. Join the second cohort now!
I challenged you with this sequence earlier.
Now I'll explain the answer.
I will also show you a nice Python 🐍 implementation for this sequence.
Here we go 🚀
First, how does the sequence work?
This sequence is called the look-and-say sequence.
Because the next term is created by looking at the previous one and saying what you are seeing.
We start with
1. What do you see?
You see “one 1” → 11.
Now you have
11. What do you see?
You see “two 1s” → 21.
Now you have
21. What do you see?
You see “one 2 and one 1” → 1211.
Keep doing this until you reach
312211. What do you see?
You see “one 3, one 1, two 2s, and two 1s” → 13112221.
Thus, the next term in the sequence would be 13112221.
Trivia fact: all terms in this sequence have even length!
(Well, except the starting
Another cute fact:
As the sequence grows, the lengths of the terms tends to increase by ~30% each time.
What does this mean?
Say you walk along the sequence and find a term with length 1000.
Then, the next term will have length ~1300!
Isn't it insane that this is a sequence described by words AND maths can prove this fact?
I wrote about it in a TIL article of mine 👇
But hey, let's jump straight into the implementation.
The key here is understanding that we want to look at groups of consecutive equal digits, right?
That's how we go from 111221 to 312211 to 13112221.
111 | 22 | 1 31 22 11 ↓ 3 | 1 | 22 | 11 13 11 22 21
How can we do this in Python?
This grouping functionality is perfect for one tool from the
groupby returns consecutive keys and groups from an iterable.
The keys are the unique elements and the groups are the runs of unique elements.
Here are some examples to show how
Notice how the keys are the unique consecutive elements.
If we don't convert groups to lists first, we can't get the length of the group.
So, do you see where this is going? 👇
>>> from itertools import groupby # The keys are the unique elements: >>> [k for k, _ in groupby("AAABAADDDCC")] ['A', 'B', 'A', 'D', 'C'] # The groups are iterables with the consecutive elements: >>> [list(g) for _, g in groupby("AAABAADDDCC")] [['A', 'A', 'A'], ['B'], ['A', 'A'], ['D', 'D', 'D'], ['C', 'C']] # We can compute the length of a group: >>> [len(list(g)) for _, g in groupby("AAABAADDDCC")] [3, 1, 2, 3, 2] # We can pair keys and length of groups to count elements: >>> [(len(list(g)), k) for k, g in groupby("AAABAADDDCC")] [(3, 'A'), (1, 'B'), (2, 'A'), (3, 'D'), (2, 'C')]
By using a similar structure as the last line of code, we can get pretty far with our look-and-say implementation 👇
>>> def look_and_say(digits): ... return [(len(list(g)), k) for k, g in groupby(digits)] ... >>> look_and_say([1, 1, 1, 2, 2, 1]) [(3, 1), (2, 2), (1, 1)]
However, the result isn't a flat list of digits... It's a list of tuples.
How can we flatten this?
itertools to the rescue again!
One of the best ways to flatten a list of lists is with
>>> from itertools import chain >>> list(chain.from_iterable( ... [(3, 'A'), (1, 'B'), (2, 'A'), (3, 'D'), (2, 'C')] ... )) [3, 'A', 1, 'B', 2, 'A', 3, 'D', 2, 'C']
So, by putting together
groupby, we have ourselves an implementation!
Bonus Q: what if you wanted your function to accept an integer and return an integer?
look_and_say(111221) → 312211.
Can you modify the function below to handle that case?
>>> from itertools import chain, groupby >>> def look_and_say(digits): ... return list(chain.from_iterable( ... (len(list(g)), k) for k, g in groupby(digits) ... )) ... >>> look_and_say([1, 1, 1, 2, 2, 1]) [3, 1, 2, 2, 1, 1]
I hope you learnt something from this thread!
Follow me @mathsppblog for more educational threads like this 😄
Also, FYI, you can read this thread – and all my other threads – on my blog:
itertoolshas a tool
groupbythat groups consecutive elements in an iterable; and
itertoolshas a tool
chainthat you can use to flatten a list of lists.
from itertools import chain, groupby def look_and_say(digits): return list(chain.from_iterable( (len(list(g)), k) for k, g in groupby(digits) ))
If you want to read more about the look-and-say sequence, you can go through this article.
I write about Python every week. Join +16.000 others who are taking their Python 🐍 skills to the next level 🚀, one email at a time.