summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorBrian Chu <brianmchu42@gmail.com>2023-01-04 21:53:00 -0800
committerBrian Chu <brianmchu42@gmail.com>2023-01-04 21:53:00 -0800
commit1b12f567f8d795224f37f757bff489ffa722a61a (patch)
tree981ea38e7d2dbbfc9245ba34cd6b2816b7109373
parente550d5e41938086d4c893f9ebadfe6a62ba08c8f (diff)
downloadAdventOfCode2022-main.tar.gz
solution for day 15main
-rw-r--r--Program.fs2
-rw-r--r--solutions/day15.fs81
2 files changed, 83 insertions, 0 deletions
diff --git a/Program.fs b/Program.fs
index 558d491..685f22a 100644
--- a/Program.fs
+++ b/Program.fs
@@ -36,5 +36,7 @@ match (day, part) with
| (13, 2) -> printf $"{Day13.part2 ()}\n"
| (14, 1) -> printf $"{Day14.part1 ()}\n"
| (14, 2) -> printf $"{Day14.part2 ()}\n"
+| (15, 1) -> printf $"{Day15.part1 ()}\n"
+| (15, 2) -> printf $"{Day15.part2 ()}\n"
| (x, y) when (1 <= x && x <= 25) && (y = 1 || y = 2) -> raise (NotImplemented("not implemented yet"))
| _ -> raise (NotImplemented("invalid values")) \ No newline at end of file
diff --git a/solutions/day15.fs b/solutions/day15.fs
new file mode 100644
index 0000000..46f03c6
--- /dev/null
+++ b/solutions/day15.fs
@@ -0,0 +1,81 @@
+module Solutions.Day15
+open System.IO
+open System.Text.RegularExpressions
+open FSharpPlus.Operators
+
+let cave = set {0 .. 4_000_000}
+
+type Sensor(location: int*int, beacon: int*int) =
+ let manhattan (x1, y1) (x2, y2) = abs (x1 - x2) + abs (y1 - y2)
+
+ member _.Location = location
+
+ member _.Beacon = beacon
+
+ member _.Distance = manhattan location beacon
+
+ member s.Range (y: int) =
+ let scanWidth = s.Distance - abs (snd s.Location - y)
+ fst s.Location - scanWidth, fst s.Location + scanWidth
+
+ override s.ToString() =
+ $"{s.Location} {s.Beacon}"
+
+let getCoords (line: string) =
+ let matches = Regex.Matches(line, "x=(-?\d+), y=(-?\d+)")
+ matches
+ |> Seq.map ((fun x -> x.Groups) >> Seq.tail >> (Seq.map (fun x -> int x.Value)) >> Array.ofSeq >> (fun x -> x[0], x[1]))
+ |> (Array.ofSeq >> (fun x -> Sensor(x[0], x[1])))
+
+let sensors = File.ReadAllLines("inputs/day15.txt")
+ |> Seq.map getCoords
+ |> List.ofSeq
+
+let rangeSort (ax, ay) (bx, by) =
+ match ax - bx with
+ | 0 -> ay - by
+ | d -> d
+
+let reduceRanges ranges =
+ let foldMerge (acc: (int * int) list) (newStart, newEnd) =
+ match acc with
+ | [] -> [newStart, newEnd]
+ | (currStart, currEnd)::tail when newStart <= (currEnd + 1) && currEnd < newEnd -> (currStart, newEnd)::tail
+ | (_, currEnd)::_ when newStart <= currEnd + 1 -> acc
+ | _ -> (newStart, newEnd)::acc
+ ranges
+ |> List.sortWith rangeSort
+ |> List.fold foldMerge List.empty
+
+let sumRanges acc (rStart, rEnd) = acc + abs (rEnd + 1 - rStart)
+
+let getRanges y =
+ sensors
+ |> List.map (fun x -> x.Range y)
+ |> List.filter (fun x -> fst x < snd x)
+ |> reduceRanges
+
+let part1 () =
+ let beaconCount =
+ sensors
+ |> List.map (fun x -> x.Beacon)
+ |> List.filter (fun x -> snd x = 2_000_000)
+ |> List.distinct
+ |> List.length
+
+ getRanges 2_000_000
+ |> List.fold sumRanges 0
+ |> fun x -> x - beaconCount
+
+
+let part2 () =
+ let getGap ranges =
+ List.sortWith rangeSort ranges
+ |> List.head
+ |> snd
+ |> (+) 1
+
+ seq {0 .. 4_000_000}
+ |> Seq.map (fun i -> i, getRanges i)
+ |> Seq.find (snd >> List.length >> (=) 2)
+ |> fun (i, ranges) -> int64 (getGap ranges) * 4_000_000L + int64 i \ No newline at end of file