From 4c1883d6612ef8d98b24aa3f57bfae3b48406f6f Mon Sep 17 00:00:00 2001 From: Jordan Doyle Date: Thu, 26 Dec 2024 11:10:45 +0700 Subject: [PATCH] Add 2024 day 14 --- README | 4 ++-- 2024/14.ml | 123 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 125 insertions(+), 2 deletions(-) diff --git a/README b/README index 8f51829..492c4a5 100644 --- a/README +++ a/README @@ -27,8 +27,8 @@ | 11 | OCaml | | 11 | Haskell | | 12 | OCaml | | 12 | Rust | | 13 | Rust | | 13 | Haskell | -+---------------------+ | 14 | Haskell | - | 15 | Haskell | +| 14 | OCaml | | 14 | Haskell | ++---------------------+ | 15 | Haskell | | 16 | Haskell | | 17 | Rust | | 18 | Haskell | diff --git a/2024/14.ml b/2024/14.ml new file mode 100755 index 0000000..cff4890 100755 --- /dev/null +++ a/2024/14.ml @@ -1,0 +1,123 @@ +#!/usr/bin/env nix-shell + +(* +#!nix-shell --pure -i ocaml -p ocaml +*) + +let grid_size = (101, 103) + +let midpoint = (fst grid_size / 2, snd grid_size / 2) + +type robot = {p: int * int; v: int * int} + +let input : robot list = + let parse_coord coord = + match + String.sub coord 2 (String.length coord - 2) |> String.split_on_char ',' + with + | [x; y] -> + (int_of_string x, int_of_string y) + | _ -> + failwith "invalid coord" + in + let parse_line line = + match String.split_on_char ' ' line with + | [pos; vel] -> + {p= parse_coord pos; v= parse_coord vel} + | _ -> + failwith "invalid line format" + in + let rec read_input acc = + try (read_line () |> parse_line) :: acc |> read_input + with End_of_file -> acc + in + read_input [] + +let interpolate n = + let positive_mod x m = ((x mod m) + m) mod m in + let interpolate_single robot : robot = + { p= + ( positive_mod (fst robot.p + (fst robot.v * n)) (fst grid_size) + , positive_mod (snd robot.p + (snd robot.v * n)) (snd grid_size) ) + ; v= robot.v } + in + input |> List.map interpolate_single + +let find_in_segments robots = + let in_segment robot = + if fst robot.p < fst midpoint && snd robot.p < snd midpoint then + Some 0 (* top left *) + else if fst robot.p > fst midpoint && snd robot.p < snd midpoint then + Some 1 (* top right *) + else if fst robot.p < fst midpoint && snd robot.p > snd midpoint then + Some 2 (* bottom left *) + else if fst robot.p > fst midpoint && snd robot.p > snd midpoint then + Some 3 (* bottom right *) + else None (* middle *) + in + robots |> List.filter_map in_segment + +module IntMap = Map.Make (struct + type t = int + + let compare = compare +end) + +let group_and_mul lst = + let aux acc x = + let count = (IntMap.find_opt x acc |> Option.value ~default:0) + 1 in + IntMap.add x count acc + in + let fold _key value acc = acc * value in + let grouped = lst |> List.fold_left aux IntMap.empty in + IntMap.fold fold grouped 1 + +let rec debug = function + | x :: xs -> + print_int x |> print_newline ; + debug xs + | [] -> + () + +let rec debug' robots = + let print_robot robot = + print_string "x=" ; + print_int (fst robot.p) ; + print_string " y=" ; + print_int (snd robot.p) |> print_newline + in + match robots with x :: xs -> print_robot x ; debug' xs | [] -> () + +let part1 = + interpolate 100 |> find_in_segments |> group_and_mul |> print_int + |> print_newline + +let part2 = + (* check if all the robots are on unique squares *) + let rec heuristic seen xs = + match xs with + | [] -> + true + | x :: xs -> + if List.mem x seen then false else heuristic (x :: seen) xs + in + let rec debug x y curr = + if x > fst grid_size then ( + print_newline () ; + debug 0 (y + 1) curr ) + else if y > snd grid_size then print_newline () + else if List.mem (x, y) curr then ( + print_int 1 ; + debug (x + 1) y curr ) + else ( + print_char '.' ; + debug (x + 1) y curr ) + in + let rec aux n = + let curr = interpolate n |> List.map (fun robot -> robot.p) in + if heuristic [] curr then ( + print_int n |> print_newline ; + debug 0 0 curr ) + else aux (n + 1) + in + aux 0 -- rgit 0.1.5