day23

7 files changed, 569 insertions, 0 deletions

diff --git a/2021/day23/day23 b/2021/day23/day23
new file mode 100755
index 0000000..a19ddb7
--- /dev/null
+++ b/2021/day23/day23
diff --git a/2021/day23/day23.cpp b/2021/day23/day23.cpp
new file mode 100644
index 0000000..a07537d
--- /dev/null
+++ b/2021/day23/day23.cpp
@@ -0,0 +1,547 @@
+#include <iostream>
+#include <fstream>
+#include <string>
+#include <map>
+#include <set>
+#include <vector>
+#include <algorithm>
+
+
+struct Game {
+	std::map<int, std::vector<int>> stars;
+	std::set<int> single_cost;
+	std::vector<int> cost;
+	std::vector<int> goal;
+};
+
+std::vector<Game> games {
+	{
+		{
+			{ 0, { 1 } },
+			{ 1, { 0, 2, 7 } },
+			{ 2, { 1, 7, 9, 3 } },
+			{ 3, { 2, 9, 11, 4 } },
+			{ 4, { 3, 11, 13, 5 } },
+			{ 5, { 4, 13, 6 } },
+			{ 6, { 5 } },
+			{ 7, { 1, 2, 8 } },
+			{ 8, { 7 } },
+			{ 9, { 2, 3, 10 } },
+			{ 10, { 9 } },
+			{ 11, { 3, 4, 12 } },
+			{ 12, { 11 } },
+			{ 13, { 4, 5, 14 } },
+			{ 14, { 13 } },
+		},
+		{ 0, 8, 10, 12, 14, 6 },
+		{ 1, 10, 100, 1000 },
+		{ 8, 10, 12, 14 }, 
+	},
+	{
+		{
+			{ 0, { 1 } },
+			{ 1, { 0, 2, 7 } },
+			{ 2, { 1, 7, 11, 3 } },
+			{ 3, { 2, 15, 11, 4 } },
+			{ 4, { 3, 15, 19, 5 } },
+			{ 5, { 4, 19, 6 } },
+			{ 6, { 5 } },
+			{ 7, { 1, 2, 8 } },
+			{ 8, { 7, 9 } },
+			{ 9, { 8, 10 } },
+			{ 10, { 9 } },		
+			{ 11, { 2, 3, 12 } },
+			{ 12, { 11, 13 } },
+			{ 13, { 12, 14 } },
+			{ 14, { 13 } },
+			{ 15, { 3, 4, 16 } },
+			{ 16, { 15, 17 } },
+			{ 17, { 16, 18 } },
+			{ 18, { 17 } },
+			{ 19, { 4, 5, 20 } },
+			{ 20, { 19, 21 } },
+			{ 21, { 22, 20 } },
+			{ 22, { 21 } },
+		},
+		{ 0, 8, 9, 10, 12, 13, 14, 16, 17, 18, 20, 21, 22, 6 },
+		{ 1, 10, 100, 1000 },
+		{ 10, 14, 18, 22 }, 
+	}
+};
+
+
+class State {
+	public:
+	State () { }
+	State (std::vector<int> pos): pos(pos) { }
+	State (const State& o): pos(o.pos) { }
+
+	std::vector<int> pos;
+	
+	bool operator==(const State &s) const { return pos==s.pos; }
+
+	void dumb_parse (std::string raw) {
+		auto newline = raw.find("\n");
+		raw = raw.substr(newline+1);
+		newline = raw.find("\n");
+		raw = raw.substr(newline+1);
+		
+		std::string chars;
+		chars += std::string{ raw[3] } 
+			+ std::string{ raw[5] } 
+			+ std::string{ raw[7] }
+			+ std::string{ raw[9] };
+
+		newline = raw.find("\n");
+		raw = raw.substr(newline+1);
+		
+		chars += std::string{ raw[3] } 
+			+ std::string{ raw[5] } 
+			+ std::string{ raw[7] }
+			+ std::string{ raw[9] };
+
+		int a = 0, b = 0, c = 0, d = 0;
+		for (int i=0; i<chars.size(); i++) pos.push_back(0);
+		
+		for (int i=0; i<chars.size(); i++) {
+			int p = 0; 
+			if (chars[i] == 'A') { p = 0+a; a++; }
+			if (chars[i] == 'B') { p = 2+b; b++; }
+			if (chars[i] == 'C') { p = 4+c; c++; }
+			if (chars[i] == 'D') { p = 6+d; d++; }
+			pos[p] = 7 + (i%4)*2+ (i/4);
+		}
+	}
+	
+	State enlarge() {
+		State big;
+		for (int i=0; i<16; i++) big.pos.push_back(0);
+		std::vector<int> row0 { 20,16,12,8 };
+		std::vector<int> row1 { 17,13,21,9 };
+		for (int i=0; i<4; i++) {
+			int a = (pos[i*2]-7) / 2;
+			int b = 1-(pos[i*2])%2;
+			big.pos[i*4] = pos[i*2]+a*2+b*2;
+			a = (pos[i*2+1]-7) / 2;
+			b = 1-(pos[i*2+1])%2;
+			big.pos[i*4+3] = pos[i*2+1]+a*2+b*2;
+			big.pos[i*4+1] = row0[i];
+			big.pos[i*4+2] = row1[i];
+		}
+		return big;
+	}
+
+	std::string show () {
+		std::string rep { "(State: [" };
+		for (int i=0; i<pos.size(); i++) {
+			rep += std::to_string(pos[i]);
+			if (i<pos.size()-1) rep += ", ";
+		}
+		rep += "])";
+		return rep;
+	}
+
+	bool done () {
+		int size = pos.size() == 8 ? 0 : 1;
+		for (int i=0; i<pos.size(); i++) {
+			int type = i/(2+size*2);
+			int goal = games[size].goal[type];
+			if (size == 0) {
+				if (pos[i] != goal && pos[i] != goal-1)
+					return false;
+			} else
+			{
+				if (pos[i] != goal && pos[i] != goal-1
+						&& pos[i] != goal-2 && pos[i] != goal-3)
+					return false;
+			}
+		}
+		return true;
+	}
+
+	int mask () {
+		int m = 0;
+		for (int p : pos) m += 1 << p;
+		return m;
+	}
+};
+
+
+using Paths = std::vector<std::pair<int, int>>;
+using AllPaths = std::map<int, std::map<int, std::map<int, Paths>>>;
+
+int bitsum (int n) {
+	int sum = 0;
+	while (n > 0) {
+		sum += n % 2;
+		n /= 2;
+	}
+	return sum;
+}
+
+Paths get_paths (int mask, int pos, int type, int size=0) {
+	std::vector<std::pair<int, int>> frontier { { pos, pos }  };
+	std::map<int, int> visited;
+	while (frontier.size() > 0) {
+		std::pair<int, int> n = frontier[0];
+		frontier.erase(frontier.begin());
+		if (!visited.contains(n.first)) {
+			visited.insert(n);
+			for (int s : games[size].stars[n.first]) {
+				if (((mask >> s) & 1) == 0) {
+					frontier.push_back(std::pair<int, int> { s, n.first } );
+				}
+			}
+		}
+	}
+	
+	Paths paths;
+	for (auto v : visited) {
+		int energy = 0;
+		int iter { v.first };
+		while (iter != pos) {
+			energy += 1;
+			int prev = visited[iter];
+			if (!games[size].single_cost.contains(iter) 
+					&& !games[size].single_cost.contains(prev))
+				energy ++;
+			iter = visited[iter];
+		}
+
+		if (energy == 0) continue;
+
+		int end = v.first;
+		int goal = games[size].goal[type];
+		if (end == goal) 
+			return Paths { std::pair<int, int> { end, energy } } ;
+
+		if (pos == goal) continue;
+		if (pos < 7 && end < 7) continue;
+		
+		if (end == goal-1 
+			&& (((mask >> goal) & 1) == 0)) continue;
+		
+		if (size == 0) {
+			if (end >= 7 
+					&& (end != goal-1 
+					&& end != goal)) continue; 
+		}
+		else if (size == 1) {
+			if (end == goal-2 
+					&& (((mask >> (goal-1)) & 1) == 0)) continue;
+			if (end == goal-3 
+					&& (((mask >> (goal-2)) & 1) == 0)) continue;
+			if (end >= 7 
+					&& end != goal-3
+					&& end != goal-2
+					&& end != goal-1 
+					&& end != goal) continue; 
+		}
+		
+		paths.push_back(std::pair<int, int> { end, energy } );
+	}
+	return paths;
+}
+
+AllPaths construct_all_paths (int size=0) {
+	AllPaths all;
+	int i=0;
+	int perms =   32768, pieces =  8, cells = 15;
+	if (size == 1) {
+		perms = 8388608; pieces = 16; cells = 23; 
+	}
+
+	for (int mask=0; mask<perms; mask++) {
+		if (bitsum(mask) == pieces) {
+			for (int pos=0; pos<cells; pos++) {
+				for (int type=0; type<4; type++) {
+					all[mask][pos][type] = 
+						get_paths (mask, pos, type, size);
+					i++;
+				}
+			}
+		}
+	}
+	std::cout << "lookup size: " << i << std::endl;
+	return all;
+}
+
+void next_states_amphipod (AllPaths &all, State state, int energy, int i, 
+		std::multimap<int, State> &states, int size=0)
+{
+	std::multimap<int, State> next;
+	int init = state.pos[i];
+	int type = i/(2+size*2);
+	for (auto p : all[state.mask()][init][type]) {
+		int goal = games[size].goal[type];
+
+		if (size == 0) {
+			int other = (i%2==0 ? 1 : 0) + (i/2)*2;
+			if (init == goal-1) 
+				if (state.pos[other] == goal) continue;
+
+			if (p.first == goal-1) {
+				if (state.pos[other] == goal) {
+					State n { state };
+					n.pos[i] = p.first;
+
+					int e = p.second * games[size].cost[type]+energy;
+					bool found = false;
+					auto range = states.equal_range(e);
+					for (auto j = range.first; j != range.second; ++j) {
+						if (j->second == n) { found = true; break; }
+					}
+					if (!found) states.insert({ e, n });
+					return;
+				} else continue;
+			}
+		} else {
+			if (goal-3 <= init && init <= goal-1) {
+				auto it = std::find(state.pos.begin(), state.pos.end(), 
+					init+1);
+				int other = it-state.pos.begin();
+				if (other/4 == type) continue;
+			}
+			if (goal-3 <= p.first && p.first <= goal-1) {
+				auto it = std::find(state.pos.begin(), state.pos.end(), 
+					p.first+1);
+				int other = it-state.pos.begin();
+				if (other/4 == type) {
+					State n { state };
+					n.pos[i] = p.first;
+					states.insert(
+						{ p.second * games[size].cost[type]+energy, n }
+					);
+					return;
+				} else continue;
+			}
+		}
+
+		State n { state };
+		n.pos[i] = p.first;
+		int e = p.second * games[size].cost[type]+energy;
+		bool found = false;
+		auto range = states.equal_range(e);
+		for (auto j = range.first; j != range.second; ++j) {
+			if (j->second == n) { found = true; break; }
+		}
+		if (!found) states.insert({ e, n });
+	}
+	for (auto n : next) {
+		states.insert(n);
+	}
+}
+
+int search (AllPaths &all, State init) {
+	std::vector<State> done;
+	std::multimap<int, State> states { { 0, init } };
+	
+	
+	int size = init.pos.size() == 8 ? 0 : 1;
+
+	int j=0;
+	int threshold = 0;
+	while (states.size() > 0) {
+		auto it = states.upper_bound(-1);
+		int energy = (*it).first;		
+		State s { (*it).second };		
+		states.erase(it);
+
+		if (j%10000 == 0)
+			std::cout << states.size() << "\t" << energy << "\t" 
+				<< s.show() << std::endl;
+		j++;
+	
+		if (!s.done()) {
+			for (int i=0; i<s.pos.size(); i++) {
+				next_states_amphipod(all, s, energy, i, states, size);
+			}
+		} else { return energy; }
+
+	}
+	return 0;
+}
+
+
+// tests
+
+bool test_paths_start () {
+	State s { { 7,8,9,10,11,12,13,14 } };
+	auto paths = get_paths(s.mask(), 7, 0); 
+	std::cout << "res paths 1: " << paths.size() << std::endl;
+	return paths.size() == 7;
+}
+
+bool test_paths_single () {
+	State s { { 0,8,9,10,11,12,13,14 } };
+	auto paths = get_paths(s.mask(), 0, 0); 
+	std::cout << "res paths 2: " << paths.size() << std::endl;
+	return paths.size() == 1;
+}
+
+bool test_paths_to_goal () {
+	State s { { 9,10,0,1,11,12,13,14 } };
+	auto paths = get_paths(s.mask(), 9, 0);
+	std::cout << "res paths 3: " << paths.size() << std::endl;
+	for (auto p : paths) {
+		std::cout << "  " << p.first << " " <<p.second << std::endl;
+	}
+	return paths.size() == 1;
+}
+
+bool test_paths_to_goal_from_below () {
+	State s { { 8,10,0,1,11,12,13,14 } };
+	auto paths = get_paths(s.mask(), 10, 0);
+	std::cout << "res paths 4: " << paths.size() << std::endl;
+	for (auto p : paths) {
+		std::cout << "  " << p.first << " " <<p.second << std::endl;
+	}
+	return paths.size() == 6;
+}
+
+bool test_paths_stuck () {
+	State s { { 8,14,10,9,11,12,13,6 } };
+	auto paths = get_paths(s.mask(), 13, 0);
+	std::cout << "res paths 5: " << paths.size() << std::endl;
+	for (auto p : paths) {
+		std::cout << "  " << p.first << " " <<p.second << std::endl;
+	}
+	return paths.size() == 7;
+}
+
+bool test_search_one_step (AllPaths all) {
+	auto s = search(all, State { { 0,8,9,10,11,12,13,14 } });
+	std::cout << "res search 1: " << s << std::endl;
+	return s != 0;
+}
+
+bool test_search_two_step (AllPaths all) {
+	auto s = search(all, State { { 0,8,1,10,11,12,13,14 } });
+	std::cout << "res search 2: " << s << std::endl;
+	return s != 0;
+}
+
+bool test_search_from_goal (AllPaths all) {
+	auto s = search(all, State { { 9,10,0,1,11,12,13,14 } });
+	std::cout << "res search 3: " << s << std::endl;
+	return s != 0;
+}
+
+bool test_search_stuck (AllPaths all) {
+	auto s = search(all, State { { 8,14,10,9,11,12,13,6 } });
+	std::cout << "res search 4: " << s << std::endl;
+	return s != 0;
+}
+
+bool test_search_strange (AllPaths all) {
+	auto s = search(all, State { { 13,8,9,10,11,12,7,14 } });
+	std::cout << "res search 5: " << s << std::endl;
+	return s != 0;
+}
+
+bool test_paths_big () {
+	State s { 
+		{ 10,17,20,22,7,13,15,16,11,12,18,21,8,9,14,19 } 
+	};
+	auto paths = get_paths(s.mask(), 7, 0, 1);
+	std::cout << "res big paths 1: " << paths.size() << std::endl;
+	for (auto p : paths) {
+		std::cout << "  " << p.first << " " <<p.second << std::endl;
+	}
+	return paths.size() == 7;
+}
+
+bool test_paths_big_simple () {
+	State s { 
+		{  7, 8, 9,10,11,12,13,14,15,16,17,18, 0 ,20,21,22 } 
+	};
+	auto paths = get_paths(s.mask(), 0, 3, 1);
+	std::cout << "res big paths 2: " << paths.size() << std::endl;
+	for (auto p : paths) {
+		std::cout << "  " << p.first << " " <<p.second << std::endl;
+	}
+	return paths.size() == 1;
+}
+
+bool test_big_done () {
+	State s { 
+		{  7, 8, 9,10,11,12,13,14,15,16,17,18,19,20,21,22 } 
+	};
+	State n { 
+		{  7, 8, 9,10,11,12,13,14,15,16,17,18,0,20,21,22 } 
+	};
+	std::cout << "res big done: " << s.done() << std::endl;
+	std::cout << "res big not done: " << n.done() << std::endl;
+	return s.done() && !n.done();
+}
+
+bool test_search_big_simple (AllPaths big) {
+	auto s = search(big, State { 
+		{  7, 8, 9,10,11,12,13,14,15,16,17,18, 0 ,20,21,22 } 
+	});
+	std::cout << "res big search 1: " << s << std::endl;
+	return s != 0;
+}
+
+bool test_search_big (AllPaths big) {
+	auto s = search(big, State { 
+		{ 10,17,20,22,7,13,15,16,11,12,18,21,8,9,14,19 } 
+	});
+	std::cout << "res big search 2: " << s << std::endl;
+	return s != 0;
+}
+
+void tests (int size) {
+	int succ = 0, fail = 0;
+	
+	AllPaths all = construct_all_paths(); 
+	if( test_paths_start () ) succ++; else fail++;
+	if( test_paths_single () ) succ++; else fail++;
+	if( test_paths_to_goal () ) succ++; else fail++;
+	if( test_paths_to_goal_from_below () ) succ++; else fail++;
+	if( test_paths_stuck () ) succ++; else fail++;
+	if( test_search_one_step (all) ) succ++; else fail++;
+	if( test_search_two_step (all) ) succ++; else fail++;
+	if( test_search_from_goal (all) ) succ++; else fail++;
+	if( test_search_stuck (all) ) succ++; else fail++;
+	if( test_search_strange (all) ) succ++; else fail++;
+	
+	if (size == 1) {
+		if( test_paths_big () ) succ++; else fail++;
+		if( test_paths_big_simple () ) succ++; else fail++;
+		if( test_big_done () ) succ++; else fail++;
+		AllPaths big = construct_all_paths(1); 
+		if( test_search_big_simple (big) ) succ++; else fail++;
+		if( test_search_big (big) ) succ++; else fail++;
+	}
+
+	std::cout << "tests: " << succ<<"/"<<succ+fail << std::endl;
+}
+
+
+int main (int argc, char *argv[]) {
+	if (std::string { argv[1] } == "-T") {
+		tests(1);
+		return 0;
+	}
+	if (std::string { argv[1] } == "-t") {
+		tests(0);
+		return 0;
+	}
+	
+	AllPaths all = construct_all_paths(); 
+	AllPaths big = construct_all_paths(1); 
+
+	std::string raw;
+	std::getline(std::ifstream(argv[1]), raw, '\0');
+	State state; state.dumb_parse(raw);
+	
+	std::cout << state.show() << std::endl;
+	int cost = search(all, state);
+	std::cout << "cost: " << cost << std::endl;
+
+	std::cout << state.enlarge().show() << std::endl;
+	cost = search(big, state.enlarge());
+	std::cout << "cost big: " << cost << std::endl;
+	return 0;
+}
diff --git a/2021/day23/day23_input.txt b/2021/day23/day23_input.txt
new file mode 100644
index 0000000..652635e
--- /dev/null
+++ b/2021/day23/day23_input.txt
@@ -0,0 +1,5 @@
+#############
+#...........#
+###D#C#A#B###
+  #C#D#A#B#
+  #########
diff --git a/2021/day23/makefile b/2021/day23/makefile
new file mode 100644
index 0000000..c2d4e55
--- /dev/null
+++ b/2021/day23/makefile
@@ -0,0 +1,2 @@
+all day23:
+	g++ -std=c++20 day23.cpp -o day23
diff --git a/2021/day23/test0.txt b/2021/day23/test0.txt
new file mode 100644
index 0000000..6a7120d
--- /dev/null
+++ b/2021/day23/test0.txt
@@ -0,0 +1,5 @@
+#############
+#...........#
+###B#C#B#D###
+  #A#D#C#A#
+  #########
diff --git a/2021/day23/test1.txt b/2021/day23/test1.txt
new file mode 100644
index 0000000..65857a0
--- /dev/null
+++ b/2021/day23/test1.txt
@@ -0,0 +1,5 @@
+#############
+#...........#
+###A#B#C#D###
+  #A#B#C#D#
+  #########
diff --git a/2021/day23/test2.txt b/2021/day23/test2.txt
new file mode 100644
index 0000000..1d7c6b8
--- /dev/null
+++ b/2021/day23/test2.txt
@@ -0,0 +1,5 @@
+#############
+#...........#
+###A#B#D#C###
+  #A#B#C#D#
+  #########