From 1b12f567f8d795224f37f757bff489ffa722a61a Mon Sep 17 00:00:00 2001
From: Brian Chu <brianmchu42@gmail.com>
Date: Wed, 4 Jan 2023 21:53:00 -0800
Subject: solution for day 15

---
 Program.fs         |  2 ++
 solutions/day15.fs | 81 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 83 insertions(+)
 create mode 100644 solutions/day15.fs

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
-- 
cgit 1.4.1-2-gfad0