Solving Boggle with Python

I attended my first Python Dojo in London last night and have to say it was great fun.  As I’ve said before these kinds of events are great to get to know people and learn something new.

The challenge settled on for last night was to solve a Boggle puzzle. For those not familiar with the game, the idea is that you get an n-by-n grid of letters and you have to form as many words as you can by ‘snaking’ through the grid.  Every grid cell may only be used once for a word.  For example, this is how you would form the word MURALS, starting from M:

Everybody got about an hour to hack on a solution after which each team presented their code to the rest.  It was interesting to see the diversity of style and solution. There was a team that used 5 or 6 classes in their solution with extra facilities for caching, ours was more straightforward & procedural, while another did the proper thing and used a Trie.

Since our code did not quite work yet I finished it on the train home and then took some time this morning to clean it up.  For kicks I also used python’s multiprocessing module to have a version that would solve large grids in paralllel.

I pushed the code to github and, while nothing fancy or super optimized, it should do the job.  As always, patches & improvements are welcome 🙂

Props to @ntoll and @tjguk for organizing the event and hopefully I can make the next one as well.

–Dirk

5 thoughts on “Solving Boggle with Python

  1. Pingback: Codenoise, A London Clojure Dojo report | Dirk's Page

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s