day6.ml

let solve lines =
  let graph = Hashtbl.create 5000 in
  let cache = Hashtbl.create 5000 in
  lines |> List.iter (fun s ->
      match CCString.split_on_char ')' s with
      | to_ :: from :: [] ->
        begin match Hashtbl.find graph from with
        | exception Not_found ->
          Hashtbl.replace graph from to_;
        | found ->
          failwith @@ Printf.sprintf "Already exists from '%s' -> %s" from found
        end
      | _ -> assert false
    );
  let rec orbits from =
    match Hashtbl.find cache from with
    | exception Not_found -> begin
      try
        let count = 1 + orbits (Hashtbl.find graph from) in
        Hashtbl.replace cache from count;
        count
      with Not_found -> 0
      end
    | count ->
      count
  in
  let part1 = Hashtbl.fold (fun from _ sum -> sum + orbits from) graph 0 in
  Printf.printf "part1 = %d\n" part1;
  let rec path_to_root from =
    match Hashtbl.find graph from with
    | exception Not_found -> []
    | to_ -> from :: path_to_root to_
  in
  let rec shared_path_len p1 p2 =
    match p1, p2 with
    | h1 :: t1, h2 :: t2 ->
      if h1 = h2 then shared_path_len t1 t2 else List.(length p1 + length p2)
    | [], [] -> 0
    | _ -> assert false
  in
  let p_san = "SAN" |> Hashtbl.find graph |> path_to_root |> List.rev in
  let p_you = "YOU" |> Hashtbl.find graph |> path_to_root |> List.rev in
  let part2 = shared_path_len p_san p_you in
  Printf.printf "part2 = %d\n" part2;