# 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