A record-breaking run of high temperatures in Sydney, broken air conditioning, wifey’s odd work schedule, and a handful of things to deal with at once at work conspired last week to suppress any motivation I may have had to do any programming at home.
…although, okay, I did update a couple of my toy Go programs to work with the changes to channel syntax. I forget sometimes that Go is still quite firmly in the early-adopter stage.
Right. So. I’ve been writing my standard hello-world Sudoku solver in Go. It reached a plateau about a week ago when some changes that I thought were going to make it faster actually made it slower. I think I did something to a function that stopped the compiler inlining it. Or something. The point is that I was getting diminishing returns from incremental improvements to the current code.
The next step is to add some concurrency. At the moment it does some steps in parallel in the puzzle-generation stage, but it’s still solving a single grid serially. (The general algorithm is: solve an empty grid; then visit each square, and clear it if the resulting puzzle still has a unique solution. Right now, the check for a unique solution (or rather, the search for other solutions, which is expected to fail) is happening in several goroutines.)
The approach I used with the Java version was to keep partial solutions in a priority queue, ordered by the number of squares filled (so that the next one out of the queue is the most complete). These were farmed out to a thread pool. The result was a more-or-less depth-first search of the solution space. For reference, the thread manager code is here. (IIRC, there’s a bug in it somewhere – it doesn’t terminate properly.)
Concurrency is one of the things that’s supposed to be nice in Go. The basic approach I’m going to take for the priority queue is to have two channels, tied together by a goroutine that reads items from the “in” channel, puts them into a heap, then pops from the heap and writes to the “out” channel.
This morning I knocked together the code to do this in abstract. (Well, with ints, anyway. I’ll try to abstract out the type before using it for the Sudoku stuff. Generics would be nice here – generics are one of the longest-standing items on the wishlist for Go – but I think I can see a Go-like way of doing it regardless…) There are some funny corner cases with blocking – it needs to read eagerly enough from the “in” channel that things don’t just pass through, but not so much that it starves the “out” channel – and I’m not sure I’ve got the most parsimonious version yet, but it seems to work. And compared to the Java version, it really is quite pretty. Okay, okay, it might be a bit messier by the time I add a couple of other things needed by the Sudoku solver.
(As an almost-related aside, I’m still tweaking my Go Sudoku solver. More on that later.)
So, after a bit of discussion, we decided to try to mess with it by feeding it invalid puzzles. Here’s one of the tests I tried – note the 4 in the upper-left block, which should be a 3.
What Goggles detected is below. Note that the 4 in question is there, but it’s missed a few numbers elsewhere in the puzzle.
It solves this version quite happily. At first I thought it was cheating by overwriting some of the original cells, until I noticed the gaps. I tried it again a few times, keeping the camera as steady as possible and cropping out other distractions; it detected a different subset of the numbers each time, so I started to think that the OCR was a bit flaky. But it always seemed to detect a valid puzzle… and when I tried it with the original valid puzzle, it detected everything.
It seems like Goggles doesn’t just recognise any old 9×9 grid of numbers as a Sudoku puzzle; it will only recognise a valid Sudoku puzzle as a Sudoku puzzle. My theory is that when it looks at the invalid Sudoku, its best match for it is a valid Sudoku with fewer numbers, plus some noise where its OCR thought there was probably a number but wasn’t quite as confident – as though, for example, there was some dust on the lens in front of those squares. (Most of the time it seemed to drop 1s, which have fewer obvious features than other numbers and are hard to distinguish from 2s.)
The interesting thing about this is that a naïve implementation (i.e. what I’d probably do) would OCR the grid first, set that in stone, then feed it into a Sudoku solver/validity-checker. Google’s implementation seems to tie more organically into however its recognition engine works (from this very limited set of tests anyway) – i.e. the space of objects it recognises includes all valid Sudoku puzzles. Somehow.
A few orders of business heading into the new year…
My resolution for 2010 to learn to use Emacs properly remains unfulfilled. Despite my flirtation with Eclipse, I’m now back with Emacs and will probably stay there unless I do something Java-related. Eclipse is just too bulky and all-encompassing – my mentality is starting to drift back towards the Unix-y toolset approach. (Yes, I just used Emacs as an example of a tool that isn’t bulky. Shut up.)
In an earlier paper, I divided the tasks in building software into essence and accident. (This Aristotleian language is not to denigrate the accidental parts of software construction. In modern language the terms would more understandably be essential and incidental.) The part of software building I called essence is the mental crafting of the conceptual construct; the part I called accident is its ZZZZZZZZZzzzzzzzzzzzz…….
This was a bit disappointing to someone with fond, formative and possibly – I worried, briefly – rose-coloured recollections of The Mythical Man-Month. It was a tough enough slog that a chapter and a half into The Design of Design (and they’re short chapters) I left it on my bedside table for a week to gather dust and guilt.
Tonight I got through to the end of chapter 3, and the tone is… different.
If you feel inclined to tackle this book, I think one way to approach it is to think of the first two chapters as Brooks leading us through Understanding Poetry, by Dr J. Evans Pritchard, Ph.D.
Chapter 3 is where Brooks chimes in and calls it excrement.
Obviously I’m not very far into the book yet, so if I do have a review it’ll come much later, but for a bit of flavour I just want to quote the very end of chapter 3:
The Waterfall Model is wrong and harmful; we must outgrow it.
Two books arrived from Amazon this morning, the first batch of a shipment of eleven. (This is our effort to take advantage of the strong Australian weak American dollar). By slight coincidence they’re both collections of essays by or interviews with programmers:
The downside of ordering a big load of books at once is that I’ll probably lose momentum at some point, and half of them will sit on the shelf for years. This is arguably too high a cost for saving a little money on shipping and effort on picking them up from the post office.
Maybe it’s time to get a Kindle.
Maybe the time to get a Kindle was before I ordered all these books.
I said at the end of my sort-of review of Effective Java that a few things bugged me while reading it, not about the book, but about Java itself. These aren’t totally well-formed in my head, so I’m going to try to write them down in an attempt to get them to make sense. This may or may not work. Stay with me here.
I’m going to flick through the book to refresh my memory of stuff, so my thoughts will roughly follow the same order as the book, if you want to follow along.
Ah, here we go. A recommendation from chapter 2 (and the first itemised piece of advice in the book).
Item 1: Consider static factory methods instead of constructors
The gist of this is that constructors have some drawbacks. To name a few: they don’t have descriptive names; they always create a new object, where you might want to reuse an existing one; and they’re forced to return an object of that class, where you might want to use a subclass. Wrapping it in a static factory method gives you control over these things, and by making the constructor private or protected you can make the factory method the primary way for an API user to get a new object.
So, good advice. But there’s a little guy in the back of my head (you know the guy) who starts whispering little subversive things at points like this. He’s always yammering on about something, so it’s usually easy to ignore him, and I wasn’t really listening to him when I was only up to chapter 2… but by the time I was halfway through the book he’d said sensible things enough times in a row that I sort of started paying attention. Anyway, here’s what he said here:
Shouldn’t a language feature called a constructor support the ways that someone might want to construct an object? Why are we being advised to work around it?
Now, look, there are plenty flaws in that argument – the advice is that you consider using it where appropriate, not that constructors are always bad; and nowhere is it written that a language feature has to be usable from anywhere in its raw form for it to be useful. So the little guy hasn’t scored any points yet.
But keep this in mind. Later on (if I stay interested enough in the topic to keep writing about it) we’ll come back to why the little guy’s point was deeper than I realised at the time.
Okay, moving on. The next Item is about using an intermediate builder object when there are a lot of constructor parameters, especially if some of them are optional. There’s a comment in this section that I want to quote because it sort of sums up what my poorly-structured rant is about, albeit bluntly, and from a slightly different direction.
The Builder pattern simulates named optional parameters as found in Ada and Python.
And, I’ll add, most Lisp dialects, C#, Scala and, of all things, Visual Basic. Oh, and recent versions of Fortran. (Cheers to Rosetta Code. Also: there are recent versions of Fortran?) I’m not arguing with Bloch here – it’s good advice for writing Java – but if you have to write boilerplate to simulate what other languages give you for free, it might be a hint that the programmer is doing work that really lies in the bailiwick of the compiler.
I’ve clocked slightly more hours writing Java than Python, but the Python hours are more recent. Reading this made me think about closing the book and swearing allegiance to Python. (Apart from the performance problems and lack of type safety. Oh, and I wasn’t reading it with the intent of converting. I was just trying to stay up to date. Seriously. Guido, I’d never leave you.)
I’ll leave it there – only two Items into the book – but to give you an idea of where the rant is heading, here’s a short talk by Rob Pike about Go.
Our family is breaking with our old everyone-buys-a-gift-for-everyone tradition this year and doing Kris Kringle instead. There’s a bit of kerfuffle about how to select names and get word out to everyone; I mentioned to wifey that the cleanest way would be to write a short program to shuffle the names and send each person a private email. This probably isn’t going to happen at this stage, but I might suggest it for next year. (Should go down well.)
In the meantime, it got me thinking about how to deal with people drawing their own name, which anecdotally seems to happen at least once without fail. I brute-forced some statistics, and the probability of someone not drawing their own name in any given run seems to approach e-1:
1: 0 of 1 = zero
2: 1 of 2 = 1 in 2.000000000000
3: 2 of 6 = 1 in 3.000000000000
4: 9 of 24 = 1 in 2.666666666667
5: 44 of 120 = 1 in 2.727272727273
6: 265 of 720 = 1 in 2.716981132075
7: 1854 of 5040 = 1 in 2.718446601942
8: 14833 of 40320 = 1 in 2.718263331760
9: 133496 of 362880 = 1 in 2.718283693893
10: 1334961 of 3628800 = 1 in 2.718281657666
In other words, there’s about a 63% chance that at least one person will pick their own name and have to redraw. (There’s a 1/n chance that it’ll be the last person, which really screws things up.)
One way to avoid this if we end up doing it programmatically – other than re-shuffling until it works – is to shuffle the list of names, then assign everyone to buy a gift for the person after them in the (cyclic) list. This guarantees nobody getting their own name (for n > 1), and also has the property that there are no disjoint sets of people – everyone is in one cycle, rather than, say, two people buying for each other, or some number of larger cycles.
That seems more festive somehow. Also, it’s an actual advantage of doing it the geek way, since I can’t think of a way of doing it manually; which means I might actually be able to convince everyone that it’s a good idea.
Okay, here’s how you’d do to do it manually. Shuffle some playing cards, one for each person. Everyone takes a card, remembers it (without showing anyone), and writes their name on the back. Take the cards back, shuffle them again, and lay them out in a circle, face up. Everyone goes out of the room. One at a time, each person comes into the room (with nobody else watching), finds their own card, picks up the card clockwise from it and reads the name on the back.