Google Code Jam
This year I'm sharing my solutions of the Google Code Jam, this is the second post, here are the previous:
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.
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
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:
enumeratethe 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.