Join-K game problem from Google Code Jam

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.

This entry was posted in Algorithms, Python and tagged . Bookmark the permalink.

2 Responses to Join-K game problem from Google Code Jam

  1. fer says:

    so did you checked if this is the right answer ?

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>