# Haskell Quiz/Splitting the Loot/Solution TomPlick

### From HaskellWiki

< Haskell Quiz | Splitting the Loot(Difference between revisions)

## Latest revision as of 02:49, 26 January 2007

## [edit] 1 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]]

## [edit] 2 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

## [edit] 3 Explanation

partitionSet

partitionSet [1, 2]

[([1,2],[]),([2],[1]),([1],[2]),([],[1,2])]

splitLoot

leftovers /= 0

mine

restOfJewels

mine

restOfJewels

splitLoot

x <- y

x

y

splitLoot

head