Resonant Collinearity: Advent of Code 2024 (Day 8)

This day’s puzzle involves a slightly complex concept but becomes simple once you understand it. The challenge is to identify locations with the highest likelihood of people buying Easter Bunny brand Imitation Mediocre Chocolate as a Christmas gift.

Resonant Collinearity

Check the whole story here and code in my GitHub.

Processing the data

The input is a city map showing the locations of antennas. Each antenna is tuned to a specific frequency, represented by a lowercase letter, uppercase letter, or digit. The map can be stored as a grid of characters, similar to Day 6.

vector<vector<char>> cityMap;
unordered_map<int, vector<pair<int, int>>> antennas;

void loadData() {
    string line = "";
    ifstream ip("ip.txt");
    int i = 0;

    if (ip.is_open()) {
        while (getline(ip, line)) {
            vector<char> row;
            int j = 0;
            for (char c : line) {
                row.push_back(c);
                if (c != '.') {
                    antennas[c].push_back(make_pair(i, j));
                }
                j++;
            }
            cityMap.push_back(row);
            i++;
        }
        ip.close();
    }
}

Here, the antennas map stores all coordinates for antennas of the same frequency.

Part 1: Find Antinodes

Part 1 focuses on finding antinodes. Antinodes are points equidistant from two antennas of the same frequency. For two antennas separated by a distance of d, the antinodes are points exactly d units away on either side. We only consider antinodes within the city boundaries.

My Approach:

1. Use the coordinates of antennas with the same frequency to calculate distances between all pairs
2. Identify antinodes at distances +d and -d
3. Use a helper function to check if the points are within city boundaries and add them to the set

Here’s the implementation:

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> antinodes;

bool isInBounds(int x, int y) {
    return x >= 0 && x < cityMap.size() && y >= 0 && y < cityMap[0].size();
}

void getAntinodes() {
    for(auto& [key, points] : antennas) {
        for(int i = 0; i < points.size(); i++) {
            for(int j = i + 1; j < points.size(); j++) {
                int dx = points[j].first - points[i].first;
                int dy = points[j].second - points[i].second;

                if(isInBounds(points[i].first - dx, points[i].second - dy)) {
                    antinodes.insert(make_pair(points[i].first - dx, points[i].second - dy));
                }

                if(!(points[j].first + dx < 0 || points[j].first + dx >= cityMap.size() || points[j].second + dy < 0 || points[j].second + dy >= cityMap[0].size())) {
                   antinodes.insert(make_pair(points[j].first + dx, points[j].second + dy));
                }
            }
        }
    }
}

In this function, isInBounds ensures that only valid points within the city are added, and antinodes are stored in a set to keep them unique.

int main() {
    
    loadData();

    getAntinodes();

    cout << "total antinodes: " << antinodes.size() << endl;
    return 0;
}

The size of the antinodes set is the answer for Part 1.

Part 2: Additional Antinodes

In Part 2, we consider all points along the line defined by the antennas, not just the points directly adjacent to them. Additionally, antennas themselves are treated as antinodes.

My Approach:

1. Modify the getAntinodes function to include all points along the line defined by two antennas
2. Use a do-while loop to traverse the line and add all valid points within the city boundaries

void getAntinodes() {
    for(auto& [key, points] : antennas) {
        for(int i = 0; i < points.size(); i++) {
            for(int j = i + 1; j < points.size(); j++) {
                int dx = points[j].first - points[i].first;
                int dy = points[j].second - points[i].second;

                pair<int, int> current = points[i];
                do {
                    antinodes.insert(current);
                    current.first -= dx;
                    current.second -= dy;
                } while(isInBounds(current.first, current.second));

                current = points[j];
                do {
                    antinodes.insert(current);
                    current.first += dx;
                    current.second += dy;
                } while(isInBounds(current.first, current.second));
                
            }
        }
    }
}

This updated function ensures all points along the line are considered.

Finally, the size of the antinodes set gives the answer for Part 2, earning you the second star of the day.

int main() {
    loadData();
    getAntinodes();
    cout << "Total antinodes: " << antinodes.size() << endl;
    return 0;
}

Conclusion

Today’s puzzle was an interesting use of maps and geometry. Once you map all the antennas of the same frequency, finding antinodes becomes straightforward.

If you want more practice, check out these similar problems on LeetCode:

• 973. K Closest Points to Origin
• 1162. As Far from Land as Possible