Next number with the same sum of digits

Question

I recently came across a email bot that would give you random problems to solve.

Here is the problem.

Please write a function in python which receives a natural decimal N-digit number (1 to 15 digits long) as an input and returns the minimal next N-digit number with the same sum of digits or -1 if there isn't one. Try not to use brute force.

Examples: Input: Output: *123 132 *0200 1001 *09999999999999 18999999999999 *90 -1 *9999 -1

I have written my solution and would like it to be reviewed. Could this be done better? Should testing be done in a different way?

test_generators.py

import pytest

from generators import NumberGenerator

@pytest.fixture
def max_number():
    return "12345678901234567890"

@pytest.fixture
def trailing_zero_none():
    return "1234"

@pytest.fixture
def trailing_zero_three():
    return "1234000"

@pytest.fixture
def trailing_zero_trick():
    return "12039000"

@pytest.fixture
def num_one():
    return "468992000"

@pytest.fixture
def num_one_step_one():
    return "468992"

@pytest.fixture
def num_one_step_two():
    return "46899"

@pytest.fixture
def num_one_step_three():
    return "468"

def test_next_number_construtor_str():
    NumberGenerator("10")

def test_next_number_construtor_int():
    with pytest.raises(TypeError):
        NumberGenerator(10)

def test_max_number_length(max_number):
    with pytest.raises(ValueError):
        NumberGenerator(max_number)

def test_find_trailing_zeros(trailing_zero_none):
    assert NumberGenerator(trailing_zero_none).get_trailing_zeros() == ""

def test_find_trailing_zeros_three(trailing_zero_three):
    assert NumberGenerator(trailing_zero_three).get_trailing_zeros() == "000"

def test_find_trailing_zeros_trick(trailing_zero_trick):
    assert NumberGenerator(trailing_zero_trick).get_trailing_zeros() == "000"

def test_get_lowest_non_zero_digit(trailing_zero_three):
    num = NumberGenerator(trailing_zero_three)
    num.get_trailing_zeros()
    assert num.get_lowest_non_zero_digit() == 4

def test_get_lowest_non_zero_digit(trailing_zero_trick):
    num = NumberGenerator(trailing_zero_trick)
    num.get_trailing_zeros()
    assert num.get_lowest_non_zero_digit() == 9

def test_get_consectutive_nines(trailing_zero_trick):
    num = NumberGenerator(trailing_zero_trick)
    num.get_trailing_zeros()
    num.get_lowest_non_zero_digit()
    assert num.get_consecutive_nines() == ""

def test_get_consectutive_nines():
    num = NumberGenerator("468992000")
    num.get_trailing_zeros()
    num.get_lowest_non_zero_digit()
    assert num.get_consecutive_nines() == "99"


def test_get_number_one(num_one, num_one_step_one):
    num = NumberGenerator(num_one)
    num.get_trailing_zeros()
    assert num.get_number() == int(num_one_step_one)

def test_get_number_two(num_one, num_one_step_two):
    num = NumberGenerator(num_one)
    num.get_trailing_zeros()
    num.get_lowest_non_zero_digit()
    assert num.get_number() == int(num_one_step_two)

def test_get_number_three(num_one, num_one_step_three):
    num = NumberGenerator(num_one)
    num.get_trailing_zeros()
    num.get_lowest_non_zero_digit()
    num.get_consecutive_nines()
    assert num.get_number() == int(num_one_step_three)


def test_next_number_one():
    assert NumberGenerator("123").get_next_number() == 132

def test_next_number_two():
    assert NumberGenerator("0200").get_next_number() == 1001

def test_next_number_three():
    assert NumberGenerator("09999999999999").get_next_number() == 18999999999999

def test_next_number_four():
    assert NumberGenerator("90").get_next_number() == -1

def test_next_number_five():
    assert NumberGenerator("9999").get_next_number() == -1

generators.py

import re

class NumberGenerator(object):

    def __rtrim_number__(self, index):
        self.__number = self.__number[:index]


    def __init__(self, number):
        if len(number) > 15:
            raise ValueError("Number cannot be larger than 15 digits")
        self.__number = number


    def get_trailing_zeros(self):
        result = re.search("(0+)\\b", self.__number)
        if result:
           self.__rtrim_number__(result.start(1))
           return result.group(1)
        else:
            return ""


    def get_lowest_non_zero_digit(self):
        digit = self.__number[-1]
        self.__rtrim_number__(-1)
        return int(digit)


    def get_consecutive_nines(self):
        result = re.search("(9+)\\b", self.__number)
        if result:
            self.__rtrim_number__(result.start(1))
            return result.group(1)
        else:
            return ""


    def get_number(self):
        if len(self.__number) > 0:
            return int(self.__number)
        else:
            return -1


    def get_next_number(self):
        zeros = self.get_trailing_zeros()
        lowest_digit = self.get_lowest_non_zero_digit()
        nines = self.get_consecutive_nines()
        base_digit = self.get_number()

        if base_digit >= 0:
            digit_str = "{0}{1}{2}{3}".format(base_digit+1, zeros, lowest_digit-1, nines)
            return int(digit_str)
        else:
            return base_digit

Answer 1

Excellent that you did this exercise with unit-testing.

I would like to take the chance to give some feedback on your unit-tests, in the hope that you find some of these hints useful.

First, you have created individual test functions for individual tests - that is a good practice! And, you are introducing symbolic names to abstract from concrete values, which I also like a lot.

Regarding the test names: There are some widely accepted conventions for naming tests, one, for example, being <method-name>_<scenario>_<expected-result>. In case of a bug, such naming conventions make it easy to understand what went wrong just from the output of the test runner. With pytest, certainly, a prefix 'test_' would have to be added. For example, your test function test_next_number_construtor_str could, as an example, be named test_constructor_withValidNumberString_doesntThrow.

Despite the fact that the use of symbolic names should improve readability, the way you use them tends to make the tests less readable. For example:

def test_find_trailing_zeros(trailing_zero_none):
    assert NumberGenerator(trailing_zero_none).get_trailing_zeros() == ""

here, you are creating an unnecessary distance between the definition of the symbolic value and its use. Think alternatively of the following definition.

def test_find_trailing_zeros():
    trailing_zero_none = "1234"
    assert NumberGenerator(trailing_zero_none).get_trailing_zeros() == ""

There is still a symbolic name that describes the abstract role of the concrete value. But, a reader of the test will now find everything in place, without need to scroll around to find the actual definition of trailing_zero_none.

A related example is the following:

def test_get_lowest_non_zero_digit(trailing_zero_three):
    num = NumberGenerator(trailing_zero_three)
    num.get_trailing_zeros()
    assert num.get_lowest_non_zero_digit() == 4

This tests contains what Meszaros calls 'magic': Suddenly there is a '4' - but why? Using the pattern described above, the test code would both contain the input value "1234000" and the '4', which would not be magic any more.

This example also contains some dead code num.get_trailing_zeros(), but I assume that you simply forgot to clean this up.

Finally, there is a more fundamental point that may be worth considering: To me it seems that the method get_next_number is the actual public interface of your class. The other functions seem to be mere helper functions to simplify the implementation of get_next_number. It is certainly good that you split up the functionality of get_next_number in several smaller functions. But, you should not necessarily write individual test cases for these helper functions: The tests of helper functions are more likely to cause maintenance problems, for example if you decide to refactor or switch to a different algorithmic approach for the problem.

Certainly, when doing unit-testing you have all the white-box knowledge about the code. But, for that maintainability reason it is generally recommended to nevertheless take a 'black box perspective' even in unit-testing. At least as long as this does not start to become awkward...

Answer 2

To be honest, I didn't read through your code much because I don't have the attention span and it seems the biggest issue is the approach rather than the solution. Nothing about your code looks terrible or un-Pythonic, so I'm going to go through a different approach instead.

The first thing that I noticed about the next number is that all but two of the digits of the original number remain unchanged. When going from 123 to 132, the 2 was incremented to a 3 and the 3 was decremented to a 2. When going from 09...9 to 18...9, the 0 was incremented to a 1 and the first 9 was decremented to an 8.

This pattern suggests that we may be able to increment one digit, decrement another, and arrive at a solution. The first challenge is to find the digit to increment.

Increment

---

123

We can't increment the 3 because decrementing any other number would result in a number that is less than the original. We can increment the 2, because we can then decrement the 3. From this, we learn that the right-most digit should not be incremented.

---

0200

We can't increment the 2 because we can't decrement any of the 0's. We can't increment the right-most 0's because then decrementing the 2 would lead to a number less than the original. Thus, we have to increment the first 0. We would reach the same conclusion if we considered the number 02 instead. From this, we learn that trailing 0's should be ignored.

---

09999999999999

We can't increment any of the 9's since 10 isn't a digit. Thus, we must increment the 0. From this, we learn that 9's can't be incremented.

---

90 and 9999

Applying the rules found above, it is clear that there is no possible digit to increment.

---

def findIncrementIndex(string):

    # ignore trailing zeros
    strip_zeros = string.rstrip('0')

    # start from the back
    index = len(strip_zeros) - 1

    # don't increment the right-most digit
    index -= 1

    # don't increment 9's
    while index >= 0 and strip_zeros[index] == '9':
        index -= 1

    return index

---

Decrement

The next challenge is to find the digit to decrement. This turns out to be simple: decrement the first non-zero number on the right...

---

def findDecrementIndex(string):
    strip_zeros = string.rstrip('0')
    return len(strip_zeros) - 1

---

Sort

But wait, this decrement function suggests that we turn 0200 into 1100 and turn 09...9 into 19...8. This clearly isn't correct. While the outputs are larger than the original and the digits sum to the correct value, they are not the respective minimal solutions. However, if we sort all of the digits after the incremented digit in ascending order, the minimal solution is achieved.

---

def nextNumber(string):
    increment_index = findIncrementIndex(string)
    decrement_index = findDecrementIndex(string)

    if increment_index == -1 or decrement_index == -1:
        return '-1'

    digits = [int(char) for char in string]
    digits[increment_index] += 1
    digits[decrement_index] -= 1

    # retain the digits up to the incremented one, sort the rest
    sorted_digits = digits[:increment_index+1] + sorted(digits[increment_index+1:])

    return ''.join(str(digit) for digit in sorted_digits)

---

With this approach, the same result is achieved, but with much less code. Combining this all into a single function yields:

def nextNumber(string):
    strip_zeros = string.rstrip('0')

    increment_index = decrement_index = len(strip_zeros) - 1
    increment_index -= len(re.match('[0-9]*(?:^|[^9])(9*)[1-9]$', strip_zeros).group(1)) + 1

    if increment_index == -1 or decrement_index == -1:
        return '-1'

    digits = [int(char) for char in string]
    digits[increment_index] += 1
    digits[decrement_index] -= 1

    sorted_digits = digits[:increment_index+1] + sorted(digits[increment_index+1:])
    return ''.join(str(digit) for digit in sorted_digits)

Notice that this isn't contained within a class because there isn't really a need for one; a method does the job better. Also, I made some (bad) changes to make the algorithm less readable. This new regular expression counts the number of 9's that occur successively starting from the second-to-last digit backwards and replaces the old while loop, the + 1 at the end absorbs the original increment_index -= 1. Now, if we really want to make things unreadable...

def nextNumber(s):
    i = d = len(s.rstrip('0')) - 1
    i -= len(re.match('[0-9]*(?:^|[^9])(9*)[1-9]0*$', s).group(1)) + 1
    if i == -1 or d == -1: return '-1'
    L = [int(c)+1 if j == i else int(c)-1 if j == d else int(c) for j, c in enumerate(s)]
    return ''.join(map(str, L[:i+1] + sorted(L[i+1:])))