path: root/solutions/day15.fs

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