aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorjacopograndi <jacopo.grandi@outlook.it>2022-02-03 13:02:15 +0100
committerjacopograndi <jacopo.grandi@outlook.it>2022-02-03 13:02:15 +0100
commite1f77dc050610fd0df8695fc27dbf817b752ad9a (patch)
tree790266375ed871ef34065fb3d66b9df9e8d1d095
parentf6234c926b911f4fb44498ab58529d8e85807457 (diff)
day18
-rwxr-xr-x2021/day18/day18bin0 -> 77160 bytes
-rw-r--r--2021/day18/day18.cpp222
-rw-r--r--2021/day18/day18_input.txt100
-rw-r--r--2021/day18/makefile2
-rw-r--r--2021/day18/test0.txt4
-rw-r--r--2021/day18/test1.txt5
-rw-r--r--2021/day18/test2.txt2
-rw-r--r--2021/day18/test3.txt2
-rw-r--r--2021/day18/test4.txt6
-rw-r--r--2021/day18/test5.txt10
-rw-r--r--2021/day18/test6.txt2
-rw-r--r--2021/day18/test7.txt2
-rw-r--r--2021/day18/test8.txt2
-rw-r--r--2021/day18/test9.txt10
14 files changed, 369 insertions, 0 deletions
diff --git a/2021/day18/day18 b/2021/day18/day18
new file mode 100755
index 0000000..414a9d7
--- /dev/null
+++ b/2021/day18/day18
Binary files differ
diff --git a/2021/day18/day18.cpp b/2021/day18/day18.cpp
new file mode 100644
index 0000000..dd91205
--- /dev/null
+++ b/2021/day18/day18.cpp
@@ -0,0 +1,222 @@
+#include <iostream>
+#include <fstream>
+#include <string>
+#include <vector>
+#include <cmath>
+
+const bool debug = false;
+
+class Snail {
+ public:
+ Snail() {}
+ Snail(std::string raw) { parse(raw); }
+ Snail(const Snail *s) : left(s->left), right(s->right) {
+ if (s->left == -1) left_child = new Snail(s->left_child);
+ if (s->right == -1) right_child = new Snail(s->right_child);
+ }
+
+ Snail *left_child, *right_child;
+ int left = -1, right = -1;
+
+ void parse(std::string raw) {
+ int indent = 0;
+ int comma = 0;
+ for (int i=0; i<raw.size(); i++) {
+ if (raw[i] == '[') indent++;
+ if (raw[i] == ']') indent--;
+ if (raw[i] == ',' && indent == 1) comma = i;
+ }
+ auto l = raw.substr(1, comma);
+ auto r = raw.substr(comma+1, raw.size()-comma-2);
+ if (l[0] == '[') left_child = new Snail(l);
+ else left = std::stoi(l);
+ if (r[0] == '[') right_child = new Snail(r);
+ else right = std::stoi(r);
+ }
+
+ std::string show () {
+ std::string rep = "[";
+ if (left != -1) rep += std::to_string(left);
+ else rep += left_child->show();
+ rep += ",";
+ if (right != -1) rep += std::to_string(right);
+ else rep += right_child->show();
+ return rep + "]";
+ }
+
+ Snail& operator+=(Snail& rhs) {
+ Snail *temp = new Snail(this);
+ left_child = temp;
+ left = -1;
+ right_child = new Snail(&rhs);
+ right = -1;
+ reduce();
+ return *this;
+ }
+
+ friend Snail operator+(Snail lhs, Snail& rhs) {
+ lhs += rhs;
+ return lhs;
+ }
+
+ void reduce () {
+ while (true) {
+ if (debug) std::cout << show() << std::endl;
+ bool dirty = false;
+ explode(0, &dirty);
+ if (dirty) continue;
+ split(&dirty);
+ if (dirty) continue;
+ break;
+ }
+ }
+
+ void spill_up (int spill) {
+ if (spill > 0) {
+ if (left == -1) left_child->spill_up(spill);
+ else left += spill;
+ }
+ if (spill < 0) {
+ if (right == -1) right_child->spill_up(spill);
+ else right += -spill;
+ }
+ }
+
+ int explode (int indent, bool *dirty) {
+ int spill = 0;
+ if (indent >= 3) {
+ if (left == -1 && !*dirty) {
+ if (debug) std::cout << "boom " << show() << " -> ";
+ left = 0;
+ if (right == -1) right_child->left += left_child->right;
+ else right += left_child->right;
+ int spill = -left_child->left;
+ *dirty = true;
+ if (debug) std::cout << show() << " spilled " << spill << std::endl;
+ return spill;
+ }
+ if (right == -1 && !*dirty) {
+ if (debug) std::cout << "boom " << show() << " -> ";
+ right = 0;
+ if (left == -1) left_child->right += right_child->left;
+ else left += right_child->left;
+ int spill = right_child->right;
+ *dirty = true;
+ if (debug) std::cout << show() << " spilled " << spill << std::endl;
+ return spill;
+ }
+ } else {
+ if (left == -1) {
+ spill = left_child->explode(indent+1, dirty);
+ if (spill > 0) {
+ if (debug) std::cout << "catch " << spill << " " << show() << " -> ";
+ if (right != -1) right += spill;
+ else right_child->spill_up(spill);
+ spill = 0;
+ if (debug) std::cout << show() << std::endl;
+ }
+ if (spill < 0) return spill;
+ }
+ if (right == -1) {
+ spill = right_child->explode(indent+1, dirty);
+ if (spill < 0) {
+ if (debug) std::cout << "catch " << spill << " " << show() << " -> ";
+ if (left != -1) left += -spill;
+ else left_child->spill_up(spill);
+ spill = 0;
+ if (debug) std::cout << show() << std::endl;
+ }
+ if (spill > 0) return spill;
+ }
+ }
+ return spill;
+ }
+
+ void split(bool *dirty) {
+ if (*dirty) return;
+ if (left == -1) { left_child->split(dirty); }
+ else if (left >= 10) {
+ if (debug) std::cout << "split " << show() << " -> ";
+ left_child = new Snail();
+ left_child->left = std::floor(left/2.0);
+ left_child->right = std::ceil(left/2.0);
+ left = -1;
+ *dirty = true;
+ if (debug) std::cout << show() << std::endl;
+ return;
+ }
+ if (*dirty) return;
+ if (right == -1) { right_child->split(dirty); }
+ else if (right >= 10) {
+ if (debug) std::cout << "split " << show() << " -> ";
+ right_child = new Snail();
+ right_child->left = std::floor(right/2.0);
+ right_child->right = std::ceil(right/2.0);
+ right = -1;
+ *dirty = true;
+ if (debug) std::cout << show() << std::endl;
+ return;
+ }
+ }
+
+ int magnitude () {
+ int mag = 0;
+ if (left == -1) mag += 3 * left_child->magnitude();
+ else mag += 3 * left;
+ if (right == -1) mag += 2 * right_child->magnitude();
+ else mag += 2 * right;
+ return mag;
+ }
+};
+
+std::vector<Snail> parse (std::string raw) {
+ std::vector<Snail> numbers;
+ while (raw.size() > 0) {
+ auto newline = raw.find("\n");
+ if (newline != std::string::npos) {
+ numbers.emplace_back(raw.substr(0, newline));
+ raw = raw.substr(newline+1);
+ } else {
+ numbers.emplace_back(raw);
+ }
+ }
+ return numbers;
+}
+
+int get_largest_perm (std::vector<Snail> nums) {
+ int max = 0;
+ for (int i=0; i<nums.size(); i++) {
+ for (int j=0; j<nums.size(); j++) {
+ if (j==i) continue;
+ Snail *a = new Snail(nums[i]);
+ Snail *b = new Snail(nums[j]);
+ int mag = (*a + *b).magnitude();
+ if (debug) std::cout << i << " " << j << " " << mag << std::endl;
+ max = std::max(max, mag);
+ }
+ }
+ return max;
+}
+
+int main (int argc, char *argv[]) {
+ std::string raw;
+ std::getline(std::ifstream(argv[1]), raw, '\0');
+ std::vector<Snail> numbers = parse(raw);
+
+ std::cout << "largest sum: " << get_largest_perm (numbers) << std::endl;
+
+ int limit = 100000;
+ if (argc > 2) limit = atoi(argv[2]);
+
+ Snail sum { numbers[0] };
+ for (int i=1; i<numbers.size() && i<limit; i++) {
+ sum += numbers[i];
+ if (debug)
+ std::cout << "sum: " << sum.show()
+ << ", mag: " << sum.magnitude() << std::endl;
+ }
+ std::cout << "sum: " << sum.show()
+ << ", mag: " << sum.magnitude() << std::endl;
+
+ return 0;
+}
diff --git a/2021/day18/day18_input.txt b/2021/day18/day18_input.txt
new file mode 100644
index 0000000..eb4e292
--- /dev/null
+++ b/2021/day18/day18_input.txt
@@ -0,0 +1,100 @@
+[3,[5,[7,[3,9]]]]
+[[[[7,0],0],[2,[2,8]]],[[[7,8],1],3]]
+[[[[2,7],0],7],4]
+[[2,1],[9,0]]
+[[[[7,1],[3,2]],[[9,8],5]],[2,7]]
+[[[8,9],[[8,7],0]],[[[8,7],[6,3]],[[1,7],[8,9]]]]
+[[8,6],[[9,[1,7]],[6,[3,9]]]]
+[[2,[[5,6],6]],[[4,[5,9]],[3,[4,5]]]]
+[[[[2,0],[1,1]],[6,6]],[[1,9],[[2,7],[6,8]]]]
+[[[4,6],[[6,3],[3,9]]],[[[2,6],[6,1]],[[9,9],[1,5]]]]
+[[[4,[3,1]],3],6]
+[[0,[[5,2],8]],[1,[9,[4,3]]]]
+[[[[8,6],[2,1]],[2,[8,6]]],[[[7,1],[3,9]],0]]
+[[[[4,7],[2,7]],[[8,9],2]],[[[2,4],[7,2]],[3,7]]]
+[[5,[2,2]],[[1,6],[[9,1],[5,0]]]]
+[[5,[[1,2],[6,4]]],[6,8]]
+[[[5,[1,7]],7],[7,[8,1]]]
+[[1,9],[[0,3],[[6,7],[2,4]]]]
+[1,[7,[[0,6],0]]]
+[[[[5,7],9],[[3,2],7]],[[5,1],[9,9]]]
+[[[[0,4],[9,6]],[[8,3],[7,4]]],[7,[6,2]]]
+[[[[1,6],0],[[8,0],[3,4]]],[[3,[0,3]],4]]
+[4,[[7,8],[4,[9,7]]]]
+[[[2,[3,7]],5],[0,[9,9]]]
+[[[2,0],[[5,8],[7,6]]],[[9,[6,2]],[3,2]]]
+[[[3,1],3],[[[3,7],6],[9,8]]]
+[[7,[[2,5],5]],[5,[3,[4,5]]]]
+[[[6,7],6],[2,[[9,3],9]]]
+[[[[5,6],7],[[3,2],5]],[[9,[4,3]],[3,8]]]
+[0,7]
+[[[4,6],[2,9]],[[[7,6],[5,1]],7]]
+[[0,5],[[1,[4,1]],[[7,3],9]]]
+[[[2,[3,8]],5],[[[5,9],8],[7,0]]]
+[[[6,[8,6]],[[3,6],7]],[[2,1],[6,[7,5]]]]
+[[2,[[6,3],[8,9]]],[[[5,6],4],[[7,0],1]]]
+[[[[7,1],[5,6]],8],[[[8,9],4],[8,3]]]
+[[[9,2],[1,0]],0]
+[[5,[5,[8,5]]],4]
+[[3,[5,[4,9]]],3]
+[[8,[[7,7],6]],5]
+[[4,[[5,1],1]],[1,[1,[9,8]]]]
+[[[7,[3,6]],[[2,8],[4,7]]],[[[8,8],[4,0]],[2,4]]]
+[[[[3,6],3],[0,9]],2]
+[[2,8],[[8,[8,6]],[[1,1],[4,5]]]]
+[[2,[1,[1,0]]],[[[6,2],[7,4]],[[7,1],6]]]
+[3,[8,[7,[8,6]]]]
+[[1,0],[[[0,4],[0,5]],[1,5]]]
+[[[[5,0],4],[[7,8],[8,8]]],[[1,7],0]]
+[1,[[[4,1],7],[6,[9,0]]]]
+[[[1,8],2],[[5,5],[8,5]]]
+[[4,[9,[0,6]]],[[[8,9],[4,5]],4]]
+[[[[5,4],[1,7]],[[3,1],[7,9]]],[[[0,8],[4,7]],[[5,9],6]]]
+[[[[8,0],9],4],[[7,[1,3]],5]]
+[[[[5,0],6],[[6,1],8]],[[9,1],7]]
+[[9,[6,[8,8]]],[7,[[7,1],6]]]
+[[[5,[1,5]],[3,[4,2]]],[[[5,2],7],[[6,9],[2,8]]]]
+[[[5,[5,5]],[5,7]],[4,[[2,9],7]]]
+[[[[0,4],0],[[0,6],[3,0]]],[0,[[8,1],2]]]
+[[[7,[4,6]],[[7,2],[4,6]]],[[[9,3],[4,9]],6]]
+[[6,7],7]
+[[[4,1],[8,[1,5]]],[[4,6],0]]
+[[[4,[5,5]],5],[[0,[2,7]],[1,1]]]
+[[[[0,1],3],[6,7]],[4,7]]
+[[4,[6,4]],[[[9,8],1],[9,3]]]
+[[[4,9],0],[[[7,0],[0,9]],[1,[1,0]]]]
+[[[7,9],[[9,5],[6,9]]],[[0,[3,0]],[0,[5,9]]]]
+[9,[[0,0],[[1,9],9]]]
+[[[5,[0,5]],[[9,8],[9,5]]],[[0,[2,5]],7]]
+[[[[5,8],6],9],[[[2,7],7],[[7,8],5]]]
+[[8,[[4,7],6]],2]
+[[[[7,1],[9,0]],[9,[1,7]]],[[8,[6,7]],[2,5]]]
+[[4,[2,9]],8]
+[[[[7,6],[5,3]],[5,[9,7]]],[[6,[8,1]],[[6,4],9]]]
+[[7,[[7,8],4]],[[1,3],[4,[9,7]]]]
+[[[6,[6,7]],[[2,8],3]],[7,[6,[0,3]]]]
+[[9,8],[[0,[4,8]],[[9,1],1]]]
+[[[[4,0],[5,9]],7],[6,[[5,9],[9,6]]]]
+[[8,1],[1,[9,[8,3]]]]
+[[[1,[5,1]],[6,7]],[[5,9],[2,[6,7]]]]
+[[[3,7],[[7,8],1]],[[0,[6,3]],[8,0]]]
+[[5,[[9,3],[1,2]]],7]
+[[[1,[9,9]],3],[[6,4],[4,1]]]
+[[6,[1,[3,6]]],[2,9]]
+[[2,[0,2]],[5,[[9,4],[5,0]]]]
+[[4,[[3,1],[7,0]]],[[9,1],[[5,5],[6,7]]]]
+[[3,[[7,1],[3,4]]],[7,[9,[9,4]]]]
+[[9,9],[[5,4],[[9,7],4]]]
+[[[5,1],8],[[6,7],9]]
+[[[0,[9,5]],[4,3]],[3,2]]
+[[[6,[4,1]],[[8,7],[5,3]]],[[[1,2],5],[[9,2],5]]]
+[[[[7,4],[9,0]],[[1,8],[2,9]]],[[5,[1,9]],[4,0]]]
+[[[4,[3,8]],[[3,3],[2,8]]],[[[1,3],9],[[8,5],6]]]
+[[[[6,4],[7,9]],[[7,6],8]],[7,[9,8]]]
+[[7,[3,5]],7]
+[[[[5,0],[2,3]],[3,7]],[[4,[6,3]],[7,[4,4]]]]
+[[6,[3,[7,6]]],[[[5,8],[8,1]],[3,[1,5]]]]
+[[8,[9,[5,2]]],2]
+[[1,[5,4]],[[7,[8,0]],8]]
+[[[[2,7],4],3],[[1,4],[8,4]]]
+[3,[9,2]]
diff --git a/2021/day18/makefile b/2021/day18/makefile
new file mode 100644
index 0000000..055a0d8
--- /dev/null
+++ b/2021/day18/makefile
@@ -0,0 +1,2 @@
+all day18:
+ g++ -std=c++20 day18.cpp -o day18
diff --git a/2021/day18/test0.txt b/2021/day18/test0.txt
new file mode 100644
index 0000000..f212f83
--- /dev/null
+++ b/2021/day18/test0.txt
@@ -0,0 +1,4 @@
+[1,1]
+[2,2]
+[3,3]
+[4,4]
diff --git a/2021/day18/test1.txt b/2021/day18/test1.txt
new file mode 100644
index 0000000..13fdd19
--- /dev/null
+++ b/2021/day18/test1.txt
@@ -0,0 +1,5 @@
+[1,1]
+[2,2]
+[3,3]
+[4,4]
+[5,5]
diff --git a/2021/day18/test2.txt b/2021/day18/test2.txt
new file mode 100644
index 0000000..61b0df6
--- /dev/null
+++ b/2021/day18/test2.txt
@@ -0,0 +1,2 @@
+[[[[4,3],4],4],[7,[[8,4],9]]]
+[1,1]
diff --git a/2021/day18/test3.txt b/2021/day18/test3.txt
new file mode 100644
index 0000000..53cd30c
--- /dev/null
+++ b/2021/day18/test3.txt
@@ -0,0 +1,2 @@
+[10, 1]
+[1, 1]
diff --git a/2021/day18/test4.txt b/2021/day18/test4.txt
new file mode 100644
index 0000000..85acce5
--- /dev/null
+++ b/2021/day18/test4.txt
@@ -0,0 +1,6 @@
+[1,1]
+[2,2]
+[3,3]
+[4,4]
+[5,5]
+[6,6]
diff --git a/2021/day18/test5.txt b/2021/day18/test5.txt
new file mode 100644
index 0000000..70e9071
--- /dev/null
+++ b/2021/day18/test5.txt
@@ -0,0 +1,10 @@
+[[[0,[4,5]],[0,0]],[[[4,5],[2,6]],[9,5]]]
+[7,[[[3,7],[4,3]],[[6,3],[8,8]]]]
+[[2,[[0,8],[3,4]]],[[[6,7],1],[7,[1,6]]]]
+[[[[2,4],7],[6,[0,5]]],[[[6,8],[2,8]],[[2,1],[4,5]]]]
+[7,[5,[[3,8],[1,4]]]]
+[[2,[2,2]],[8,[8,1]]]
+[2,9]
+[1,[[[9,3],9],[[9,0],[0,7]]]]
+[[[5,[7,4]],7],1]
+[[[[4,2],2],6],[8,7]]
diff --git a/2021/day18/test6.txt b/2021/day18/test6.txt
new file mode 100644
index 0000000..9c21397
--- /dev/null
+++ b/2021/day18/test6.txt
@@ -0,0 +1,2 @@
+[[[[6,6],[6,6]],[[6,0],[6,7]]],[[[7,7],[8,9]],[8,[8,1]]]]
+[2,9]
diff --git a/2021/day18/test7.txt b/2021/day18/test7.txt
new file mode 100644
index 0000000..d8023ed
--- /dev/null
+++ b/2021/day18/test7.txt
@@ -0,0 +1,2 @@
+[3,[2,[1,[7,3]]]]
+[6,[5,[4,[3,2]]]]
diff --git a/2021/day18/test8.txt b/2021/day18/test8.txt
new file mode 100644
index 0000000..b6c884a
--- /dev/null
+++ b/2021/day18/test8.txt
@@ -0,0 +1,2 @@
+[[[[7,0],[7,7]],[[7,7],[7,8]]],[[[7,7],[8,8]],[[7,7],[8,7]]]]
+[7,[5,[[3,8],[1,4]]]]
diff --git a/2021/day18/test9.txt b/2021/day18/test9.txt
new file mode 100644
index 0000000..1368dc4
--- /dev/null
+++ b/2021/day18/test9.txt
@@ -0,0 +1,10 @@
+[[[0,[5,8]],[[1,7],[9,6]]],[[4,[1,2]],[[1,4],2]]]
+[[[5,[2,8]],4],[5,[[9,9],0]]]
+[6,[[[6,2],[5,6]],[[7,6],[4,7]]]]
+[[[6,[0,7]],[0,9]],[4,[9,[9,0]]]]
+[[[7,[6,4]],[3,[1,3]]],[[[5,5],1],9]]
+[[6,[[7,3],[3,2]]],[[[3,8],[5,7]],4]]
+[[[[5,4],[7,7]],8],[[8,3],8]]
+[[9,3],[[9,9],[6,[4,9]]]]
+[[2,[[7,7],7]],[[5,8],[[9,3],[0,2]]]]
+[[[[5,2],5],[8,[3,7]]],[[5,[7,5]],[4,4]]]