Day 6: Guard Gallivant | Maxwell Durrant | Senior Full-Stack Developer Specialising in Database Systems

Part 1

To begin I parsed the map into a 2D array.

function parseInput(input: string) {
    return input.split('\n').map(line => line.split(''));
}

I also then created a function to find add blockades to a set.

function parseBlockades(map: string[][]): Set<string> {
    const blockades = new Set<string>();
    for (let i = 0; i < map.length; i++) {
        for (let j = 0; j < map[i].length; j++) {
            if (map[i][j] === '#') {
                blockades.add(`${i},${j}`);
            }
        }
    }
    return blockades;
}

As well as detecting the guards original location.

function parseGuard(map: string[][]) {
    let guardLocation: number[] = [];
    let direction: string = '';
    for (let i = 0; i < map.length; i++) {
        for (let j = 0; j < map[i].length; j++) {
            const currentPos = map[i][j];
            if (currentPos === '^' || currentPos === '>' || currentPos === '<' || currentPos === 'v') {
                guardLocation = [i, j];
                direction = currentPos;
                break;
            }
        }
    }
    return [guardLocation, direction];
}

I then liked the idea of making a Guard object and having them actually walk around. As such this isn't the most optimal code, but it was very fun to create.

class Guard {
    uniqueLocationsArray: boolean[][];
    uniqueCount: number = 0;
    location: number[];
    blockades: Set<string> = new Set<string>();
    directionMap = { '^': 0, '>': 1, 'v': 2, '<': 3 };
    map: string[][];
    directionIndex: number;

My guard has the following:

uniqueLocationsArray, this will store the coords of all unique locations they visit.
uniqueCount, the stores the total amount of unique locations.
location, this is the guards current location.
blockades, this is the guards record of what blockades exist.
directionMap, this the directions the guard can move.
map, the map in which the guard can move.
directionIndex, an index letting us know the currect direction we are moving in.

I then create a constructor, in which I blank my uniqueLocationsArray and set my direction.

constructor(location, direction, blockades, map) {
        this.location = location;
        this.blockades = blockades;
        this.map = map;
        this.uniqueLocationsArray = Array.from({ length: map.length }, () => new Array(map[0].length).fill(false));
        this.directionIndex = this.directionMap[direction];
    }

I then create movement methods.

moveUp() {
        const [x, y] = this.location;
        return [x - 1, y];
    }

    moveDown() {
        const [x, y] = this.location;
        return [x + 1, y];
    }

    moveLeft() {
        const [x, y] = this.location;
        return [x, y - 1];
    }

    moveRight() {
        const [x, y] = this.location;
        return [x, y + 1];
    }

Up next are my two conditional methods, one to detect if a location contains a boundary and another to check if we are out of the map.

checkBlockade(newLocation: number[]) {
        return !this.blockades.has(`${newLocation[0]},${newLocation[1]}`);
    }

    hasLeftBoundary() {
        const [x, y] = this.location;
        return x < 0 || y < 0 || x > this.map.length - 1 || y > this.map[0].length - 1;
    }

Finally, I create a movement function, this will, whilst the guard is within the boundary allow them to move about the board. They will move based on their direction and upon approaching a blockade will turn 90 degrees clockwise to continue, all whilst logging their unique positions.

move() {
        while (!this.hasLeftBoundary()) {
            let newLocation: number[] = [];

            if (this.directionIndex === 0) newLocation = this.moveUp();
            else if (this.directionIndex === 1) newLocation = this.moveRight();
            else if (this.directionIndex === 2) newLocation = this.moveDown();
            else newLocation = this.moveLeft();

            if (this.checkBlockade(newLocation)) {
                this.location = newLocation;
                if (!this.hasLeftBoundary()) {
                    if (!this.uniqueLocationsArray[this.location[0]][this.location[1]]) {
                        this.uniqueLocationsArray[this.location[0]][this.location[1]] = true;
                        this.uniqueCount++;
                    }
                }
            }
            else {
                this.directionIndex = (this.directionIndex + 1) % 4;
            }
        }
    }

Finally, I create an accessor to get the total unique locations of my guard.

getUniqueLocations() {
        return this.uniqueCount;
    }

Final Guard class

class Guard {
    uniqueLocationsArray: boolean[][];
    uniqueCount: number = 0;
    location: number[];
    blockades: Set<string> = new Set<string>();
    directionMap = { '^': 0, '>': 1, 'v': 2, '<': 3 };
    map: string[][];
    directionIndex: number;

    constructor(location, direction, blockades, map) {
        this.location = location;
        this.blockades = blockades;
        this.map = map;
        this.uniqueLocationsArray = Array.from({ length: map.length }, () => new Array(map[0].length).fill(false));
        this.directionIndex = this.directionMap[direction];
    }

    moveUp() {
        const [x, y] = this.location;
        return [x - 1, y];
    }

    moveDown() {
        const [x, y] = this.location;
        return [x + 1, y];
    }

    moveLeft() {
        const [x, y] = this.location;
        return [x, y - 1];
    }

    moveRight() {
        const [x, y] = this.location;
        return [x, y + 1];
    }

    checkBlockade(newLocation: number[]) {
        return !this.blockades.has(`${newLocation[0]},${newLocation[1]}`);
    }

    hasLeftBoundary() {
        const [x, y] = this.location;
        return x < 0 || y < 0 || x > this.map.length - 1 || y > this.map[0].length - 1;
    }

    move() {
        while (!this.hasLeftBoundary()) {
            let newLocation: number[] = [];

            if (this.directionIndex === 0) newLocation = this.moveUp();
            else if (this.directionIndex === 1) newLocation = this.moveRight();
            else if (this.directionIndex === 2) newLocation = this.moveDown();
            else newLocation = this.moveLeft();

            if (this.checkBlockade(newLocation)) {
                this.location = newLocation;
                if (!this.hasLeftBoundary()) {
                    if (!this.uniqueLocationsArray[this.location[0]][this.location[1]]) {
                        this.uniqueLocationsArray[this.location[0]][this.location[1]] = true;
                        this.uniqueCount++;
                    }
                }
            }
            else {
                this.directionIndex = (this.directionIndex + 1) % 4;
            }
        }
    }

    getUniqueLocations() {
        return this.uniqueCount;
    }
}

To finish this task I then simply build my data and have the guard traverse the map.

function traverseMap(map: string[][]) {
    const blockades = parseBlockades(map);
    const [location, direction] = parseGuard(map);
    const guard = new Guard(location, direction, blockades, map);
    guard.move();

    console.log(guard.getUniqueLocations());
}

const map = parseInput(input);
traverseMap(map);

Part 2

For part 2, I wanted to re-use as much of part 1 as possible. As such I added the following to my Guard class.

visited: boolean[][][];

constructor(location, direction, blockades, map) {
    this.location = location;
    this.blockades = blockades;
    this.map = map;
    this.uniqueLocationsArray = Array.from({ length: map.length }, () => new Array(map[0].length).fill(false));
    this.directionIndex = this.directionMap[direction];

    // construct visited array
    this.visited = Array.from({ length: this.map.length }, () =>
        Array.from({ length: this.map[0].length }, () => new Array(4).fill(false)),
    );
    this.visited[this.location[0]][this.location[1]][this.directionIndex];
}

This visited array will allow me to keep track of the positions the guard has previously been and their direction. If the guard then hits a record of visited that already exists we are in a loop.

The next step is to create variations of blockades along the original guards path (this is because he will only interact with those on the original path). My approach is the following, have 1 guard walk without additional blockades, record their path. Then looping over the path test how many guards will have a loop when blockades are placed on each position.

To get the path from the original guard I created the method.

getVisitedCoords() {
        const coords: [number, number][] = [];
        for (let i = 0; i < this.uniqueLocationsArray.length; i++) {
            for (let j = 0; j < this.uniqueLocationsArray[0].length; j++) {
                if (this.uniqueLocationsArray[i][j]) {
                    coords.push([i, j]);
                }
            }
        }
        return coords;
    }

Before finally updating my move method to track visits and also to return true upon a loop occuring.

move() {
        while (!this.hasLeftBoundary()) {
            let newLocation: number[] = [];

            // if up
            if (this.directionIndex === 0) newLocation = this.moveUp();
            else if (this.directionIndex === 1) newLocation = this.moveRight();
            else if (this.directionIndex === 2) newLocation = this.moveDown();
            else newLocation = this.moveLeft();

            if (this.checkBlockade(newLocation)) {
                this.location = newLocation;
                if (!this.hasLeftBoundary()) {
                    if (!this.uniqueLocationsArray[this.location[0]][this.location[1]]) {
                        this.uniqueLocationsArray[this.location[0]][this.location[1]] = true;
                        this.uniqueCount++;
                    }

                    // visited stores location and direction for exact loop checking, if same cell and direction has appeared before, we are looping
                    if (this.visited[this.location[0]][this.location[1]][this.directionIndex]) {
                        // return true on loop
                        return true;
                    }

                    this.visited[this.location[0]][this.location[1]][this.directionIndex] = true;
                }
            }
            else {
                this.directionIndex = (this.directionIndex + 1) % 4;
            }
        }
        return false;
    }

Final Guard class

class Guard {
    uniqueLocationsArray: boolean[][];
    uniqueCount: number = 0;
    location: number[];
    blockades: Set<string> = new Set<string>();
    directionMap = { '^': 0, '>': 1, 'v': 2, '<': 3 };
    map: string[][];
    directionIndex: number;
    visited: boolean[][][];

    constructor(location, direction, blockades, map) {
        this.location = location;
        this.blockades = blockades;
        this.map = map;
        this.uniqueLocationsArray = Array.from({ length: map.length }, () => new Array(map[0].length).fill(false));
        this.directionIndex = this.directionMap[direction];

        // construct visited array
        this.visited = Array.from({ length: this.map.length }, () =>
            Array.from({ length: this.map[0].length }, () => new Array(4).fill(false)),
        );
        this.visited[this.location[0]][this.location[1]][this.directionIndex];
    }

    moveUp() {
        const [x, y] = this.location;
        return [x - 1, y];
    }

    moveDown() {
        const [x, y] = this.location;
        return [x + 1, y];
    }

    moveLeft() {
        const [x, y] = this.location;
        return [x, y - 1];
    }

    moveRight() {
        const [x, y] = this.location;
        return [x, y + 1];
    }

    getVisitedCoords() {
        const coords: [number, number][] = [];
        for (let i = 0; i < this.uniqueLocationsArray.length; i++) {
            for (let j = 0; j < this.uniqueLocationsArray[0].length; j++) {
                if (this.uniqueLocationsArray[i][j]) {
                    coords.push([i, j]);
                }
            }
        }
        return coords;
    }

    checkBlockade(newLocation: number[]) {
        return !this.blockades.has(`${newLocation[0]},${newLocation[1]}`);
    }

    hasLeftBoundary() {
        const [x, y] = this.location;
        return x < 0 || y < 0 || x > this.map.length - 1 || y > this.map[0].length - 1;
    }

    move() {
        while (!this.hasLeftBoundary()) {
            let newLocation: number[] = [];

            // if up
            if (this.directionIndex === 0) newLocation = this.moveUp();
            else if (this.directionIndex === 1) newLocation = this.moveRight();
            else if (this.directionIndex === 2) newLocation = this.moveDown();
            else newLocation = this.moveLeft();

            if (this.checkBlockade(newLocation)) {
                this.location = newLocation;
                if (!this.hasLeftBoundary()) {
                    if (!this.uniqueLocationsArray[this.location[0]][this.location[1]]) {
                        this.uniqueLocationsArray[this.location[0]][this.location[1]] = true;
                        this.uniqueCount++;
                    }

                    // visited stores location and direction for exact loop checking, if same cell and direction has appeared before, we are looping
                    if (this.visited[this.location[0]][this.location[1]][this.directionIndex]) {
                        // return true on loop
                        return true;
                    }

                    this.visited[this.location[0]][this.location[1]][this.directionIndex] = true;
                }
            }
            else {
                this.directionIndex = (this.directionIndex + 1) % 4;
            }
        }
        return false;
    }

    getUniqueLocations() {
        return this.uniqueCount;
    }
}

Then to create the blockades for each position I made a generator. This generator function will simulate the map with additional blockades, as the guards path is known we only need to simulate maps in which we place blockades to block the guards current path.

function* addBlockades(map, blockades, startingGuard) {
    const visitedCoords = startingGuard.getVisitedCoords();
    const [startX, startY] = startingGuard.location;
    for (const [x, y] of visitedCoords) {
        // Don't place a blockade where one already exists or at the guard's start
        if (blockades.has(`${x},${y}`)) continue;
        if (x === startX && y === startY) continue;

        // Yield a new configuration of blockades
        yield new Set([...blockades, `${x},${y}`]);
    }
}

Before finally updating my map traversal to use these yielded blockades whilst counting loops.

function traverseMap(map: string[][]) {
    const blockades = parseBlockades(map);

    const [location, direction] = parseGuard(map);
    const startingGuard = new Guard(location, direction, blockades, map);
    // run the starting guard to build his path
    startingGuard.move();

    let loops = 0;
    for (const newBlockades of addBlockades(map, blockades, startingGuard)) {
        const loopingGuard = new Guard(location, direction, newBlockades, map);
        if (loopingGuard.move()) loops++;
    }

    console.log(loops);
}

const map = parseInput(input);
traverseMap(map);

Day 5: Print Queue

Advent of Code - December 5th 2024