blob: 298898b7988e80b688e9fe88da4de18c2469f6d0 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
|
module AufgabeFFP8
where
import Data.Char
import Data.Array
import Data.List hiding ((\\), insert, delete, sort)
import Test.QuickCheck
type Nat = [Int]
(\\) :: Eq a => [a] -> [a] -> [a]
xs \\ ys = filter (\x -> x `notElem` ys) xs
minfree_bv :: [Int] -> Int
minfree_bv xs = head ([0..] \\ xs)
-- checklist
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 = 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 divide-and-conquer
minfree_b :: [Int] -> Int
-- refined divide-and-conquer
--minfree_r :: [Int] -> Int
-- optimised divide-and-conquer
--minfree_o :: [Int] -> Int
--
-- basic divide-and-conquer mittels higher order function
--minfree_bhof :: [Int] -> Int
-- refined divide-and-conquer mittels higher order function
--minfree_rhof :: [Int] -> Int
-- optimised divide-and-conquer mittels higher order function
--minfree_ohof :: [Int] -> Int
-- QuickCheck part
|
