Advent of Code Day 4 in Golang: Searching XMAS and X-MAS

Introduction

Moving on to day 4, we have a grid problem in front of us, we are given some numbers in the form of a grid, i.e. some rows and columns with some upper case letters. What we need to do is to find is the word XMAS in any direction (up, left, down, right, diagonals), and in the second part we need to find the word MAS forming an X.

So, let’s see how we can approach this and solve it in golang.

You can check out my solutions here on GitHub.

Mr-Destructive / advent_of_code

Advent of Code

Constructing the grid

The most fundamental part of the problem lies in actually converting the text into a grid or a matrix form. We can split the lines, into individual lines and append each character as an element in a list, and that way we can have a list of list of strings which is a matrix or grid-like (2-dimensional) structure.

So, below is the input for the puzzle.

MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX

We need to convert it into something like this

[
    [M M M S X X M A S M]
    [M S A M X M S M S A]
    [A M X S X M A A M M]
    [M S A M A S M S M X]
    [X M A S A M X A M M]
    [X X A M M X X A M A]
    [S M S M S A S X S S]
    [S A X A M A S A A A]
    [M A M M M X M M M M]
    [M X M X A X M A S X]
]

So, this is a list of strings, we can say in golang it is a [][]string . We can do that by creating a function like this:

func ConstructGrid(lines []string) [][]string {
    grid := [][]string{}
    for _, line := range lines {
        row := []string{}
        for _, char := range strings.Split(line, "") {
            row = append(row, char)
        }
        grid = append(grid, row)
    }
    return grid
}

The above function takes in a list of strings and returns a list of list of strings that are individual letters in the grid.

We can read the file bytes and split the bytes on newline characters and then this will be used as the input for this function.

So, once the input is parsed into a grid, we can start thinking about the actual logic of finding the word XMAS in it.

Part 1

So, in the first part, we need to find the word XMAS in the matrix which could be appearing:

• forwards (as XMAS)

• backward (as SAMX)

• upwards
  

            S
            A
            M
            X

• downwards

            X
            M
            A
            S    

• Diagonal upwards (right or up left)

            S
              A
                M
                  X

            OR
                  S
                A
              M 
            X

• Diagonals downwards (right or left)

                     X
                   M
                 A
               S

            OR

            X
              M
                A
                  S

So, there are 8 directions where XMAS could appear in the grid, there could n number of these XMAS . We need to find the count of these in the grid.

To approach this, we can either find the first character in the word XMAS and then search in all directions one by one and check if we find M and if we have found M in any of the directions, we keep moving ahead in that direction and check if there is A and S in that direction.

The approach looks like this:

• Initialize the counter to 0

• Iterate over each line

  • Iterate over each character in the line

    • Check if the character is equal to X

    • If the character is X→

      • Iterate over all the directions (up, down, right, left, up-left, up-right, down-left, down-right)

        • For that direction if we find the character to be M
        • Keep moving ahead in the same direction to find A and S similarly, if we found all the characters XMAS then, increment the counter
        • Else choose another direction in the loop

This looks complex and large but is simple, focus one thing at a time and you can solve this easily.

So, for the implementation of this, we need to define a few things first:

 var directions [][]int = [][]int{
    []int{0, -1},   // up
    []int{0, 1},  // down
    []int{1, 0},   // right
    []int{-1, 0},  // left
    []int{1, -1},   // up right
    []int{-1, -1},  // up left
    []int{1, 1},  // down right
    []int{-1, 1}, // down left
}

var wordList []string = []string{"X", "M", "A", "S"}

So, we have defined the list of integers in the directions which are the x and y coordinates that we need to add or subtract to get to the desired location. It is basically like a unit vector, it has a distance of 1 and a direction indicated by + or - indicating to move the left or right for x coordinates and up and down for y c-ordinates.

So, let me explain that more clearly, let’s say I am at (1,2) in the grid which is of 4x4 dimension.

A B C D
E F G H
I J K L
M N O P

So, at 2,1 we have G , so we check some directions for this

up → 0,-1 → 2+0, 1-1 → 2,0, we have moved to C

right → 1,0 → 2+1, 1+0 → 3,1 , we have moved to H

down, left → -1,1 → 2-1, 1+1 → 1, 2, we have moved to J

So, you get the idea, that we are moving in some directions using these coordinates.

We can use these to get the next direction jump we want to make to find if that element has the next character in the word that we are searching.

We will write a function that does this first and abstract the function that checks if we have found the word in the grid.

func TraverseGrid(grid [][]string) int {
    score := 0
    for x, row := range grid {
        for y, char := range row {
            if char == wordList[0] {
                for _, direction := range directions {
                    if FindXMAS(x, y, 1, direction, grid) {
                        score += 1
                    }
                }
            }
        }
    }
    return score
}

The above function takes in a grid and returns an integer which will be the score i.e. the count of words XMAS found in the grid/matrix.

First, we need to iterate through each of the rows in the grid, for each row, we iterate over the character, so we will have x and y coordinates as the index of the grid. We need to then check if the current character is X or wordList[0] , if that is the case, we iterate over all the directions and check if we can find XMAS i.e. MAS in that direction, if so we increment the counter. What is the FindXMAS function, let’s abstract that away, and pass in the x, y, which are the coordinates of the current word, 1 which will be the word position of the XMAS and in this case, we already have found X we need to find MAS in that direction. We pass the grid and the direction, so this function will return true or false if that direction has MAS in it.

So to iterate:

• We iterate over the grid and get row and x as the list of strings and index of the current row.

• For each row i.e. list of strings, we iterate over the list of strings to get char and y as the character (string) and the index of that character in the list of the string.

• If we find the current character to be equal to X which is the 0th index of the wordList then

  • We iterate over all the directions and call the function FindXMAS to check if the remaining word MAS in that direction
  • If we find all the words, we increment the counter.

• So, we return the counter as we count the number of words XMAS in the grid/matrix.

Now, we can implement the FindXMAS function, that takes in a x, y coordinates, the wordPosition, the direction and the grid, and return if the word is found.

• First, we take the current x coordinates and add the direction’s x component (0th index or first element)

• add current y coordinates to the direction’s y component (1st index or second element)

• if the word position i.e.. the word index or the word itself in the current function is equal to the wordList, it means that it has found the required word completely

• We need to check by adding the direction to the x and y coordinates, we are not overshooting the width and height of the grid, so if we do, we return a false

• The final if is for checking if the current character is equal to the word that we are looking for, it could be M, A , or S . If so, we return the recursively call the FindXMAS function by passing the updated x and y coordinates and the next word in the wordList, we keep the direction the same and pass the entire grid.
  

func FindXMAS(x, y, wordPosition int, direction []int, grid [][]string) bool {
    xNext := x + direction[0]
    yNext := y + direction[1]
    if wordPosition > len(wordList)-1 {
        return true
    }

    if xNext < 0 || xNext >= len(grid) || yNext < 0 || yNext >= len(grid[x]) {
        return false
    }

    if grid[xNext][yNext] == wordList[wordPosition] {
        return FindXMAS(xNext, yNext, wordPosition+1, direction, grid)
    }
    return false

}

So, we have implemented the FindXMAS function, this will just return if we have found the MAS word by going in a particular direction by updating the coordinates and checking if the word at that position in the gird is the next word in MAS list.

So, this is what the entire first part looks like:

func main() {
    lines := ReadFileLines("sample.txt")
    grid := ConstructGrid(lines)
    score := TraverseGrid(grid)
    fmt.Println(score)
}

We take in the lines as a list of strings and pass that to ConstructGrid and get the grid, finally, we call TraverseGrid , by passing the grid and getting the score as the count of the words XMAS in the grid.

That’s it from the part 1.

Part 2

For part two, we need to find MAS in the cross shape, like below:

M.S
.A.
M.S

So, to solve this, we can do a similar approach but much simpler, we just need to find A as there will always be the word MAS in the center, so we just check if we have A and the top-left, top-right, or bottom-right, bottom-left has M or S .

We get the coordinates of the top-right, top-left positions, down-right, and down-left positions by adding and subtracting 1 from it. We make a basic check if we are not overshooting the boundary of the grid. If we overshoot the boundaries, we won’t find the MAS

But if we are within the grid, we now get the character at those 4 positions, we check if the top-left and bottom-right have M and S or S or M, similarly for top-right and bottom-left has M and S or S or M respectively. This is the diagonal search for M and S above and below the character A.

So, if we have both the diagonal matched we return true.

func FindMAS(x, y int, grid [][]string, wordList []string) bool {
    xL, yT := x-1, y+1 // Top-left neighbor
    xR, yD := x+1, y-1 // Bottom-right neighbor

    // Check if the indices are within bounds
    if xL < 0 || xR >= len(grid) || yT < 0 || yD < 0 ||
        yT >= len(grid[xL]) || yD >= len(grid[xR]) {
        return false
    }

    topLeft := grid[xL][yT]
    bottomRight := grid[xR][yD]
    topRight := grid[xR][yT]
    bottomLeft := grid[xL][yD]

    word1, word3 := wordList[1], wordList[3]

    isDiagonalMatch := (topLeft == word1 && bottomRight == word3) || (topLeft == word3 && bottomRight == word1)
    isAntiDiagonalMatch := (topRight == word1 && bottomLeft == word3) || (topRight == word3 && bottomLeft == word1)

    return isDiagonalMatch && isAntiDiagonalMatch
}

So, that is the simple implementation for finding the MAS the diagonal.

Now, we need to change the TraverseGrid a bit, as we just iterate over the grid, and check if we have A in the character in the row, i.e. wordList[2]. Now, if we have A, we need to call the FindMAS function with the current coordinates and the grid, if that function returns true, we increment the counter,.

func TraverseGrid2(grid [][]string) int {
    score := 0
    for x, row := range grid {
        for y, char := range row {
            if char == wordList[2] {
                if FindMAS(x, y, grid) {
                    score += 1
                }

            }
        }
    }
    return score
}

So, that is the final implementation of part 2, we get the count of MAS in the cross direction.

You can check out my solutions here on GitHub.

Conclusion

So, that is it from day 4 of Advent of Code in Golang, let me know if you have any suggestions, and how you approached it. any better solutions?

Happy Coding :)