checklist & countlist

1 files changed, 36 insertions, 10 deletions

diff --git a/AufgabeFFP8.hs b/AufgabeFFP8.hs
index c2e3583..298898b 100644
--- a/AufgabeFFP8.hs
+++ b/AufgabeFFP8.hs
@@ -2,7 +2,8 @@ module AufgabeFFP8
 where
 
 import Data.Char
-import Data.List hiding ((\\), insert, delete)
+import Data.Array
+import Data.List hiding ((\\), insert, delete, sort)
 import Test.QuickCheck
 
 type Nat = [Int]
@@ -14,27 +15,52 @@ minfree_bv :: [Int] -> Int
 minfree_bv xs = head ([0..] \\ xs)
 
 -- checklist
---minfree_chl :: [Int] -> Int
+minfree_chl :: [Int] -> Int
+minfree_chl = search . checklist
+
+search :: Array Int Bool -> Int
+search = length . takeWhile id . elems
+
+checklist :: [Int] -> Array Int Bool
+checklist xs = accumArray (||) False (0, n) 
+        (zip (filter (<=n) xs) (repeat True))
+        where n = length xs
 
 -- countlist
---minfree_col :: [Int] -> Int
+minfree_col :: [Int] -> Int
+minfree_col = search_countlist . countlist
+
+countlist :: [Int] -> Array Int Int
+countlist xs = accumArray (+) 0 (0, n) (zip xs (repeat 1))
+        where n = safe_maximum xs
+
+safe_maximum :: [Int] -> Int
+safe_maximum [] = 0
+safe_maximum xs = maximum xs
+
+-- unused
+sort :: [Int] -> [Int]
+sort xs = concat [replicate k x | (x, k) <- assocs ( countlist xs ) ]
+
+search_countlist :: Array Int Int -> Int
+search_countlist = length . takeWhile (/= 0) . elems
 
--- basic divice-and-conquer
---minfree_b :: [Int] -> Int
+-- basic divide-and-conquer
+minfree_b :: [Int] -> Int
 
--- refined divice-and-conquer
+-- refined divide-and-conquer
 --minfree_r :: [Int] -> Int
 
--- optimised divice-and-conquer
+-- optimised divide-and-conquer
 --minfree_o :: [Int] -> Int
 --
--- basic divice-and-conquer mittels higher order function
+-- basic divide-and-conquer mittels higher order function
 --minfree_bhof :: [Int] -> Int
 
--- refined divice-and-conquer mittels higher order function
+-- refined divide-and-conquer mittels higher order function
 --minfree_rhof :: [Int] -> Int
 
--- optimised divice-and-conquer mittels higher order function
+-- optimised divide-and-conquer mittels higher order function
 --minfree_ohof :: [Int] -> Int