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

September 21st, 2009 | Filed under Misc, Python | 2 comments

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)

28 17 78

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:

73-close-up2

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:

PLAIN TEXT
PYTHON:
  1. ...
  2.   p = self.img.getpixel((x,y))
  3.   (hue,sat,val) = rgb_to_hsv(*pxtofloat(p))
  4.   if sat> 0.5:  # Ignore greyscale colors
  5.       ...

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:

PLAIN TEXT
PYTHON:
  1. def pxtofloat(px):
  2.     return tuple(map(lambda x: float(x)/255, px))
  3.  
  4. def pxtoint(px):
  5.     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:

PLAIN TEXT
PYTHON:
  1. if hue <0.1:
  2.       self._colour = Colour.RED
  3.   elif hue> 0.3 and hue <0.35:
  4.       self._colour = Colour.GREEN
  5.   elif hue> 0.77 and hue <0.81:
  6.       self._colour = Colour.PURPLE
  7.   else:
  8.       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:

PLAIN TEXT
PYTHON:
  1. # Convert to greyscale by removing saturation and hue, and averaging
  2. # RGB to be V
  3. def toGreyscale(px):
  4.     fpx = pxToFloat(px)
  5.     rgb = hsv_to_rgb(0,0, reduce(lambda a,b: a+b, fpx)/3.0)
  6.     return pxToInt(rgb)
  7.  
  8. ...
  9.  
  10. bwimg = pxfilter(img, toGreyscale)

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

79-color 79-gs

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:

PLAIN TEXT
PYTHON:
  1. # All px above val == white, all below == black
  2. def threshold(th, px):
  3.     v = rgb_to_hsv(*pxtofloat(px))[2]
  4.     if v <th:
  5.         return (0,0,0)
  6.     else:
  7.         return (255,255,255)
  8. ...
  9. bwimg = pxfilter(bwimg, partial(threshold, 0.6))

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

79-color 79-gs 79-bw

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:

PLAIN TEXT
PYTHON:
  1. # Return new copy of image that has been flooded
  2. def flooded(img, target, replacement):   
  3.     i2 = img.copy()
  4.  
  5.     # Recursive flood routing, based on version in wikipedia.
  6.     #
  7.     #     http://en.wikipedia.org/wiki/Flood_fill
  8.     #
  9.     # This requires bumping Python's recursion limit up, and should
  10.     # probably be coverted to a queue-based version ...
  11.     sys.setrecursionlimit(10000)
  12.     def flood(img, target, replacement, sx, sy, x=0, y=0):
  13.         if img[x,y] != target: return
  14.         if img[x,y] == replacement: return
  15.         img[x,y] = replacement
  16.         if x-1>= 0: flood(img, target, replacement, sx, sy, x-1, y)
  17.         if x+1 <sx: flood(img, target, replacement, sx, sy, x+1, y)
  18.         if y-1>= 0: flood(img, target, replacement, sx, sy, x, y-1)
  19.         if y+1 <sy: flood(img, target, replacement, sx, sy, x, y+1)
  20.  
  21.     flood(i2.load(), target, replacement, *i2.size)
  22.     return i2
  23.  
  24. fcol = (255,0,0)
  25. fimg = flooded(self.bwimg, (255,255,255), fcol)

79-flooded

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:

PLAIN TEXT
PYTHON:
  1. y = fimg.size[1]/2  # Half-way down
  2.   for x in range(fimg.size[0]):
  3.       p = fimg.getpixel((x,y))
  4.       if p != fcol and prev == fcol:
  5.       # This is a rising edge; count
  6.       trans += 1
  7.       span = [x,None]
  8.       elif p == fcol and prev != fcol:
  9.       # Falling edge, save span
  10.       span[1] = x
  11.       self._spans.append(span)
  12.       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:

PLAIN TEXT
PYTHON:
  1. span = self.spans[0]
  2.   x = span[0] + ((span[1]-span[0]) / 2)
  3.  
  4.   white = (255,255,255)
  5.   prev = white
  6.   trans = 0
  7.   for y in range(self.bwimg.size[1]):
  8.       p = self.bwimg.getpixel((x,y))
  9.       if prev == white and p != white:
  10.       # White->Black edge
  11.       trans += 1
  12.       prev = p
  13.  
  14.   if trans == 1:
  15.       self._pattern = Pattern.SOLID
  16.   elif trans == 2:
  17.       self._pattern = Pattern.BLANK
  18.   elif trans> 5:  # Lines should be between 6-10 transitions
  19.       self._pattern = Pattern.LINES
  20.   else:
  21.       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:

PLAIN TEXT
PYTHON:
  1. # Scan to find top/bottom edge
  2.   span = self.spans[0]
  3.   def findtop(sy, ey, step):
  4.       for y in range(sy, ey, step):
  5.       for x in range(span[0],span[1]+1):
  6.           if self.bwimg.getpixel((x,y)) != (255,255,255):
  7.           return y
  8.  
  9.   top = findtop(0,self.bwimg.size[1], 1)
  10.   bottom = findtop(self.bwimg.size[1]-1, 0, -1)
  11.  
  12.   # Scan left side, recording values
  13.   def findleft(y):
  14.       #for x in range(span[0],span[1]+1):
  15.       for x in range(0,self.bwimg.size[0]):
  16.       if self.bwimg.getpixel((x,y)) != (255,255,255):
  17.           return x
  18.  
  19.   left = []
  20.   for y in range(top, bottom+1):
  21.       left.append(findleft(y))

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

PLAIN TEXT
PYTHON:
  1. prev = None
  2.   diff = []
  3.   for x in left:
  4.       if prev != None:
  5.       d = x-prev
  6.       diff.append(d)
  7.       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:

PLAIN TEXT
PYTHON:
  1. # Calculate the overall variance trend by reducing contiguous
  2.   # trends to single values
  3.   vdiff=[]
  4.   prev = 0
  5.   for d in diff:
  6.       if d <0 and not prev <0:
  7.       vdiff.append(-1)
  8.       prev = -1
  9.       elif d> 0 and not prev> 0:
  10.       vdiff.append(1)
  11.       prev = 1

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:

PLAIN TEXT
PYTHON:
  1. # Calc zero to non-zero variation
  2.   zcount = 0.0
  3.   nzcount = 0.0
  4.   for d in diff:
  5.       if d == 0:
  6.       zcount += 1
  7.       else:
  8.       nzcount +=1
  9.   zratio = nzcount / zcount

With these statistics we can categorise the shapes appropriately:

PLAIN TEXT
PYTHON:
  1. if vdiff == [-1, 1, -1, 1]:
  2.       # Wavy == squiggle:
  3.       self._shape = Shape.SQUIGGLE
  4.   elif vdiff == [-1, 1] and zratio <0.5:
  5.       # Up then down, but has large contiguous area == oval
  6.       self._shape = Shape.OVAL
  7.   elif vdiff == [-1, 1] and zratio> 0.70:
  8.       # Up then down, but not especially flat == diamond           
  9.       self._shape = Shape.DIAMOND
  10.   else:
  11.       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, 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.

The programming language for this year is my own

September 13th, 2009 | Filed under Lisp, Python | 1 comment

Generally I try and learn a programming language a year; it's useful to constantly test your assumptions and your ability to reason in new ways. However, as I started to learn Javascript earlier this year I also started to wonder about exactly what I'm trying to achieve with this practice.

Where am I going here?

Learning other programming languages is useful because is causes you to question, and hopefully expand, the practices you use in the programs write day-to-day. But expansion can be in more than one dimension; Erlang may force me to think about the trade-offs of concurrency and immutability but I am still none-the-wiser about how Erlang achieves its blindingly-fast context switching. I've learned the power of Common Lisp's conditions/restarts but don't really grok why they're faster than Java's exceptions.

There are also some questions no programming language by itself is going to answer; what are the benefits of converting code to CPS during compilation? Everyone seems to be building JIT compilers on LLVM; how much work is that? Could we eliminate NullPointerExceptions by just removing the concept of null and telling programmers to suck it up?

Some things can only be learned by doing. Time to implement a language rather than just learning one.

Implementing Lisp

I didn't want to get bogged down in language syntax design and parser details (not yet anyway), so I decided that the first run should be to implement a Lisp system. The core of Lisp is simple to parse, flexible enough to implement any concepts that interest me and famously easy to bootstrap. The initial plan was to implement a basic Scheme-like interpreter in Python, implement compilation to LLVM, then re-implement the compiler in my minimal language in the classic compiler bootstrap pattern. I figured the Python/Scheme implementation shouldn't take me long as I knew Lisp pretty well.

About 200 lines of Python in I realised I didn't know shit.

Back to basics

One of the insight that learning lisp brings is realising that virtually all programming data-structures and operations can be implemented via lambdas, but I quickly realised that I didn't actually know how to do much of this in practice. Oh well, back to the books; SICP and in particular Lisp in Small Pieces.

Having revised the fundamentals, I initially went on to implement a metacircular interpreter in Chicken Scheme. However this rapidly became confusing; you have to constantly keep track of which version of lisp you're currently working with; the implementer or the implementee. And if your implementation of lambda is just a call to the implementation language's lambda then how much have you really learned? So once I had something equivalent to LiSP's basic evaluator I ported the resulting code to Python, building up from cons cells and the fundamental first-class objects (functions, integers, strings and symbols).

Where I'm at

At this point I have a core Lisp-1 interpreter with a handful of primitives defined. The next step is to implement CL-style macros, and then start looking at compiling this down to LLVM. Once I have a working executable I will then re-implement the compiler in the new language. This then will become the test-bed for adding whatever aspects interest me; immutability, monads, unnullable references, etc.

I'm not planning on rushing this; this is not intended to be a production language but a vehicle for learning. If I need to wander off on a tangent of digging into Oz or OCaml for inspiration then I will. But even at this early stage I've learned a lot about the theory and practice of language implementation and the limits of my own (assumed) knowledge.

Reading queues asynchronously in Python’s multiprocessing module

September 7th, 2008 | Filed under Python | 2 comments

Python 2.6 will add a multiprocessing module that supports fork/join semantics and management of process pools. However even in this multiprocessor environment it is still necesary to do some asynchronous. The main way that processes communicate in this environment are through shared queues (implemented as socket-pairs or unix pipes under the hood), but we need a method for the UI to be notified about updates to any queues it is listening on without blocking (for example in a UI). Luckily it is possible to get at underlying file-descriptor, which can then be managed with select() or some abstraction thereof. Unfortunately there's no official support for this but we can still poke around inside the implementation class to get at the details. The code below shows how to do this with GTK. This just spawns off a sub-process that counts up and sends the current number to the UI via a queue, which then displays the number:

PLAIN TEXT
PYTHON:
  1. from __future__ import print_function
  2. import gtk, gobject, time, multiprocessing, Queue
  3.  
  4.  
  5. class UI:
  6.  
  7.     def destroy(self, widget, data=None):
  8.         self.outq.put("quit")
  9.         gtk.main_quit()
  10.  
  11.     def __init__(self):
  12.         self.window = gtk.Window(gtk.WINDOW_TOPLEVEL)
  13.         self.window.connect("destroy", self.destroy)
  14.         self.window.set_border_width(10)
  15.    
  16.         self.label = gtk.Label("Not Set!")
  17.         self.window.add(self.label)
  18.    
  19.         self.label.show()
  20.         self.window.show()
  21.  
  22.     def update(self, fd, cond):
  23.         val = self.inq.get()
  24.         self.label.set_text("Value is %s" % val)
  25.         return True
  26.  
  27.     def main(self, outq, inq):
  28.         self.outq = outq
  29.         self.inq = inq
  30.  
  31.         # This is the tricky bit, we get the socket FD of the
  32.         # underlying pipe from the queue object.  We hope that the
  33.         # internal reader variable doesn't change.
  34.         fd = inq._reader.fileno()
  35.  
  36.         # This tells GTK to watch this FD and notify us when data is
  37.         # available.  We use newer API, gdk_input_read is deprecated
  38.         gobject.io_add_watch(fd, gobject.IO_IN, self.update)
  39.         gtk.main()
  40.  
  41.  
  42. def counter(inq, outq, interval):
  43.     count = 1
  44.     again = True
  45.     while again:
  46.         print("Putting %s on queue" % count)
  47.         outq.put(count)
  48.         count += 1
  49.  
  50.         try:
  51.             print("Reading from queue...")
  52.             ret = inq.get(True, interval)
  53.             if ret == "quit":
  54.                 print("Got quit message")
  55.                 again = False
  56.         except Queue.Empty:
  57.             # Timed-out, carry on
  58.             pass
  59.  
  60.  
  61. if __name__ == "__main__":
  62.     q1 = multiprocessing.Queue()
  63.     q2 = multiprocessing.Queue()
  64.  
  65.     proc = multiprocessing.Process(target=counter, args=(q1, q2, 1,))
  66.     proc.start()
  67.  
  68.     ui = UI()
  69.     ui.main(q1, q2)
  70.  
  71.     proc.join()

Obviously if the underlying implementation variables change this will break; hopefully a more standard way of getting at this information will be added to the API.

  1. Archives

  2. Categories

  3. Twitter

    • Just got pictures of the earthquake damage from my sister in Kaiapoi. Real "the ground opened up" stuff. 46 minutes ago
    • Ooo, the beta of Angry Birds is out on Android. 18 hours ago
    • Released a new version of my Android Internode widget; fixes the problem with Internode's new SSL cert. 23 hours ago
    • @wangjammer5: Cool, here's something to get you started: http://is.gd/eT33b :) 1 day ago
    • So, if iTune Ping is Apple's social network will the perpetual Apple tweet circle-jerk move there now? 1 day ago

  4. RSS Google Reader Shared Items