-
Notifications
You must be signed in to change notification settings - Fork 6
/
Copy pathWeek02Live.hs
124 lines (100 loc) · 3.64 KB
/
Week02Live.hs
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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
{-# OPTIONS_GHC -fwarn-incomplete-patterns #-}
module Week02Live where
type Coin = Int
makeChange :: [Coin] -- coins that are available
-> [Coin] -- coins used so far
-> Int -- target amount
-> Maybe [Coin] -- coins that add up to the target (maybe)
makeChange available used 0 = Just used
makeChange [] _ n = Nothing
makeChange (coin:available) used n
| n >= coin = makeChange available (coin:used) (n - coin)
| otherwise = makeChange available used n
correctChange :: [Coin] -> Int -> Bool
correctChange available target = case makeChange available [] target of
Nothing -> True
Just used -> sum used == target
makeChange_v2 :: [Coin] -> [Coin] -> Int -> Maybe [Coin]
makeChange_v2 available used 0 = Just used
makeChange_v2 [] used n = Nothing
makeChange_v2 (coin:available) used n
| n >= coin = case makeChange_v2 available (coin:used) (n - coin) of
Just change -> Just change
Nothing -> makeChange_v2 available used n
| otherwise = makeChange_v2 available used n
------------------------------------------------------------------------------
success :: a -> Maybe a
success x = Just x
failure :: Maybe a
failure = Nothing
orElse :: Maybe a -> Maybe a -> Maybe a
orElse (Just x) _ = Just x
orElse Nothing y = y
makeChange_v3 :: [Coin] -> [Coin] -> Int -> Maybe [Coin]
makeChange_v3 available used 0 = success used
makeChange_v3 [] used n = failure
makeChange_v3 (coin:available) used n
| n >= coin =
makeChange_v3 available (coin:used) (n - coin)
`orElse`
makeChange_v3 available used n
| otherwise = makeChange_v3 available used n
-- myFunc(f(), g())
successL :: a -> [a]
successL x = [x]
failureL :: [a]
failureL = []
orElseL :: [a] -> [a] -> [a]
orElseL xs ys = xs ++ ys
makeChange_v4 :: [Coin] -> [Coin] -> Int -> [[Coin]]
makeChange_v4 available used 0 = successL used
makeChange_v4 [] used n = failureL
makeChange_v4 (coin:available) used n
| n >= coin =
makeChange_v4 available (coin:used) (n - coin)
`orElseL`
makeChange_v4 available used n
| otherwise = makeChange_v4 available used n
------------------------------------------------------------------------------
data Choices a
= Success a
| Failure
| Choose (Choices a) (Choices a)
deriving Show
successC :: a -> Choices a
successC x = Success x
failureC :: Choices a
failureC = Failure
orElseC :: Choices a -> Choices a -> Choices a
orElseC xs ys = Choose xs ys
makeChange_v5 :: [Coin] -> [Coin] -> Int -> Choices [Coin]
makeChange_v5 available used 0 = successC used
makeChange_v5 [] used n = failureC
makeChange_v5 (coin:available) used n
| n >= coin =
makeChange_v5 available (coin:used) (n - coin)
`orElseC`
makeChange_v5 available used n
| otherwise = makeChange_v5 available used n
greedy :: Choices a -> Maybe a
greedy (Success x) = Just x
greedy Failure = Nothing
greedy (Choose x y) = greedy x
firstChoice :: Choices a -> Maybe a
firstChoice (Success x) = Just x
firstChoice Failure = Nothing
firstChoice (Choose x y) = firstChoice x `orElse` firstChoice y
allChoices :: Choices a -> [a]
allChoices (Success x) = [x]
allChoices Failure = []
allChoices (Choose x y) = allChoices x ++ allChoices y
best :: (a -> Int) -> Choices a -> Maybe a
best cost (Success x) = Just x
best cost Failure = Nothing
best cost (Choose x y) =
case (best cost x, best cost y) of
(Nothing, Nothing) -> Nothing
(Just x, Nothing) -> Just x
(Nothing, Just y) -> Just y
(Just x, Just y) ->
if cost x <= cost y then Just x else Just y