Skip to content

Instantly share code, notes, and snippets.

@leviroth
Created December 5, 2019 00:34
Show Gist options
  • Save leviroth/880d7ea041afd0c326b44f9151cdee22 to your computer and use it in GitHub Desktop.
Save leviroth/880d7ea041afd0c326b44f9151cdee22 to your computer and use it in GitHub Desktop.
Advent of code 2019 / day 3
open! Core
open! Import
module Direction = struct
type t =
| Up
| Down
| Left
| Right
[@@deriving sexp]
let add t distance (x, y) =
match t with
| Up -> x, y + distance
| Down -> x, y - distance
| Left -> x - distance, y
| Right -> x + distance, y
;;
end
module Step = struct
type t =
{ direction : Direction.t
; distance : int
}
[@@deriving sexp]
end
let visited_points steps =
let points = Int_pair.Table.create () in
let number_of_steps = ref 0 in
let run_one point ({ direction; distance } : Step.t) =
List.range ~stop:`inclusive 1 distance
|> List.iter ~f:(fun distance ->
incr number_of_steps;
Direction.add direction distance point
|> Hashtbl.update points ~f:(function
| None -> !number_of_steps
| Some n -> n));
Direction.add direction distance point
in
let (_ : Int_pair.t) = List.fold steps ~init:(0, 0) ~f:run_one in
points
;;
let manhattan_distance (x, y) = abs x + abs y
let map_pair (a, b) ~f = f a, f b
let solve_part_1 steps =
let visited_points steps =
visited_points steps |> Hashtbl.keys |> Int_pair.Hash_set.of_list
in
let points_a, points_b = map_pair steps ~f:visited_points in
let intersection_without_origin =
let result = Hash_set.inter points_a points_b in
Hash_set.remove result (0, 0);
result
in
Hash_set.to_list intersection_without_origin
|> List.map ~f:manhattan_distance
|> List.min_elt ~compare
|> Option.value_exn
;;
let solve_part_2 steps =
let distances_a, distances_b = map_pair steps ~f:visited_points in
let intersection_without_origin =
let points distances = Hashtbl.keys distances |> Int_pair.Hash_set.of_list in
let result = Hash_set.inter (points distances_a) (points distances_b) in
Hash_set.remove result (0, 0);
result
in
Hash_set.to_list intersection_without_origin
|> List.map ~f:(fun point ->
Hashtbl.find_exn distances_a point + Hashtbl.find_exn distances_b point)
|> List.min_elt ~compare
|> Option.value_exn
;;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment