advent_of_code_day9_2022

09.cpp

#include <assert.h>
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <unordered_set>
#include <vector>

using namespace std;

namespace {

template<typename T, typename T1>
struct pair_hash {
    inline size_t operator() (const pair<T, T1>& v) const {
        hash<T> THasher;
        hash<T1> T1Hasher;
        return (THasher(v.first) * 31) + T1Hasher(v.second);
    }
};

typedef pair<int, int> Position;
typedef unordered_set<Position, pair_hash<int, int>> VisitedPoints;

ostream& operator<<(ostream& ostream, const Position& p) {
    ostream << "(" << p.first << ", " << p.second << ")";
    return ostream;
}

}

void moveAndUpdateSet(VisitedPoints    *visitedPoints,
                      vector<Position> *positions,
                      int               knotIdx,
                      const char        direction,
                      unsigned int      steps,
                      bool              updateTails = true)
{
    assert(visitedPoints != nullptr && positions != nullptr);

    Position::first_type Position::*x = &Position::first;
    Position::second_type Position::*y = &Position::second;

    int& headx = (*positions)[knotIdx].*x;
    int& heady = (*positions)[knotIdx].*y;
    
    unsigned int step = 0;
    while (step < steps) {
        ++step;
        // update the head's position
        switch(direction) {
            case 'R': {
                headx += 1;
            } break;
            case 'U': {
                heady += 1;
            } break;
            case 'L': {
                headx -= 1;
            } break;
            case 'D': {
                heady -= 1;
            } break;
            default: {
                assert("Undefined direction received");
            }
        }

        // just in case we have a rope on length 1
        if (positions->size() - knotIdx < 2 || !updateTails) {
            continue;
        }

        // have the tail react to the head's change

        // if they overlap no need to do anything
        if ((*positions)[knotIdx] == (*positions)[knotIdx + 1]) {
            continue;
        }

        int& tailx = (*positions)[knotIdx + 1].*x;
        int& taily = (*positions)[knotIdx + 1].*y;
    

        // already touching, no need to do anything
        if (abs(headx - tailx) <= 1 && abs(heady - taily) <= 1) continue;

        const auto direction = [](int a, int b) {
            return (a - b) / abs(a - b);
        };

        // check if they are both on the x axis
        if (heady - taily == 0 && abs(headx - tailx) > 1) {
            moveAndUpdateSet(visitedPoints,
                             positions,
                             knotIdx + 1,
                             direction(headx, tailx) > 0 ? 'R' : 'L', 1, true);
        }
        // check if they are both on the y axis
        else if (headx - tailx == 0 && abs(heady - taily) > 1) {
            moveAndUpdateSet(visitedPoints,
                             positions,
                             knotIdx + 1,
                             direction(heady, taily) > 0 ? 'U' : 'D', 1, true);
        }
        // check if they are more than a diagonal from each other
        else if (abs(heady - taily) > 1 || abs(headx - tailx) > 1) {
            moveAndUpdateSet(
                         visitedPoints,
                         positions,
                         knotIdx + 1,
                         direction(headx, tailx) > 0 ? 'R' : 'L', 1, false);
            moveAndUpdateSet(
                         visitedPoints,
                         positions,
                         knotIdx + 1,
                         direction(heady, taily) > 0 ? 'U' : 'D', 1, true);
        }

        // add the new position
        if (knotIdx == positions->size() - 2) {
            visitedPoints->insert((*positions)[knotIdx + 1]);
        }
    }
}

void part_1(ifstream& fs) {
    return;
    VisitedPoints visitedPoints;

    visitedPoints.insert(make_pair<int, int>(0, 0));

    string line;

    const unsigned int N = 2;
    vector<Position> positions(N);

    while (fs.good()) {
        getline(fs, line);
        if (!line.length()) break;
        istringstream iss(line);
        char direction;
        iss >> direction;
        unsigned int steps;
        iss >> steps;
        moveAndUpdateSet(&visitedPoints, &positions, 0, direction, steps);
    }

    cout << "number of visited spots: " << visitedPoints.size() << '\n';
}

void part_2(ifstream& fs) {
    VisitedPoints visitedPoints;

    visitedPoints.insert(make_pair<int, int>(0, 0));

    string line;

    const unsigned int N = 10;
    vector<Position> positions(N);

    while (fs.good()) {
        getline(fs, line);
        if (!line.length()) break;
        istringstream iss(line);
        char direction;
        iss >> direction;
        unsigned int steps;
        iss >> steps;
        moveAndUpdateSet(&visitedPoints, &positions, 0, direction, steps);
    }
    cout << "number of visited spots: " << visitedPoints.size() << '\n';
}

int main() {

#ifdef TESTING
    std::string filename{"./inputs/2022/09_sample.txt"};
#else
    std::string filename{"./inputs/2022/09.txt"};
#endif // TESTING
    ifstream fs{filename, ifstream::in};

    if (!fs.is_open()) {
        cout << "Unable to open file " << filename << '\n';
        exit(1);
    }

    part_1(fs);

    // need to `clear` since the `eof` and `fail` flags would be set.
    fs.clear();
    fs.seekg(0);

    part_2(fs);

    fs.close();

    return 0;
}