Advent of Code 2023 Day 16

day16.cpp

#include <iostream>
#include <fstream>
#include <vector>
#include <numeric>
#include <functional>

static const char MIRROR_A = '\\';
static const char MIRROR_B = '/';
static const char SPLIT_HORIZONTAL_BEAM = '|';
static const char SPLIT_VERTICAL_BEAM = '-';
enum class Direction { North, East, South, West };

void traverse(
    int startX,
    int startY,
    const Direction initialDir,
    const std::vector<std::string> &map,
    std::vector<std::vector<int>> &visited
)
{
    int currentX = startX;
    int currentY = startY;
    Direction currentDirection = initialDir;
    bool justStarted = true;
    while (true)
    {
        if (currentX < 0 || currentX >= map.size() || currentY < 0 || currentY >= map.size())
        {
            //went out of range
            return;
        }
        if (currentX == startX && currentY == startY && currentDirection == initialDir && !justStarted)
        {
            //we're in loop
            return;
        }
        bool visitedBefore = visited[currentY][currentX] == 1;
        visited[currentY][currentX] = 1;
        auto terrain = map[currentY][currentX];
        Direction nextDirection = currentDirection;

        switch (terrain)
        {
            case MIRROR_A:
                switch(currentDirection)
                {
                    case Direction::North:
                        nextDirection = Direction::West;
                        break;
                    case Direction::East:
                        nextDirection = Direction::South;
                        break;
                    case Direction::West:
                        nextDirection = Direction::North;
                        break;
                    case Direction::South:
                        nextDirection = Direction::East;
                        break;
                }
                break;
            case MIRROR_B:
                switch(currentDirection)
                {
                    case Direction::North:
                        nextDirection = Direction::East;
                        break;
                    case Direction::East:
                        nextDirection = Direction::North;
                        break;
                    case Direction::West:
                        nextDirection = Direction::South;
                        break;
                    case Direction::South:
                        nextDirection = Direction::West;
                        break;
                }
                break;

            case SPLIT_HORIZONTAL_BEAM:
                if (currentDirection == Direction::West || currentDirection == Direction::East)
                {
                    if (!visitedBefore)
                    {
                        int yAbove = currentY - 1;
                        int yBelow = currentY + 1;
                        traverse(currentX, yAbove, Direction::North, map, visited);
                        traverse(currentX, yBelow, Direction::South, map, visited);
                    }
                    return;
                }
                else
                {
                    nextDirection = currentDirection;
                }
                break;
            
            case SPLIT_VERTICAL_BEAM:
                if (currentDirection == Direction::South || currentDirection == Direction::North)
                {
                    if (!visitedBefore)
                    {
                        int xLeft = currentX - 1;
                        int xRight = currentX + 1;
                        traverse(xLeft, currentY, Direction::West, map, visited);
                        traverse(xRight, currentY, Direction::East, map, visited);
                    }
                    return;
                }
                else
                {
                    nextDirection = currentDirection;
                }
                break;
        }
        currentX = nextDirection == Direction::West ? currentX - 1 : nextDirection == Direction::East ? currentX + 1 : currentX;
        currentY = nextDirection == Direction::North ? currentY - 1 : nextDirection == Direction::South ? currentY + 1 : currentY;
        currentDirection = nextDirection;
    }
}

int countVisitedTiles(const std::vector<std::string> &map, int startX, int startY, Direction direction)
{
    static std::vector<std::vector<int>> visited(map.size(), std::vector<int>(map.size(), 0));
    for (auto &it : visited)
    {
        std::fill(it.begin(), it.end(), 0);
    }
    traverse(startX, startY, direction, map, visited);
    return std::accumulate(
        visited.begin(),
        visited.end(),
        0L,
        [](long acc, const std::vector<int> &row) {
            return acc + std::accumulate(row.begin(), row.end(), 0, std::plus<int>());
        }
    );
}

void part1(const std::vector<std::string> &map)
{
    std::cout << "Result: " << countVisitedTiles(map, 0, 0, Direction::East) << std::endl;
}

void part2(const std::vector<std::string> &map)
{
    std::vector<int> results;
    // top down
    for (int i = 0; i < map.size(); i++)
    {
        results.push_back(countVisitedTiles(map, i, 0, Direction::South));
        results.push_back(countVisitedTiles(map, i, map.size() - 1, Direction::North));
        results.push_back(countVisitedTiles(map, 0, i, Direction::East));
        results.push_back(countVisitedTiles(map, map.size() - 1, i, Direction::West));
    }
    std::cout << "Result: " << *(std::max_element(results.begin(), results.end())) << std::endl;;
}

int main()
{
    std::vector<std::string> map;
    std::ifstream input("day16_input.txt");
    std::string line;
    while (std::getline(input, line))
    {
        map.push_back(line);
    }

    part1(map);
    part2(map);
    return 0;
}