content: 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)
  