25
\$\begingroup\$

I've written code that solves a problem from codewars.com. My code passes all the tests on the codewars site. It's a simple enough problem to solve naïvely, but I would love to improve the structure.

The prompt for the problem is as follows:

Write a function, persistence, that takes in a positive parameter num and returns its multiplicative persistence, which is the number of times you must multiply the digits in num until you reach a single digit.

For example:

persistence(39) => 3  # Because 3*9 = 27, 2*7 = 14, 1*4=4
                      # and 4 has only one digit.

So my solution follows:

def get_digits(num, digits=[]):
    while num > 0:
        digits.append(num % 10)
        return get_digits(num / 10, digits)
    if num == 0:
        return digits


def multiply_all(digits, multiplier=1):
    while len(digits) > 0:
        multiplier = multiplier * digits.pop(0)
        return multiply_all(digits, multiplier)
    if len(digits) == 0:
        return multiplier


def persistence(num, count=0):
    while num >= 10:
        num = multiply_all(get_digits(num))
        count += 1
        return persistence(num, count)
    if num < 10:
        return count

I was thinking I might consolidate these three little recursive functions into one function containing all three... but I'd really like input from more seasoned programmers, so I very much appreciate you taking the time to make any suggestions.

\$\endgroup\$
  • \$\begingroup\$ I'm not as familiar with Python; is count an optional parameter? Can whatever calls your code still use persistence(39)? \$\endgroup\$ – Brian J Mar 3 '17 at 14:15
  • 2
    \$\begingroup\$ @BrianJ count=0 means it's optional with a default of 0 \$\endgroup\$ – JollyJoker Mar 3 '17 at 15:00
18
\$\begingroup\$

Python 3.x bug

Did you know that your program outputs 1 for the number 39 if executed on Python 3?

This is because of the / division operator on this line:

return get_digits(num / 10, digits)

The meaning of / in Python 3.x was changed (PEP 238). Switching to // would be a quick fix.


Improving the solution

I was thinking I might consolidate these three little recursive functions into one function containing all three..

What if we would get all the digits of a number by iterating over the string representation of an integer and converting every digit back to an integer - map(int, str(num)). In order to multiple the digits of a number we can use reduce() applying the operator.mul (multiplication operator) function:

from functools import reduce
from operator import mul


def persistence(number, count=0):
    # recursion base case - exit once the number is less than 10
    if number < 10:
        return count

    # get new number by multiplying digits of a number
    new_number = reduce(mul, map(int, str(number)))

    return persistence(new_number, count + 1)

Note that you don't actually need the while loop at all, since you are going recursive and have a num < 10 base case as a recursion "exit condition".


Note that you can also approach the "getting digits of a number" "mathematically" instead of converting the types back and forth:

from functools import reduce
from operator import mul


def get_digits(number):
    """Generates digits of a number."""
    while number:
        digit = number % 10

        yield digit

        # remove last digit from number (as integer)
        number //= 10


def persistence(number, count=0):
    if number < 10:
        return count

    # get new number by multiplying digits of a number
    new_number = reduce(mul, get_digits(number))

    return persistence(new_number, count + 1)

This would also be generally faster than the first version.

\$\endgroup\$
  • \$\begingroup\$ That's an interesting way to do it! I guess I've been avoiding taking advantage of the properties of strings when it comes to numbers. Do I have a false impression of it being taboo? Your solution is definitely very neat, though. I like that. And yes... I wrote this in Python 2.7, and wasn't thinking much about 3 at the time. I need to get in a better habit of writing cross-compatible code. And I have no idea how I missed that about the while loop. That's very true. Thank you for your help! \$\endgroup\$ – Caitlin Quintero Weaver Mar 3 '17 at 4:48
  • \$\begingroup\$ @CaitlinQuinteroWeaver yes, this part is a bit arguable - there is that "mathematical" way of getting the digits of a number - updated the answer with this solution applied. Thanks. \$\endgroup\$ – alecxe Mar 3 '17 at 5:00
  • \$\begingroup\$ I'd argue that the while loop is actually better in this scenario than the recursive solution. Also, converting strings to integers is a time intensive process. Definitely use the mathematical way for retrieving digits. \$\endgroup\$ – pzp Mar 3 '17 at 5:18
  • \$\begingroup\$ @pzp repl.it disagrees: they are about the same. \$\endgroup\$ – TemporalWolf Mar 3 '17 at 5:37
  • \$\begingroup\$ @TemporalWolf On my computer, testing both in iPython with numbers in the range 10e6 to 10e9, the mathematical solution is at least 10 times faster. \$\endgroup\$ – pzp Mar 3 '17 at 5:43
10
\$\begingroup\$

What you had was generally very good. I have just a couple of notes.

The default argument in get_digits probably does not do what you expect it to do. That one list will be shared across all calls to the get_digits function. As an example, try calling get_digits(12) followed by get_digits(7). The output? [2, 1, 7]. A quick fix to this is to set the default value to None and then conditionally initialize the digits to the empty list if digits is None.

For efficiency reasons, you probably want to avoid creating a new list every time get_digits is called. I recommend that you instead make get_digits a generator function by using the yield keyword. (I also gave it an optional arbitrary base argument just for fun.)

Finally, make all of the functions iterative. It probably has better performance than the recursive solution, and is logically clearer to most people.

All in all...

from functools import reduce
from operator import mul


def get_digits(num, base=10):
    while num > 0:
        yield num % base
        num /= base


def product(it):
    return reduce(mul, it, 1)


def persistence(num):
    count = 0
    while num > 9:
        num = product(get_digits(num))
        count += 1
    return count
\$\endgroup\$
10
\$\begingroup\$
  • I'd suggest you stay away from recursion in Python. Python has a maximum recursion depth, with a default of about 1000. This is to prevent system problems when using recursion, and the fixes of using sys.setrecursionlimit are workarounds, and don't actually fix the problem. Instead to remove these headaches don't use recursion.

  • Don't pass mutable datatypes as default arguments, this is as if you call get_digits twice, then it'll output both numbers. Take:

    >>> get_digits(12345)
    [5, 4, 3, 2, 1]
    >>> get_digits(12345)
    [5, 4, 3, 2, 1, 5, 4, 3, 2, 1]
    
  • If you need to pop data try to use list.pop() over list.pop(0). This is as the former only has to remove one item, but the latter has to remove the first item in the list, and move all the items down to take it's place. This question talks about these performance problems relative to deque.popleft. However here you don't need a deque, or to reverse the array in this case.

    The following is an equivalent of list.pop:

    def pop(list, index=None):
        end = len(list) - 1
        if index is None:
            index = end
        result = list[index]
        for i in range(index, end):
            list[i] = list[i + 1]
        del list[end]
        return result
    

However there are a couple of non-major changes you can make:

  • If you stay with using recursion, don't use while as a replacement for if.
  • If you remove the recursion, there's no need to have your ifs in your functions.
  • rather than doing both a % b and a // b you can instead use divmod.
  • Values in Python can implicitly be converted to booleans. An empty array is False where an array with at least one item is True. This also happens with ints, 0 is False where all other numbers are True.

And so changing the code to not suffer from the above problems can result in:

def get_digits(num):
    digits = []
    while num:
        num, digit = divmod(num, 10)
        digits.append(digit)
    return digits


def multiply_all(digits):
    multiplier = 1
    while digits:
        multiplier *= digits.pop()
    return multiplier


def persistence(num):
    count = 0
    while num >= 10:
        num = multiply_all(get_digits(num))
        count += 1
    return count
\$\endgroup\$
4
\$\begingroup\$

Without changing any of the other functions, passing count to the recursive function isn't the cleanest way to do recursion:

def persistence(number):
    if number < 10:
        return 0

    new_number = multiply_all(get_digits(number))
    return 1 + persistence(new_number)

or, shorter:

def persistence(number):
    return 0 if number < 10 else 1 + persistence(multiply_all(get_digits(number)))
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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