December 20, 2010
On the train back from the Me_tail Christmas do, Duncan (our Research Director) set this fun problem. It’s actually a slight misremembering of a puzzle with slightly different conditions, but I think the differences make it more fun to solve computationally.
A pirate king dies, leaving his accumulated booty of 100 gold dubloons. His 5 sons gather to drink to his memory and share out the treasure. The old king’s first mate reads out the will:
“Aaarrrr! My eldest son will propose a division of this booty. If this be accepted by a majority vote, then it goes. If not, cut him into collops, and give the decision as to how to divide to the eldest surviving son. Rinse and repeat. Arrrrrr!”
What division does the eldest son propose?
You can assume that pirates are both perfectly rational but extremely bloodthirsty: if they have two choices with an equal amount of material gain, they’ll go for the one that involves killing a brother. The pirate proposing the split gets a vote. A tied vote is not a majority, as the British electorate should be well aware
The fun, of course, is to write a program that generalizes this to any number of pirates, whence you could work out what the maximum number of sons that can survive is.
If my blog had a larger or avid readership, I might leave this out there for a couple of days to see if someone posted a solution. But it doesn’t, so here it is. Solution by induction in clojure (of course): -
(:require [clojure.contrib.math :as math]))
(defn votes-required [n]
(math/ceil (/ (- n 1) 2)))
;; Currently doesn't 0 out the unneeded bits of bid.
(defn increased-bid [current-bid votes]
"increment the lowest votes values in current-bid by 1"
(let [[change zero] (split-at votes (sort-by val current-bid))]
[(map (fn [[k v]] [k (inc v)]) change)
(map (fn [[k v]] [k 0]) zero) ]))))
(defn best-bid [current-bid n]
(let [ votes (votes-required n)
rest-of-bid (increased-bid current-bid votes),
remainder (- 100 (reduce + (vals rest-of-bid))),
next-id (keyword (str n)) ]
(if (>= remainder 0)
(assoc rest-of-bid next-id remainder)
;; If he doesn't have enough to give away, he's dead.
(assoc current-bid next-id -1))))
(defn proposal [n]
(if (= 1 n)
(best-bid (#'proposal (dec n)) n)))
(def proposal (memoize proposal))
Comments on / criticism of solution or clojure style more than welcome!
November 19, 2010
at the Haymakers, 18th November.
They have 4 guitars. They rock hard. That would be enough.
They perform really well, and I love the sound. Easily enough to buy some of the music to listen to the lyrics.
An exchange I particularly enjoyed – the lead’s guitarist had packed in.
Lead: “What was it Thoreau said about ‘all our inventions’? ‘Just improved means to unimproved ends’?”
Bass: “This shit’s not plugged in”
Lead: “Oh, yeah.”
Update – they’re awesome. They’ve been on heavy rotation in my playlist for much of the last three months.
I will not deny my humanity
I’ll be rolling in it like a pig in faeces
Because there’s no other integrity
In awaiting the demise of our species
May 17, 2010
Over the last couple of years and from time to time the JISC have asked me to mark grant funding proposals. If you’re asked, and you have the time, I’d recommend it – it’s been the single most useful thing I’ve done in trying to understand the JISC + community mindset, and in improving my own bid writing.
Last week I was marking bids and getting quite frustrated – some bids can be evaluated pretty well on a single read through and then another pass to collect the facts, while others take several read-throughs, and still the bits don’t seem to hang together. By and large, the former scored well and got a positive recommendation for funding. The latter didn’t. I doubt my scores and recommendations will be very different to others’. By the end of the batch of bids I realised that the really important differentiator wasn’t in following a particular structure, GANTT charts or well structured risk assessments (although those things are good to have, and hopefully evince the planning that has gone in to the proposal).
The better bids described what the project was going to do, and why, early on.
As a marker, once you understand what the project is about, you have a mental framework around which to add all the rest of the proposal’s impacts, plans and costs. Even if you don’t agree with the project methodology you can assess whether it’s useful. Most importantly in this day and age: if you don’t know what the project is doing, you can’t judge the likely impact, and if you can’t judge the impact, you can’t judge the value for money.
So here’s some advice for bid writers as a parting shot: your front page abstract (or first para) should be like an elevator pitch. Describe, very clearly and briefly, what your project is going to do, and why it’s a good idea.
P.S. I’ve been as guilty as anyone of getting this wrong, and I’ve written some poor funding proposals. If I were still going to be around, I’d be taking my own advice!
April 21, 2010
I really like the Vote for Policies website. I wasn’t too surprised that when I took the survey I came out with a pretty good fit against the Green manifesto and the Conservative manifesto as well a better fit with the Lib Dems.
Evidently #iagreewithnick, but not all the time.
Chatting with a friend over the weekend, I mentioned the site, and she replied that she couldn’t be bothered: “They never do what they say anyway”. It’s a fair point, and it got me thinking about how you could add a healthy level of cynicism to a policy-based voting model, without giving up on it entirely. In my model, I assume that a political party, once elected, will implement about 30% of the manifesto items I like, and 100% of the manifesto items I dislike. Unless something either wonderful or dreadful happens, I don’t have time to code it up though. Any takers?
Warning: this is a longish post. If you care about the DE Act it will probably be interesting. If you kind-of care about the DE Act, and live in SE Cambs, you might want to skip to the summary.
I’ve been agitated about the Digital Economy Bill. I e-mailed my MP (James Paice, Con) a few of weeks ago asking him to vote against it going into the pre-election wash-up, and again a day before the bill went through, asking him whether he went to hear the second reading and asking him to vote against the bill at the 3rd. He hadn’t turned up for either reading, and didn’t vote either way. He did reply to my e-mail (after the bill passed) though: -
Dear Mr Downing,
Thank you for your further email about the Digital Economy Bill which has now become law. My Party took the decision to seek to remove those clauses of the Bill that we did not support or feel received proper legislative scrutiny, while supporting the Bill as a whole. Rejecting the Bill would have been an unacceptable set-back for the important measures it contains.
You may still be concerned about Clause 18 which attempts to tackle online copyright infringement. This is an extremely serious issue that costs the creative industries hundreds of millions of pounds each year. I want to make sure that Britain has the most favourable intellectual property framework in the world for innovators, digital content creators and high tech businesses and so I support the efforts of the Bill to do this.
The measures in the Bill aimed at tackling online copyright infringement received robust scrutiny in the House of Lords. My Party was concerned about the lack of parliamentary oversight of the original clauses and as such the Bill now has a super-affirmative resolution in it. This means Parliament will debate any order that the Secretary of State lays that would allow people to be disconnected. These measures can also not be introduced for 12 months after the Bill becomes law. This means that we are by no means rushing in to these decisions and that the next Parliament will be able to consider them beforehand.
The measures in the Bill designed to tackle illegal peer to peer file sharing set up a proportionate regime that would, only following public consultation, repeated warnings and due process, lead to people having their internet connection temporarily suspended. It will not, as many have suggested, lead to people being disconnected without an appeal. Even if people are disconnected they will be able to sign up to another ISP immediately without penalty.
While I have no doubt that these measures could have been improved if the Government had allocated time for this Bill to be debated in Committee, blocking these measures in their entirety would have risked hundreds of thousands of jobs in the TV, film, music and sports industries and was therefore not something we were willing to do.
James Paice MP
partyperson’s entitled to their views. I’m really not entirely sure what to read into this and would welcome any explanation or expansion. It seems to me that it doesn’t answer why we need a due process outside the courts. It also seems protectionist, which I’m not keen on, and it implicitly includes the BPI in a list that starts with “innovators”, which isn’t somewhere I’d put them. I’m also mystified by this ability of the disconnected to immediately reconnect with a different provider. Won’t that will just lead to more customer churn and higher ISP charges for everyone? I’m also unconvinced that the creative industry, which employs an estimated 1M people, is in imminent danger of >10% contraction without the DE Act (if it is, in fact, in any danger at all).
So that’s the Tory view, what about the rest?
Since we in the UK have a rare opportunity to feign democracy next month, and this issue is an important one to me, I thought I’d do a bit of inverse canvassing, and find out what all of the potential election candidates for SE Cambs thought of the DE bill. I’m publishing it here because it’s quite probably an important issue for others too (a large proportion of the “silicon fen” workers live and vote in SE Cambs).
Dear Mr ,
As a voter in SE Cambs, I’m keen to know your stance on the recently passed Digital Economy Bill. Will the bill, and / or IP reform feature in your election manifesto?
Not like for like with my interaction with Mr Paice, I grant you, but I feel it fairly reflects the contrast between the unelecteds’ capacity to make vague promises and the elected’s capacity to disappoint, which is what makes elections so much fun. The responses (in order of my receiving them): -
David (on behalf of Daniel Bell) Christian Peoples Alliance
From our website you will see that the CPA favours new responsibilities being placed on ISPs over what they ‘allow’ as traffic to peoples’ homes.
Were there are issues you wanted addressed?
Went to check their website, found stuff about making ISPs responsible for censorship of ‘nasty’ content (e.g. suicide sites) and paedophiles grooming children (in the sense of “stopping”, not “ensuring”…). Not much about copyright materials. Not encouraging, and worth discussing at another time, but let’s stick to our theme. I didn’t particularly want to draw out attitudes to individual issues – I’d really like a representative in parliament who knows what’s important without me having to write to them every verse end. I thought I’d cut the chap some slack though, since the reply had been so prompt.
> From our website you will see that the CPA favours new responsibilities being placed on ISPs over what they ‘allow’ as traffic to peoples’ homes.
Could you send me a link? I can’t find anything that particularly pertains to copyright materials, which is what the contentious parts of the DE bill cover.
> Were there are issues you wanted addressed?
I don’t think so – I’m particularly concerned that the DE bill erodes civil liberties by moving the remedy for a particular civil crime (copyright violation) out of existing process (the courts) and into the hands of some government body. I’m also concerned that the bill represents a protectionist measure and will consequently repress innovation. Furthermore, clause 17 allows the home secretary to extend the scope of bill without due process – hardly democratic!
Came the reply:
To do with blocking worst aspects of pornography. But what you say about the illiberal measures and the assumption of guilt until the consumer proves innocence are ones we share. We’ll need to look closer. Thanks for pointing this out.
… which is about what I expected.
Jonathan Chatfield, Liberal Democrats
Thank you for your email on the Digital Economy Bill.
I believe the Liberal Democrats have the most up-to-date and liberal policy on freedom, creativity and the internet of any of the parties (see our Spring conference emergency motion). That led to our vocal opposition to the web-blocking provisions of the Bill and our MPs voting against the whole Bill at 3rd reading.
Our party’s position is not 100% against everything in the Bill, but we have more concerns than the other parties, and our MPs were the only ones whipped against the Bill at 3rd reading. All the other parties voted for the Bill (even if a few of their rebels did not) and the Lib Dems voted against the Bill.
In my view it is important thing to get as many Lib Dem MPs as possible in the next Parliament because they are web-users’ best safeguard against Labour introducing arbitrary disconnection powers. We are also the only party committed to reforming the voting system and the parliamentary process so that Labour’s railroading of this Bill can never happen again.
With best wishes,
Again, pretty much what I expected.
John Cowan, Labour
Thank you for your email.
Many of the measures of the Digital Economy Bill I welcome most of the measures but am concerned that the penalities against file sharers are a heavy handed.
Heavy-handed? This government? Surely some mistake?
Andy Monk, UKIP
I strongly believe that the Bill should not have been rushed through Parliament during the wash up period before Parliamemnt dissolves. There should have been a proper detailed debate about the bill’s consequences on the British public. Piracy is obviously a crime but the bill goes far further than just trying to address this issue, important though it is.
It is another example of central government bowing to the ever more poweful lobbying of the music/film industry. I don’t believe that the british public will realise that they will be personally responsible for protecting their home computer from hackers etc and can have their web access cutoff. It is a very draconian bill that needs much wider media coverage to address the consequences of the bill.
I believe that only around 5% of MP’s were present at its second reading. That is hardly democracy. If I had been an MP at the time I would have ensured wider press coverage and sought to delay the bill so that it could have been properly debated in a democratic way.
I received no reply from the Green PPC. Since I sent these e-mails I’ve become aware of an independent candidate who I’ll e-mail similarly in due course. I’ll update this post as and when any more info arrives.
Seems to me that if you want to use your vote for someone who will stand against the bits of the DE bill that have resulted from a mixture of lobbying and total technical ignorance, you should vote for Jonathan Chatfield (Liberal) or Andy Monk (UKIP).
March 29, 2010
This came sooner than I had expected, but I’m moving on: I have resigned from the University and will finish working here in the middle of June.
I have had a really interesting few years working in the University, first for the library (but sitting in the computing service) on the DSpace@Cambridge project, then in the Unilever Centre. In the 6 years I’ve been here I’ve worked with, and for, some really great people, and worked on some really interesting projects. In my current position I work with the incomparable Peter Murray-Rust and a bunch of the brightest folks you could hope to work with, on a programme of work I’m interested in because I helped to form it and take it forward. I wake up wanting to go to work. So why the change?
I’ve had a hankering to go back into small business whence I came for a while, and was presented with an opportunity to join another group of bright folk who are developing and delivering exciting new technology for online clothes retail. In June I’ll join Metail (http://www.metail.co.uk/) as lead developer, and move into the role of Head of Technology early next year. I can’t say too much about the business offering yet, or about the details of technology; suffice to say that I’ll have the opportunity to do some hardcore (“decidedly non-trivial”, for the geekwardly minded) algorithmic programming in the medium term, and I relish the challenges that lie beyond it.
It’s going to be an exciting couple of years!
February 16, 2010
I’m running a clojure activity at next week’s dev8d unconference, and going to do some data processing of government data on data.gov.uk. I’ll blog as I prepare.
First thought: Would be nice to get Linked Data right from the front page: -
heresiar:~ ojd20$ curl -I -H "Accept: application/rdf+xml" http://data.gov.uk/
HTTP/1.1 200 OK
Server: Apache/2.2.11 (Ubuntu) PHP/5.2.6-3ubuntu4.5 with Suhosin-Patch mod_ssl/2.2.11 OpenSSL/0.9.8g
Cache-Control: public, max-age=10800
Last-Modified: Tue, 16 Feb 2010 13:42:16 +0000
Expires: Sun, 11 Mar 1984 12:00:00 GMT
Set-Cookie: SESS4559741dbfdd43b9d568f35769e2ec7b=2c14bc12c261aa52e20abbc1fc021464; expires=Thu, 11 Mar 2010 17:15:37 GMT; path=/; domain=.data.gov.uk; HttpOnly
Content-Type: text/html; charset=utf-8
Date: Tue, 16 Feb 2010 13:42:17 GMT
Via: 1.1 varnish
January 5, 2010
“Push and Pull Messaging …” by Sean McGrath is a decision document between push and pull in a service delivery bus designed for the Irish government. Although the application is specific to that system, it also contains a great summary of the rationales one should use when choosing between push and pull. It fell off the web, but the Irish government very helpfully dug it out and gave me permission to re-distribute it.
I’d recommend it particularly to anyone thinking “Should I use SWORD for this system?”.
December 11, 2009
December 2, 2009
At the Cambridge Clojure meetup last night I decided to have a go at something work-related, but that I don’t usually get time for. The OSCAR3 chemistry entity extraction and text-mining tool uses N-Grams to create feature vectors to classify words. It turned out to be pretty short work for
loop...recur, but then Nick Day pointed out that I’d just reimplemented
partition, which turned the function into: -
(defn ngrams [word n] (let [pad (repeat (dec n) \#))] (partition n 1 (concat pad word pad)))) (ngrams "foobar" 3) -> ((\# \# \f) (\# \f \o) (\f \o \o) (\o \o \b) (\o \b \a) (\b \a \r) (\a \r \#) (\r \# \#))