diff options
| author | manuel <manuel@mausz.at> | 2012-04-28 12:36:07 +0200 |
|---|---|---|
| committer | manuel <manuel@mausz.at> | 2012-04-28 12:36:07 +0200 |
| commit | 9016d85976cfb582fc555ba9d0b29160e5efadc7 (patch) | |
| tree | 8fc8d2d4ebd56429ff6ef6700f6ea57d3420f3b8 | |
| parent | 5a245328763cabdae55f50682dab973c097177af (diff) | |
| download | ffp-9016d85976cfb582fc555ba9d0b29160e5efadc7.tar.gz ffp-9016d85976cfb582fc555ba9d0b29160e5efadc7.tar.bz2 ffp-9016d85976cfb582fc555ba9d0b29160e5efadc7.zip | |
fix indenting of aufgabe3
| -rw-r--r-- | AufgabeFFP3.hs | 44 | ||||
| -rw-r--r-- | TestAufgabeFFP3.hs | 12 |
2 files changed, 28 insertions, 28 deletions
diff --git a/AufgabeFFP3.hs b/AufgabeFFP3.hs index 459f510..8b1d748 100644 --- a/AufgabeFFP3.hs +++ b/AufgabeFFP3.hs | |||
| @@ -16,36 +16,36 @@ type MaxWeight = Weight | |||
| 16 | 16 | ||
| 17 | safeGet :: [Integer] -> Int -> Integer -- get element of list, default to 0 | 17 | safeGet :: [Integer] -> Int -> Integer -- get element of list, default to 0 |
| 18 | safeGet l i | 18 | safeGet l i |
| 19 | | i < length l = l !! i | 19 | | i < length l = l !! i |
| 20 | | otherwise = 0 | 20 | | otherwise = 0 |
| 21 | 21 | ||
| 22 | toBin :: Integer -> [Integer] -- get binary representation of integer | 22 | toBin :: Integer -> [Integer] -- get binary representation of integer |
| 23 | toBin 0 = [] | 23 | toBin 0 = [] |
| 24 | toBin i = [rem] ++ toBin quot | 24 | toBin i = [rem] ++ toBin quot |
| 25 | where ( quot, rem ) = quotRem i 2 | 25 | where ( quot, rem ) = quotRem i 2 |
| 26 | 26 | ||
| 27 | hasBit :: Integer -> Int -> Bool -- check if the binary representation of a number has the ith bit set | 27 | hasBit :: Integer -> Int -> Bool -- check if the binary representation of a number has the ith bit set |
| 28 | hasBit num ith = (safeGet (toBin num) ith) == 1 | 28 | hasBit num ith = (safeGet (toBin num) ith) == 1 |
| 29 | 29 | ||
| 30 | getChoice :: Items -> Int -> Items -- choose a subset determined by binary representation of l | 30 | getChoice :: Items -> Int -> Items -- choose a subset determined by binary representation of l |
| 31 | getChoice l i = concat ( map (choose l) [0..(length l)-1] ) | 31 | getChoice l i = concat ( map (choose l) [0..(length l)-1] ) |
| 32 | where | 32 | where |
| 33 | choose l pos | 33 | choose l pos |
| 34 | | hasBit (fromIntegral i) pos = [ l !! pos ] | 34 | | hasBit (fromIntegral i) pos = [ l !! pos ] |
| 35 | | otherwise = [] | 35 | | otherwise = [] |
| 36 | 36 | ||
| 37 | generator:: Items -> Loads -- get all possible choices (2^n) | 37 | generator:: Items -> Loads -- get all possible choices (2^n) |
| 38 | generator l = map ( getChoice l ) [1..num] | 38 | generator l = map ( getChoice l ) [1..num] |
| 39 | where num = (2^(length l)) - 1 | 39 | where num = (2^(length l)) - 1 |
| 40 | 40 | ||
| 41 | transformer :: Loads -> [LoadWghtVal] -- calc sum of weight and value for all lists of items | 41 | transformer :: Loads -> [LoadWghtVal] -- calc sum of weight and value for all lists of items |
| 42 | transformer l = map trans l | 42 | transformer l = map trans l |
| 43 | 43 | ||
| 44 | trans :: Load -> LoadWghtVal -- worker of transformer | 44 | trans :: Load -> LoadWghtVal -- worker of transformer |
| 45 | trans load = (load, weight, value) | 45 | trans load = (load, weight, value) |
| 46 | where | 46 | where |
| 47 | weight = sum $ map fst load | 47 | weight = sum $ map fst load |
| 48 | value = sum $ map snd load | 48 | value = sum $ map snd load |
| 49 | 49 | ||
| 50 | getWeight :: LoadWghtVal -> Weight | 50 | getWeight :: LoadWghtVal -> Weight |
| 51 | getWeight (_, w, _) = w | 51 | getWeight (_, w, _) = w |
| @@ -58,16 +58,16 @@ filter max l = [ x | x <- l, getWeight x <= max ] | |||
| 58 | 58 | ||
| 59 | selector :: [LoadWghtVal] -> [LoadWghtVal] -- get those with max val | 59 | selector :: [LoadWghtVal] -> [LoadWghtVal] -- get those with max val |
| 60 | selector l = [ x | x <- l, getVal x == max ] | 60 | selector l = [ x | x <- l, getVal x == max ] |
| 61 | where max = maximum $ map getVal l | 61 | where max = maximum $ map getVal l |
| 62 | 62 | ||
| 63 | selector1 :: [LoadWghtVal] -> [LoadWghtVal] -- all with max val | 63 | selector1 :: [LoadWghtVal] -> [LoadWghtVal] -- all with max val |
| 64 | selector1 = selector | 64 | selector1 = selector |
| 65 | 65 | ||
| 66 | selector2 :: [LoadWghtVal] -> [LoadWghtVal] -- get ones with min weight | 66 | selector2 :: [LoadWghtVal] -> [LoadWghtVal] -- get ones with min weight |
| 67 | selector2 l = [ x | x <- best, getWeight x == min ] | 67 | selector2 l = [ x | x <- best, getWeight x == min ] |
| 68 | where | 68 | where |
| 69 | min = minimum $ map getWeight best | 69 | min = minimum $ map getWeight best |
| 70 | best = selector l | 70 | best = selector l |
| 71 | 71 | ||
| 72 | 72 | ||
| 73 | -- pascal's triangle from exercise 1 | 73 | -- pascal's triangle from exercise 1 |
| @@ -77,22 +77,22 @@ pd = [[1]] ++ (zipWith (\x y -> zipWith (+) ([0] ++ x) (y ++ [0])) pd pd) | |||
| 77 | -- naive | 77 | -- naive |
| 78 | binom :: (Integer, Integer) -> Integer | 78 | binom :: (Integer, Integer) -> Integer |
| 79 | binom (n, k) | 79 | binom (n, k) |
| 80 | | k == 0 || n == k = 1 | 80 | | k == 0 || n == k = 1 |
| 81 | | otherwise = binom (n-1, k-1) + binom (n-1, k) | 81 | | otherwise = binom (n-1, k-1) + binom (n-1, k) |
| 82 | 82 | ||
| 83 | -- stream using pascal | 83 | -- stream using pascal |
| 84 | binomS :: (Integer, Integer) -> Integer | 84 | binomS :: (Integer, Integer) -> Integer |
| 85 | binomS (n, k) = pd !! fromInteger n !! fromInteger k | 85 | binomS (n, k) = pd !! fromInteger n !! fromInteger k |
| 86 | 86 | ||
| 87 | -- calc table | 87 | -- calc table |
| 88 | binomMemoTable :: [[Integer]] | 88 | binomMemoTable :: [[Integer]] |
| 89 | binomMemoTable = [ [ binomM (n, k) | k <- [0..] ] | n <- [0..] ] | 89 | binomMemoTable = [ [ binomM (n, k) | k <- [0..] ] | n <- [0..] ] |
| 90 | 90 | ||
| 91 | -- using memoisation | 91 | -- using memoisation |
| 92 | -- base case or recursion formula using lookup table | 92 | -- base case or recursion formula using lookup table |
| 93 | binomM :: (Integer, Integer) -> Integer | 93 | binomM :: (Integer, Integer) -> Integer |
| 94 | binomM (n, k) | 94 | binomM (n, k) |
| 95 | | k == 0 || n == k = 1 | 95 | | k == 0 || n == k = 1 |
| 96 | | otherwise = get (n-1) (k-1) + get (n-1) (k) | 96 | | otherwise = get (n-1) (k-1) + get (n-1) (k) |
| 97 | where get n k = binomMemoTable !! fromInteger n !! fromInteger k | 97 | where get n k = binomMemoTable !! fromInteger n !! fromInteger k |
| 98 | 98 | ||
diff --git a/TestAufgabeFFP3.hs b/TestAufgabeFFP3.hs index c83099c..065401d 100644 --- a/TestAufgabeFFP3.hs +++ b/TestAufgabeFFP3.hs | |||
| @@ -12,26 +12,26 @@ cases1 = TestLabel "foo" $ TestList [ | |||
| 12 | TestCase $ assertEqual "b" ((selector1 . (filter 13) . transformer . generator) [(5,3),(2,7),(2,6),(10,100)]) [([(2,7),(10,100)],12,107)], | 12 | TestCase $ assertEqual "b" ((selector1 . (filter 13) . transformer . generator) [(5,3),(2,7),(2,6),(10,100)]) [([(2,7),(10,100)],12,107)], |
| 13 | TestCase $ assertEqual "c" ((selector1 . (filter 1) . transformer . generator) [(5,3),(2,7),(2,6),(10,100)]) [], | 13 | TestCase $ assertEqual "c" ((selector1 . (filter 1) . transformer . generator) [(5,3),(2,7),(2,6),(10,100)]) [], |
| 14 | 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)], | 14 | 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)], |
| 15 | TestCase $ assertEqual "e" ((selector2 . (filter 5) . transformer . generator) [(5,13),(2,7),(2,6),(10,100)]) [([(2,7),(2,6)],4,13)] | 15 | TestCase $ assertEqual "e" ((selector2 . (filter 5) . transformer . generator) [(5,13),(2,7),(2,6),(10,100)]) [([(2,7),(2,6)],4,13)] |
| 16 | ] | 16 | ] |
| 17 | 17 | ||
| 18 | cases2 = TestLabel "bar" $ TestList [ | 18 | cases2 = TestLabel "bar" $ TestList [ |
| 19 | TestCase $ assertEqual "a" [ binomS (8, i) | i <- [0..7] ] [ binom (8, i) | i <- [0..7] ], | 19 | TestCase $ assertEqual "a" [ binomS (8, i) | i <- [0..7] ] [ binom (8, i) | i <- [0..7] ], |
| 20 | TestCase $ assertEqual "a" (binom (1,1)) (binomS (1,1)), | 20 | TestCase $ assertEqual "a" (binom (1,1)) (binomS (1,1)), |
| 21 | TestCase $ assertEqual "a" (binom (2,1)) (binomS (2,1)), | 21 | TestCase $ assertEqual "a" (binom (2,1)) (binomS (2,1)), |
| 22 | TestCase $ assertEqual "a" (binom (18,12)) (binomS (18,12)) | 22 | TestCase $ assertEqual "a" (binom (18,12)) (binomS (18,12)) |
| 23 | ] | 23 | ] |
| 24 | 24 | ||
| 25 | cases3 = TestLabel "bar" $ TestList [ | 25 | cases3 = TestLabel "bar" $ TestList [ |
| 26 | TestCase $ assertEqual "a" [ binomM (8, i) | i <- [0..7] ] [ binom (8, i) | i <- [0..7] ], | 26 | TestCase $ assertEqual "a" [ binomM (8, i) | i <- [0..7] ] [ binom (8, i) | i <- [0..7] ], |
| 27 | TestCase $ assertEqual "a" (binom (1,1)) (binomM (1,1)), | 27 | TestCase $ assertEqual "a" (binom (1,1)) (binomM (1,1)), |
| 28 | TestCase $ assertEqual "a" (binom (2,1)) (binomM (2,1)), | 28 | TestCase $ assertEqual "a" (binom (2,1)) (binomM (2,1)), |
| 29 | TestCase $ assertEqual "a" (binom (18,12)) (binomM (18,12)) | 29 | TestCase $ assertEqual "a" (binom (18,12)) (binomM (18,12)) |
| 30 | ] | 30 | ] |
| 31 | 31 | ||
| 32 | cases4 = TestLabel "bar" $ TestList [ | 32 | cases4 = TestLabel "bar" $ TestList [ |
| 33 | TestCase $ assertEqual "a" ( [binomS (n, k) | k <- [0..50], n <- [k..50] ] ) ( [binomM (n, k) | k <- [0..50], n <- [k..50] ] ) | 33 | TestCase $ assertEqual "a" ( [binomS (n, k) | k <- [0..50], n <- [k..50] ] ) ( [binomM (n, k) | k <- [0..50], n <- [k..50] ] ) |
| 34 | ] | 34 | ] |
| 35 | 35 | ||
| 36 | 36 | ||
| 37 | tests :: [Test] | 37 | tests :: [Test] |
| @@ -39,5 +39,5 @@ tests = [cases1, cases2, cases3, cases4] | |||
| 39 | 39 | ||
| 40 | main = do | 40 | main = do |
| 41 | forM tests $ \test -> | 41 | forM tests $ \test -> |
| 42 | runTestTT test | 42 | runTestTT test |
| 43 | 43 | ||
