Halt Condition

Cheating at puzzles for fun and … well, just fun actually

As mentioned elsewhere, I recently moved to the internal-systems team at Atlassian. The team there are puzzle obsessed; each day works stops in the afternoon to engage in bout of competitive puzzle solving. One particular favorite is Daily Set, which involves finding matching sets of three tiles based on some simple rules. This is diligently solved each day by the team members and the times recorded for comparison. An amusing little diversion and team-building ritual. With one problem: I fucking suck at it.

Really, I'm appalling. While everyone else's scores are recorded in a spreadsheet to be pored over and analysed, I can't even complete the bloody puzzle. Each day I end up repeatedly finding the same couple of sequences over and over again, stuck in some sort of sisyphian nightmare.

I joked that I'd have better luck writing a program to do image analysis and pattern-recognition to solve the puzzle than actually doing it myself. After being humiliated by the bloody thing one time too many I realised this probably really is the case. After all, I'm a tool-user at heart, and the idea of beating it into submission was starting to look quite attractive. It turns out this is perfectly feasible and not that hard if you know a few tricks; what follows is an explanation of how I got a working Set cheater.

The full Python sourcecode is available at Github. The code itself was hacked together with much experimentation in a day; it's inconsistent, frequently redundant and shouldn't be considered best, or even sane, practice. However it does have reasonably complete unit-tests and contains a few tricks that novice Pythonistas may find useful.

The Rules

Set consists of 12 tiles. Each tile has 4 properties that with 3 possible values:

• Number of shapes (1-3)
• Type of shapes (diamond, oval or squiggle)
• Colour of shapes (red, green or purple)
• Shape pattern (empty, solid or lines)

Each 'set' consists of 3 tiles where each attribute is either all the same or all different. There are 6 sets. That's it.

Getting the images

Fetching the images is simple; we use urllib2 to fetch the main page, use a simple regular expression to extract the puzzle-image paths, then urllib2 to download them.

Once downloaded we need to convert them into something we can process easily. GIF is a palette-based format which is a pain for this sort of work; we'd prefer an array of RGB values. I toyed with implementing a GIF decoder but it turns out the Python Imaging Library will do the conversion for us so I ran with this in the end. The result is an RGB image representation that can be addressed either with getpixel(x,y) or as a 2D array.

Finding The Shape's Colour

The seemingly simplest parameter to fetch is the colour. On the surface it seems to just be a case of dropping all the white pixels then just selecting the most common pixel colour. We then just apply some tolerance values to roughly catagorise the colours into red, green and purple. However in practice this fails on images with low surface-area due to antialiasing:

All those greys and low-intensity reds are actually more common than the base color, confusing the matching.

For colour catagorisation and manipulation RGB isn't always the most useful representation. In particular in this case we're not actually all that interested in the actual colour as much as the intensity of the colour. HSV gives a better 'human-oriented' view of colour, so to strip out the antialiased pixels we convert into the HSV colourspace and drop anything below an appropriate saturation value:

The 'rgb_to_hsv' routine is built into Python. Unfortunately it expects values in the 0.0-1.0 range, and the imaging library uses 0-255 values (this mismatch is unfortunately rather common in graphics libraries). So a some quick conversion routines are needed:

HSV also makes sense when categorising the colours as we can work with a single 'hue' value rather than three colour components:

Finding The Number Of Shapes

Counting the images is also presents issues with colour. While the horizontal alignment of the shapes should reduce the problem to drawing a line through the middle and counting the transitions, in practice the patterns and antialiasing confuse the issue so we need to get rid of these. The first step is to drop the colour; once again HSV helps us out here: if we zero out the hue and saturation and make the value an average of the RGB values we get a greyscale representation of the source image:

('pxfilter' is a routine that returns a copy of an image with a function applied to each pixel.)

However, the antialiasing is still visible and could potentially cause problems later so we want to get rid of it. So we apply a threshold filter:

('partial' is Python's currying implementation; for more information see the functools documentation.

We now have a 'clean' image to work with. However the shape patterns still confuse the counting. My solution to this is use flood-fill to set all the area outside the image borders to a known colour (e.g. red) and then treat anything else as shape contents. There are probably Python librarys out there to do this for us but flood-filling is so simple it's easier to just implement our own:

Now we can just use simple 2D raycasting to count the red->other transitions. We also save the shape edge-locations ('spans') for later use:

Finding The Pattern

We use a similar technique to find the pattern; we use the spans we saved in the previous step to find the center of one shape. Then we raycast vertically through it, counting the transitions. The count tells us the pattern:

Finding The Shape

The shapes are the trickiest part to work out. The images are rather small, so techniques such as converting to polygons or vectors are not going to be very consistent. This is compounded by the fact that two of the images (the diamond and the oval) are, topologically-speaking, quite similar. In the end, after pondering a few techniques I came up with a hybrid system.

The first step is to get some data about one edge of a shape. To do this we use the span-and-raycast technique:

And with this we can calculate the variance in the edge:

However the number of values varies slightly between the same shape in different configurations. For that reason we want to remove duplicate variances and flat areas to get a distilled view of the edge:

This give us a suprisingly concise view of the shapes; the squiggle is [-1, 1, -1, 1] and the oval and diamond are [-1, 1]. To differentiate between the last two we can count the overall ratio of flatness to changes:

With these statistics we can categorise the shapes appropriately:

Calculating The Sets

This part is actually pretty simple; I won't post the code here. Basically we just brute-force iterate over every combination of images and compare them, dicarding any group that is not either all the same or all different. The surviving groups are placed into a set container to remove duplicates. Once done these are then printed out as x/y positions in the original webpage to be entered manually.

One obvious improvement would be to have the program enter the values for us. The webpage uses javascript to record the selections so this would either be a case or working out what calls are being made back to the server or using Selenium to control a browser.

This entry was posted on Monday, September 21st, 2009 at 9:19 am and is filed under Misc, Python. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.