# Haskell Quiz/Splitting the Loot/Solution TomPlick

### From HaskellWiki

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

Line 1: | Line 1: | ||

[[Category:Haskell Quiz solutions|Splitting the Loot]] |
[[Category:Haskell Quiz solutions|Splitting the Loot]] |
||

+ | |||

+ | == Explanation == |
||

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

Line 8: | Line 10: | ||

<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. |
||

+ | |||

+ | == Examples == |
||

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

+ | |||

+ | <haskell> |
||

> splitLoot 3 [1..4] |
> splitLoot 3 [1..4] |
||

Line 23: | Line 29: | ||

[[9,12,32,34,49],[14,17,23,40,42]] |
[[9,12,32,34,49],[14,17,23,40,42]] |
||

− | Solution: |
+ | </haskell> |

+ | |||

+ | |||

+ | == Solution == |
||

<haskell> |
<haskell> |

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

## 1 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

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

## 3 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