From 6d5084dde0a659debb606e837e8edf06b4b534cf Mon Sep 17 00:00:00 2001
From: Matthias Wisniowski <matthias.wisniowski@gmail.com>
Date: Sun, 6 May 2012 19:22:14 +0200
Subject: Aufgabe 5, 1-3

---
 AufgabeFFP5.hs | 63 +++++++++++++++++++++++++++++++++++++++++++++++++++-------
 1 file changed, 56 insertions(+), 7 deletions(-)

(limited to 'AufgabeFFP5.hs')

diff --git a/AufgabeFFP5.hs b/AufgabeFFP5.hs
index d84307c..c528be4 100644
--- a/AufgabeFFP5.hs
+++ b/AufgabeFFP5.hs
@@ -25,26 +25,75 @@ dynamic compute bnds = t
     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
-  
-asDyn :: Array Int Int -> (Int, Int) -> Int
-asDyn a (i,j) = findTable t (i,j)
-  where
-      t = dynamic (compAS a) (bndsAS a)
 
+-- computes table for array
+asTbl :: Array Int Int -> Table Int (Int, Int)
+asTbl a = dynamic (compAS a) (bndsAS a)
+  
 -- maximum function for tables
-tblMax :: Table Int (Int,Int) -> Int
+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 $ dynamic (compAS a) (bndsAS a)
+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>=m]
+  where
+    t@(Tbl array) = asTbl a
+    m = 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.
+-------------------------------------------------------------------------------
+
-- 
cgit v1.2.3