Garden Groups: Advent of Code 2024 (Day 12)
Another interesting application of graphs. This challenge revolves around helping a gardener estimate the cost of fencing a large farm. The farm consists of various regions of plants, each represented by a specific character in a grid. The goal is to calculate the fencing cost for these regions based on their size and boundaries.
Check the story here and find my code on GitHub!
Processing the data
The farm is represented as a grid of characters where each character denotes a type of plant. We’ll load this grid into a vector of strings using the following code:
vector<string> farm;
void loadData() {
string line;
ifstream ip("tmp.txt");
if (ip.is_open()) {
while (getline(ip, line)) {
farm.push_back(line);
}
ip.close();
}
}Part 1: Fencing Cost
In part 1, you need find fencing cost for a region by multiplying its area with its perimeter. The perimeter of a region is the number of plots that are on boundaries whereas the area is the total number of plots in the region.
My Approach:
- Use BFS
- Count all plots in a region to get the area
- Count the edges at the boundary of the region to get the perimeter
As always, here’s a helper function to check if a point is within bounds:
bool isInBounds(int x, int y) {
return x >= 0 && x < farm.size() && y >= 0 && y < farm[0].size();
}Now, we perform BFS to process the regions:
struct pair_hash {
template <class T1, class T2>
size_t operator()(const pair<T1, T2>& p) const {
auto hash1 = hash<T1>{}(p.first);
auto hash2 = hash<T2>{}(p.second);
return hash1 ^ (hash2 << 1);
}
};
unordered_set<pair<int, int>, pair_hash> visited;
vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int findRegionCost(int startX, int startY) {
int perimeter = 0;
int area = 1;
queue<pair<int, int>> q;
q.push(make_pair(startX, startY));
visited.insert(make_pair(startX, startY));
while(!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for(pair<int, int>& dir : directions) {
int nx = x + dir.first;
int ny = y + dir.second;
if(isInBounds(nx, ny) && farm[nx][ny] == farm[x][y]) {
if(!visited.count(make_pair(nx, ny))) {
area++;
visited.insert(make_pair(nx, ny));
q.push(make_pair(nx, ny));
}
} else {
perimeter++;
}
}
}
return area * perimeter;
} For each unvisited plot, we calculate its fencing cost and add it to the total:
int main() {
loadData();
long int totalPrice = 0;
for(int i = 0; i < farm.size(); i++) {
for(int j = 0; j < farm[i].size(); j++) {
if(!visited.count(make_pair(i, j))) {
totalPrice += findRegionCost(i, j);
}
}
}
cout << "total price: " << totalPrice << endl;
return 0;
}Pretty striaght forward, right?
Part 2: Fencing Cost with Discount
In Part 2, the cost is based on the number of sides of each region instead of the perimeter. To calculate this, we need to count the corners of each region.
My Approach:
I tried to count the corners of the polygon to find the number of sides, but it didn’t work out. Extra corners were being added, especially when regions were nested inside each other, and I spent half a day trying to fix it without success.
Then I learned from this YouTube video that the correct way to count corners is by using the vertices of the points, not the points themselves. I recommend watching the video for a full explanation.
The Correct Approach:
Instead of counting boundary edges, we calculate the vertices of each plot. A vertex is a corner if it has exactly 1 or 3 neighbours. Junctions between two regions (diagonal edges) are count as two corners one for each.
Here’s the function to count corners:
int countCorners(const unordered_set<pair<int, int>, pair_hash>& region) {
unordered_set<pair<float, float>, pair_hash> vertices;
for(const pair<int, int>& point : region) {
vertices.insert(make_pair(point.first - 0.5, point.second - 0.5));
vertices.insert(make_pair(point.first + 0.5, point.second - 0.5));
vertices.insert(make_pair(point.first + 0.5, point.second + 0.5));
vertices.insert(make_pair(point.first - 0.5, point.second + 0.5));
}
int corners = 0;
for(const pair<float, float>& vertex : vertices) {
vector<bool> config;
vector<pair<float, float>> checkPoints = {
{vertex.first - 0.5, vertex.second - 0.5},
{vertex.first + 0.5, vertex.second - 0.5},
{vertex.first + 0.5, vertex.second + 0.5},
{vertex.first - 0.5, vertex.second + 0.5}
};
for (const auto& cp : checkPoints) {
config.push_back(!region.count(make_pair(static_cast<int>(cp.first), static_cast<int>(cp.second))));
}
int number = 0;
for(bool b : config) {
if(b) {
number++;
}
}
if (number == 1) {
corners += 1;
} else if (number == 2) {
if ((config[0] && config[2] && !config[1] && !config[3]) || (config[1] && config[3] && !config[0] && !config[2])) {
corners += 2;
}
} else if (number == 3) {
corners += 1;
}
}
return corners;
}- For each plot in the region, the code finds its four corners by adjusting the coordinates slightly
- It checks each corner to see which of its neighbouring plots are missing
- Based on the number and position of missing neighbours, it identifies the type of corner
- It adds up all the corners to get the total count
Now, modify the findRegionCost, to use the countCorners function:
int findRegionCost(int startX, int startY) {
int perimeter = 0;
unordered_set<pair<int, int>, pair_hash> region;
queue<pair<int, int>> q;
q.push(make_pair(startX, startY));
visited.insert(make_pair(startX, startY));
region.insert(make_pair(startX, startY));
while(!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for(pair<int, int>& dir : directions) {
int nx = x + dir.first;
int ny = y + dir.second;
if(isInBounds(nx, ny) && farm[nx][ny] == farm[x][y]) {
if(!visited.count(make_pair(nx, ny))) {
visited.insert(make_pair(nx, ny));
region.insert(make_pair(nx, ny));
q.push(make_pair(nx, ny));
}
} else {
perimeter++;
}
}
}
return region.size() * countCorners(region);
}Conclusion
Part 1 is straightforward and involves basic BFS. However, Part 2 is a bit challenging, requiring careful calculation of corners to determine the number of sides. This problem is an excellent example of how graph algorithms can be used in creative ways.
