day18

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
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]]]