Look-and-say Sequence With Python | by Jose Carlos Borrayo | Mar, 2022

Photograph by Cyrus Lopes on Unsplash

Patterns… are all over the place and our species has advanced to acknowledge them. Final week I noticed an attention-grabbing publish on Twitter:

I’ve a problem for you! Here’s a sequence of numbers:
1–11–21–1211–111221–312211
Are you able to guess the subsequent quantity?

Normally, patterns or sequences are visible, however not this one. Simply by taking a look at it you’ll be able to inform there’s a development of numbers, however what’s the order?

This can be a tough one as a result of it’s a must to say it out loud to seek out the reply! To decipher the subsequent component one has to depend what number of occasions a digit exists within the given state of the sequence. Let’s see the way it goes:

  1. 1 — “One” one (which turns into the subsequent quantity within the collection).
  2. 11 — “Two” one
  3. 21 — “One” two, “one” one
  4. 1211 — “One” one, “one” two, “two” one
  5. 111221 — and so forth and so forth…

The numbers in quotations mark are the variety of occasions a quantity is current within the sequence.

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

Are you able to write a program that computes the subsequent time period of the sequence?

After a number of makes an attempt utilizing dictionaries, checklist comprehensions, and NumPy arrays I discovered the proper module to unravel this downside: itertools. The premise is that this: it’s essential to depend what number of occasions a quantity reveals up within the sequence earlier than the subsequent quantity. This may be accomplished utilizing thegroupby technique.

In keeping with the itertools documentation, groupby returns an iterator with a number of keys and teams from an iterable (checklist, tuple, dictionary). Let’s check out a itertools instance:

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

As you’ll be able to see, the keys are the letters every group is made from. When groupby finds a brand new letter distinct from the final one, it creates a brand new key. For instance, it returns two keys for ‘A’ and ‘B’ as a result of even when they’re the identical letters, these are separated by teams of different letters.

Now we’ll get the group. On this case, group is an iterable of grouped objects. Thus, we’ll unpack its parts as a listing.

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

The following step is to get the variety of objects for every group:

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

Are you able to see how we are able to accomplish the Look-and-say sequence utilizing groupby ? If it’s not clear but, let’s go one other step additional and mix every group’s depend 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’ll be able to see, we all know have tuples with the depend of every group and the worth that represents it. We are able to use the logic above to compute the Look-and-say sequence with Python!

I’ll use a recursive technique that begins with the primary component of the sequence, on this case 1, calculates the subsequent component, and provides it as a string to a listing known as arr . This technique repeats once more, till the variety of iterations is 0.

The reply final_sequence, with iterator = 15 , appears to be like one thing like this:

And that’s it! This can be a trivial recreation, but it surely demonstrates how highly effective groupby technique is.

More Posts