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.

Current affairs programs suck

July 8th, 2008 | Filed under Misc | Leave a comment

I've been importing my old mail into Gmail and discovering some interesting snippets I'd all but forgotten. The following is from a mail I sent a friend when I was the lead programmer for a startup in 2000 doing mortgage brokering online:

One interesting event was that we appeared (for free) on a current-affairs program in various cities one night. [Note: It was "Today Tonight".] That was mental. They saw one of our press-releases about the "true cost of your mortgage", and thought it would make a good piece. We basically wrote the thing for them and supplied all the people that told their 'story' on it. Lesson: when you see an 'expose', ask who stands to benefit from it. Worked for us though. After it aired somewhere between 4000-8000 people logged onto the site *at the same time*.

Caveat Spectator.

The Economist on boomers and bubbles

May 18th, 2008 | Filed under Misc | Leave a comment

My old team-leader Scott "Satan" MacGibbon pointed out a couple of Economist articles that touch on some of the things I've been thinking about...

The first article is on the migration to less centralised and specialised workplaces. Most of it is another variation on the "Starbucks is the new cubicle" theme that seems to be discovered by journalists every couple of months, but I found the discussion on the revival of "Third Places" interesting, not least because I hadn't actually encountered the term before.

The other is a short and (for the Economist) to-the-point article on the further damage that the boomer retirement wave of housing sales may do to the already seriously-wounded US property market. Most of it is along the line of the points I made below, in that the same logic applies in the Australian market, maybe even more so given that the investment property has been the preferred method of salting something away for the future for some time now. However his paragraph caught my eye:

Suburbs, which swelled with the baby-boomers, may begin to decline. If the building industry contracts, home prices may remain more stable. Or developers may switch to serving the old, building more compact housing near amenities. Towns may make new efforts to attract immigrants, who already accounted for 40% of the growth in homeownership between 2000 and 2006.

Unfortunately what the article fails to address is how this will interact with the rising cost of private transportation caused by peak-oil (or the less hysterical "plateau-oil", as John Quiggin terms it). My first thought is that there are two ways this can play out; rising costs will further speed the collapse of the suburban lifestyle, or they will force the accommodation of more flexible work conditions. But there is another factor; the most remarkable effect of the changes in the oil market is likely to be in food production. There is already a recognition that most of the food we eat travels are ridiculous distance to our plates (supposedly ~2,500Km on average, although I can't find a source for that). This may cause a fundamental change in the way we live as it becomes more economical to move closer to the centres of food production. This in turn may revitalise the currently bland and homogeneous environment of the suburban tracts; it's possible that in the end the suburbs may become the country villages of the 21st century.

The grey tide, the future of the Australian workplace and the pain of renting

May 8th, 2008 | Filed under Misc | 1 comment

Last November I posted the following to a private mailing-list in a discussion on telecommuting:

My feeling is that such arrangements will become more common in the future. The reasoning behind this is that as Australia's population ages there will be an increasing shortage of skilled knowledge workers, and consequently working conditions will become more negotiable. Add to this the likely gradual increase in oil prices (reflected at the pump) and the continuing high cost of property near the city and this option will be attractive to many employees.

If the above holds (and I may very well be wrong) then this will start to really kick-in in 2010 (when the baby-boomers start to retire), peaking around 2015. But we're already starting to see some of the effects, with companies going to lengths to hire and retain younger employees ....

The Australian Financial Review today had a article (paywalled so no link) on the coming hiring crisis that reflects a lot of what I've said there. Particularly interesting is this quote from the Terence Budge of the Australian Institute of Company Directors:

This generation want to live where they work and not just be in the office from nine to five ... They want to do some work over a coffee at the cafe, something else on their laptop at night ...

I think this problem is going to see a lot more attention over the next couple of years, and is going to have other side-effects that are as yet unseen. Certainly it is going to affect the tools that are used by these increasingly mobile workers; SaaS, wikis and other manifestation of the internet-as-the-platform are likely to have an even greater uptake than we are already seeing.

Another quote that caught my eye is this from Craig Perrett of act3:

Mr Perrett said only about 25 per cent of workers at retirement age believed they could afford to retire and many were rejecting the traditional notion of retirement.

If it is true that 75% can't afford to retire then this is going to have some huge implications. The first one that springs to mind is that unless these underfunded retiree's are prepared to work full time they are going to have to find money from somewhere, and for most the only significant asset they have is their home. This will lead to a glut of housing entering the market in the medium term. Ultimately this and the decentralisation of the workplace could have a far greater effect on the Sydney housing crisis than government intervention.

Sudden huge debt

January 15th, 2008 | Filed under Misc | 2 comments

So today, after a mad 24-hour deadline to deliver a bank-cheque (not helped by a crashed bank network) myself and Maree officially took ownership of our first home:


House Front
Ya ain't in Newtown anymore, boy!

We've bought up in Katoomba, for two main reasons:

  • This is where we eventually want to live
  • This is where we could afford

Lets call it one of life's fortuitous coincidences that these two things came together.

The first reason probably doesn't need much explanation; the Blue Mountains is a World Heritage listed area, recognised for its beauty and culture, and last year became recognised as a Cittaslow area. Katoomba itself is a small but vibrant town with many of the benefits of Newtown, not least the cafes and other eateries. Given I have a long history of burning myself out at work I had promised Maree (and myself) that I would work towards getting a better work/life balance and this is a key part of that plan (the move from military projects to the more healthy environments of Vislab and Atlassian were the first steps in that direction).

The financial aspect should be fairly obvious to anyone who's lived in Sydney in recent years; it's just too expensive to buy unless you're prepared to go into deep debt for a long time. Given I have a deep life-long aversion to debt this wasn't really an option for us. Although the price difference between Sydney and Katoomba isn't as big as it has been in the past, the few-hundred thousand saved can make a huge difference to the length of the loan; this is because the initial deposit will take up a larger proportion of the total cost (assuming you've actually been saving of course), meaning you get to the tipping point much faster:


What we'd be paying if we followed the rules
What we'd be paying if we followed the rules (red being interest)

Add to this that I'm playing some games with full-offset accounts and we have a best-case scenario of completely owning the property in under 4 years*. Of course, in Katoomba you also get a hell of a lot more for your money; 1000m² at the end of a tree-lined street 5 minutes from the station in our case.

A more interesting question (at least to me) is "Why now?". The recent over-heated market aside, property rarely out-performs the shares market so logically we should invest elsewhere for now and then purchase nearer the time. The reasoning goes like this:

Australia is getting older. This is an accepted fact now, and is of some concern to economists and politicians (the latter of which are starting to realise what a giant ponzi-scheme has been going on for decades). This is going to come to a head in the next few years, specifically 2010-2015 (the period when the baby-boomer generation start retiring**). One of the side-effects of this is that a large number of people currently living in the city and suburbs are going to start migrating out to the sea-change and tree-change areas. This in turn will drive up the prices, possibly to the level of the city (if this seems excessive check out the property prices in Leura some time). (There's a related effect to do with pay and work conditions for those left-behind in the workforce, but that's probably wandering too far off topic; Ross Gittins has written about this in his book.)

Given all this it seemed prudent to buy now rather than later before the market heats up.

Of course, it goes without saying that I could be completely fucking wrong about all of this.

The bigger question now is how to manage the distance to the city. Some people at Atlassian do commute from the mountains but I'm not sure we can handle that. Longer term I would like to come to an arrangement where I can work from home most of the time, but in the interim we're going to try it for six-months or so while keeping a rental place in the city; if it we can't keep it up we'll have to rent the house out for a few years before making the final move.

So all that remains now is to start moving our stuff up to the new place and get settled in. There's also some work and minor improvements to be done over the next couple of months so that will be taking up a lot of my weekends. All-in-all I have an odd feeling of adulthood about me, which is probably about 10 years late now.

* There's a strong case to be made that paying-off your mortgage quickly is not always the best option. One advantage of using a full-offset account to rapidly pay off the mortgage is that the principal is still available to us, so we can change this tactic later if we wish.

** I'm working on the assumption that the 1968 "Summer of Love" was the peak of the baby-boomer's coming-of-age (i.e. turning 18-21); some believe we'll start seeing the effects even sooner.

Usyd positions feed updated

October 7th, 2007 | Filed under Misc | Leave a comment

Back when I worked at Vislab I wrote a quick and dirty script that generated an RSS feed from the University of Sydney jobs page, mainly to suggest jobs to my girlfriend (who at that time worked in the Faculty of Arts and was looking for alternatives). Since I left bit-rot had set in and it stopped updating; I didn't care, both of us had moved on to other things.

However the other day I suggested to a friend they look at University jobs and realised I should probably reinstate the feeds. The problem is that University jobs are generally not advertised on boards such as Seek and have the be checked manually, and the lack of feeds makes this situation worse. As a bonus I've also added a basic feed for UWS as that's what the original conversation was about; I may add more later, time permitting. The current crop of feeds can be found in this directory, or use the links below:

More weekend lisp hacking: serve-event for ECL

October 2nd, 2007 | Filed under Lisp | Leave a comment

Some time ago I wrote a single-threaded server implementation in SBCL using its serve-event abstraction. However recently I've been working with ECL, which has some interesting possibilities due to its small size. However currently there is no abstraction of non-blocking IO, so I spent a bit of time porting the SBCL/CMUCL serve-event across. The hardest part about this was working out how to declare opaque C-structs with ECL lisp blocks in a robust way. In the end the old stalwart unsigned-char that saved the day, a technique I've documented elsewhere. But without further ado, the code:

(Update: This is now in ECL trunk; you can view an updated version here)

PLAIN TEXT
Lisp:
  1. (defpackage "serve-event"
  2.   (:use "CL" "FFI" "UFFI"))
  3. (in-package "serve-event")
  4.  
  5. (clines "#include <sys/select.h>")
  6.  
  7. (defstruct (handler
  8.             (:constructor make-handler (direction descriptor function))
  9.             (:copier nil))
  10.   ;; Reading or writing...
  11.   (direction nil :type (member :input :output))
  12.   ;; File descriptor this handler is tied to.
  13.   ;; FIXME: Should be based on FD_SETSIZE
  14.   (descriptor 0)
  15.   ;; Function to call.
  16.   (function nil :type function)
  17.   ;; T if this descriptor is bogus.
  18.   bogus)
  19.  
  20.  
  21. (defvar *descriptor-handlers* nil
  22.   #!+sb-doc
  23.   "List of all the currently active handlers for file descriptors")
  24.  
  25.  
  26. ;;; Add a new handler to *descriptor-handlers*.
  27. (defun add-fd-handler (fd direction function)
  28.   "Arrange to call FUNCTION whenever FD is usable. DIRECTION should be
  29.   either :INPUT or :OUTPUT. The value returned should be passed to
  30.   SYSTEM:REMOVE-FD-HANDLER when it is no longer needed."
  31.   (unless (member direction '(:input :output))
  32.     ;; FIXME: should be TYPE-ERROR?
  33.     (error "Invalid direction ~S, must be either :INPUT or :OUTPUT" direction))
  34.   (let ((handler (make-handler direction fd function)))
  35.     (push handler *descriptor-handlers*)
  36.     handler))
  37.  
  38. ;;; Remove an old handler from *descriptor-handlers*.
  39. (defun remove-fd-handler (handler)
  40.   #!+sb-doc
  41.   "Removes HANDLER from the list of active handlers."
  42.   (setf *descriptor-handlers*
  43.         (delete handler *descriptor-handlers*)))
  44.  
  45. ;;; Add the handler to *descriptor-handlers* for the duration of BODY.
  46. (defmacro with-fd-handler ((fd direction function) &rest body)
  47.   "Establish a handler with SYSTEM:ADD-FD-HANDLER for the duration of BODY.
  48.    DIRECTION should be either :INPUT or :OUTPUT, FD is the file descriptor to
  49.    use, and FUNCTION is the function to call whenever FD is usable."
  50.   (let ((handler (gensym)))
  51.     `(let (,handler)
  52.        (unwind-protect
  53.            (progn
  54.              (setf ,handler (add-fd-handler ,fd ,direction ,function))
  55.              ,@body)
  56.          (when ,handler
  57.            (remove-fd-handler ,handler))))))
  58.  
  59.  
  60. (defmacro fd-zero(fdset)
  61.   `(c-inline (,fdset) (:object) :void
  62.              "FD_ZERO((fd_set*)#0->foreign.data)"
  63.              :one-liner t
  64.              :side-effects t))
  65.  
  66. (defmacro fd-set (fd fdset)
  67.   `(c-inline (,fd ,fdset) (:int :object) :void
  68.              "FD_SET(#0, (fd_set*)#1->foreign.data);"
  69.              :one-liner t
  70.              :side-effects t))
  71.  
  72. (defmacro fd-isset (fd fdset)
  73.   `(c-inline (,fd ,fdset) (:int :object) :int
  74.              "FD_ISSET(#0, (fd_set*)#1->foreign.data)"
  75.              :one-liner t
  76.              :side-effects t))
  77.  
  78. (defun fdset-size ()
  79.   (c-inline () () :int "sizeof(fd_set)" :one-liner t :side-effects nil))
  80.  
  81.  
  82. (defun serve-event (&optional (seconds 0))
  83.   "Receive pending events on all FD-STREAMS and dispatch to the appropriate
  84.    handler functions. If timeout is specified, server will wait the specified
  85.    time (in seconds) and then return, otherwise it will wait until something
  86.    happens. Server returns T if something happened and NIL otherwise. Timeout
  87.    0 means polling without waiting."
  88.  
  89.   ;; fd_set is an opaque typedef, so we can't declare it locally.
  90.   ;; However we can fine out its size and allocate a char array of
  91.   ;; the same size which can be used in its place.
  92.   (let ((fsize (fdset-size)))
  93.     (with-foreign-objects ((rfd `(:array :unsigned-char ,fsize))
  94.                            (wfd `(:array :unsigned-char ,fsize)))
  95.       (fd-zero rfd)
  96.       (fd-zero wfd)
  97.  
  98.       (let ((maxfd 0))
  99.         ;; Load the descriptors into the relevant set
  100.         (dolist (handler *descriptor-handlers*)
  101.           (let ((fd (handler-descriptor handler)))
  102.             (ecase (handler-direction handler)
  103.               (:input (fd-set fd rfd))
  104.               (:output (fd-set fd wfd)))
  105.             (when (> fd maxfd)
  106.           (setf maxfd fd))))
  107.  
  108.         (let ((retval
  109.                (c-inline (rfd      wfd    (1+ maxfd) seconds)
  110.                          (:object :object :int       :int) :int
  111.                          "{ struct timeval tv;
  112.                             tv.tv_sec = #3;
  113.                             tv.tv_usec = 0;
  114.                             @(return) = select(#2, #0->foreign.data,
  115.                                                    #1->foreign.data,
  116.                                                    NULL, &tv); }"
  117.                   :one-liner nil
  118.                   :side-effects t)))
  119.       (cond ((zerop retval) nil)
  120.             ((minusp retval)
  121.              (error "Error during select"))
  122.             (t
  123.              (dolist (handler *descriptor-handlers*)
  124.                (let ((fd (handler-descriptor handler)))
  125.                  (if (plusp (ecase (handler-direction handler)
  126.                               (:input (fd-isset fd rfd))
  127.                               (:output (fd-isset fd wfd))))
  128.                      (funcall (handler-function handler)
  129.                               (handler-descriptor handler))))))))))))
  130.  
  131.  
  132. ;;; Wait for up to timeout seconds for an event to happen. Make sure all
  133. ;;; pending events are processed before returning.
  134. (defun serve-all-events (&optional (timeout 0))
  135.   "SERVE-ALL-EVENTS calls SERVE-EVENT with the specified timeout. If
  136. SERVE-EVENT does something (returns T) it loops over SERVE-EVENT with a
  137. timeout of 0 until there are no more events to serve. SERVE-ALL-EVENTS returns
  138. T if SERVE-EVENT did something and NIL if not."
  139.   (do ((res nil)
  140.        (sval (serve-event timeout) (serve-event 0)))
  141.       ((null sval) res)
  142.     (setq res t)))
  143.  
  144.  
  145. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  146. ;; Test Example
  147. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  148.  
  149. ;; (defun test-stdin ()
  150. ;;   (format t "DOING STDIN~%")
  151. ;;   (with-fd-handler (0 :input #'(lambda (fd) (declare (ignore fd))
  152. ;;                                        (format t "Got data~%")
  153. ;;                                        (read-char)))
  154. ;;     (loop ;; FIXME: End condition
  155. ;;        (format t "Entering serve-all-events...~%")(force-output)
  156. ;;        (serve-all-events 5)
  157. ;;        (format t "Events served~%"))))

I've submitted a patch to the ECL list, and there's been some interest in integrating it so it should be part of it soon.

Update: This was added in the ECL 0.9j release.

Robust backups

October 1st, 2007 | Filed under Misc | 1 comment

Jamie Zawinski has just posted some instructions on a basic backup scheme. While the general advice is good, there are a couple of improvements that could be made, so I thought I'd describe my home backup system.

The main problem the the rsync script Jamie posted is that if you accidentally delete some important files the next time your backup runs rsync will delete the backups of those files. This is due to the --delete command. The obvious solution is to remove that option, but that will tend to leave a very messy filesystem over time. My preferred solution is to use the --backup and --backup-dir options to create a simple form of incremental backup. My script looks like this:

PLAIN TEXT
Bash Script:
  1. dir=/media/backup
  2. stamp=`date +'%Y%m%d'`
  3. bdir=$dir/.incremental.$stamp
  4.  
  5. rsync -Pav --backup --backup-dir=$bdir --delete-after \
  6.      /home /etc /usr/local /opt \
  7.      --exclude-from=/home/ssmith/.backup-exclude  \
  8.     $dir

Note that my script doesn't do a full-drive image like Jamie's as I don't find that important. Also, my script excludes some files I don't care about (i.e. can replace easily). Regardless, the principle is the same.

However this doesn't cover the house-burns-down scenario. Obviously the above script could easily be used with a drive you then bring to work as with JWZ's suggestion. But in my experience you will simply never do that.

The solution? I use a near-identical script to backup to a remote host. If you already have a machine somewhere you can use that, or there are many remote backup services, some of which have a direct rsync service. While the initial upload will be pretty large the subsequent incremental uploads will be much quicker, especially if you have ADSL2+, which has 1Mbit uploads. The cool part is that this leverages the uploads-are-free aspect of most Australian ISPs.

The only issue with this is that your data is possibly exposed to third-parties. My normal solution to this is to place any critical data in a directory that is encrypted using encfs. However I'm now having a look at Duplicity as an alternative, which works in much the same way but has GnuPG signing and encryption. It also supports more protocols, such as webdav and Amazon's S3 service.

  1. Archives

  2. Categories

  3. Twitter

  4. RSS Google Reader Shared Items