Merge branch 'master' of ssh://git.manuel.mausz.at:2211/ffp

3 files changed, 188 insertions, 0 deletions

diff --git a/AufgabeFFP5.hs b/AufgabeFFP5.hs
new file mode 100644
index 0000000..75383f7
--- /dev/null
+++ b/AufgabeFFP5.hs
@@ -0,0 +1,118 @@
+module AufgabeFFP5
+where
+
+import Data.Array
+
+newtype Table a b = Tbl (Array b a)
+  deriving Show
+
+newTable :: (Ix b) => [(b, a)] -> Table a b
+newTable l = Tbl (array (lo, hi) l)
+  where
+    indices = map fst l
+    lo = minimum indices
+    hi = maximum indices
+
+findTable :: (Ix b) => Table a b -> b -> a
+findTable (Tbl a) i = a ! i
+
+updTable :: (Ix b) => (b, a) -> Table a b -> Table a b
+updTable p@(i, x) (Tbl a) = Tbl (a // [p])
+
+dynamic :: (Ix coord) => (Table entry coord -> coord -> entry) -> (coord, coord) -> (Table entry coord)
+dynamic compute bnds = t
+  where
+    t = newTable (map (\coord -> (coord, compute t coord)) (range bnds))
+
+-------------------------------------------------------------------------------
+-- 1.
+-------------------------------------------------------------------------------
+
+bndsAS :: Array Int Int -> ((Int, Int), (Int, Int))
+bndsAS a = ((l,l), (h,h))
+  where
+    (l,h) = bounds a
+
+-- fill the table. Lower half below diagonal not necessary
+-- but filled with the symmetric value
+compAS :: Array Int Int -> Table Int (Int, Int) -> (Int, Int) -> Int
+compAS a t (i,j)
+  | i == j = a ! j
+  | i<j = compAS a t (j,i)
+  | otherwise = findTable t (i-1, j) + a!i
+
+-- computes distance-sum-table for array
+asTbl :: Array Int Int -> Table Int (Int, Int)
+asTbl a = dynamic (compAS a) (bndsAS a)
+
+-- maximum function for tables
+tblMax :: (Ord a, Ix b) => Table a b -> a
+tblMax (Tbl a) = maximum $ elems a
+
+-- maximum of the array's distance-sums
+mas :: Array Int Int -> Int
+mas a = tblMax $ asTbl a
+
+-------------------------------------------------------------------------------
+-- 2.
+-------------------------------------------------------------------------------
+
+-- all indices where the value equals to the maximum distance-sum
+amas :: Array Int Int -> [(Int, Int)]
+amas a = [(i,j) | ((i,j),v) <- (assocs array), i<=j, v>=maxAS]
+  where
+    t@(Tbl array) = asTbl a
+    maxAS = tblMax t
+
+-------------------------------------------------------------------------------
+-- 3.
+-------------------------------------------------------------------------------
+
+-- computes index with maximum index-difference
+maxL :: [(Int, Int)] -> (Int, Int)
+maxL [] = error "maximum of empty list"
+maxL [x] = x
+maxL (x:xs)
+  | l x >= l maxTail = x
+  | otherwise = maxTail
+  where
+    l (x,y) = y-x
+    maxTail = maxL xs
+
+-- index with maximum distance-sum and maximum index-difference
+lmas :: Array Int Int -> (Int, Int)
+lmas a = maxL $ amas a
+
+-------------------------------------------------------------------------------
+
+divideAndConquer :: (p->Bool) -> (p->s) -> (p->[p]) -> (p->[s]->s) -> p -> s
+divideAndConquer indiv solve divide combine initPb = dAC initPb
+  where
+    dAC pb
+      | indiv pb = solve pb
+      | otherwise = combine pb (map dAC (divide pb))
+
+
+-------------------------------------------------------------------------------
+-- 4.
+-------------------------------------------------------------------------------
+
+mi_indiv :: [a] -> Bool
+mi_indiv a = length a <= 1
+
+mi_solve :: (Ix a, Show a) => (b -> Bool) -> [(a,b)] -> [(a,b)]
+mi_solve wf [(a,b)]
+  | wf b = [(a,b)]
+  | otherwise = []
+
+mi_divide :: [a] -> [[a]]
+mi_divide (x:xs) = [[x], xs]
+
+mi_combine :: [a] -> [[a]] -> [a]
+mi_combine _ [] = error "No matching index"
+mi_combine a (x:xs)
+  | null x = mi_combine a xs
+  | otherwise = [head x]
+
+minIndex :: (Ix a, Show a) => Array a b -> (b -> Bool) -> a
+minIndex a wf = fst $ head $ divideAndConquer mi_indiv (mi_solve wf) mi_divide mi_combine $ assocs a
diff --git a/AufgabeFFP6.pdf b/AufgabeFFP6.pdf
new file mode 100644
index 0000000..0fe111b
--- /dev/null
+++ b/AufgabeFFP6.pdf
diff --git a/TestAufgabeFFP5.hs b/TestAufgabeFFP5.hs
new file mode 100644
index 0000000..865f503
--- /dev/null
+++ b/TestAufgabeFFP5.hs
@@ -0,0 +1,70 @@
+module Main where
+
+import Test.HUnit
+import Control.Monad
+import Data.Array
+import AufgabeFFP5
+
+a :: Array Int Int
+a = array (1,9) [(1,3),(2,(-5)),(3,0),(4,9),(5,2),(6,(-1)),(7,2),(8,(-5)),(9,1)]
+
+b :: Array Int Int
+b = array (1,9) [(1,3),(2,(-1)),(3,(-2)),(4,9),(5,2),(6,(-1)),(7,2),(8,0),(9,(-1))]
+
+c :: Array Int Int
+c = array (1,5) [(1,2),(2,3),(3,(-10)),(4,1),(5,4)]
+
+d :: Array Int Int
+d = array (1,6) [(1, (-3)), (2, 1), (3, 10), (4, (-5)), (5, 8), (6, 7)]
+
+minA :: Array Int Int
+minA = array (0,0) [(0,0)]
+
+data Week = Mon | Tue | Wed | Thu | Fri | Sat | Sun deriving (Eq, Ord, Ix, Show)
+
+w :: Array Week String
+w = array (Tue, Sat) [(Wed, "work"), (Thu, "study"), (Tue, "study"), (Fri, "chill"), (Sat, "relax")]
+
+cases1 = "mas" ~: TestList [
+  "mas a"     ~: 12   ~=?   (mas a),
+  "mas b"     ~: 12   ~=?   (mas b),
+  "mas c"     ~: 5    ~=?   (mas c),
+  "mas d"     ~: 21   ~=?   (mas d),
+  "mas minA"  ~: 0    ~=?   (mas minA)
+  ]
+
+cases2 = TestLabel "amas" $ TestList [
+  "amas a"    ~: [(3,7), (4,7)]             ~=?   (amas a),
+  "amas b"    ~: [(1,7),(1,8),(4,7),(4,8)]  ~=?   (amas b),
+  "amas c"    ~: [(1,2),(4,5)]              ~=?   (amas c),
+  "amas d"    ~: [(2,6)]                    ~=?   (amas d),
+  "amas minA" ~: [(0,0)]                    ~=?   (amas minA)
+  ]
+
+cases3 = TestLabel "lmas" $ TestList [
+  "lmas a"    ~: (3,7)  ~=?   (lmas a),
+  "lmas b"    ~: (1,8)  ~=?   (lmas b),
+  "lmas c"    ~: (1,2)  ~=?   (lmas c),
+  "lmas d"    ~: (2,6)  ~=?   (lmas d),
+  "lmas minA" ~: (0,0)  ~=?   (lmas minA)
+  ]
+
+cases4 = TestLabel "minIndex" $ TestList [
+  "minIndex a (>5)"         ~: 4    ~=?   (minIndex a (>5)),
+  "minIndex a (<0)"         ~: 2    ~=?   (minIndex a (<0)),
+  "minIndex a (even)"       ~: 3    ~=?   (minIndex a (even)),
+  "minIndex b (odd)"        ~: 1    ~=?   (minIndex b (odd)),
+  -- "minIndex b (>100)"       ~: error "No matching index" ~=? (minIndex b (>100)),
+  "minIndex w (=='relax')"  ~: Sat  ~=?   (minIndex w (=="relax")),
+  "minIndex w (=='work')"   ~: Wed  ~=?   (minIndex w (=="work")),
+  "minIndex w (=='chill')"  ~: Fri  ~=?   (minIndex w (=="chill")),
+  "minIndex w (/='chill')"  ~: Tue  ~=?   (minIndex w (/="chill"))
+  -- "minIndex w (=='swim')"   ~: error "No matching index" ~=? (minIndex w (=="swim"))
+  ]
+
+tests :: [Test]
+tests = [cases1, cases2, cases3, cases4]
+
+main = do
+  forM tests $ \test ->
+    runTestTT test