(* Common util. Should probably put this in a module or something.. *)
let get_one_line file =
  try Some (input_line file) with
    End_of_file -> None

let get_lines file =
  let rec input lines =
    match get_one_line file with
      Some line -> input (line :: lines)
    | None -> List.rev lines
  in input []

let read_file file =
  let channel = open_in(file) in
  get_lines channel

let explode s = (* convert a string to a list of chars *)
  let rec exp i l =
   if i < 0 then l else exp (i - 1) (s.[i] :: l) in
  exp (String.length s - 1) []

let implode l = String.of_seq (List.to_seq l)

let range start len = (* makes a new list from start with length len *)
  List.init len (fun x -> x + 1) |> List.map (fun x -> x + start)

(* --- *)

type 'a tree = Leaf of 'a | Node of 'a tree * 'a tree

let rec build_tree l = (* build a balanced tree from a list *)
  match l with (* exception for [] would probably be good here.. *)
  | x::[] -> Leaf x
  | x::xs ->
      let len = List.length l in
      let mid_val = List.nth l (len/2) in
      let left = range (x-1) (len/2) in
      let right = range (mid_val-1) (len/2) in
      Node (build_tree left, build_tree right)

let rec walk tree steps =
  match tree with
  | Leaf a -> a (* if we've hit a leaf, return the value *)
  | Node (l, r) ->
      match steps with (* if we get to the end of theh list and we haven't hit a leaf, that's a problem.. if only i knew how to do exceptions *)
        | 'F' :: xs -> walk l xs
        | 'L' :: xs -> walk l xs
        | 'B' :: xs -> walk r xs
        | 'R' :: xs -> walk r xs

let rows = build_tree (range 0 128)
let cols = build_tree (range 0 8)

let find_seat map =
  let row = walk rows (explode (String.sub map 0 7)) - 1 in (* one-off b/c of their non-0-indexed lists? *)
  let col = walk cols (explode (String.sub map 7 3)) - 1 in
  (row, col)

let seat_id (row, col) = row * 8 + col

let rec list_max li =
  match li with (* again non exhaustive, empty list fails. be better *)
  | x :: [] -> x
  | x :: xs -> max x (list_max xs)

let rec find_missing seats =
  match seats with
  | x :: y :: z -> if y = x + 1 then find_missing (y :: z) else x + 1
  | x :: [] -> x

let seats = read_file "day5.txt" |> List.map find_seat
let seat_ids = List.map seat_id seats
let sorted_seats = List.sort (fun a b -> if a > b then 1 else if a < b then -1 else 0) seat_ids;;

Printf.printf "max seat id %i\n" (list_max seat_ids);;
Printf.printf "missing seat %i\n" (find_missing sorted_seats);;