In that post, I will present my attempt to solve problem from Google Code Jam (2010) – Rotate . In about week, new edition GCJ will start so I decided take the challenge. Let’s solve one riddle from previous edition, to warm up brain. For my solution I chose python – I consider it as ideal tool for algorithm’s proof-of-concept, although I am not very advance python programmer.
My first noteworthy idea is that, we don’t really need to rotate our matrix, all we need to do is change gravity line – to the right border of checkboard.
Relative positions of all pieces will be the same as we really rotate matrix. It saves a lot of operation.
Now let’s gravity takes effect. It have to do 2 things:
- removes all empty field between any 2 pieces and
self.matrix [y] .pop(x)
- move the whole row to the right side
self.matrix [y] .insert(0, ".")
I did it in the following way – after checking if there is really cause to move Xst piece:
Last step, will be of course looking for the winner. Nothing special here, for each non-empty field, I invoke
checkKMatrix() method, to check sub-matrix starting from x & y. To more readable code, I used exception instead of bunch of “ifs”, which slows down execution of course. As following (micro) tests shows, exceptions slow down algorithms a lot !
>>> timeit.Timer(lambda : [raiseAndcatchException(x) for x in range(10)] ).timeit() 20.328131673448752 >>> timeit.Timer(lambda : [check3conditions(x) for x in range(10)] ).timeit() 3.606481800403799
One another nice optimization what we could do. Consider following case: There is no reason to move all rows to right border, much better will be move only one mismatched row to the left. Generalizing, to better performance we should find the most filled column going from right to left, and align another rows to it.
That is all what I could figure out to make the best solution Join-K problem. My latest version of code could be find at my github account.