2024_day7.ml

let input =
"190: 10 19
3267: 81 40 27
83: 17 5
156: 15 6
7290: 6 8 6 15
161011: 16 10 13
192: 17 8 14
21037: 9 7 18 13
292: 11 6 16 20";;

type operator = Add | Mul | Concat;;

let not_eq to_ = Fun.negate ((=) to_);;

let concat_numbers n1 n2 =
  let n1' = Int64.to_string n1 in
  let n2' = Int64.to_string n2 in
  String.concat "" [n1'; n2'] |> Int64.of_string;;

let rec generate_operator_combinations n =
  if n = 0 then [[]]
  else
    let prev = generate_operator_combinations (n - 1) in
    List.concat (List.map (fun l ->
                     [Add::l; Mul::l]
                   ) prev);;

let rec generate_operator_combinations_part_two n =
  if n = 0 then [[]]
  else
    let prev = generate_operator_combinations_part_two (n - 1) in
    List.concat (List.map (fun l ->
                     [Add::l; Mul::l; Concat::l]
                   ) prev);;

let evaluate numbers operators =
  let rec eval nums ops acc =
    match nums, ops with
    | [], []            -> acc
    | n::ns, []         -> acc
    | n::ns, Add::os    -> eval ns os (Int64.add acc n)
    | n::ns, Mul::os    -> eval ns os (Int64.mul acc n)
    | n::ns, Concat::os -> eval ns os (concat_numbers acc n)
    | _, _ -> failwith "Invalid input"
  in
  match numbers with
  | [] -> 0L
  | n::ns -> eval ns operators n

let nums_reach_value generator (test_value, numbers) =
  let operators = generator (List.length numbers - 1) in
  let results   = List.map (evaluate numbers) operators in
  List.exists ((=) test_value) results;;

let parse_line line =
  let seq_line   = String.to_seq line in
  let test_value = Seq.take_while (not_eq ':') seq_line in
  (* Printf.printf "Test value is %s: \n" (String.of_seq test_value); *)
  let test_value_parsed = Int64.of_string (String.of_seq test_value) in
  let numbers = Seq.drop (Seq.length test_value + 2) seq_line
                |> String.of_seq
                |> String.split_on_char ' '
                |> List.map Int64.of_string in
  (test_value_parsed, numbers);;

let part_one_solution input =
  String.split_on_char '\n' input
  |> List.map parse_line
  |> List.filter (nums_reach_value generate_operator_combinations)
  |> List.map fst
  |> List.fold_left Int64.add 0L;;

let part_one () =
  In_channel.with_open_text "../inputs/day7.in" In_channel.input_all
  |> part_one_solution;;

let part_two_solution input =
  String.split_on_char '\n' input
  |> List.map parse_line
  |> List.filter (nums_reach_value generate_operator_combinations_part_two)
  |> List.map fst
  |> List.fold_left Int64.add 0L;;

let part_two () =
  In_channel.with_open_text "../inputs/day7.in" In_channel.input_all
  |> part_two_solution;;