Pirates!

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 
         (flatten
            [(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!

About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 84 other followers

%d bloggers like this: