-
Notifications
You must be signed in to change notification settings - Fork 15
/
ex1.hs
82 lines (63 loc) · 1.59 KB
/
ex1.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
import Data.List
size :: Int
size = 3
type Grid = [[Player]]
data Player
= O
| B
| X
deriving (Eq, Ord, Show)
next :: Player -> Player
next O = X
next B = B
next X = O
empty :: Grid
empty = replicate size (replicate size B)
full :: Grid -> Bool
full = notElem B . concat
wins :: Player -> Grid -> Bool
wins p g = any line (rows ++ cols ++ dias)
where
line = all (== p)
rows = g
cols = transpose g
dias = [diag g, diag (map reverse g)]
diag :: Grid -> [Player]
diag g = [g !! n !! n | n <- [0 .. size - 1]]
won :: Grid -> Bool
won g = wins O g || wins X g
valid :: Grid -> Int -> Bool
valid g i = 0 <= i && i < size ^ 2 && concat g !! i == B
move :: Grid -> Int -> Player -> [Grid]
move g i p =
if valid g i
then [chop size (xs ++ [p] ++ ys)]
else []
where
(xs, B:ys) = splitAt i (concat g)
chop :: Int -> [a] -> [[a]]
chop n [] = []
chop n xs = take n xs : chop n (drop n xs)
data Tree a =
Node a [Tree a]
deriving (Show)
gametree :: Grid -> Player -> Tree Grid
gametree g p = Node g [gametree g' (next p) | g' <- moves g p]
moves :: Grid -> Player -> [Grid]
moves g p
| won g = []
| full g = []
| otherwise = concat [move g i p | i <- [0 .. ((size ^ 2) - 1)]]
prune :: Int -> Tree a -> Tree a
prune 0 (Node x _) = Node x []
prune n (Node x ts) = Node x [prune (n - 1) t | t <- ts]
depth :: Int
depth = 9
-- ex1 starts here
-- total (gametree empty O) is 549946
total :: Tree a -> Int
total (Node _ []) = 1
total (Node _ ts) = 1 + sum (map total ts)
maxdepth :: Tree a -> Int
maxdepth (Node _ []) = 0
maxdepth (Node _ ts) = 1 + maximum (map maxdepth ts)