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): –

(ns pirates 
   (: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))]
      (apply sorted-map 
            [(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)
      {:1 100}
      (best-bid (#'proposal (dec n)) n)))
(def proposal (memoize proposal))

(proposal 5)

Comments on / criticism of solution or clojure style more than welcome!