Personal tools

Haskell Quiz/Splitting the Loot/Solution TomPlick

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
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
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.

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
Retrieved from "http://www.haskell.org/haskellwiki/Haskell_Quiz/Splitting_the_Loot/Solution_TomPlick"

Category: Haskell Quiz solutions