In this post we'll walk through my solution to AOC 2024 Day 6 using F#.

HAMINIONs Members get full access to the project files so you can git clone and run it yourself.

Day 6 Part 1

Prompt: https://adventofcode.com/2024/day/6

Given:

• A Map
  • ^ - Guard facing up
  • # - Obstacle
  • . - Empty space
• Guard moves in straight line
  • If hits obstacle, turns right 90 degrees and continues

Ask:

• How many distinct positions will the guard visit before leaving map?

SubProblems:

• A: Moving guard around

  • 1: Imperative
    • Track guard as position, direction
    • Each tick:
      • Check if infinite loop
      • Check if need to turn
      • Try move forward

• B: Tracking positions mapped

  • 1: Keep a visited log - copy of map w visited locations -
    • Data: n
    • Write - O(1)
    • Sum - O(n)
  • 2: Keep a visited log - set of tuples
    • Data: visited
    • Write - O(1)
    • Sum - O(1)

Solutions:

• A:
  • Read input in w map as string list list
  • generate_guard_positions
  • Sum all positions up

Code:

type Position = 
    {
        X: int 
        Y: int
    }

type Direction = 
    | Up 
    | Down 
    | Left 
    | Right 

type GuardPosition = 
    {
        Position: Position 
        Direction: Direction
    }

type MapItem = 
    | Empty 
    | Obstacle 
    | Guard 

type Day6Input = 
    {
        GuardMap: MapItem list list
        GuardPosition: GuardPosition
    }

let string_to_map_item 
    (s: string)
    : MapItem 
    = 
    match s with 
    | s when s = "." -> Empty 
    | s when s = "#" -> Obstacle 
    | s when s = "^" -> Guard 
    | _ -> (raise (InvalidOperationException($"Got value: {s}")))

let is_guard (item: MapItem) = 
    match item with 
    | Guard -> true 
    | _ -> false

let read_input 
    (file_name: string)
    : Day6Input
    =

    let lines = 
        Utils.read_all_input_file_lines
            file_name

    let guard_map = 
        lines 
        |> Seq.map (fun l -> 
            l.ToCharArray()
            |> Array.map (fun c -> string c)
            |> Array.toList
            // l.Split("") |> Array.toList
        )
        |> Seq.toList

    let guard_map_items = 
        guard_map
        |> List.map(fun row -> 
            row |> List.map (fun cell -> string_to_map_item cell)
        )

    let guard_position = 
        guard_map_items 
        |> List.mapi(fun i row -> 
            let guard_position = 
                row 
                |> List.tryFindIndex (fun item -> is_guard item)
            
            match guard_position with 
            | None -> None 
            | Some x -> Some (x, i)
        )
        |> List.choose id 
        |> List.head
        |> fun (x, y) -> 
            {
                X = x 
                Y = y
            }

    let guard = 
        {
            Position = guard_position 
            Direction = Direction.Up
        }

    {
        GuardMap = guard_map_items
        GuardPosition = guard
    }

let get_next_direction
    (direction: Direction)
    : Direction 
    =
    match direction with 
    | Up -> Right 
    | Right -> Down 
    | Down -> Left 
    | Left -> Up

let get_next_position
    (current_position: Position)
    (current_direction: Direction) 
    : Position 
    = 
    match current_direction with 
    | Up -> 
        {
            X = current_position.X 
            Y = current_position.Y - 1
        }
    | Right -> 
        {
            X = current_position.X + 1 
            Y = current_position.Y 
        }
    | Down -> 
        {
            X = current_position.X 
            Y = current_position.Y + 1
        }
    | Left -> 
        {
            X = current_position.X - 1 
            Y = current_position.Y 
        }

let get_map_item_at_position 
    (map: MapItem list list) 
    (position: Position) 
    : MapItem option
    =
    if position.Y < 0 || position.Y >= map.Length 
    then None 
    else 

    if position.X < 0 || position.X >= map[0].Length
    then None 
    else 

    Some (map[position.Y][position.X])

let calculate_all_guard_positions
    (map: MapItem list list)
    (guard_position: GuardPosition)
    : Set<Position>
    =

    let mutable current_position = guard_position.Position
    let mutable current_direction = guard_position.Direction 

    let mutable visited_position_set = Set<Position>([current_position])
    let mutable keep_iterating = true 

    while keep_iterating do 

        let next_position = 
            get_next_position
                current_position
                current_direction

        let next_map_item = 
            get_map_item_at_position 
                map
                next_position

        match next_map_item with 
        | None -> keep_iterating <- false 
        | Some item -> 
            match item with 
            | Guard | Empty -> 
                current_position <- next_position
                visited_position_set <- visited_position_set.Add(current_position)
            | Obstacle -> 
                let new_direction = 
                    get_next_direction
                        current_direction

                current_direction <- new_direction

    visited_position_set


let solve_part1 
    (file_name: string) 
    = 

    printfn "* Day 6.1: Solving"

    let input = read_input file_name

    let visited_position_set = 
        calculate_all_guard_positions
            input.GuardMap
            input.GuardPosition
    
    printfn "* Day 6.1: Total %A" visited_position_set.Count

My Answer -> Accepted

Day 6 Part 2

Prompt: https://adventofcode.com/2024/day/6

Given:

• Same input as above

Ask:

• Find all positions where a new obstacle could be placed that would lead to infinite loop
  • Cannot place at guard start position

SubProblems:

• A: How to determine if in infinite loop?
  • 1: Keep track of all visited locations, including direction
    • Position is not enough (can crossover positions)
    • But if we ever see the exact same (position, direction) then we will loop
    • If get a match -> Loop
    • If instead we leave the map -> No loop
• B: How to figure out if an infinite loop could be created w obstacle at position?
  • 1: Brute force
    • At every position of the guard (except the very first...) see if is loop
      • Same logic as before except we check for infinite loop and early return if so...

Solutions:

• A: Try brute force
  • Iterate over positions - at each, see if would be a loop
  • return all loops

Note:

• Though I initially started with "brute force" it was actually brute forcing on every position the guard walked. I assumed this would be more efficient because we only needed to try places the guard walked to. However this was actually incorrect because the initial path of the guard may have changed base on the addition of an obstacle. It wasn't until I tried true brute force (let's put an obstacle at every x, y and see what happens) that I got the correct answer.

Code:

let is_map_a_loop 
    (map: MapItem list list)
    (guard_position: GuardPosition)
    : bool 
    = 
    let mutable current_position = guard_position.Position
    let mutable current_direction = guard_position.Direction 

    let mutable visited_position_set = Set<(Position * Direction)>([])
    let mutable keep_iterating = true 
    let mutable is_loop = false 

    while keep_iterating do 

        if visited_position_set.Contains((current_position, current_direction)) then 
            is_loop <- true
            keep_iterating <- false

        visited_position_set <- visited_position_set.Add((current_position, current_direction))

        let next_position = 
            get_next_position
                current_position
                current_direction

        let next_map_item = 
            get_map_item_at_position 
                map
                next_position

        match next_map_item with 
        | None -> keep_iterating <- false 
        | Some item -> 
            match item with 
            | Guard | Empty -> 
                current_position <- next_position
            | Obstacle -> 
                let new_direction = 
                    get_next_direction
                        current_direction

                current_direction <- new_direction

    is_loop

let change_map_coordinate 
    (map: MapItem list list) 
    (position_to_change: Position)
    (item: MapItem) 
    : MapItem list list 
    = 
    let new_map = 
        map 
        |> List.indexed 
        |> List.map (fun (y, row) -> 
            row 
            |> List.mapi (fun x i -> 
                let current_position = { X = x; Y = y}
                match position_to_change = current_position with 
                | true -> item 
                | false -> i
                )
        )

    new_map

let find_all_guard_loop_positions_brute_force 
    (map: MapItem list list)
    (guard_position: GuardPosition)
    : Position List 
    =

    let mutable loop_obstacle_positions = List<Position>()

    for y = 0 to map.Length - 1 do
        for x = 0 to map[0].Length - 1 do 

            let current_position = { X = x; Y = y}

            let next_map_item = 
                get_map_item_at_position 
                    map
                    current_position

            match next_map_item with 
            | None -> (raise (InvalidOperationException("Reached end of map")))
            | Some item -> 
                match item with 
                | Guard | Obstacle -> () 
                | Empty -> 
                    let new_map = 
                        change_map_coordinate
                            map
                            current_position
                            Obstacle 
                    
                    let is_loop = 
                        is_map_a_loop 
                            new_map
                            guard_position

                    if is_loop then 
                        loop_obstacle_positions.Add(current_position)


    loop_obstacle_positions

let solve_part2 
    (file_name: string) 
    = 

    printfn "* Day 6.2: Solving"

    let input = read_input file_name
    
    let all_loop_positions = 
        find_all_guard_loop_positions_brute_force
            input.GuardMap
            input.GuardPosition
        |> Set.ofSeq
        |> Set.remove (input.GuardPosition.Position)
    
    printfn "* Day 6.2: Total %A" all_loop_positions.Count

My answer -> Accepted

Next

If you liked this post you might also like my other AOC 2024 solutions.