-- Convert paths to tree structure

def paths : [[(Integer, [Integer], [Integer])]] :=
  [[(1, [1, 1], [1, 1]), (2, [1, 1], [1, 2]), (1, [1, 2], [1, 2]), (2, [1, 2], [2, 2]), (1, [1, 4], [2, 2]), (2, [1, 4], [2]), (1, [1], [2]), (2, [1], [3]), (1, [4], [3]), (-1, [4], [])]
  ,[(1, [1, 1], [1, 1]), (2, [1, 1], [1, 2]), (1, [1, 2], [1, 2]), (2, [1, 2], [2, 2]), (1, [1, 4], [2, 2]), (2, [1, 4], [2]), (1, [3, 4], [2]), (-1, [3, 4], [])]
  ,[(1, [1, 1], [1, 1]), (2, [1, 1], [1, 2]), (1, [1, 2], [1, 2]), (2, [1, 2], [2, 2]), (1, [1, 4], [2, 2]), (2, [1, 4], [2]), (1, [3, 4], [2]), (2, [3, 4], [5]), (1, [3], [5]), (-1, [3], [])]
  ,[(1, [1, 1], [1, 1]), (2, [1, 1], [1, 2]), (1, [1, 2], [1, 2]), (2, [1, 2], [2, 2]), (1, [1, 4], [2, 2]), (2, [1, 4], [2]), (1, [3, 4], [2]), (2, [3, 4], [5]), (1, [4], [5]), (-1, [4], [])]
  ,[(1, [1, 1], [1, 1]), (2, [1, 1], [1, 2]), (1, [1, 2], [1, 2]), (2, [1, 2], [2, 2]), (1, [2, 3], [2, 2]), (2, [2, 3], [2, 4]), (1, [2, 5], [2, 4]), (2, [2, 5], [4]), (1, [2], [4]), (-1, [2], [])]
  ,[(1, [1, 1], [1, 1]), (2, [1, 1], [1, 2]), (1, [1, 2], [1, 2]), (2, [1, 2], [2, 2]), (1, [2, 3], [2, 2]), (2, [2, 3], [2, 4]), (1, [2, 5], [2, 4]), (2, [2, 5], [4]), (1, [5], [4]), (-1, [5], [])]
  ,[(1, [1, 1], [1, 1]), (2, [1, 1], [1, 2]), (1, [1, 2], [1, 2]), (2, [1, 2], [2, 2]), (1, [2, 3], [2, 2]), (2, [2, 3], [2, 4]), (1, [2], [2, 4]), (2, [2], [2]), (1, [4], [2]), (-1, [4], [])]
  ,[(1, [1, 1], [1, 1]), (2, [1, 1], [1, 2]), (1, [1, 2], [1, 2]), (2, [1, 2], [2, 2]), (1, [2, 3], [2, 2]), (2, [2, 3], [2, 4]), (1, [3, 4], [2, 4]), (2, [3, 4], [4]), (1, [3], [4]), (-1, [3], [])]
  ,[(1, [1, 1], [1, 1]), (2, [1, 1], [1, 2]), (1, [1, 2], [1, 2]), (2, [1, 2], [2, 2]), (1, [2, 3], [2, 2]), (2, [2, 3], [2, 4]), (1, [3, 4], [2, 4]), (2, [3, 4], [4]), (1, [4], [4]), (-1, [4], [])]
  ,[(1, [1, 1], [1, 1]), (2, [1, 1], [1, 2]), (1, [1, 2], [1, 2]), (2, [1, 2], [2, 2]), (1, [2, 3], [2, 2]), (2, [2, 3], [2, 4]), (1, [3], [2, 4]), (2, [3], [2]), (1, [5], [2]), (-1, [5], [])]
  ,[(1, [1, 1], [1, 1]), (2, [1, 1], [1, 2]), (1, [1, 2], [1, 2]), (2, [1, 2], [2, 2]), (1, [2, 3], [2, 2]), (2, [2, 3], [2, 5]), (1, [2, 5], [2, 5]), (2, [2, 5], [5]), (1, [2], [5]), (-1, [2], [])]
  ,[(1, [1, 1], [1, 1]), (2, [1, 1], [1, 2]), (1, [1, 2], [1, 2]), (2, [1, 2], [2, 2]), (1, [2, 3], [2, 2]), (2, [2, 3], [2, 5]), (1, [2, 5], [2, 5]), (2, [2, 5], [5]), (1, [5], [5]), (-1, [5], [])]
  ,[(1, [1, 1], [1, 1]), (2, [1, 1], [1, 2]), (1, [1, 2], [1, 2]), (2, [1, 2], [2, 2]), (1, [2, 3], [2, 2]), (2, [2, 3], [2, 5]), (1, [2], [2, 5]), (2, [2], [2]), (1, [4], [2]), (-1, [4], [])]
  ,[(1, [1, 1], [1, 1]), (2, [1, 1], [1, 2]), (1, [1, 2], [1, 2]), (2, [1, 2], [2, 2]), (1, [2, 3], [2, 2]), (2, [2, 3], [2, 5]), (1, [3, 4], [2, 5]), (2, [3, 4], [5]), (1, [3], [5]), (-1, [3], [])]
  ,[(1, [1, 1], [1, 1]), (2, [1, 1], [1, 2]), (1, [1, 2], [1, 2]), (2, [1, 2], [2, 2]), (1, [2, 3], [2, 2]), (2, [2, 3], [2, 5]), (1, [3, 4], [2, 5]), (2, [3, 4], [5]), (1, [4], [5]), (-1, [4], [])]
  ,[(1, [1, 1], [1, 1]), (2, [1, 1], [1, 2]), (1, [1, 2], [1, 2]), (2, [1, 2], [2, 2]), (1, [2, 3], [2, 2]), (2, [2, 3], [2, 5]), (1, [3], [2, 5]), (2, [3], [2]), (1, [5], [2]), (-1, [5], [])]
  ,[(1, [1, 1], [1, 1]), (2, [1, 1], [1, 2]), (1, [1, 3], [1, 2]), (2, [1, 3], [2, 2]), (1, [1, 5], [2, 2]), (2, [1, 5], [2]), (1, [1], [2]), (2, [1], [3]), (1, [4], [3]), (-1, [4], [])]
  ,[(1, [1, 1], [1, 1]), (2, [1, 1], [1, 2]), (1, [1, 3], [1, 2]), (2, [1, 3], [2, 2]), (1, [1, 5], [2, 2]), (2, [1, 5], [2]), (1, [3, 5], [2]), (-1, [3, 5], [])]
  ,[(1, [1, 1], [1, 1]), (2, [1, 1], [1, 2]), (1, [1, 3], [1, 2]), (2, [1, 3], [2, 2]), (1, [1, 5], [2, 2]), (2, [1, 5], [2]), (1, [3, 5], [2]), (2, [3, 5], [5]), (1, [3], [5]), (-1, [3], [])]
  ,[(1, [1, 1], [1, 1]), (2, [1, 1], [1, 2]), (1, [1, 3], [1, 2]), (2, [1, 3], [2, 2]), (1, [1, 5], [2, 2]), (2, [1, 5], [2]), (1, [3, 5], [2]), (2, [3, 5], [5]), (1, [5], [5]), (-1, [5], [])]
  ,[(1, [1, 1], [1, 1]), (2, [1, 1], [1, 2]), (1, [1, 3], [1, 2]), (2, [1, 3], [2, 2]), (1, [3, 3], [2, 2]), (2, [3, 3], [2, 5]), (1, [3, 5], [2, 5]), (2, [3, 5], [5]), (1, [3], [5]), (-1, [3], [])]
  ,[(1, [1, 1], [1, 1]), (2, [1, 1], [1, 2]), (1, [1, 3], [1, 2]), (2, [1, 3], [2, 2]), (1, [3, 3], [2, 2]), (2, [3, 3], [2, 5]), (1, [3, 5], [2, 5]), (2, [3, 5], [5]), (1, [5], [5]), (-1, [5], [])]
  ,[(1, [1, 1], [1, 1]), (2, [1, 1], [1, 2]), (1, [1, 3], [1, 2]), (2, [1, 3], [2, 2]), (1, [3, 3], [2, 2]), (2, [3, 3], [2, 5]), (1, [3], [2, 5]), (2, [3], [2]), (1, [5], [2]), (-1, [5], [])]]

def paths2 : [[(Integer, [Integer], [Integer])]] := map (\p -> take 3 p) paths

def listToTree {Eq a} (ps: [[[a]]]) : [Tree [a]] := matchDFS ps as list (list eq) with
  | [] :: [] -> []
  | loop $i (1, $m)
      (($x_i :: $r_i_1) :: (loop $j (2, $n_i)
                              ((#x_i :: $r_i_j) :: ...)
                              (!((#x_i :: _) :: _) & ...)))
      []
  -> map (\i -> Node x_i (listToTree (map (\j -> r_i_j) [1..(n_i)]))) [1..m]

assertEqual "listToTree [[1]]"
  (listToTree [[1]])
  [Node 1 []]

assertEqual "listToTree [[1,2],[1,3]]"
  (listToTree [[1,2],[1,3]])
  [Node 1 [Node 2 [], Node 3 []]]

assertEqual "listToTree [[1,2,3],[1,2,4],[1,3]]"
  (listToTree [[1,2,3],[1,2,4],[1,3]])
  [Node 1 [Node 2 [Node 3 [], Node 4 []], Node 3 []]]

assertEqual "listToTree [[1..10]]"
  (listToTree [[1..10]])
  [Node 1 [Node 2 [Node 3 [Node 4 [Node 5 [Node 6 [Node 7 [Node 8 [Node 9 [Node 10 []]]]]]]]]]]

-- listToTree paths produces a tree structure representing the game tree
-- The result is a complex tree structure with game states as nodes