2 files changed, 95 insertions, 0 deletions

diff --git a/AufgabeFFP3.hs b/AufgabeFFP3.hs
new file mode 100644
index 0000000..67519be
--- /dev/null
+++ b/AufgabeFFP3.hs
@@ -0,0 +1,71 @@
+module AufgabeFFP3
+where
+
+import Prelude hiding (filter)
+
+type Weight = Int
+type Value = Int
+type Item = (Weight, Value)
+type Items = [Item]
+
+type Load = [Item]
+
+type Loads = [Load]
+type LoadWghtVal = (Load, Weight, Value)
+type MaxWeight = Weight
+
+safeGet :: [Integer] -> Int -> Integer -- get element of list, default to 0
+safeGet l i
+        | i < length l = l !! i
+        | otherwise = 0
+
+toBin :: Integer -> [Integer] -- get binary representation of integer
+toBin 0 = []
+toBin i = [rem] ++ toBin quot
+        where ( quot, rem ) = quotRem i 2
+
+hasBit :: Integer -> Int -> Bool -- check if the binary representation of a number has the ith bit set
+hasBit num ith = (safeGet (toBin num) ith) == 1
+
+getChoice :: Items -> Int -> Items -- choose a subset determined by binary representation of l
+getChoice l i = concat ( map (choose l) [0..(length l)-1]  )
+        where
+        choose l pos 
+                | hasBit (fromIntegral i) pos = [ l !! pos ]
+                | otherwise = []
+
+generator:: Items -> Loads -- get all possible choices (2^n)
+generator l = map ( getChoice l ) [1..num]
+        where num = (2^(length l)) - 1
+
+transformer :: Loads -> [LoadWghtVal] -- calc sum of weight and value for all lists of items
+transformer l = map trans l
+
+trans :: Load -> LoadWghtVal -- worker of transformer
+trans load = (load, weight, value)
+        where 
+        weight = sum $ map fst load
+        value = sum $ map snd load
+
+getWeight :: LoadWghtVal -> Weight
+getWeight (_, w, _) = w
+
+getVal :: LoadWghtVal -> Value
+getVal (_, _, v) = v
+
+filter :: MaxWeight -> [LoadWghtVal] -> [LoadWghtVal] -- drop those with too much weight
+filter max l = [ x | x <- l, getWeight x <= max ]
+
+selector :: [LoadWghtVal] -> [LoadWghtVal] -- get those with max val
+selector l = [ x | x <- l, getVal x == max ]
+        where max = maximum $ map getVal l
+
+selector1 :: [LoadWghtVal] -> [LoadWghtVal] -- all with max val
+selector1 = selector
+
+selector2 :: [LoadWghtVal] -> [LoadWghtVal] -- get ones with min weight
+selector2 l = [ x | x <- best, getWeight x == min ]
+        where
+        min = minimum $ map getWeight best
+        best = selector l 
+
diff --git a/TestAufgabeFFP3.hs b/TestAufgabeFFP3.hs
new file mode 100644
index 0000000..bbb5fbc
--- /dev/null
+++ b/TestAufgabeFFP3.hs
@@ -0,0 +1,24 @@
+module Main where
+
+import Prelude hiding (filter)
+
+
+import Test.HUnit
+import Control.Monad
+import AufgabeFFP3
+
+cases1 = TestLabel "foo" $ TestList [
+  TestCase $ assertEqual "a" [([(2,7),(2,6)],4,13)] ((selector1 . (filter 5) . transformer . generator) [(5,3),(2,7),(2,6),(10,100)]),
+  TestCase $ assertEqual "b" ((selector1 . (filter 13) . transformer . generator) [(5,3),(2,7),(2,6),(10,100)]) [([(2,7),(10,100)],12,107)],
+  TestCase $ assertEqual "c" ((selector1 . (filter 1) . transformer . generator) [(5,3),(2,7),(2,6),(10,100)]) [],
+  TestCase $ assertEqual "d" ((selector1 . (filter 5) . transformer . generator) [(5,13),(2,7),(2,6),(10,100)]) [([(5,13)],5,13), ([(2,7),(2,6)],4,13)],
+        TestCase $ assertEqual "e" ((selector2 . (filter 5) . transformer . generator) [(5,13),(2,7),(2,6),(10,100)]) [([(2,7),(2,6)],4,13)]
+        ]
+
+tests :: [Test]
+tests = [cases1]
+
+main = do
+  forM tests $ \test ->
+            runTestTT test
+