tidy-numbers.py

#!/usr/bin/env python3

digits = '0123456789'
decrement_map = dict(zip(digits[1:], digits))


def solve(N: str):
    m = N[0]
    for i, x in enumerate(N):
        if m <= x:
            m = max(m, x)
        elif x == '0' and i == 1 and N[i-1] == '1':  # 10... => 9...
            return '9' * (len(N) - 1)
        else:
            return solve(N[:i-1] + decrement_map[N[i-1]]) + '9' * (len(N) - i)
    return N


def main():
    T = int(input())
    for x in range(1, T+1):
        print('Case #%d: %s' % (x, solve(input())))


if __name__ == "__main__":
    main()