Finally! Pathfinding!

It's not quite the pathfinding problem I thought would need to be solved, but it's nonetheless a classic pathfinding problem.

I have a mind to implement A* for this, or another pathfinding algorithm to get the path... but looking at the problem, I don't need to genuinely find the path at any moment for this. I only need to find the risk for the path. The easiest way would be to find the risk for every possible space, moving backwards from the exit to calculate that. I don't need any paths, just calculations.

Even easier, if I can figure out how to diagonally go through a 2d array, it's just iterating across it, taking the lower of the two known adacent values, and adding the current risk.

// Seed risk map with initial value
int size = cavern[0].size() - 1;
riskMap[size][size] = cavern[size][size];

for (int i = 1; i <= size; i++)
for (int j = 0; j <= i; j++) {
    int x = size - (i-j);
    int y = size - j;
    riskMap[x][y] =
        cavern[x][y]
        + min(
            x == size ? INT_MAX : riskMap[x+1][y],
            y == size ? INT_MAX : riskMap[x][y+1]
        );
}

// Top Diagonal
for (int i = size-1; i >= 0; i--)
for (int j = 0; j <= i; j++) {
    riskMap[j][i-j] =
        cavern[j][i-j]
        + min(
            j     == size ? INT_MAX : riskMap[j+1][(i-j)],
            (i-j) == size ? INT_MAX : riskMap[j][(i-j)+1]
        );
}

... Except that only works for square inputs. It turns out the actual input is 100x101, very slightly rectangular. So my calculations all skipped an entire row. Ugh.

// Seed risk map with initial value
int width = cavern[0].size() - 1;
int height = cavern.size() - 1;

// Start at 1 to skip exit risk; that is manually set
riskMap[height][width] = cavern[height][width];
for (int i = 1; i <= width + height; i++)
for (int j = 0; j <= i; j++) {
    int k = i - j;

    if (k <= height && j <= width) {
        int x = height - k;
        int y = width - j;
        riskMap[x][y] =
            cavern[x][y]
            + min(
                x == height ? INT_MAX : riskMap[x+1][y],
                y == width ? INT_MAX : riskMap[x][y+1]
            );
    }
}

Still not the right answer...

Ugh... I'll have to actually do pathfinding. Great. Time to throw this out and start anew.

~

Okay, it's like an hour later. Let's see... (safer() is just a comparison function for the NODE type based on risk)

#define NODE pair<int, pair<int, int>>

// Seed heap
riskQueue.push_back(NODE(0, pair<int, int>(0, 0)));
make_heap(riskQueue.begin(), riskQueue.end(), safer());

while (!riskQueue.empty()) {
    NODE node = riskQueue.front();
    pop_heap(riskQueue.begin(), riskQueue.end(), safer());
    riskQueue.pop_back();

    int risk = node.first;
    int x = node.second.first;
    int y = node.second.second;

    // Check if the end
    if (node.second.first == height && node.second.second == width) {
        cout << "Total risk is: " << node.first << endl;
        return 0;
    }

    // Top, Bottom, Left, Right
    if (x > 0 && cavern[x-1][y] > 0) { 
        riskQueue.push_back(NODE(risk + cavern[x-1][y], pair<int, int>(x-1, y)));
        push_heap(riskQueue.begin(), riskQueue.end(), safer());
        cavern[x-1][y] = -1;
    }
    /// repeat for each direction...
}

That... doesn't... work...

I even tried a test output that specifically checks for going backwards at some points!

...

And trying random things like switching up width and height at a few points, it just works now? I have a headache...

Okay, part 2 seems like it's just a larger version of the first, tiling the output in a unique way. Interesting, but I just need to adjust how I parse the input.

// Populate cavern
while (!input.eof()) {
    input >> line;
    vector<int> row;
    for (auto c: line) 
        row.push_back(c -'0');
    cavernTile.push_back(row);
    for (int i = 0; i < 5; i++) cavern.push_back(vector<int>());
}

int tileWidth = cavernTile[0].size();
int tileHeight = cavernTile.size();

// Populate LARGER cavern
for (int i = 0; i < 5 * tileHeight; i++)
for (int j = 0; j < 5 * tileWidth; j++) {
    int mx = i / tileHeight;
    int my = j / tileWidth;
    cavern[i].push_back((cavernTile[i%cavernTile.size()][j%cavernTile[0].size()] - 1 + mx + my) % 9 + 1);
}

The cavern is bigger, but correct.

... and it STILL doesn't work?

...

I added an extra line at the end of the input while looking at it. I removed it and it worked.

The confusing thing is that my input code still parsed it just fine, but it read the empty line as a duplicate of the last line. Whoops.

I feel dumb. But it works.