Python Forum
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Digits increasing
#1
Could anyone help me in the following problem from https://artofproblemsolving.com/communit...ts_ordered . Given a positive integer n, find the smallest positive integer m>n whose digits are in ascending or descending order. I tried to do recursively two functions where the first finds the next number whose digits are in ascending order and the seconds the next number whose digits are in descending order. But I am not sure how to do the recursion? It looks like the decreasing function does not work properly.

def increasing(n):
    asastring = str(n)
    length = len(asastring)
    if asastring == "9"*length:
        return "1"*(length+1)
    if length == 1:
        return int(n)+1

    if length >= 2:
        firstcharacter = asastring[0]
        secondcharacter = asastring[1]
        if int(firstcharacter) > int(secondcharacter):
            return int(str(firstcharacter)*length)
        if firstcharacter == secondcharacter:
             return firstcharacter+str(increasing(int(asastring[1:])))
        if int(firstcharacter) < int(secondcharacter):
            if secondcharacter == "9":
                return str(int(firstcharacter)+1) * len(str(n))
            return firstcharacter+str(increasing(int(asastring[1:])))

def decreasing(n):
    asastring = str(n)
    length = len(asastring)
    if length > 1:
        if asastring == "1"+"0"*(len(asastring)-1):
            return "11"+"0"*(len(asastring)-2)
    if len(asastring) == 1:
        if asastring == 9:
            return 11
        else:
            return int(n)+1

    if len(asastring) >= 2:
        firstcharacter = asastring[0]
        secondcharacter = asastring[1]
        #print("f:"+str(asastring[0])+" s:"+str(asastring[1]))
        if int(firstcharacter) > int(secondcharacter):
            if int(secondcharacter) > 0:
                return str(str(firstcharacter)+str(int(secondcharacter)-1))
            else:
                return str(str(int(firstcharacter) -1)*2)
        if firstcharacter == secondcharacter:
             return firstcharacter+str(decreasing(int(asastring[1:])))
        if int(firstcharacter) < int(secondcharacter):
            if secondcharacter == "9":
                return str(int(firstcharacter)+1) * len(str(n))
            return firstcharacter+str(decreasing(int(asastring[1:])))

i=1
for j in range(100):
    i = min(int(increasing(i)),int(decreasing(i)))
    print(i)
Reply
#2
Is there some reason this has to be done recursively? It does not strike me as a program well suited for recursion, certainly not in Python. It would be far to easy to hit the recursion limit.

I would just have a function that checks for increasing digits. Then a simple loop where you increase n by one, check that for increasing digits, and then break and return if you have them. The same code with a function for decreasing digits solves the other side of the problem.
Craig "Ichabod" O'Brien - xenomind.com
I wish you happiness.
Recommended Tutorials: BBCode, functions, classes, text adventures
Reply
#3
There is no reason why I have to do it recursively. I just though it would be easiest to do by recursion as I was able to make first every single digit numbers and then generate two digit numbers by adding every digit to every one digit number and so on. But I found it would take much memory to generate huge numbers by this approach. So I was wondering if I could make recursive functions to solve the problem with less memory usage.
Reply
#4
I didn't test all specific cases, but the following solution (I just wrote) is a working starting point to make a better one...

decompose = lambda x: list(map(int, str(x))) # x assumed to be a positive integer
compose = lambda x: int(''.join(map(str, x)))  # x assumed to be a list of digits (each digit is int)

def min_asc(x):
    d = decompose(x)
    res = d[:]
    m = None
    for j in range(len(d) - 1):
        if d[j] > d[j + 1] and not m:
           m = d[j]
        elif m and d[j + 1] > m:
             m = d[j +1]
        res[j + 1] = m or d[j + 1]
    return compose(res)
min_asc(123614270121)
Output:
123666677777
min_asc(287)
Output:
288
Reply
#5
min_asc(123614270121) should return 123666666666 rather than 123666677777, as you can see by the function increasing by my first post.
Reply
#6
It looks like the recursive approach is wrong:
# the next integer whose digits are increasing.
def increasing(n):
    asastring = str(n)
    length = len(asastring)
    if asastring == "9"*length:
        return "1"*(length+1)
    if length == 1:
        return int(n)+1

    if length >= 2:
        firstcharacter = asastring[0]
        secondcharacter = asastring[1]
        if int(firstcharacter) > int(secondcharacter):
            return int(str(firstcharacter)*length)
        if firstcharacter == secondcharacter:
             return firstcharacter+str(increasing(int(asastring[1:])))
        if int(firstcharacter) < int(secondcharacter):
            if secondcharacter == "9":
                return str(int(firstcharacter)+1) * len(str(n))
            return firstcharacter+str(increasing(int(asastring[1:])))


def decreasing(n):
    asastring = str(n)
    length = len(asastring)
# First the case where we need to add a digit.
    if asastring == "9"*length:
        return "1"+"0"*length
# Now we know that the next integer has the same number of digits as the original number.
    if length == 1:
        return int(n)+1
    if length >= 2:
        firstcharacter = asastring[0]
        secondcharacter = asastring[1]
        if int(firstcharacter) > int(secondcharacter):
            return str(firstcharacter) + str(decreasing(asastring[1:]))
        if int(firstcharacter) == int(secondcharacter):
            return decreasing(firstcharacter+str(decreasing(asastring[1:])))
        if int(firstcharacter) < int(secondcharacter):
            return str(int(firstcharacter)+1)+'0'*(length-1)

i = 1
found = False
for k in range(4000):
    i = min(int(increasing(i)), int(decreasing(i)))

print(i)
outputs RecursionError: maximum recursion depth exceeded while getting the str of an object
Reply
#7
That was an unforgivable error... This is where writing some tests are highly desirable.
I have rewritten my code, added some tests, and now it seems work fine.

decompose = lambda x: list(map(int, str(x))) # x assumed to be a positive integer
compose = lambda x: int(''.join(map(str, x)))  # x assumed to be a list of digits (each digit is int)
is_asc = lambda x: compose(sorted(decompose(x))) == x # check if x is alredy "good" number
is_dsc = lambda x: compose(sorted(decompose(x)[::-1])[::-1]) == x
 
def min_asc(x):
    def _make_preorder(x):
        d = decompose(x)
        res = d[:]
        m = None
        for j in range(len(d) - 1):
            if d[j] > d[j + 1] and not m:
                m = d[j]
            res[j + 1] = m or d[j + 1]
        return compose(res)
    return _make_preorder(x + 1) if is_asc(x) else _make_preorder(x)


def min_dsc(x):
    def _make_preorder(x):
        d = decompose(x)
        res = d[:]
        for j in range(len(d) - 1, 0,  -1):
            if res[j] > res[j - 1]:
                res[j - 1] += 1
                res[j:] = [0] * (len(d) - j)
        return compose(res)
    return _make_preorder(x + 1) if is_dsc(x) else _make_preorder(x)
                


asc_autotest_data = ((3124123, 3333333),
                     (1, 2),
                     (10, 11),
                     (99, 111),
                     (154, 155),
                     (277, 278),
                     (0, 1),
                     (9, 11),
                     (47893, 47899),
                     (int('1' * 39 + '0' * 90 + '7' * 100), int('1' * (39 + 90 + 100))), # a very big num
                     (99999, 111111),
                     (123614270121, 123666666666)
                    )



dsc_autotest_data = ((1, 2),
                     (9, 10),
                     (543105, 543110),
                     (299, 300),
                     (109012, 110000),
                     (0, 1),
                     (999889, 999900),
                     (101, 110),
                     (99999, 100000),
                     (1009, 1100),
                     (0, 1),
                     (int('1' * 100 +'0'*100 + '9'*100), int('1'*101 + '0' * 199)) # a very big num
                    )


def test_functions(data, f):
    print("Testing {}....".format(f.__name__))
    for a, b in data:
        if f(a) != b:
            print("Failed test: {} != {}".format(f(a), b))
            break
    else:
        print("All tests were passed.")
        return
    print("Some tests were failed.")


if __name__ == '__main__':
    test_functions(asc_autotest_data, min_asc)
    test_functions(dsc_autotest_data, min_dsc)
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  Increasing difficulty of a maths game Maxxy_Gray 1 3,148 Apr-04-2018, 03:00 PM
Last Post: sparkz_alot
  Increasing depth in python malling 19 13,709 Oct-20-2016, 10:43 PM
Last Post: malling

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020