# Haskell Quiz/Splitting the Loot/Solution TomPlick

### From HaskellWiki

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

Line 8: | Line 8: | ||

<hask>splitLoot</hask> returns all solutions; if only one is desired, call <hask>head</hask> on the result. | <hask>splitLoot</hask> returns all solutions; if only one is desired, call <hask>head</hask> on the result. | ||

+ | |||

+ | 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: | ||

<haskell> | <haskell> |

## Revision as of 02:46, 26 January 2007

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

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