# 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>splitLoot</hask> 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 <hask>leftovers /= 0</hask>). Then, we examine each partition of the jewels into two sets <hask>mine</hask> and <hask>restOfJewels</hask>. For each <hask>mine</hask> that adds up to a fair share, we attempt division of <hask>restOfJewels</hask> among the rest of the people. |
||

− | |||

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

− | |||

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

== Examples == |
== Examples == |
||

Line 57: | Line 47: | ||

else mzero |
else mzero |
||

</haskell> |
</haskell> |
||

+ | |||

+ | |||

+ | == 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>splitLoot</hask> 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 <hask>leftovers /= 0</hask>). Then, we examine each partition of the jewels into two sets <hask>mine</hask> and <hask>restOfJewels</hask>. For each <hask>mine</hask> that adds up to a fair share, we attempt division of <hask>restOfJewels</hask> among the rest of the people. |
||

+ | |||

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

+ | |||

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

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