Next number with the same sum of digits

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_ze

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]

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*, 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...

%%CODEBLOCK_4%%, 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:])))

, 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...

%%CODEBLOCK_4%%

StackExchange Code Review Q#119618, answer score: 3