advent2024

Word Search Puzzle Solution Documentation

Overview

This documentation explores a Rust solution for a word search puzzle, demonstrating several programming principles including functional programming, iterator chaining, and spatial algorithms. The solution effectively searches a 2D grid for specific patterns (“XMAS” and “MAS”) in various directions.

Solution Intuition

The core challenge is to scan a 2D grid of characters to find specific words in multiple directions. The solution utilizes:

A spatial representation model to manage the 2D grid
Direction-based scanning algorithms to find patterns
Functional programming principles to create reusable, composable search functions
Efficient algorithms that avoid unnecessary work

Step 1: Data Representation

The first step is to parse and represent the 2D character grid from the input file.

Insight

A 2D grid requires a data structure that supports efficient positional access and boundary checks. The solution uses a Field<char> type, which wraps a vector of characters and provides methods for accessing elements by their 2D coordinates.

Implementation

let input = std::fs::read_to_string("src/bin/day4/input.txt").expect("File not found");
let field = input.parse::<Field<char>>().expect("Doesn't error");
let (height, width) = (field.height(), field.width());

This code reads the input file and parses it into a Field<char> representation, then extracts the grid dimensions for later use.

Step 2: Direction-Based Word Matching

Next, we need a function to check if a word exists in a specific direction starting from a particular position.

Insight

Word matching needs to:

Start from a specific position
Follow a specific direction vector
Check each character along the path
Handle grid boundaries gracefully

Implementation

fn is_word_matched(field: &Field<char>, word: &str, start: Location, dir: DirVector) -> bool {
    word.char_indices()
        .all(|(i,c)| start
            // calculate new location based on (a) current index (b) starting position & (c) direction
            .move_relative((dir.0 * i as isize, dir.1 * i as isize))
            .map(|p| field
                // match the value in position with input's character
                .get(p)
                .map(|&val| val == c)
                .unwrap_or(false)
            ).unwrap_or(false)
        )
}

This function:

Iterates through each character in the target word with its index
For each character, calculates its expected position using the starting point and direction
Checks if the character at that position matches the expected character
Returns true only if all characters match

The use of map and unwrap_or ensures graceful handling of out-of-bounds coordinates.

Step 3: Building a Reusable Scanner Factory

To avoid code duplication, the solution creates a function that generates specialized word scanners.

Insight

Creating a higher-order function allows:

Preloading common parameters (field, directions)
Returning a specialized function that only needs the word and starting location
Abstracting the complexity of the scanning process

Implementation

fn search_directions<'a>(
    field: &'a Field<char>,
    dirs: &'a [DirVector]
) -> impl Fn(&'a str, Location) -> Box<dyn Iterator<Item=(Location,DirVector)> + 'a>
{
    // return a function that takes a world and location
    // and performs a scan on field and set of directions that has be constructed with
    move |word: &'a str, pos: Location| {
        let ret = dirs.iter()
            .copied()
            .filter(move |&dir| is_word_matched(field, word, pos, dir))
            .map(move |dir| (pos,dir));
        // iterator must be boxed as it doesn't compile with "-> impl Iterator"
        Box::new(ret)
    }
}

This function:

Takes a field and a set of directions to search
Returns a function that takes a word and starting position
The returned function checks if the word exists in any of the specified directions
Returns an iterator of matching positions and directions

The use of Rust’s lifetime annotations and boxed iterators ensures the returned function can be used flexibly.

Step 4: Part 1 - Finding “XMAS” Words

The first part of the puzzle requires counting occurrences of “XMAS” and “SAMX” in the grid.

Insight

For efficiency, we can:

Search for “XMAS” and its reverse “SAMX” simultaneously
Only scan in half the possible directions (the other half is covered by the reverse word)
Use nested iteration over the grid to check all starting positions

Implementation

let xmas_scanner = search_directions(&field, &[(1,0),(0,1),(1,1),(1,-1)]);
let sum = (0..width)
    .map(|x| (0..height)
        .map(|y|
            xmas_scanner("XMAS", Location(x,y)).count()
            + xmas_scanner("SAMX", Location(x,y)).count()
        )
        .sum::<usize>()
    )
    .sum::<usize>();

This code:

Creates a scanner for the horizontal, vertical, and diagonal directions
Iterates over each position in the grid
Counts occurrences of both “XMAS” and “SAMX” starting at each position
Sums the total occurrences

Step 5: Part 2 - Finding “MAS” Crosses

The second part looks for a specific pattern: “MAS” (or “SAM”) in two diagonal directions forming a cross.

Insight

To find this pattern:

We need specialized scanners for the two diagonal directions
We need to check if both diagonals have matches at the same position
The pattern forms a cross with a specific geometry

Implementation

let mas_leg1_scanner = search_directions(&field, &[(1,1)]);
let mas_leg2_scanner = search_directions(&field, &[(1,-1)]);
let sum = (0..height)
    .map(|y| (0..width)
        .filter(|&x|
            (mas_leg1_scanner("MAS",Location(x,y)).count() == 1 ||
                mas_leg1_scanner("SAM",Location(x,y)).count() == 1) &&
                (mas_leg2_scanner("MAS",Location(x,y+2)).count() == 1 ||
                    mas_leg2_scanner("SAM",Location(x,y+2)).count() == 1)
        )
        .count()
    )
    .sum::<usize>();

This code:

Creates two specialized scanners: one for diagonal down-right and one for diagonal up-right
Checks each position to see if it has a “MAS” or “SAM” in the down-right direction
Also checks if there’s a “MAS” or “SAM” in the up-right direction starting 2 positions down
These two conditions together form the cross pattern
Counts the total number of positions where both conditions are true

Testing and Validation

The solution includes a test function to verify the word matching logic:

#[test]
fn test_scan_for_xmas() {
    let input = std::fs::read_to_string("src/bin/day4/sample.txt").expect("File not found");
    let field = input.parse::<Field<char>>().expect("Doesn't error");

    assert!(is_word_matched(&field, "XMAS", Location(9, 9), (-1, -1)));
    assert!(!is_word_matched(&field, "XMAS", Location(8, 9), (-1, -1)));
    // Additional assertions...
}

This test ensures the is_word_matched function correctly identifies words in the expected positions.

Key Design Principles Demonstrated

Function Composition: The solution builds complex behavior from simple, composable functions
Higher-Order Functions: Using functions that produce specialized functions
Iterators and Functional Chains: Leveraging Rust’s iterators for clean, expressive code
Spatial Algorithms: Efficiently handling 2D grid traversal and pattern matching
Error Handling: Gracefully handling boundary conditions and potential errors
Performance Optimization: Minimizing unnecessary work by searching in half the directions

Conclusion

This solution demonstrates how to approach a 2D grid search problem using functional programming principles in Rust. By breaking down the problem into smaller, reusable pieces and leveraging Rust’s type system and iterator patterns, the solution achieves both clarity and efficiency.

The approach is also extensible - new patterns or directions could be easily added by modifying the direction vectors and pattern recognition logic without changing the core algorithm structure.

This site is open source. Improve this page.