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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
|
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
minfree_b xs = if (null ([0..b-1] \\ us))
then (head ([b..] \\ vs))
else (head ([0..] \\ us))
where
(us, vs) = partition (<b) xs
b = 1 + (length xs) `div` 2
-- refined divide-and-conquer
minfree_r :: [Int] -> Int
minfree_r xs = minfrom 0 xs
minfrom :: Int -> [Int] -> Int
minfrom a xs
| null xs = a
| length us == b-a = minfrom b vs
| otherwise = minfrom a us
where
(us, vs) = partition (<b) xs
b = a + 1 + (length xs) `div` 2
-- optimised divide-and-conquer
minfree_o :: [Int] -> Int
minfree_o xs = minfrom_o 0 (length xs, xs)
minfrom_o :: Int -> (Int, [Int]) -> Int
minfrom_o a (n, xs)
| n == 0 = a
| m == b-a = minfrom_o b (n-m, vs)
| otherwise = minfrom_o a (m, us)
where
(us, vs) = partition (<b) xs
b = a + 1 + n `div` 2
m = length us
-- 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
|
