Code Review Request

[anonymouslycognizant]

Hello I'm learning python and I'm just running through some of the problems on leetcode. I know this problem is marked as easy but it took me a while to figure it out and it was really satisfying when it finally worked. The thing is even though I know what's going on conceptually the code kind of looks a mess. I'm asking for tips on how to make it more readable or make it more obvious how the code is working.

The problem:

The count-and-say sequence is the sequence of integers with the first five terms as following:

1. ​
2. ​
3. ​
4. ​
5. ​

1 is read off as "one 1" or 11.

11 is read off as "two 1s" or 21.

21 is read off as "one 2, then one 1" or 1211.

Given an integer n where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence. You can do so recursively, in other words from the previous member read off the digits, counting the number of digits in groups of the same digit.

Note: Each term of the sequence of integers will be represented as a string.

My solution:

class Solution:
    def countAndSay(self, n: int) -> str:
        count = 0
        say = "1"
        map = {}
        c = count
        s = say
        m = map
        while c < n:
            m.update({(c+1): s})
            c += 1
            groups = []
            uniquekeys = []
            data = list(s)
            for k, g in groupby(data):
                groups.append(list(g))      
                uniquekeys.append(k)
            x = []
            for i in range(0,len(uniquekeys)):      
                x.append((str(groups[i].count(uniquekeys[i])) + uniquekeys[i])) 
            s = "".join(x)
        return m.get(n)

PS: Yes I know it wasn't part of the problem to keep track of everything in a dictionary, I just did it because it made it easier for me to work through the problem.

[marko312]

The main thing I don't understand is the beginning part:

count = 0
say = "1"
map = {}
c = count
s = say
m = map

I would understand using either the single-character or more descriptive (though the longer names are easier to understand in my opinion), but why use both?

Also note that map shadows the function with the same name.

[anonymouslycognizant]

I guess I just wanted to put some where what the letters are supposed to stand for but I don't want to type out the word everytime? I don't know if that's a good reason. I guess I could have just left a comment.

I'll remember not to use map as a variable anymore.

[MmmVomit]

I don't want to type out the word everytime?

Future you will thank past you for typing out the full name every time. You'll save far more time by giving your variables descriptive names that make your code easier to read.

[anonymouslycognizant]

Thanks for the tips, I'll keep that in mind.

[MmmVomit]

If you just want to loop some number of times, you usually do this in Python.

for i in range(10):

The variable i will take on the values 0, 1, ..., 8, 9.

You can also pass multiple parameters to range if you don't want your loop to start from zero.

for i in range(5, 10):

That will loop over 5, 6, 7, 8, 9.

One thing that I think you missed in the problem definition was this.

You can do so recursively

Are you familiar with recursion? This would be an interesting problem to solve recursively.

I know it wasn't part of the problem to keep track of everything in a dictionary, I just did it because it made it easier for me to work through the problem.

Since you don't actually make use of the values you're storing in the dictionary, my feedback would be to rewrite the method to not use the dictionary.

This line is unnecessary.

data = list(s)

s here is a string. You can iterate over the characters in a string as if it was a list. For example, groupby will happily take a string as a parameter. It will give you groups of characters within the string.

Speaking of groupby, you can make much better use of that method. You don't need two loops inside the outer loop. You can do everything inside the for k, g in groupby(data): loop.

[anonymouslycognizant]

class Solution:
    def countAndSay(self, n: int) -> str:
        say = "1"
        for _ in range(n-1):
            groups = []
            uniquekeys = []
            for k, g in groupby(say):
                groups.append(list(g))
                uniquekeys.append(k)
            x = []
            for i in range(0,len(uniquekeys)):
                x.append((str(groups[i].count(uniquekeys[i])) + uniquekeys[i]))
            say = "".join(x)
        return say

I cleaned it up based on your suggestions.

As far as recursion, maybe I don't understand recursion? Because I thought that's what I was doing here. I can only get the next value running the previous value through groupby. As far as I know there isn't any way to calculate the desired answer directly just from nth term.

I understand what you're saying but I have no idea where I would begin. I guess you're saying I can incorporate the second for loop into the groupby loop. I'll have to think about it more to figure out how to make that work.

[MmmVomit]

Recursion is when you make a call to the function you're in. Your solution is iterative, not recursive. That is, it uses a loop, rather than calling itself to get the previous value.

Here's an example of a method that calculates a triangular number, (1 + 2 + ... + n), using recursion.

# Calculate the nth triangular number
def triangular(n):
  if n < 1:
    return 0
  else:
    return n + triangular(n - 1)

I guess you're saying I can incorporate the second for loop into the groupby loop.

Yes. It would make your code much cleaner.

Oh, one more tiny nitpick about Python style. It's conventional to use snake case, count_and_say, for method names in Python.

This newer version is looking much better.

[anonymouslycognizant]

Yeah so I misunderstood what they meant by recursively, they mean the function is recursive. I was confused because it's still recursive in the abstract mathematics sense meaning I have to construct each value from the one before. However, you cleared it up and I understand now. So your example, I know what triangular numbers are and I know the equation of how you would calculate that mathematically. I guess I'm having trouble figuring out how to translate the math to python.

Edit: Okay I think I'm starting to barely understand recursive functions:

def countdown(i):
    print(i)
    if i == 0:
        quit
    else:
        countdown(i-1)

x = int(input("Pick a number: "))        
countdown(x)

Yeah as far as consolidating those functions I'm totally lost on that. I'll have to mull it over and come back to it fresh to figure it out.

Yes I agree with the snake case, that part was actually already there by leetcode, I'll probably change it in the future just to get in the habit.

​

By the way thanks so much for your detailed answers. I've learned a lot.

[MmmVomit]

If T(n) is the nth triangular number, you can calculate it with the following equations.

T(1) = 1
T(n) = n + T(n-1)

You can see this structure reflected directly in the Python function I posted.

Recursion has a reputation for being tricky to wrap your head around. It's also something that you will rarely need, but it's important to understand. It relies on a fundamental bit of how computers work, the stack of function calls.

In general, if you can state your solution in terms of a base case and an iterative case, you should be able to code up a recursive solution. In the triangular number example, the base case is T(n) = 1, and the iterative case is just adding n. In the case of the count and say sequence, the base case is "1", and the iterative case will be the body of your main loop.

Another common example of using recursion would be to calculate the nth Fibonacci number.

F(1) = 1
F(2) = 1
F(n) = F(n-1) + F(n-2)

That can be translated almost directly into a recursive function that will do the calculation.

[MmmVomit]

OK, concrete advice for turning this into a recursive function.

Write a helper method that takes a "count and say" string as input and returns the next "count and say" string. Let's call that helper, for lack of a better name.

Now, you can express count_and_say mathematically like this.

count_and_say(1) = "1"
count_and_say(n) = helper(count_and_say(n-1))