Today doesn't seem that bad. Perform a breadth-first search from the starting point, go until all avaliable points are exhausted, then the maximum is the answer.
It's the first "2d graph search" kind of question for this year, which is always fun. In this case it involves a lot of peeking along the x/y directions and a lot of different cases to search for, but it's not hard, just a lot of typing and potential off-by-one errors.
string uChars = "|7F";
string dChars = "|LJ";
string lChars = "-LF";
string rChars = "-J7";
vector<string> feild;
vector<vector<int>> distances;
queue<PipeSeg> toSearch;
int maxDist = -1;
while (!toSearch.empty())
{
PipeSeg c = toSearch.front(); toSearch.pop();
if (distances[c.x][c.y] >= 0) continue;
distances[c.x][c.y] = c.dist;
maxDist = max(c.dist, maxDist);
while (!toSearch.empty())
{
PipeSeg pipeSeg = toSearch.front(); toSearch.pop();
if (distances[pipeSeg.x][pipeSeg.y] >= 0) continue;
distances[pipeSeg.x][pipeSeg.y] = pipeSeg.dist;
maxDist = max(pipeSeg.dist, maxDist);
// Up
if (pipeSeg.x > 0 && uChars.find(feild[pipeSeg.x-1][pipeSeg.y]) != string::npos)
toSearch.push(PipeSeg{pipeSeg.x-1, pipeSeg.y, pipeSeg.dist+1});
// Down
if (pipeSeg.x < feild.size()-1 && dChars.find(feild[pipeSeg.x+1][pipeSeg.y]) != string::npos)
toSearch.push(PipeSeg{pipeSeg.x+1, pipeSeg.y, pipeSeg.dist+1});
// Left
if (pipeSeg.y > 0 && lChars.find(feild[pipeSeg.x][pipeSeg.y-1]) != string::npos)
toSearch.push(PipeSeg{pipeSeg.x, pipeSeg.y-1, pipeSeg.dist+1});
// Right
if (pipeSeg.y < feild[0].size()-1 && rChars.find(feild[pipeSeg.x][pipeSeg.y+1]) != string::npos)
toSearch.push(PipeSeg{pipeSeg.x, pipeSeg.y+1, pipeSeg.dist+1});
}
Part 2 seems pretty... easy actually. Fully distinct problem from Part 1. It's a simple enough scanning algorithm. Go across each line, and if it's not going across plain ground or a particular kind of pipe segment, increment a counter. While the counter is even and above 0, count any blank spaces as a ground tile.
It almost doesn't use anything from part 1, except using it to determine which pipes in the field are part of the loop or not.
// Find enclosed spaces
int innerTiles = 0;
for (int x = 0; x < feild.size(); x++)
{
bool encricled = false;
for (int y = 0; y < feild[x].size(); y++)
{
switch (feild[x][y]) {
case '-':
continue;
case 'F':
case 'L':
encricled = true;
break;
case 'J':
case '7':
encricled = false;
break;
case '|':
case 'S':
encricled = !encricled;
break;
case '.':
if (encricled)
{
innerTiles++;
feild[x][y] = '~';
}
break;
}
}
}
Nope, that doesn't give quite the right answer... it's just counting incorrectly. Hmm.
I could just easily mark all ground tiles that are touching the border tiles, but it's that whole pesky "squeeze behind pipes" thing that makes this difficult. I would have to find a way to find the space between it all.
Hmm.....
What if I just... do that? Explode every tile into a 9x9 version of itself, and have a "blown up" version of it all? Something like:
L:
.|.
.L-
...
That would expose the gaps! Then I can just eliminate ground tiles from that map!
// Zoom in
vector<string> bigFeild;
for (int x = 0; x < feild.size(); x++)
{
string top, middle, bottom;
for (int y = 0; y < feild[x].size(); y++)
{
switch(feild[x][y])
{
case '|': top += ".|."; middle += ".|."; bottom += ".|."; break;
case '-': top += "..."; middle += "---"; bottom += "..."; break;
case 'L': top += ".|."; middle += ".L-"; bottom += "..."; break;
case 'J': top += ".|."; middle += "-J."; bottom += "..."; break;
case '7': top += "..."; middle += "-7."; bottom += ".|."; break;
case 'F': top += "..."; middle += ".F-"; bottom += ".|."; break;
case '.': top += "..."; middle += ".@."; bottom += "..."; break;
case 'S': top += "|||"; middle += "|||"; bottom += "|||"; break;
}
}
bigFeild.push_back(top);
bigFeild.push_back(middle);
bigFeild.push_back(bottom);
}
Note that for the ground tile ., I added a @ in the middle. This is going to be my marker. For all of the tiles I find not surrounded (touching the outside), I remove that @ from the map. Then in the end it's simply counting the remaining @ markers in the big map! For example, this:
..........
.S------7.
.|F----7|.
.||....||.
.||....||.
.|L-7F-J|.
.|..||..|.
.L--JL--J.
..........
Becomes:
..............................
.@..@..@..@..@..@..@..@..@..@.
..............................
....|.........................
.@.-S--------------------7..@.
....|....................|....
....|....................|....
.@..|..F--------------7..|..@.
....|..|..............|..|....
....|..|..............|..|....
.@..|..|..@..@..@..@..|..|..@.
....|..|..............|..|....
....|..|..............|..|....
.@..|..|..@..@..@..@..|..|..@.
....|..|..............|..|....
....|..|..............|..|....
.@..|..L-----7..F-----J..|..@.
....|........|..|........|....
....|........|..|........|....
.@..|..@..@..|..|..@..@..|..@.
....|........|..|........|....
....|........|..|........|....
.@..L--------J..L--------J..@.
..............................
..............................
.@..@..@..@..@..@..@..@..@..@.
..............................
Easy, right?
// Mark 'outside' tiles
queue<pair<int, int>> outside;
outside.push(pair<int, int>(0,0));
while (!outside.empty())
{
auto c = outside.front(); outside.pop();
if ((bigFeild[c.first][c.second]) == ' ') continue;
bigFeild[c.first][c.second] = ' ';
// Up
if (c.first > 0 && emptyChars.find(bigFeild[c.first-1][c.second]) != string::npos)
outside.push(pair<int, int>(c.first-1, c.second));
// Down
if (c.first < bigFeild.size()-1 && emptyChars.find(bigFeild[c.first+1][c.second]) != string::npos)
outside.push(pair<int, int>(c.first+1, c.second));
// Left
if (c.second > 0 && emptyChars.find(bigFeild[c.first][c.second-1]) != string::npos)
outside.push(pair<int, int>(c.first, c.second-1));
// Right
if (c.second < bigFeild[0].size()-1 && emptyChars.find(bigFeild[c.first][c.second+1]) != string::npos)
outside.push(pair<int, int>(c.first, c.second+1));
}
|
F--S-----------------7
|..|.................|
|....................|
|..F--------------7..|
|..| |..|
|..| |..|
|..| |..|
|..| |..|
|..| |..|
|..| |..|
|..| |..|
|..| |..|
|..L-----7 F-----J..|
|........| |........|
|........| |........|
|..@..@..| |..@..@..|
|........| |........|
|........| |........|
L--------J L--------J
Easy!
... except it doesn't work on more complex maps with lots of useless segments. It turns out there's a bug in my code - it just keeps in some of the disconnected segments.
F- F--7
| |..|
| |..|
L- |..L--7
|.....|
|..|..|
F- L--S--J
| |
But if I explode the original map first and THEN do everything again...
F--7
|..|
|..|
|..L--7
|.....|
|..|..|
L--S--J
|
But new problem - because I moved where the 'exploding' code moved to, the empty tile markers aren't getting replaced, and there's no easy way to do it. Hrm.
I guess I just have to manually check every 3x3 section, and if it's all .s, then that must be a tile that I care about.
bool isEmpty(int x, int y)
{
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
if (feild[x+i][y+j] != '.') return false;
}
}
return true;
}
Whew, that did it!
I feel like this code is super inefficient; it does a 2d loop multiple times over, but each pass does something important.