An implementation of the problem B - Tidy numbers: Google Code Jam 2017

1) tidy-numbers-stmt.txt

# Complete statement of the problem
# https://code.google.com/codejam/contest/3264486/dashboard#s=p1

# Tatiana likes to keep things tidy. Her toys are sorted from smallest
# to largest, her pencils are sorted from shortest to longest and her computers
# from oldest to newest. One day, when practicing her counting skills, she
# noticed that some integers, when written in base 10 with no leading zeroes,
# have their digits sorted in non-decreasing order. Some examples of this are 8,
# 123, 555, and 224488. She decided to call these numbers tidy. Numbers that do
# not have this property, like 20, 321, 495 and 999990, are not tidy.

# She just finished counting all positive integers in ascending order from 
# 1 to N. What was the last tidy number she counted?

# Input
# The first line of the input gives the number of test cases, T. T lines follow. 
# Each line describes a test case with a single integer N, the last number 
# counted by Tatiana.

# Output
# For each test case, output one line containing Case #x: y, where x is the test 
# case number (starting from 1) and y is the last tidy number counted by Tatiana.

2) tidy.py

class Tidynumber():

	def is_tidy( self ):

		self.digits = list(reversed(self.rev))
		# A number is tidy if its array-integer representation is equivalent
		# to its sorted version. eg. 1810 is not tidy because the sorted array
		# [1,8,1,0] is not equal to [0,1,1,8].
		return self.digits == sorted(self.digits)


	def __init__( self, num ):

		# self.num is a string, eg. "1810"
		self.num = num
		# self.rev is the reversed-integer-array representation of the 
		# same number, e.g. [0,1,8,1]
		self.rev = [int(d) for d in num[::-1]]
		self.result = int(num)


	def calculate_tidy( self ):

		while not self.is_tidy():

			# until self.result is not tidy 
			# 1) compare the first to elements of the reversed array [0,1,8,1] 
			# 2) if (0 ≥ 1) continue and goto #1 with next pairs of indexes 
			# 3) else remove the quantity from the starting number plus one 
			#    (1810 - (0 + 1) = 1809), update self.rev with that number ([9,0,8,1]) 
			#    and break the <for> loop
			# 4) the while checks if the number is tidy. 1809 it's not, so enter the
			#    for-loop with the index starting again from 0
			# 5) Look at the first pairs of elements of the reversed array [9,0,8,1]
			# 6) compare (9, 0) (9 ≥ 0, continue)
  			# 7) compare (0, 8) (0 ≱ 8, removing the left quantity 09 plus 1 from 1809 
  			#    (1809 - (9 + 1) = 1799)
  			# 8) since [1,7,9,9] == sorted([1,7,9,9]) the programs ends returning
  			#    1799 as the last tidy number encountered.
			
			for i in range(0, len(self.rev)):

				if self.rev[i] < self.rev[i + 1]:

					index = i + 1

					self.result -= int(self.num[-index:]) 
					self.result -= 1
					
					self.num = str(self.result)
					self.rev = [int(d) for d in self.num[::-1]]

					break;

		return self.result


print("Algorithm for Google Code Jam - Qualification round 2017")
print("Exercise B - Tidy numbers")
print("Implemented by Fabrizio Calderan on March 7th, 2018\n")

infile   = open( 'B-practice.in', 'r' )
numtasks = int( infile.readline() ) + 1
output   = []

for i in range(1, numtasks):

	tidy = Tidynumber(infile.readline().rstrip())
	result = "Case #%d: %d" % (i, tidy.calculate_tidy())
	output.append(result)

print("\n".join(output));

3) B-practice.in

10
1810
42021
19099
4
76543
13408756
912345678
11111111111110
1978
1676

4) B-practice.out

Case #1: 1799
Case #2: 39999
Case #3: 18999
Case #4: 4
Case #5: 69999
Case #6: 13399999
Case #7: 899999999
Case #8: 9999999999999
Case #9: 1899
Case #10: 1669