In this post we'll walk through my solution to Advent of Code 2024 Day 4 using F#.

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

Day 4 - Part 1

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

Given:

• Grid of letters

Ask:

• Count all instances of XMAS
  • All start with X
  • Can be multiple X-MAS
  • Can be horizontal, vertical, diagonal, backwards, overlapping

Note: I thought this question was asking for snaking letters but actually it's asking for XMAS in a single direction. This wasted a LOT of time so read the prompts closely =)

My Solution after realizing this was:

• Iterate over grid, finding all xes
  • If x - count all XMAS
    • Generate all possible directions (8) and find their potential coords
    • Check that each coordinate set equals the expected character
    • Sum the full matches
  • Add to total

Code:

let generate_all_relative_grid_vals = fun () -> 
    let relative_grid_vals = [-1; 0; 1]

    relative_grid_vals
    |> List.map (fun y -> 
        relative_grid_vals
        |> List.map (fun x -> (x, y))
    )
    |> List.concat
    |> List.filter (fun v -> v <> (0, 0))

let is_char_at_position_matching 
    (grid: string array array)
    (x: int)
    (y: int) 
    (to_match: string) 
    : bool 
    = 
    if y < 0 || y >= grid.Length || x < 0 || x >= grid[0].Length 
    then false
    else grid[y][x] = to_match

let count_all_matching_words_straight_line_from_start_position 
    (grid: string array array)
    (x_start: int)
    (y_start: int)
    (target_word: string)
    : int 
    =
    (*
    Foreach direction 
    * get all letter positions
    * check letter against position
    * if all match then check
    *)
    generate_all_relative_grid_vals() 
    |> List.map (fun (x, y) -> 
        seq {0..target_word.Length - 1}
        |> Seq.map (fun v -> (x * v, y * v))
    )
    |> List.map (fun all_coords -> 
        all_coords 
        |> List.ofSeq
        |> List.mapi (fun i (x, y) -> (i, x, y))
        |> List.forall (fun (i, x, y) -> 
            is_char_at_position_matching
                grid 
                (x_start + x)
                (y_start + y) 
                (string target_word[i])
        )
    )
    |> List.filter id 
    |> List.length

let solve_part1 
    (file_name: string)
    =

    printfn "Day 4.1: Solving"

    let input_lines = 
        Utils.read_all_input_file_lines
            file_name

    let letter_grid = 
        input_lines
        |> Seq.map (fun l -> 
            l.ToCharArray()
            |> Array.map (fun c -> string c)
        ) 
        |> Array.ofSeq

    let mutable total = 0

    printfn "Day 4.1: Debug - letter grid length: %A" letter_grid.Length

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

            let found_words_count = 
                count_all_matching_words_straight_line_from_start_position
                    letter_grid
                    x
                    y
                    "XMAS"

            total <- total + found_words_count

    printfn "Day 4.1: Total: %A" total

-> Accepted

Day 4 - Part 2

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

Given:

• Same input as above

Ask:

• Count all MAS in an X shape

SubProblems:

• A: Finding all possible Xes - O(n)
  • A.1: They all have an A in the middle so use that - O(n), exhaustive
• B: Determining if we've found an X - O(n)
  • B.1: Check down_left and down_right
    • down_left if down_left M up_right S or down_left S up_right M

Code:

let is_x_mas 
    (grid: string array array) 
    (x: int) 
    (y: int)
    : bool 
    =
    let is_char_equal = is_char_at_position_matching grid 

    if not (is_char_equal x y "A")
    then false 
    else 

    let left_slash = (
        (is_char_equal (x-1) (y-1) "M"
        && is_char_equal (x+1) (y+1) "S")
        || (is_char_equal (x-1) (y-1) "S"
        && is_char_equal (x+1) (y+1) "M")
    ) 

    let right_slash = (
        (is_char_equal (x+1) (y-1) "M"
        && is_char_equal (x-1) (y+1) "S")
        || (is_char_equal (x+1) (y-1) "S"
        && is_char_equal (x-1) (y+1) "M")
    ) 

    left_slash && right_slash

let solve_part2 
    (file_name: string) 
    = 
    printfn "Day 4.2: Solving"

    let input_lines = 
        Utils.read_all_input_file_lines
            file_name

    let letter_grid = 
        input_lines
        |> Seq.map (fun l -> 
            l.ToCharArray()
            |> Array.map (fun c -> string c)
        ) 
        |> Array.ofSeq

    let mutable total = 0

    printfn "Day 4.2: Debug - letter grid length: %A" letter_grid.Length

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

            let found_words_count = 
                match (is_x_mas letter_grid x y) with 
                | true -> 1 
                | false -> 0

            total <- total + found_words_count

    printfn "Day 4.2: Total: %A" total