aoc

My solutions for the Advent of Code
git clone https://git.tronto.net/aoc
Download | Log | Files | Refs | README

day11b-hash.cpp (1288B)


      1 #include <algorithm>
      2 #include <cstdint>
      3 #include <iostream>
      4 #include <unordered_map>
      5 #include <ranges>
      6 #include <set>
      7 #include <sstream>
      8 #include <string>
      9 #include <string_view>
     10 #include <vector>
     11 using namespace std;
     12 
     13 struct hash_pair {
     14 	template <class T1, class T2>
     15 	size_t operator()(const std::pair<T1, T2>& p) const {
     16 		return std::hash<T1>{}(p.first) ^ std::hash<T2>{}(p.second);
     17 	}
     18 };
     19 
     20 unordered_map<pair<uint64_t, uint64_t>, uint64_t, hash_pair> t;
     21 
     22 pair<uint64_t, uint64_t> split(uint64_t a) {
     23 	int digits = 0;
     24 	for (uint64_t b = a; b != 0; b /= 10)
     25 		digits++;
     26 
     27 	if (digits % 2 == 1)
     28 		return make_pair(0, 0);
     29 
     30 	uint64_t j = 1;
     31 	for (int k = 0; k < digits/2; k++)
     32 		j *= 10;
     33 
     34 	return make_pair(a/j, a%j);
     35 }
     36 
     37 uint64_t count(uint64_t a, int n) {
     38 	if (n == 0)
     39 		return 1;
     40 
     41 	if (auto it = t.find(make_pair(a, n)); it != t.end())
     42 		return it->second;
     43 
     44 	if (a == 0)
     45 		return t[make_pair(a, n)] = count(1, n-1);
     46 
     47 	if (auto [x, y] = split(a); x != 0) {
     48 		auto c1 = count(x, n-1);
     49 		auto c2 = count(y, n-1);
     50 		return t[make_pair(a, n)] = c1+c2;
     51 	}
     52 
     53 	return t[make_pair(a, n)] = count(a*2024, n-1);
     54 }
     55 
     56 int main() {
     57 	uint64_t x;
     58 	vector<uint64_t> old, v;
     59 	while (cin >> x)
     60 		v.push_back(x);
     61 
     62 	uint64_t tot = 0;
     63 	for (auto a : v)
     64 		tot += count(a, 75);
     65 
     66 	cout << tot << endl;
     67 
     68 	return 0;
     69 }