my solution of Tidy Number (Google Code Jam)

Posted on Tue 11 April 2017 in blog


Google Code Jam

This year I'm sharing my solutions of the Google Code Jam, this is the second post, here are the previous:

The problem

Here the complete problem text.

Tatiana is a nice girl with a bit of OCD, she likes to find numbers with the digits in non-decreasing order, the so-called "tidy numbers".

Given a number, we have to find the biggest tidy number below it.

The solution

Here my complete code.

The first thing to do is to understand what a tidy number is: a number with non-decreasing digits. In other words: each digit should be equal or greater than the preceding.

>>> n = 1234
>>> def is_tidy(number):
...     prev = "0"
...     for digit in str(number):
...         if digit < prev:
...             return False
...         prev = digit
...     return True
>>> is_tidy(12345)
>>> is_tidy(4444)
>>> is_tidy(42)
>>> is_tidy(10)

Pretty straight forward, right?

But we're just at the beginning of our alorithm: how can we find the previous tidy number?

It seems simple, right? Just try all the preceding numbers until you find a tidy one:

>>> def find_preceding_tidy(number):
...     while not is_tidy(number):
...         number -= 1
...     return number
>>> find_preceding_tidy(10)
>>> find_preceding_tidy(12345)
>>> find_preceding_tidy(12350)
>>> find_preceding_tidy(12000)

It works!

But... what if the numbers are really big and strange?

>>> find_preceding_tidy(3914589564)

On my machine it takes about 12 seconds to find the number. This is too much time for the large dataset, where we can have numbers with 18 digits.

It's time to take pencil and paper.





So the logic seems to be: when you find the decreasing digit, that's the point you have to decrease the left part and then put 9s for the right part:

39 14589564
38 99999999

3459 18
3458 99

123 000
122 999

123 200
122 999

And so this is what I do: enumerate the digits so I can see them one by one and have also the index when I find the decreasing digit, I use slicing to separate the two parts I convert the left part to integer and decrease by 1 create the new right part, repeating 9 for the number of characters

def find_preceding_tidy(number):
    line = str(number)
    prev = "0"
    for i, digit in enumerate(line):
        if digit < prev:
            left_part = str(int(line[:i])-1)
            right_part = "9" * (len(line) - i)
            return left_part + right_part
        prev = digit

What I learnt

It's ok to make a brute force algorithm, but you know it will be just for the small data set.

The first solution, however, can be used as a "unit test" when you'll write the second, possibly more complex, algorithm.