open Base
open Core
open Angstrom

type seq = int list [@@deriving sexp]

module Parse = struct
  let maybe p = option () (p >>= fun _ -> return ())

  let intP =
    take_while1 (fun c -> Char.(c = '-' || is_digit c)) >>| Int.of_string

  let int_listP = skip_many (char ' ') *> sep_by1 (skip_many1 (char ' ')) intP
  let int_listsP = sep_by1 (char '\n') int_listP <* maybe (char '\n')

  exception Parse_exn of string

  let parse_input ch : seq list =
    let inp = In_channel.input_all ch in
    match parse_string ~consume:All int_listsP inp with
    | Ok ok -> ok
    | Error e -> raise (Parse_exn e)
end

module Part1 = struct
  let reduce1 s =
    let f (a, last) e = ((e - last) :: a, e) in
    match s with
    | [] -> assert false
    | [ _ ] -> assert false
    | x :: xs -> List.fold ~init:([], x) ~f xs

  let rec all_zeros = function
    | 0 :: rest -> all_zeros rest
    | _ :: _ -> false
    | [] -> true

  (* a very simple recursive procedure: *)
  let rec reduce_all s =
    let last_elem = List.last_exn s in
    let reduced, _ = reduce1 s in
    if all_zeros reduced then last_elem
    else
      let next = reduce_all (List.rev reduced) in
      Out_channel.printf "%d / %d\n" next last_elem;
      next + last_elem

  let process = List.map ~f:reduce_all
end

module Part2 = struct
  (* The same as Part1.reduce_all, except we look at the first element and do a subtraction. *)
  let rec reduce_all s =
    let first_elem = List.hd_exn s in
    let reduced, _ = Part1.reduce1 s in
    if Part1.all_zeros reduced then first_elem
    else
      let next = reduce_all (List.rev reduced) in
      Out_channel.printf "%d / %d\n" next first_elem;
      first_elem - next

  let process = List.map ~f:reduce_all
end

let () =
  let inp = Parse.parse_input In_channel.stdin in
  let result = Part2.process inp in
  let str = Sexp.to_string_hum @@ sexp_of_seq result in
  Out_channel.(
    output_string stdout str;
    output_string stdout "\n";
    printf "Result: %d\n" (List.fold ~init:0 ~f:Int.( + ) result))