my solution of Tidy Number (Google Code Jam)

Google Code Jam

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

• Oversized Pancake Flipper

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)
True
>>> is_tidy(4444)
True
>>> is_tidy(42)
False
>>> is_tidy(10)
False

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)
9
>>> find_preceding_tidy(12345)
12345
>>> find_preceding_tidy(12350)
12349
>>> find_preceding_tidy(12000)
11999

It works!

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

>>> find_preceding_tidy(3914589564)
3899999999

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.

3914589564
3899999999

345918
345899

123000
122999

123200
122999

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.