Gareth Rees — LiveJournal
Below are the 10 most recent journal entries recorded in the "gareth_rees" journal:
[<< Previous 10 entries]
I also blog from time to time at CTC Cambridge, Listen With Others, and Otterly. I re-post everything at garethrees.org, so if you want to read all my posts, you should be following my RSS feed.
You can also find me on Google Plus.
Plan to throw one away|
Exact cover II|
The story so far: I wrote a solver for a generic exact cover problem in Python, and used it to find polyomino tilings. The reason for using Python was because Python’s simplicity, terseness, and flexibility makes it easy to write solvers for other combinatorial problems. ( So let’s have a look at a second problem … )
Karp (1972) introduces the name ‘exact cover’ for the following decision problem:
INPUT: Family Sj of subsets of a set ui, i=1,2,…,t
PROPERTY: There is a subfamily Th ⊆ Sj such that the sets Th are disjoint and ∪Th = ∪Sj = ui, i=1,2,…,t
(The problem being to determine, for an arbitrary input, whether it possesses the property.) Karp goes on to prove that this problem is NP-complete, using a reduction from chromatic number, which has a reduction from satisfiability with at most three literals per clause, which in turn has a reduction from satisfiability, which he proves is NP-complete directly.
( Instances of this problem often arise in the solution of combinatorial problems … )
A performance regression|
So, another day at the customer site, another issue to fix:
Issue 234. Over the past three months, the performance of [PRODUCT] has regressed. In December, at commit 919074d, [TESTCASE] ran in 21 seconds, but now it takes 44 seconds.
The first step is to check that the problem is reproducible (it is), ( and the next is to run a
git bisect to see if there was a bad commit … )
Emacs/Perforce integration: a retrospective|
I’ve been maintaining the Perforce/Emacs integration for a couple of years now, so it’s time for a retrospective. … Perforce and Emacs are tools that I use all day every day, which means that small inconveniences in the integration stand out to me and I can see clearly cases where I have a frequently performed task that deserves some extra automation or assistance. I’m also in a position to check quickly that my change really fixes the problem. ( Here are examples of improvements I’ve made based on this approach… )
The ping that wouldn’t die|
It was Friday afternoon at the customer site and I had completed my tasks for the week. I had implemented the new feature and its test cases, written a design justifying the implementation, and drafted a section of the user manual explaining how to use it, so now I was looking for something else to do. In any large program, there are always things that need fixing, so I poked about in the depths of the issue tracker to see if there were any interesting problems that could be appropriated from the other developers. ( The unluckily numbered and long unsolved issue 13 caught my eye… )
Joe sits in the office of his detective agency in Vientiane, drinking and smoking, watching the rain come down, and reading trashy fiction:
The book was a worn paperback with a garish, colourful cover. It showed a multi-story building in the final stages of collapse, a dusty African street, and people running away from the blast. The book was called Assignment: Africa and, in an only slightly smaller subtitle, announced it as the third title in the series Osama Bin-Laden: Vigilante. The unlikely named of the author was Mike Longshott.
A woman comes into in Joe’s office with a job for him:
At last, she said, ‘I want you find him,’ and her fingers caressed the book; he couldn’t put a name to the look she had in her eyes then; he thought she looked lost, and sad, and a little vulnerable.
‘Mike Longshott,’ she said.
( What follows is a pastiche of the hard-boiled detective genre... )
The Quantum Thief|
Jean le Flambeur, gentleman thief, is sprung from prison by the beautiful Mieli, who persuades him to undertake one last job. Author Hannu Rajaniemi works hard to obscure the familiar outline of this hoariest of heist plots, by layering on the worldbling with a trowel:
The hidden Sobornost tech beneath the Oortian sapphire coral wakes up. The spidership reconfigures itself. The scattered modules pull themselves together along their tethers and fuse together into a tight, hard cone. The q-dot winglets transform from a perfectly reflective material into a diamond-hard firewall. Just in time, before the Archon’s nanomissiles hit.
I do like the experience of being confronted by a complex fictional world and having to make sense of it. ( But I also like to feel that there is in fact some sense to be made, and in this novel I frequently failed to make it. )
In ‘Completion annotations’, I illustrated the interactive completion feature in Emacs with a screenshot showing what happens if you type M-x set-cursor-color RET Dark TAB: you get a
*Completions* buffer containing the colour names starting with ‘Dark’. Nick Barnes posted a comment pointing out a potential usability improvement:
It would be nice to have a bit more control still, so that (for instance) when completing on colour names one could see the colours.
To do this, just evaluate the following expression:
(dolist (c (defined-colors))
(put-text-property 0 (length c) 'face `(:foreground ,c) c))
and then run any command that prompts you to pick a colour, for example
read-color. ( At this point, if you are used to the way strings work in most programming languages, you ought to be asking yourself, how does this work? )
[<< Previous 10 entries]