Created
December 5, 2019 00:34
-
-
Save leviroth/880d7ea041afd0c326b44f9151cdee22 to your computer and use it in GitHub Desktop.
Advent of code 2019 / day 3
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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