Day 4 - Word Search

Ok, we're at our first grid based day of the advent of code.

We're looking for the word XMAS in grids that look a bit like this:

..X...
.SAMX.
.A..A.
XMAS.S
.X....

Well, except that in this case, they've made the grid easier to read, the real input is going to have the . characters replaced with other characters, so it's going to look more like this:

MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX

There are two data structures we can use here, a simple one or a slightly more complex one.

In the simple one, we simply use a vector of vectors, so [[1,2],[3,4]] style, and index into it using grid[y][x].

The downside to that is that we need to handle asking for x or y coordinates that are outside the bounds.

The more complex one is to use a Map structure that stores the glyph for each coordinate, so grid[(x,y)].

The advantage of a map structure is we can use a get_or_default fetch, and return a known null glyph . for coordinate that isn't matched.

Generally speaking, Maps are better for sparse grids, where we have a small number of items. In this case we have a dense structure, so I think I'm going to go for the Vector of Vectors approach.

We're going to wrap that in a Grid struct, with a getAt function that handles out of bounds checking.

On the actual algorithm, I think the simplest option is to go through the entire grid, character by character, lookng for X glyphs.

When we find one, we'll then start a search in all 8 cardinal directions, moving the coordinates by 1 each time, and search for M, A and S. We'll return the number we found, and then continue the search.

I note that we're going to want to think about coordinates and maybe add them together (because a move north is like adding (0,-1) to (x,y)), and so we may want a coordinate structure as well.

Here's our coordinate, with an X and Y fields. We're making sure it can be copied, clones, compared and printed

#[derive(Debug, Copy, Clone, PartialEq)]
pub struct Coordinate {
    x: i32,
    y: i32
}

We want to be able to create new ones

impl Coordinate {
    fn new(x: i32, y:i32) -> Self {
        Self {
            x,
            y,
        }
    }
}

We want to add Coordinates together, which is std::ops:Add to enable us to use the + symbol in the compiler

impl std::ops::Add for Coordinate {
    type Output = Self;
    fn add(self, other: Self) -> Self {
        Self {
            x: self.x + other.x,
            y: self.y + other.y
        }
    }
}

Get on the grid

My plan is for our grid to hold our array of arrays. Note I said vector above, but actually, this isn't going to change size once initialised, so an array is probably more efficient.

We can't define the size in the struct because we don't know it at compile time, only at runtime

However, Rust is really pedantic and wont let us create fixed sized arrays of chars, because different chars are different sizes.

Since I know these are all ascii characters, I could cheat here, but while it feels less efficient, we're going to use Vector of Vectors instead.

Our first attempt at a Grid based structure and functions therefore looks a bit like this:

pub struct Grid {
    grid: Vec<Vec<char>>,
    width: usize,
    height: usize
}

impl Grid {
    fn new(source: &Vec<Vec<char>>) -> Self {
        // We're going to initialise from the collection becase we want to know the length up front
        let mut grid = Grid {
            grid: source.clone(), // We're making a copy here, this might make more sense to be a borrow
            height: source.len(),
            width: source[0].len()
        };
        return grid;
    }

    fn get(self: &Self, c: Coordinate) -> char {
        // Number conversions in Rust make me sad... lots of "expect" here.
        if c.x >= i32::try_from(self.width).expect("Width is way too high") || c.x < 0 || c.y >= i32::try_from(self.height).expect("Height is way too high") || c.y < 0 { 
            '.' 
        } else { 
            self.grid[usize::try_from(c.y).expect("")][usize::try_from(c.x).expect("")] 
        }
    }
}

I really dislike that get function, which takes a coordinate and returns the char at that coordinate. We want to handle errors and going out of bounds, but comparing an i32 32 bit signed number with a usize which is an architecture dependant value that can hold the size of an array in memory is undefined.

I'm later going to learn that I can do this much nicer with self.width as i32, but at this point I didn't know that.

USize doesn't matter right?

As I get into solving the actual word search, I run up against this usize versus numbers type problem repeatedly. I think I'm partly thankful for this, if I were building much lower level system code, such as device drivers, kernal code or anything actively dealing with memory, having to stop and think about whether the numbers I want to use are actually reasonable for indexing the amount of memory I have is handy. But for this kind of problem, especially where I'm considering coordinates on a grid, I find it keeps getting in my way.

I create a helper function for creating a new coordinate from some usize numbers, and also discover that Rust doesn't have operator type overloading in the way I remember from my C++ days. This results in the very ugly new_usize method:

fn new_usize(x: usize, y: usize) -> Self {
    Self {
        x: i32::try_from(x).expect("X out of bounds"),
        y: i32::try_from(y).expect("Y out of bounds"),
    }
}

I also realise that as well as being able to add two coordinates together, so (5,2) + (2,3) should equal (7,5), I might want to multiply them. Now technically, we can't actually multiply a point, it makes no real sense, and I'd argue you can't really add points together either. I'm combining the concept of a mathmatical vector with a point.

The joy of having done games development is that certain patterns are ingrained in me. A vector is normally defined as a start point, a direction and a magnitude. i.e. your vector of your heading when driving is your current position, your heading and the speed you are traveling at. If you do any games programming that involves bullets, people, vehicles or really anything moving, it's useful to have something to represent these. Your current location is a point, and a point+a vector results in a new point. However, because we often want vectors to be used in lots of places, we often use a zero-based vector, so always assuming that the position is at (0,0), this means our vector is just a heading and a magnitude. But if we assume that a vector going directly in the positive direction of the X axis for a magnitude of 3 units, we could store that as something like ((1,0), 3), but it's far easier to internally store that as simply a change in x and a change in y, so (3,0). That looks a lot like a coordinate, so I've reused coordinate types for this. At some point, if we have enough grid problems, I might refactor this all out into some utility classes and I might tidy this up.

This is what I do in the next section, I store a set of transformations that indicate moving in a given direction. In this case, all by one square, including diagonally, so we end up with 8 cardinal directions, represented by this list [(-1, -1),(0, -1),(1, -1),(-1, 0),(1, 0),(-1, 1),(0, 1),(1, 1)], or to lay it out in a more obvious way:

(-1, -1),(0, -1), (1, -1),
(-1, 0 ),         (1,  0),
(-1, 1 ),(0,  1), (1,  1)

However, we also want to check 2 steps, 3 steps and 4 steps out in each direction, and for that we need a multiplication of our vector. So what do you get if you adjust the magnitude of a vector? Well it's actually pretty each, and exactly what you'd expect, you simply multiply all the axes by your single scalar value, so (1,-2) * 2 = (2,-4).

We add that to our type system:

// Multiplying a coordinate by a scalar is a lengthwise multiplication, i.e. (2,3)*3 should be (6,9)
impl std::ops::Mul<i32> for Coordinate {
    type Output = Self;
    fn mul(self, other: i32) -> Self {
        Self {
            x: self.x * other,
            y: self.y * other,
        }
    }
}

And now we can solve the problem. The algorithm is pretty simple, it's the same one I taught my children when doing those wordsearches you get on childrens menus in restaurants. You find the word you are looking for XMAS and take the first letter, you then scan the grid left to right, top to bottom looking for the first letter. When you find it, you look in all 8 directions looking to see if the second letter is 1 place away, the third letter and so on.

    let directions = [
        Coordinate::new(-1, -1),
        Coordinate::new(0, -1),
        Coordinate::new(1, -1),
        Coordinate::new(-1, 0),
        Coordinate::new(1, 0),
        Coordinate::new(-1, 1),
        Coordinate::new(0, 1),
        Coordinate::new(1, 1),
    ];
    let mut found = 0;
    for y in 0..grid.height {
        for x in 0..grid.width {
            if grid.get(Coordinate::new_usize(x, y)) == 'X' {
                let c = Coordinate::new_usize(x, y);
                for direction in directions {
                    let mut foundhere = true;
                    for (step, letter) in [(1, 'M'), (2, 'A'), (3, 'S')] {
                        if grid.get(c + (direction * step)) != letter {
                            foundhere = false
                        }
                    }
                    if foundhere {
                        found += 1;
                    }
                }
            }
        }
    }
    return found;

We use the mutable foundhere variable as a short circuit to see if we've found just XMX for example. If we hit a letter we're not supposed to have, we set the variable to false. Only if once we've searched all 3 extra letters, if the variable is still true, then we've found a word.

We're just counting the number of words found, and this is an exhaustive search, but it works well and we move onto part 2

Part 2 - Oh... An Ex-Mas

This isn't actually an XMAS puzzle; it's an X-MAS puzzle in which you're supposed to find two MAS in the shape of an X. One way to achieve that is like this:

M.S
.A.
M.S

Irrelevant characters have again been replaced with . in the above diagram. Within the X, each MAS can be written forwards or backwards.

Ok, this looks horrendous at first, but actually it's just a variation of the previous approach.

Instead of searching for X's and then walking 3 steps in a direction, we're now going to look for 'A's first.

We're then going to look in the 4 diagonal directions, for specificallly, 'M' and 'S' tokens.

Again, I could simplify, but I'm not sure I want to.

2 minutes later...

Oh inteersting, where the M and the S are doesn't matter, providing they are opposite. That's an interesting twist. So if we find an 'A', we don't know if we're looking for an 'M' or an 'S'. Easy exhaustive search is to look at all four corners for an M and then look in opposite corner for an S. To find the opposite corner, I suspect we can multiply the coordinate by -1, becuase (1,1)'s opposite is -1,-1, and 1,-1 is opposite -1,1...

pub fn part2(grid: &GeneratorResult) -> RunResult {
   let directions = [
       Coordinate::new(-1, -1),
       Coordinate::new(1, -1),
       Coordinate::new(-1, 1),
       Coordinate::new(1, 1),
   ];
   let mut found = 0;
   for y in 0..grid.height {
       for x in 0..grid.width {
           if grid.get(Coordinate::new_usize(x, y)) == 'A' {
               let c = Coordinate::new_usize(x, y);
               let mut foundhere = 0;
               for direction in directions {
                   if grid.get(c + direction) == 'M' && grid.get(c + (direction * -1)) == 'S' {
                       foundhere += 1
                   }
               }
               if foundhere == 2 {
                   found += 1;
               }
           }
       }
   }
   return found;
}

A couple of thoughts here. At first I tried just counting the M and S tokens, but that would have matched

M S
 A
S M

Which isn't valid. So we compare the opposites, and make sure that if there's an M in one direction, there's an S in the other direction.

We also expect that a proper cross should have two examples of that, so we only say we've found one if we get exactly two examples.

We still search in all 4 corners because we want to account for MAS to be written forwards or backwards. We could have alternatively just picked two corners and looked for either MAS or SAM, but this felt cleaner