Haskell Quiz/Splitting the Loot/Solution TomPlick

From HaskellWiki

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

Current revision

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

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

3 Explanation

partitionSet

takes a list and returns a list of ways to divide the set into two. For example,

partitionSet [1, 2]

returns

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

splitLoot

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

leftovers /= 0

). Then, we examine each partition of the jewels into two sets

mine

and

restOfJewels

. For each

mine

that adds up to a fair share, we attempt division of

restOfJewels

among the rest of the people.

splitLoot

uses the list monad; under the list monad, a binding of the form

x <- y

means roughly that

x

is to take on each member of the list

y

, one at a time.

splitLoot

returns all solutions; if only one is desired, call

head

on the result.

Retrieved from "http://www.haskell.org/haskellwiki/Haskell_Quiz/Splitting_the_Loot/Solution_TomPlick"

Category: Haskell Quiz solutions

@@ Line 1: / Line 1: @@
 [[Category:Haskell Quiz solutions|Splitting the Loot]]
-<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>.
+== Examples ==
-<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.
+Using the examples from http://www.rubyquiz.com/quiz65.html:
-<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.
+<haskell>
-<hask>splitLoot</hask> returns all solutions; if only one is desired, call <hask>head</hask> on the result.
+> 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]]
+</haskell>
+== Solution ==
 <haskell>
@@ Line 32: / Line 47: @@
                     else mzero
 </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.

Personal tools

Views