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 sisyphean 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 categorisation 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:
...
p = self.img.getpixel((x,y))
(hue,sat,val) = rgb_to_hsv(*pxtofloat(p))
if sat > 0.5: # Ignore greyscale colors
...
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:
def pxtofloat(px):
return tuple(map(lambda x: float(x)/255, px))
def pxtoint(px):
return tuple(map(lambda x: int(x*255), px))
HSV also makes sense when categorising the colours as we can work with a single ‘hue’ value rather than three colour components:
if hue < 0.1:
self._colour = Colour.RED
elif hue > 0.3 and hue < 0.35:
self._colour = Colour.GREEN
elif hue > 0.77 and hue < 0.81:
self._colour = Colour.PURPLE
else:
raise RuntimeError("Couldn't work out the color")
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:
# Convert to greyscale by removing saturation and hue, and averaging
# RGB to be V
def toGreyscale(px):
fpx = pxToFloat(px)
rgb = hsv_to_rgb(0,0, reduce(lambda a,b: a+b, fpx)/3.0)
return pxToInt(rgb)
...
bwimg = pxfilter(img, toGreyscale)
(‘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:
# All px above val == white, all below == black
def threshold(th, px):
v = rgb_to_hsv(*pxtofloat(px))[2]
if v < th:
return (0,0,0)
else:
return (255,255,255)
...
bwimg = pxfilter(bwimg, partial(threshold, 0.6))
(‘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 libraries out there to do this for us but flood-filling is so simple it’s easier to just implement our own:
# Return new copy of image that has been flooded
def flooded(img, target, replacement):
i2 = img.copy()
# Recursive flood routing, based on version in wikipedia.
#
# http://en.wikipedia.org/wiki/Flood_fill
#
# This requires bumping Python's recursion limit up, and should
# probably be coverted to a queue-based version ...
sys.setrecursionlimit(10000)
def flood(img, target, replacement, sx, sy, x=0, y=0):
if img[x,y] != target: return
if img[x,y] == replacement: return
img[x,y] = replacement
if x-1 >= 0: flood(img, target, replacement, sx, sy, x-1, y)
if x+1 < sx: flood(img, target, replacement, sx, sy, x+1, y)
if y-1 >= 0: flood(img, target, replacement, sx, sy, x, y-1)
if y+1 < sy: flood(img, target, replacement, sx, sy, x, y+1)
flood(i2.load(), target, replacement, *i2.size)
return i2
fcol = (255,0,0)
fimg = flooded(self.bwimg, (255,255,255), fcol)
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:
y = fimg.size[1]/2 # Half-way down
for x in range(fimg.size[0]):
p = fimg.getpixel((x,y))
if p != fcol and prev == fcol:
# This is a rising edge; count
trans += 1
span = [x,None]
elif p == fcol and prev != fcol:
# Falling edge, save span
span[1] = x
self._spans.append(span)
prev = p
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:
span = self.spans[0]
x = span[0] + ((span[1]-span[0]) / 2)
white = (255,255,255)
prev = white
trans = 0
for y in range(self.bwimg.size[1]):
p = self.bwimg.getpixel((x,y))
if prev == white and p != white:
# White->Black edge
trans += 1
prev = p
if trans == 1:
self._pattern = Pattern.SOLID
elif trans == 2:
self._pattern = Pattern.BLANK
elif trans > 5: # Lines should be between 6-10 transitions
self._pattern = Pattern.LINES
else:
raise RuntimeError("Not enough transitions in shape: %s"%trans)
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:
# Scan to find top/bottom edge
span = self.spans[0]
def findtop(sy, ey, step):
for y in range(sy, ey, step):
for x in range(span[0],span[1]+1):
if self.bwimg.getpixel((x,y)) != (255,255,255):
return y
top = findtop(0,self.bwimg.size[1], 1)
bottom = findtop(self.bwimg.size[1]-1, 0, -1)
# Scan left side, recording values
def findleft(y):
#for x in range(span[0],span[1]+1):
for x in range(0,self.bwimg.size[0]):
if self.bwimg.getpixel((x,y)) != (255,255,255):
return x
left = []
for y in range(top, bottom+1):
left.append(findleft(y))
And with this we can calculate the variance in the edge:
prev = None
diff = []
for x in left:
if prev != None:
d = x-prev
diff.append(d)
prev = x
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:
# Calculate the overall variance trend by reducing contiguous
# trends to single values
vdiff=[]
prev = 0
for d in diff:
if d < 0 and not prev < 0:
vdiff.append(-1)
prev = -1
elif d > 0 and not prev > 0:
vdiff.append(1)
prev = 1
This give us a surprisingly 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:
# Calc zero to non-zero variation
zcount = 0.0
nzcount = 0.0
for d in diff:
if d == 0:
zcount += 1
else:
nzcount +=1
zratio = nzcount / zcount
With these statistics we can categorise the shapes appropriately:
if vdiff == [-1, 1, -1, 1]:
# Wavy == squiggle:
self._shape = Shape.SQUIGGLE
elif vdiff == [-1, 1] and zratio < 0.5:
# Up then down, but has large contiguous area == oval
self._shape = Shape.OVAL
elif vdiff == [-1, 1] and zratio > 0.70:
# Up then down, but not especially flat == diamond
self._shape = Shape.DIAMOND
else:
raise RuntimeError("Couldn't work out the shape of %s" % self.pos)
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, discarding 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 of working out what calls are being made back to the server or using Selenium to control a browser.
So recently I took a break from fighting with a