After coming off the last one in under an hour, I think I can finish this all today. Heck, maybe before the sun goes down!
This one seems more complex than it actually is! It seems like you'll need to cross a chaotic ever-changing chasm, but the truth is that it's all cyclical! Each blizzard will be in the same starting position after R
iterations for those moving sidesways, and C
iterations for those moving up and down. Overall, this means that there are at most X*Y
iterations, and these can just be indexed to make it even simpler. And better than that, only up to the least common multiple need to be simulated, that's when it starts repeating!
One oddity that might come to mind is the overlapping cyclones. A 'smarter' way of doing this would be having each space be some sort of object, or or
ing together some values, or somethign like that. But I'm just going to keep it simple: character representations! It may be a bit of a pain in the ass doing extra checks to keep it all in line, but... I think it'll work out, and the performance gain might be useful. Though it might bite me in the ass for part 2;
a = ^>
b = ^v
c = ^<
d = >v
e = ><
f = v<
g = ^>v
h = ^><
i = ^v<
j = >v<
k = ^>v<
char du[8] = { '^', 'a', 'b', 'c', 'g', 'h', 'i', 'k' };
char dr[8] = { '>', 'a', 'd', 'e', 'g', 'h', 'j', 'k' };
char dd[8] = { 'v', 'b', 'd', 'f', 'g', 'i', 'j', 'k' };
char dl[8] = { '<', 'c', 'e', 'f', 'h', 'i', 'j', 'k' };
// Generate valley configurations
for (int iter = 1; iter < maxIterations; iter++)
{
vector<string> &cur = cycles.back();
vector<string> next = blank;
for (int i = 1; i < cur.size(); i++)
for (int j = 1; j < cur[i].size(); j++)
{
if (cur[i][j] == '#') continue;
if (cur[i][j] == '.') continue;
auto isUp = find(begin(du), end(du), cur[i][j]) != end(du);
auto isDown = find(begin(dd), end(dd), cur[i][j]) != end(dd);
auto isLeft = find(begin(dl), end(dl), cur[i][j]) != end(dl);
auto isRight = find(begin(dr), end(dr), cur[i][j]) != end(dr);
if (isUp)
{
int nextRow = i-1 == 0 ? valley.size()-2 : i-1;
next[nextRow][j] = combineChar(next[nextRow][j], '^');
}
if (isDown)
{
int nextRow = i+2 == valley.size() ? 1 : i+1;
next[nextRow][j] = combineChar(next[nextRow][j], 'v');
}
if (isLeft)
{
int nextCol = j-1 == 0 ? valley[0].size()-2 : j-1;
next[i][nextCol] = combineChar(next[i][nextCol], '<');
}
if (isRight)
{
int nextCol = j+2 == valley[0].size() ? 1 : j+1;
next[i][nextCol] = combineChar(next[i][nextCol], '>');
}
}
cycles.push_back(next);
}
Now that all of the cycles are accounted for, time to do a pathfinding thing. Essentailly a breadth-first search, cycling through the states on each step;
#define COORD pair<int, int>
// Perform search
int maxLen = 0;
queue<vector<COORD>> searches;
searches.push(vector<COORD>({ COORD(0, 1) }));
while (!searches.empty())
{
vector<COORD> curPath = searches.front(); searches.pop();
COORD curSpot = curPath.back();
vector<string> curMap = cycles[curPath.size() % cycles.size()];
if (curPath.size() > maxLen)
{
maxLen = curPath.size();
cout << "Searching paths length: " << maxLen << "\t[Q: " << searches.size() << "]" << endl;
}
// Check end condition
if (curSpot.first == valley.size()-1
&& curSpot.second == valley[0].size()-2)
{
cout << "Takes " << curPath.size()-1 << " minutes" << endl;
break;
}
// Up - extra condition to prevent rentering to the entrance
if (curSpot.first > 1 && curMap[curSpot.first-1][curSpot.second] == '.')
{
vector<COORD> newPath = curPath;
newPath.push_back(COORD(curSpot.first-1, curSpot.second));
searches.push(newPath);
}
// Down
// Left
// Right
// Wait in place
}
Which gets the right answer, but ends up being pretty wasteful. Likely a lot of searches involves paths of the same length at the same spot, so I need to cache some of these paths as well.
set<pair<int, COORD>> visited;
//...
if (visited.find(pair<int, COORD>(curPath.size(), curSpot)) != visited.end()) continue;
visited.emplace(pair<int, COORD>(curPath.size(), curSpot));
Just those few lines of code shrank my search queue from growing exponentially every step (up to 5x), down to never going above 2000!
These elves... I imagine doing whatever yearly tasks with these elves would be trivial if they could just document things, communicate, and most importantly not forget their snacks. Ugh.
Anyway, this seems pretty trivial. I could just break this out into a new function that could work based on a start, end, and cycle count at the beginning, and add the times together. Or I could be lazy and copy-paste code. This isn't meant to be production quality code, just a little something to solve a single and very specific problem, so I think that would be fine.
And it was very fine. Perfectly fine.
Admittedly I don't like that I have a mostly-copy-pasted section, but it still turned out rather performant and gave the right answer.
The sun went down as I finished :(