Mercurial > lbo > hg > aoc22
changeset 44:070e01565b16
Day 06 Part 1
| author | Lewin Bormann <lbo@spheniscida.de> |
|---|---|
| date | Wed, 06 Dec 2023 20:13:48 +0100 |
| parents | 865325736c6f |
| children | ec052bcd3e40 |
| files | 2023/day06.ml 2023/input/06.txt 2023/input/06_test.txt |
| diffstat | 3 files changed, 74 insertions(+), 0 deletions(-) [+] |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/2023/day06.ml Wed Dec 06 20:13:48 2023 +0100 @@ -0,0 +1,70 @@ +open Angstrom +open Base +open Core + +type race = { time : int; distance : int } [@@deriving sexp] + +module Parse = struct + let maybe p = option () (p >>= fun _ -> return ()) + + let intP = + take_while1 (function '0' .. '9' -> true | _ -> false) >>| Int.of_string + + let int_listP = + skip_many (char ' ') *> sep_by1 (skip_while Char.is_whitespace) intP + + let timesP = + string "Time:" *> skip_while Char.is_whitespace *> int_listP <* char '\n' + + let distancesP = + string "Distance:" *> skip_while Char.is_whitespace *> int_listP + <* maybe (char '\n') + + exception Parse_exn of string + + let parse_input ch = + let input = In_channel.input_all ch in + match parse_string ~consume:All (list [ timesP; distancesP ]) input with + | Ok (a :: b :: _) -> + let zipped = List.zip_exn a b in + List.map ~f:(fun (time, distance) -> { time; distance }) zipped + | Ok _ -> raise (Parse_exn "not enough parts") + | Error e -> raise (Parse_exn e) +end + +module Part1 = struct + (* we only need to calculate the two roots of the quadratic equation + + 0 = t_hold ** 2 - t_race * t_hold + distance / acceleration + + where acceleration is 1 mm/ms**2. + + The number of integers between roots is the solution. + *) + let hold_times t0 x0 = + let open Float in + let p_half = -.t0 /. 2. in + let q = x0 in + let min = -.p_half -. sqrt ((p_half ** 2.) -. q) in + let max = -.p_half +. sqrt ((p_half ** 2.) -. q) in + (min, max -. 1e-6) + + let possibilities t0 x0 = + let min, max = hold_times (Float.of_int t0) (Float.of_int x0) in + Out_channel.printf "%f %f\n" min max; + let diff = + Int.of_float (Float.round_down min) - Int.of_float (Float.round_down max) + in + Int.abs diff + + let process races = + let f { time; distance } = possibilities time distance in + let all_possibs = List.map ~f races in + Out_channel.print_endline + (Sexp.to_string_hum (List.sexp_of_t Int.sexp_of_t all_possibs)); + List.fold ~init:1 ~f:( * ) all_possibs +end + +let () = + let parsed = Parse.parse_input In_channel.stdin in + Out_channel.printf "%d\n" (Part1.process parsed)