Advent of code 2024 - Day 6 part 2

Day6Part2.fsx

open System
let input = """
..................#................................................................#........#.....................................
...#...........#...................................................#........................................#.................#...
...................................#................#.#...............#.................................................#.........
.....#......#................#.....................................................................#..........#........#......#...
............................................................................................#.....................#...............
.....................#..##...#........................#.................#.......................#..#.........#.......#...#......#.
............##....................................##..................#...............................#....#......................
.............#............#.#..#.......#...........#..............#...............#.....#.........................................
....................#..........##.........#.........#................#............................................................
....#.......#................................................................#...#.#..........................................#.#.
..#..............#.....................................#..........#.#....#..............#..................#.#............#.......
.#.......#.........................#........................#..#.....#............................................................
........#...#......................#...........#......................................#....................#......................
.............................#..............#........##....#....................#......#....................#............#......#.
..............#..............#............#.......................##....#..........................................#.........#....
.............#............#..........#..........#...#.....................................................#.......................
..#........#.....#..........................................#................................................#...#.#...#..........
........#.....................#...#..#......#.........................................................#.....##.........#..........
..............................................................................................#...#...............................
..#.......................#..........................#......#...................................................................#.
.......#.........................#..............#.........#.............#.......................................#...#.............
..................#.................#.......................#....................#....................................#...........
...#...#.......#......##.#...............#....#..............#..........................................#....#..#.................
#................................#.......#.....#.......#.............#..................#........#................................
...........#..................................#.......................................................................#.#..#......
.......#........#.........................................#..........................#...........................#.....#..........
................#..#.....................#..#...........................#...........................................#.............
#...#.......................#................................................#................#................................#..
..........#...........................#.......#............................................................................#.....#
..................................#............................................................#..................................
......................#........#.............#....#.....#.......#..........................#..........................#...........
...........................##.................#.............#........................#...#..................#.....................
.............................................................................................................#....#..........#....
................#...................................#...........#..........#....................#............................#....
........#....#................................................#................##..#..................................#...........
...........#....................................................#...#.#......#....................................................
.......................#.........................................................^....................................#...........
..........................#.............##..#........#.#....#.......#....................#...........#.........#.....#............
........#...........................#..#..........................................................#...............................
....#....................................#....#.........................................#.........#...............................
...............#...................................#.....#.................................#....................................#.
......#...............................................................#.............................#........................#....
.........................#.....#.........................#.#...............#.........#.....#..................#..#.........#......
.........................................................#......#........##.......................#...#......#................#...
.......................................#.....#.................................#..................................................
..................#..................................#..........................................................................#.
...................#....#.........#.......#................#....................#.........................#......#.....#..#.......
................................#..............................................................................#....#.............
.....................#.#.............#.................#..........#.......#.........................................#.............
......#....................#....................................................................#...#.............................
........#........#...........#.##.............#........................#............#..............#.........#....#........#......
........................#.................................................................#.......................................
............................................................#.....#....................#............#.....#....#............#.....
...........#............#....#........................................................##............#..............#..............
...........#...........#.....#..............#..............##....#........#......#................................................
..#................................................................................#......................#......#................
....................#.........#......................#.............................#.......#.......................#.............#
..#...#....#......................................................................................................#...............
...........#................................................................................#...............................#.....
....................................#............#..........#.........................#..................................#.......#
...................#......#...................#............#......#........#................#.............#...........#.........#.
........................#..................................#........#..................#..........................................
............#..#...........#..................##....................#...........................................#.................
.......................................................................................#.....#............#.......................
...............................................#....#................................#..#..........................#..#...........
..............#..#.....#.........#....................#.......#..#..............#...............................#.....#...........
..........#............................#..........................................................................................
........................................#........#........................................................#.#.....................
#................#......................#..................................................................................#......
...............................................................................#................................#.................
...................................................................................................................#.#........#...
#........................................................................#......................................#.#...............
...#......#............#...................#.............#........#..........................................#......#.............
..............##....#...................................................#......................#..................................
...............#........................................................................#...........#...#.#.......................
..........#.#.....#................................#...........#........#.......#.................................................
#....................#......................................................................................#.....................
..............#...##...........................................#.............#.......#..................#..............#..........
.#.............................................#..............................................................................#...
...#................................#............................................#............................#...................
..............................#......................................................#..........................................#.
...................#.....................................#..................................#......#..............................
....#.#..........##.............#.......#........................##..........#.................#..................................
#..#................#........##....................................................................................#..............
........#...#.........................................................................#...........................................
......................................................#....#...................#..#.................................#.............
........#...............#........#..............................................#............................#....................
...#..............................#.........................................##.......................................#....#.......
...#................#..............#.......#......................................................................................
........#..................#.............................................................#...........................#....#.......
......................#.#..........#.......#..................................#..#...#............#...............#...............
.....#..................#....#..#......#.......................#.....................................................#............
.....#................................#.........................#..................#.#..........#...#............#.....#..........
....#...................#....#.#.........#........#..................................................................#....#..#....
........#...............#......................................#........#..............................#..........................
....#...#.#.....#..............#..................#..........#...#..#......................#...#..........#......................#
...........#...................................................................................................#................#.
.................................##..............#.............................#...............................#..................
...........#.................#.............##...................................#.......................#.................##......
.....#..................#......#........#.................................................#..#........................#..#........
......#.......#......................................................................#.#.........#....#...........................
..................#.#........................#......#................................................................#......#.....
.....................#............#...................#.....#....................................#.......#..........#.......#.....
#.............................#...............................#...#...............................................................
..##.........#........#......................................#.....................#...#.............#............#..#............
..........#.....................#..#....................#...#....................#....................#.....................#.....
...........#..........#...............#..#..........#..............................................#.#............................
............#...#...#.............#.........#.............................#...............#.......................................
.........#...........#...............................................................#............................................
.#..#.................................................................#............#.#.......................##...................
........##............#...................#................................#......................................................
............................................#..........................#..........................................................
#...................#...........#..............#...#............#.#........#.................#......#.............................
........#....................................#....................................................................................
...........#.........#..#...............#...........#.....##.#......#....##............#....#....#.#.........##.........#.........
..#......................#..........#.................#.................#......#.............................#........#...........
....................#.................#....#..............................#....#.............#....#....#.....................#....
............#.................#.................................#...............................#..#...........................#..
...................................................#.....#..............#.......#....................#.#..........................
..#.........##..#........#...................................................................................#............#.......
.....#..............................#......................................................................#........#.............
................................#........##.......#...............#..............#.......#...#.#........#.........................
..............................#.....................#.........................................#..................................#
...........#...................##.................#.................................#...............................#........#....
..............................#...##......#..................#...#................................#......#.......#...............#
.....................##......#......#.#.......#..............#......#.................#.........#...................#.............
..........................#................................#...........#..........................................................
...#.....#....................#.....................#...#.....#.............................#.#....#.....#.#.................#....
............................#...#........#......................................................................#.....#...........
............#..........##..................#.............................................................#.....#..#...............

"""

let lines (text: string): string list =
    text.Split(Environment.NewLine, StringSplitOptions.TrimEntries ||| StringSplitOptions.RemoveEmptyEntries)
    |> List.ofArray

module DaySix =
    open System.Diagnostics
    type Direction =
        | North
        | East
        | South
        | West

    type Position = Position of x:int * y:int

    type Guard = Guard of Direction * Position

    // Direction helper functions
    module Direction =
        let turnRight = function
            | North -> East
            | East -> South
            | South -> West
            | West -> North

    // Position helper functions
    module Position =
        let isOutsideOf limit (Position(x, y)) =
            x >= limit || y >= limit || x < 0 || y < 0

    // Guard helper functions
    module Guard =
        let rec move (obstacles: Set<Position>) (Guard(direction, (Position (x, y) as position)): Guard) =
            let movedPosition =
                match direction with
                | North -> Position(x, y - 1)
                | East -> Position(x + 1, y)
                | South -> Position(x, y + 1)
                | West -> Position(x - 1, y)

            if Set.contains movedPosition obstacles then
                let turnedDirection = Direction.turnRight direction
                Guard(turnedDirection, position)
                |> move obstacles
            else
                Guard(direction, movedPosition)

        let position (Guard(_, pos)) = pos
        let direction (Guard(dir, _)) = dir

    type FloorPlan = {
        Obstacles: Set<Position>
        Guard: Guard
        Size: int
    }

    module FloorPlan =
        type private ParseState = {
            Obstacles: Position list
            Guard: Guard option
        }

        let private parseChar state x y: char -> ParseState = function
            | '#' -> { state with Obstacles = Position(x, y) :: state.Obstacles }
            | '^' -> { state with Guard = Some(Guard(North, Position(x, y))) }
            | _ -> state

        let parse (lines: string list) =
            let parseState =
                lines 
                |> List.mapi (fun y line ->
                    line.ToCharArray()
                    |> Array.mapi (fun x c -> 
                        parseChar { Obstacles = []; Guard = None } x y c))
                |> List.collect List.ofArray
                |> List.fold 
                    (fun state newState -> 
                        { 
                            Obstacles = newState.Obstacles @ state.Obstacles
                            Guard = match newState.Guard with 
                                       | Some g -> Some g 
                                       | None -> state.Guard 
                        }) 
                    { Obstacles = []; Guard = None }

            match parseState.Guard with
            | None -> None
            | Some guard ->
                Some { 
                    Obstacles = Set.ofList parseState.Obstacles
                    Guard = guard
                    Size = List.length lines 
                }

        let simulateAllMovePositions (floorPlan: FloorPlan) =
            let rec loop guard visited =
                let movedGuard = Guard.move floorPlan.Obstacles guard
                let movedGuardPosition = Guard.position movedGuard

                let guardMovedOffGrid = Position.isOutsideOf floorPlan.Size movedGuardPosition
                if guardMovedOffGrid then 
                    visited
                else 
                    loop movedGuard (Set.add movedGuardPosition visited)

            let initialPosition = Guard.position floorPlan.Guard
            loop floorPlan.Guard (Set.singleton initialPosition)

        let simulate (floorPlan: FloorPlan) =
            let rec detectLoop obstacles visited guard =
                let movedGuard = Guard.move obstacles guard
                let newPosition = Guard.position movedGuard
                let guardMovedOffGrid = Position.isOutsideOf floorPlan.Size newPosition
                
                if guardMovedOffGrid then 
                    false
                else
                    let loopDetected = Set.contains movedGuard visited
                    if loopDetected then 
                        true
                    else
                        let newVisited = Set.add movedGuard visited
                        detectLoop obstacles newVisited movedGuard

            let inFrontOfGuardPosition = 
                floorPlan.Guard 
                |> Guard.move floorPlan.Obstacles 
                |> Guard.position

            let positionsToSimulate = 
                simulateAllMovePositions floorPlan
                |> Set.remove inFrontOfGuardPosition

            printfn $"positions to simulate count: {Set.count positionsToSimulate}"

            positionsToSimulate
            |> Set.toList
            |> List.map (fun pos -> Set.add pos floorPlan.Obstacles)
            |> List.filter (fun obstacles ->
                detectLoop obstacles (Set.singleton floorPlan.Guard) floorPlan.Guard
            )
            |> List.length

    module PartTwo =
        let solve () =
            let parsedFloorPlan =
                input
                |> lines
                |> FloorPlan.parse
            match parsedFloorPlan with
            | None -> failwith "Invalid floorplan"
            | Some floorPlan ->
                FloorPlan.simulate floorPlan

DaySix.PartTwo.solve ()
|> printfn "%d"