Haskell Quiz/Splitting the Loot/Solution TomPlick

Examples

Using the examples from http://www.rubyquiz.com/quiz65.html:

> splitLoot 3 [1..4]
[]

> splitLoot 2 [9, 12, 14, 17, 23, 32, 34, 40, 42, 49]
[[[9,12,32,34,49],[14,17,23,40,42]],[[14,17,23,40,42],[9,12,32,34,49]]]

> head $ splitLoot 3 [1..4]
*** Exception: Prelude.head: empty list

> head $ splitLoot 2 [9, 12, 14, 17, 23, 32, 34, 40, 42, 49]
[[9,12,32,34,49],[14,17,23,40,42]]

Solution

import Control.Monad.List

partitionSet :: [a] -> [([a], [a])]
partitionSet [] = [([], [])]
partitionSet (x:xs) =
    concat [[(x:p1, p2), (p1, x:p2)] | (p1, p2) <- partitionSet xs]

type Distribution = [[Integer]]

splitLoot :: Integer -> [Integer] -> [Distribution]
splitLoot 0 [] = return []
splitLoot 0 _  = mzero
splitLoot numPeople jewels = 
    let (share, leftovers) = (sum jewels) `quotRem` numPeople
    in if leftovers /= 0 
        then []
        else do (mine, restOfJewels) <- partitionSet jewels
                if (sum mine) == share 
                    then do restOfDivision <- splitLoot (numPeople - 1) restOfJewels
                            return (mine : restOfDivision)
                    else mzero

Explanation

partitionSet takes a list and returns a list of ways to divide the set into two. For example, partitionSet [1, 2] returns [([1,2],[]),([2],[1]),([1],[2]),([],[1,2])].

splitLoot operates by trying to take one person's loot from the jewels, then dispersing the remainder to the rest of the people. First, care must be taken that an equal distribution is possible (hence leftovers /= 0). Then, we examine each partition of the jewels into two sets mine and restOfJewels. For each mine that adds up to a fair share, we attempt division of restOfJewels among the rest of the people.

splitLoot uses the list monad; under the list monad, a binding of the form x <- y means roughly that x is to take on each member of the list y, one at a time.

splitLoot returns all solutions; if only one is desired, call head on the result.