commit a050f700e90dfd22421196e357639af4dc8a52a0
parent 1ef73fadbacf267c38ca06b63edab52da8bb4366
Author: bsandro <email@bsandro.tech>
Date: Thu, 12 Dec 2024 02:23:39 +0200
Day 11 p2
Diffstat:
4 files changed, 79 insertions(+), 16 deletions(-)
diff --git a/day11/Makefile b/day11/Makefile
@@ -2,7 +2,7 @@ NAME=$(shell basename ${PWD})
SRC=$(wildcard *.cpp)
DEPS:=$(wildcard *.hpp)
OBJ:=$(SRC:.cpp=.o)
-CXXFLAGS=-O2 -std=c++23 -Werror -Wall -Wextra -I. -I../include
+CXXFLAGS=-Os -std=c++23 -Werror -Wall -Wextra -I. -I../include
LDFLAGS=-lstdc++
all: $(NAME)
@@ -26,3 +26,6 @@ test1: $(NAME)
test2: $(NAME)
@./$(NAME) test2.txt
+
+test3: $(NAME)
+ @./$(NAME) test3.txt
diff --git a/day11/main.cpp b/day11/main.cpp
@@ -6,6 +6,7 @@
#include <cstdio>
#include <tuple>
#include <algorithm>
+#include <map>
#include <thread>
#include <future>
#include "utils.hpp"
@@ -25,19 +26,80 @@ T read_file(const std::string &path) {
return buf;
}
-void blink(Data &stones) {
- for (auto it=stones.begin(); it!=stones.end(); ++it) {
- std::string s = std::to_string(*it);
- if (*it==0) {
- *it = 1;
+typedef std::tuple<int, uint64_t, uint64_t> Memo;
+typedef std::map<uint64_t, Memo> Cache;
+typedef std::map<uint64_t, std::vector<std::pair<int, uint64_t>>> GenCache;
+
+uint64_t findGenCache(GenCache &cache, uint64_t stone, int num) {
+ uint64_t val = 0;
+ for (auto v:cache[stone]) {
+ auto [blinks, sum] = v;
+ if (blinks==num) {
+ val=sum;
+ break;
+ }
+ }
+ return val;
+}
+
+uint64_t calc(uint64_t stone, int num, Cache &cache, GenCache &genCache) {
+ if (num<=0) return 1;
+ if (genCache.contains(stone)) {
+ uint64_t v = findGenCache(genCache, stone, num);
+ if (v!=0) return v;
+ }
+ if (cache.contains(stone)) {
+ auto [blinks, s1, s2] = cache[stone];
+ if (blinks>num) return 1;
+ else if (s1==0) return 1;
+ uint64_t res = calc(s1, num-blinks, cache, genCache)+calc(s2, num-blinks, cache, genCache);
+ genCache[stone].push_back(std::make_pair(num, res));
+ return res;
+ }
+
+ uint64_t derived = stone;
+ for (int i=1; i<=num; ++i) {
+ std::string s = std::to_string(derived);
+ if (derived==0) {
+ derived = 1;
} else if (s.size()%2==0) {
uint64_t n1 = std::stoi(s.substr(0, s.size()/2));
uint64_t n2 = std::stoi(s.substr(s.size()/2, s.size()));
- *it = n2;
- it = stones.insert(it, n1);
- it++;
+ cache[stone] = std::make_tuple(i, n1, n2);
+ return calc(n1, num-i, cache, genCache)+calc(n2, num-i, cache, genCache);
} else {
- *it *= 2024;
+ derived *= 2024;
+ }
+ }
+ genCache[stone].push_back(std::make_pair(num, 1));
+ return 1;
+}
+
+uint64_t blink3(Data &stones, int num) {
+ Cache cache;
+ GenCache genCache;
+ uint64_t result = 0;
+ for (uint64_t s:stones) {
+ result += calc(s, num, cache, genCache);
+ }
+ return result;
+}
+
+void blink(Data &stones, int num) {
+ for (int i=0; i<num; ++i) {
+ for (auto it=stones.begin(); it!=stones.end(); ++it) {
+ std::string s = std::to_string(*it);
+ if (*it==0) {
+ *it = 1;
+ } else if (s.size()%2==0) {
+ uint64_t n1 = std::stoi(s.substr(0, s.size()/2));
+ uint64_t n2 = std::stoi(s.substr(s.size()/2, s.size()));
+ *it = n2;
+ it = stones.insert(it, n1);
+ it++;
+ } else {
+ *it *= 2024;
+ }
}
}
}
@@ -45,13 +107,11 @@ void blink(Data &stones) {
void blink2(uint64_t start, int num, std::promise<uint64_t> &&result) {
Data stones;
stones.push_back(start);
- for (int i=0; i<num; ++i) {
- blink(stones);
- }
+ blink(stones, num);
result.set_value(stones.size());
}
-void printStones(const Data &stones) {
+[[ maybe_unused ]] void printStones(const Data &stones) {
for (auto n:stones) {
std::cout << "[" << n << "]";
}
@@ -76,7 +136,7 @@ int64_t part1(Data input [[ maybe_unused ]]) {
}
int64_t part2(Data input [[ maybe_unused ]]) {
- return 0;
+ return blink3(input, 75);
}
int main(int argc, char **argv) {
diff --git a/day11/test2.txt b/day11/test2.txt
@@ -1 +1 @@
-125 17
+0
diff --git a/day11/test2.txt b/day11/test3.txt
