4
\$\begingroup\$

This is my first rough attempt at creating a function to return the nth number within the look-and-say sequence. I'm pretty sure there are some ways to simplify it, even given my current approach. Also, I feel kind of guilty that the first number is hard-coded.

def look_and_say(iterations):
    if iterations == 0:
        return 1
    seq = '11'
    for _ in range(iterations-1):
        new_seq = ''
        num = ''
        count = int
        for i in range(len(seq)):
            if seq[i] != num:
                if i != 0:
                    new_seq += str(count) + num
                num = seq[i]
                count = 1
            else:
                count += 1
            if i == len(seq)-1:
                new_seq += str(count) + num
        seq = new_seq
    return int(seq)
\$\endgroup\$
1
  • 4
    \$\begingroup\$ Add some description of what "look and say" means. For a specific input, what is the expected output. \$\endgroup\$
    – toolic
    Feb 12 at 20:58

6 Answers 6

6
\$\begingroup\$

There are some problems with your code.

feeling guilty

Hard coding an initial value is perfectly ok. However I do not agree it is the 'first' value. I consider it the second one. If we initialize seqlike

seq = '1'

we also get rid of the ugly loop counter and get a nicer one

for _ in range(iterations):

Still, we have the value coded twice, once in

return 1

once in the new line

seq = '1'

How to fix? E. g.

call your function recursively

seq = str(look_and_say(0))

or, the other way round

return int(seq)

Oh wait, the latter looks familiar, it is the final return line. So, do we need the if clause at all? No. The for loop safely incorporates the "no runs at all" case. So we start our function like

def look_and_say(iterations):
    seq = '1'
    for _ in range(iterations):

Note: The if clause is required if you go for recursion instead of the outer loop.

Loop like a pro

for i in range(len(seq)):
    if seq[i] != num:

is considered (exceptionally) bad style.

In Python we loop like

for elem in seq:
    if elem != num:

and avoid accessing elements via index.

If the index is required as well (like in your case) we loop like

for i, e in enumerate(seq):
    if e != num:
        if i != 0:

Even if you need the index only you may loop like

for i, _ in enumerate(seq):
    if i != 0:

Inner loop

The body has a high complexity as there are 4 cases to be handled. The regular cases within a string "char change" and "char equality" and the special cases "loop break in" handling initialisation and "loop break out" handling tear down (reporting). This pattern is very common in e. g. loops working on a stream in a receive callback.

In your case such a state machine changing state is hard to read. You should go for algorithmic (and testable) steps, even if this requires you to loop multiple times.

Still, if you stick to your loop like that, Python offers the else clause on a for loop, which is executed finally after a regularly exhausted loop.

for i in range(len(seq)):
    # ...
    if i == len(seq)-1:
        new_seq += str(count) + num

may read

for i in range(len(seq)):
    # ...
else:
    new_seq += str(count) + num

We also can eliminate the index i completely as we use num or count to check if num is holding a digit. The code looks now like

def look_and_say(iterations):
    seq = '1'
    for _ in range(iterations):
        new_seq = ''
        num = ''
        count = 0
        for e in seq:
            if e != num:
                if count:
                    new_seq += str(count) + num
                num = e
                count = 1
            else:
                count += 1
        else:
            new_seq += str(count) + num
        seq = new_seq
    return int(seq)

Inner loop II

The reason for the complexity of the inner loop is that it is a superposition of two loops, the outer one looping over sequences of equal characters changing e. g. num, the inner one counting the equal characters changing count. You could make nested loops instead with the help of a generator. In our example we can eliminate the inner one with library functions. The string representation of seq allows us to consume equal character sequences with lstrip()

def look_and_say(iterations):
    seq = '1'
    for _ in range(iterations):
        new_seq = ''
        while seq:
            num = seq[0]
            remain = seq.lstrip(num)
            count = len(seq) - len(remain)
            new_seq += str(count) + num
            seq = remain
        seq = new_seq
    return int(seq)

num and count are now helper variables not needing 'global' initialisation.

itertools

Get familiar with this great library. It offers highly efficient solutions for many iteration problems. From the documentation you can learn many iteration patterns. Your problem is solved by groupby(). But remember, itertools work with iterators, they may be consumed only once.

from itertools import groupby

def look_and_say(iterations):
    seq = '1'
    for _ in range(iterations):
        lst = [str(len(list(v))) + k for k, v in groupby(seq)]
        seq = "".join(lst)
    return seq
\$\endgroup\$
3
  • \$\begingroup\$ Is the groupby solution also highly efficient, or did you just mean that about itertools in general? I'm wondering since the groups are very small. \$\endgroup\$ Feb 17 at 14:59
  • \$\begingroup\$ The "Inner loop II" section is a bit amusing, it's about reducing complexity but increases complexity. Ok, a different kind of complexity. Reducing code complexity, and increasing time complexity to forced quadratic time. \$\endgroup\$ Feb 17 at 22:57
  • \$\begingroup\$ @Kelly itertools - in general. complexity - in terms of coding. I consider neither memory footprint nor algorithmic complexity a problem here. \$\endgroup\$
    – stefan
    Feb 21 at 22:39
7
\$\begingroup\$

Naming

The iterations argument is not a great name.

The purpose of the function is to return the n-th element of the sequence, and whether this element is obtained by iterating, or not, is an implementation detail.

Therefore, the argument is best named n.

Typing

It is useful to the reader to make explicit the types of the arguments and return value of your functions.

In your case:

def look_and_say(n: int) -> int:
    pass

Documentation

It is useful to the reader to document what the function is doing. This is generally done using docstrings for a brief explanation.

def look_and_say(n: int) -> int:
    """Returns the `n`th element of the look-and-say sequence starting at `seed`.

    For background information see: https://en.wikipedia.org/wiki/Look-and-say_sequence."""

    pass

Testing

You should use unit-tests to verify that basic properties hold, as well as to verify edge cases. This can require some setup.

A quick way to get at least a few tests is to use doctests:

def look_and_say(n: int) -> int:
    """Returns the `n`th element of the look-and-say sequence starting at `seed`.

    For background information see: https://en.wikipedia.org/wiki/Look-and-say_sequence.

    >>> look_and_say(4)
    312211
    """

    pass

It's particular nice because it also showcases how to use the function to the reader.

Hardcoded seed

If you do not want to hardcode the seed, a good option is to accept the seed as an optional parameter, with a default value:

  • Users who wish to use the default seed do not have to specify it.
  • Users who wish for a different seed may specify it.

It's all upsides.

Break it down!

I would argue that your function does a bit too much, which in turns may make it harder to test.

Suppose that in the process of testing you realize there's a bug because the output doesn't match the expected number... but where? Is the bug because you're not splitting the string into the appropriate runs? Or not catenating the new string properly? Forgetting a part in some cases?

By breaking down the functionality into elementary pieces, you can test each elementary piece in isolation, ensuring it works as expected, and then assemble all the pieces together.

Generators

Whenever you think of "sequence" in Python, you should think of generators. Generators are the Pythonic way of lazily generating a sequence of elements, one at a time.

The first task, thus, should be about creating a generator, which will generate the sequence of elements for us.

In this specific case, we can sketch our generator like so:

def generate_look_and_say(seed: int) -> Iterator[int]:
    """Returns an iterator of the look-and-say sequence starting with `seed`.

    For background information see: https://en.wikipedia.org/wiki/Look-and-say_sequence.

    >>> generator = generate_look_and_say(11)
    >>> [next(generator) for _ in range(5)]
    [11, 21, 1211, 111221, 312211]
    """

    #   Manipulate the elements as strings, as it's easier.
    element = str(seed)

    while True:
        yield int(element)

        element = compute_next_look_and_say(element)

With this structure in place, we just need to define the function to actually compute the new element:

def compute_next_look_and_say(element: str) -> str:
    """Computes the next element of the look-and-say sequence after `element`.

    >>> compute_next_look_and_say('111221')
    '312211'
    """

    return ''.join(f'{len(r)}{r[0]}' for r in generate_runs(element))


def generate_runs(element: str) -> Iterator[str]:
    """Returns an iterator of the runs of equal characters in `element`.
    
    >>> list(generate_runs('312211'))
    ['3', '1', '22', '11']
    """

    assert len(element) > 0

    start = 0

    while start < len(element):
        end = start + 1

        while end < len(element) and element[end] == element[start]:
            end += 1

        yield element[start:end]

        start = end    

Note that no attempt at optimizing this code was performed. I do hope it's Pythonic.

Using the generator

From then on, it's a simple matter of using the generator to provide the answer:

def look_and_say(n: int, seed: int = 11) -> int:
    """Returns the `n`th element of the look-and-say sequence starting at `seed`.

    This is but a convenience function over the iterator returned by `generate_look_and_say`, if you wish to obtain multiple elements of the sequence, using the iterator directly is more efficient.

    For background information see: https://en.wikipedia.org/wiki/Look-and-say_sequence.

    >>> look_and_say(4)
    312211
    """

    for i, element in enumerate(generate_look_and_say(seed)):
        if i == n:
            return element
\$\endgroup\$
4
  • \$\begingroup\$ Tiny suggestions, not sure if better: "Returns an iterator" (instead of "iterable") and "Pythonic" (instead of "pythonic", see the glossary). \$\endgroup\$ Feb 17 at 23:00
  • \$\begingroup\$ Potentially interesting: Using generators not just internally, but also making that the return type. Could lead to very low memory usage. The sequence grows exponentially, so you'd need relatively very few stacked generators. \$\endgroup\$ Feb 17 at 23:05
  • \$\begingroup\$ @KellyBundy: Thanks for the "spelling" suggestions. Am I right that you suggest returning a generator of the sequence element, instead of an int? If so, I'm not quite sure how you'd go about that, and I'd love to see it if you posted such an answer. \$\endgroup\$ Feb 18 at 11:55
  • 1
    \$\begingroup\$ Yes, generating one digit at a time. Posted. \$\endgroup\$ Feb 18 at 16:06
5
\$\begingroup\$

I agree with the documentation and testing comments of another answer.

Additionally, there are a few points worth considering.

This statement is not obvious to me:

    count = int

Since the for loop increments count, I assume you intended to initialize count to 0. The statement is more simply written as:

    count = 0

Since count is guaranteed to be initialized to 1 inside the for i loop before it is incremented, there is no need to initialize it to 0 at all.

It is not clear to me why you return an int for seq. Your function operates on it as a string throughout, and it seems natural to return a string.

You call len(seq) in two places, one of which is called every time through the for loop. You could set it to a variable, then use the variable:

    seq_len = len(seq)

Here is the code with the changes:

def look_and_say(iterations):
    if iterations == 0:
        return '1'
    seq = '11'
    for _ in range(iterations-1):
        new_seq = ''
        num = ''
        seq_len = len(seq)
        for i in range(seq_len):
            if seq[i] != num:
                if i != 0:
                    new_seq += str(count) + num
                num = seq[i]
                count = 1
            else:
                count += 1
            if i == seq_len-1:
                new_seq += str(count) + num
        seq = new_seq
    return seq
\$\endgroup\$
0
2
\$\begingroup\$

signature annotations

def look_and_say(iterations):

Here, let me help you out with that:

def look_and_say(iterations: int) -> int:

Tell us the meaning of "iterations". Offering a negative number of iterations will affect the function's output, but it isn't clear whether that will produce the intended effect.

reference

Cite your reference. If there is some TI speak-n-spell game you're trying to emulate, or some LeetCode puzzle you're trying to solve, tell us about it. Put a one-line URL citation comment in the source code.

type stability

        count = int
        ...
                count += 1

This marks the point where I just gave up on the Author being at all sympathetic to the Gentle Reader. If the intent was for that increment to trigger a TypeError, then None would have been the idiomatic way to express it. Setting a variable to a callable is very different from setting it to a particular integer value. As things stand the first line looks a lot like the idiom of

        sentinel = object()

except that there's no motivation for the assignment. It's quite different from count = int(). In short, it's not clear what that initialization hoped to accomplish, and we have no docstring or comments to guide us through the wilderness.

It's axiomatic that code submitted for review has already been verified to Do The Right Thing. A given Author can choose to explain why that is, or can choose to pose an intricate puzzle with concealed solution. Puzzling code doesn't get merged down to main.

docstring

There isn't any. And that is a big problem: Author's Intent is entirely obscure. Why would I call this library routine? What should I expect from it? How would I know if the answer is correct?

There is no written specification for this code. Absent a spec, we cannot declare a bug exists (beyond "it stack traced!").

There is simply no way to know if this produced the right result.

This code appears to be OT, in the sense that we don't know it correctly implements a function.


automated tests

There aren't any.

Author passed up the opportunity to educate future maintenance engineers about the functionality that was intended.


It is unclear whether this code achieves certain unspecified design goals.

I would not be willing to delegate or accept maintenance tasks on it.

\$\endgroup\$
2
\$\begingroup\$

(Rethinking the task, inspired by Matthieu M.'s answer.)

The sequence grows fast. Exponentially, with growth factor ~1.3 (see the Wikipedia article). For look_and_say(50) it's already ~1.2 million digits, and you take over 2 MB of memory as measured like this:

import tracemalloc as tm
import sys
sys.set_int_max_str_digits(0)
tm.start()
look_and_say(50)
print(tm.get_traced_memory()[1])
tm.stop()

For look_and_say(80) it's over 3 billion digits. What if you don't have enough memory for that?

For look_and_say(100) it's over 600 trillion digits, and you certainly don't have enough memory. Granted, it would also take a lot of time, but what if you for example only want to print the first 1000 digits?

You can easily do that if you make your function instead return an iterator that lazily computes and yields one digit at a time:

from itertools import groupby

def lazy_look_and_say(n):
    if n == 0:
        yield 1
        return
    for digit, occurrences in groupby(lazy_look_and_say(n - 1)):
        yield len(list(occurrences))
        yield digit

If you call lazy_look_and_say(50), you get an iterator for that sequence. Nothing is getting computed yet. Only when you iterate through it, asking it for its digits, does it go to work. It in turn creates an iterator lazy_look_and_say(49) for itself, whose digits it lazily analyzes to compute and yield its own digits. That lower iterator in turn creates one for n=48, and so on all the way down to n=0, where it instead only yields the single digit 1. So that's a stack of 51 iterators, all waiting to be asked for their next digit.

It takes only 26 KB to go through lazy_look_and_say(50) (doing nothing with the digits here, in reality you print them or count the frequency of each different digit or whatever else you're interested in):

tm.start()
for _ in lazy_look_and_say(50):
    pass
print(tm.get_traced_memory()[1])
tm.stop()

Even going through the first 1000 digits of lazy_look_and_say(100) only takes 46 KB:

from itertools import islice
tm.start()
for _ in islice(lazy_look_and_say(100), 1000):
    pass
print(tm.get_traced_memory()[1])
tm.stop()

Note that memory usage isn't small because we only go through 1000 digits. That is irrelevant. It also only takes 46 KB to go through the first million digits (I tested it) or through all ~600 trillion digits (not tested, but I'm confident :-). The memory usage is small because we only have 101 iterators, each using a small constant amount of memory. For lazy_look_and_say(1000) it's 1001 iterators and we need about 400 KB. About 400 bytes per iterator.

And speed? How long does it take to get the first 100 digits of lazy_look_and_say(1000), which has over 10115 digits? About 2 milliseconds. Here they are:

1113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213

The first million digits take about 1 second, and the first ten million take about 10 seconds. It doesn't get slower, produces about a million digits every second.

Script with all measurements (Attempt This Online!):

import tracemalloc as tm
from itertools import groupby, islice
from time import perf_counter as time
import sys

# Disable the conversion limit and allow deeper recursion
sys.set_int_max_str_digits(0)
sys.setrecursionlimit(9999)


# The question's original, but not converting the result string to int
def look_and_say(iterations):
    if iterations == 0:
        return '1'
    seq = '11'
    for _ in range(iterations-1):
        new_seq = ''
        num = ''
        count = int
        for i in range(len(seq)):
            if seq[i] != num:
                if i != 0:
                    new_seq += str(count) + num
                num = seq[i]
                count = 1
            else:
                count += 1
            if i == len(seq)-1:
                new_seq += str(count) + num
        seq = new_seq
    return seq


# Estimate the number of digits of look_and_say(100)
print(len(look_and_say(50)) * 1.303577269034**50)


# Memory usage of look_and_say(50)
tm.start()
look_and_say(50)
print(tm.get_traced_memory()[1])
tm.stop()


# The iterator solution
def lazy_look_and_say(n):
    if n == 0:
        yield 1
        return
    for digit, occurrences in groupby(lazy_look_and_say(n - 1)):
        yield len(list(occurrences))
        yield digit


# Memory usage for lazy_look_and_say(50)
tm.start()
for _ in lazy_look_and_say(50):
    pass
print(tm.get_traced_memory()[1])
tm.stop()


# Memory usage for lazy_look_and_say(1000)
tm.start()
for _ in islice(lazy_look_and_say(1000), 1000):
    pass
print(tm.get_traced_memory()[1])
tm.stop()


# Time for the first 100 digits of lazy_look_and_say(1000)
t0 = time()
digits = list(islice(lazy_look_and_say(1000), 100))
print((time() - t0) * 1e3, 'milliseconds')

# Those 100 digits
print(*digits, sep='')
\$\endgroup\$
3
  • \$\begingroup\$ This is beautiful! \$\endgroup\$ Feb 18 at 16:19
  • \$\begingroup\$ I do think "occurrances" should be "occurrences", unless there's a regional dialect I'm not aware of -- which not being a native speaker could very well be. \$\endgroup\$ Feb 18 at 16:19
  • \$\begingroup\$ @MatthieuM. Thanks, fixed (not a native speaker, either). \$\endgroup\$ Feb 18 at 16:24
1
\$\begingroup\$

I'd just return your string instead, not convert it to int at the end. Because, really, what are you going to do with it? Most likely you're just going to print it, not use it as a number. In which case you have your conversion from string to int in your function and then a conversion back to string for the printing. These conversions from/to base 10 are inefficient and CPython even limits that so by default I can't even do look_and_say(29), I get an error because it's more than 4300 digits.

Your seq is a string of digits. I suggest making it a list instead, with digits as ints. Advantages:

  • It's somewhat simpler, as you then only operate on ints instead of a mix of ints and characters.
  • It avoids potential quadratic complexity of repeated string extensions.
  • It allows to modify the latest appended count, so you don't need extra variables for the current run and delay its appending until it's over. Which simplifies things. My new is always the complete new sequence for all digits processed so far.

So here's my version:

def look_and_say(n):
    seq = [1]
    for _ in range(n):
        new = []
        for digit in seq:
            if not new or digit != new[-1]:
                new += 1, digit
            else:
                new[-2] += 1
        seq = new
    return ''.join(map(str, seq))

Speed comparison with n=50 (after disabling the limit, as the result has ~1.2 million digits) in CPython 3.11.4 (Attempt This Online!):

9.31 seconds  yours
1.16 seconds  yours_returning_string
0.73 seconds  mine
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.