advent_of_code_2022_day_15.nim

import strscans, strformat, sequtils, strutils, algorithm, intsets

type
    Point = tuple[x: int, y: int]
    Sensor = object
        position: Point
        beacon: Point
        maxRange: int
    Bounds = tuple[lower: int, upper: int]

const inputPattern = "Sensor at x=$i, y=$i: closest beacon is at x=$i, y=$i"

proc computeMaxRange(sensor, beacon: Point): int =
    let vOffset = abs(beacon.y - sensor.y)
    let xOffset = abs(beacon.x - sensor.x)
    xOffset + vOffset

proc parseSensors*(input: seq[string]): seq[Sensor] =
    for line in input:
        let (ok, x, y, beaconX, beaconY) = line.scanTuple(inputPattern)

        if ok: 
            var sensor = Sensor(position: (x, y), beacon: (beaconX, beaconY))
            sensor.maxRange = computeMaxRange(sensor.position, sensor.beacon)
            result.add(sensor)
        else: raise newException(Exception, fmt"Invalid input: {line}")

proc rangeAt(sensor: Sensor, y: int): int =
    sensor.maxRange - abs(y - sensor.position.y)

proc noBeaconSpotsCount(sensors: seq[Sensor], y: int): int =
    var noBeaconSpots = initIntSet()

    for sensor in sensors:
        var range = rangeAt(sensor, y)

        if range >= 0:
            for x in sensor.position.x-range..sensor.position.x+range:
                if (x, y) != sensor.beacon and (x, y) != sensor.position:
                    noBeaconSpots.incl(x)
    
    noBeaconSpots.card

proc findDistressBeacon*(sensors: seq[Sensor], bounds: Bounds): Point =
    for y in bounds.lower..bounds.upper:
        block row_loop:
            var ranges: seq[Bounds] = @[(bounds.lower - 1, bounds.lower - 1)]
            for sensor in sensors:
                let range = rangeAt(sensor, y)
                if range >= 0:
                    var lower = sensor.position.x - range
                    var upper = sensor.position.x + range
                    if lower <= bounds.lower and upper >= bounds.upper: break row_loop
                    if lower <= bounds.lower: lower = bounds.lower
                    if upper >= bounds.upper: upper = bounds.upper
                    ranges.add((lower, upper))

            if ranges.len > 1:
                ranges.sort do (a, b: Bounds) -> int: cmp(a.lower, b.lower)

                var maxRight = ranges[0].upper

                for idx in 0..<ranges.len-1:
                    let current = ranges[idx]
                    let next = ranges[idx+1]

                    if maxRight + 1 < next.lower:
                        return (maxRight + 1, y)
                    
                    if current.upper > maxRight:
                        maxRight = current.upper
                    elif next.upper > maxRight:
                        maxRight = next.upper
                
                if maxRight < bounds.upper:
                    return (maxRight + 1, y)
 
let sensors = parseSensors("day-15/input.txt".lines.toSeq)

echo fmt"Count of spots where no beacon can be present: {noBeaconSpotsCount(sensors, 2_000_000)}"
let distressBeaconLocation = findDistressBeacon(sensors, (0, 4_000_000))

echo fmt"Tuning frequency: {(distressBeaconLocation.x * 4_000_000) + distressBeaconLocation.y}"