day25

7 files changed, 354 insertions, 0 deletions

diff --git a/2021/day25/day25 b/2021/day25/day25
new file mode 100755
index 0000000..fca4079
--- /dev/null
+++ b/2021/day25/day25
diff --git a/2021/day25/day25.cpp b/2021/day25/day25.cpp
new file mode 100644
index 0000000..5797ee2
--- /dev/null
+++ b/2021/day25/day25.cpp
@@ -0,0 +1,195 @@
+#include <iostream>
+#include <fstream>
+#include <string>
+
+#include "gtest/gtest.h"
+
+
+class Board {
+	private:
+	std::vector<int> tiles;
+
+	int at_uncheck (int i, int j) { return i+j*sx; }
+	int at (int i, int j) const { return (i%sx)+(j%sy)*sx; }
+
+	public:
+	int sx, sy;
+
+	Board(const Board &b): sx(b.sx), sy(b.sy), tiles(b.tiles) { }
+	Board(int sx, int sy): sx(sx), sy(sy) {
+		for (int j=0; j<sy; j++)
+			for (int i=0; i<sx; i++)
+				tiles.push_back(0);
+	}
+	Board(std::string raw) {
+		sy = 0;
+		while (raw.size() > 0) {
+			std::string line = raw;
+			auto token = raw.find("\n");
+			if (token != std::string::npos) {
+				line = raw.substr(0, token);
+				raw = raw.substr(token+1);
+			} else raw = "";
+			for (int i=0; i<line.size(); i++) {
+				if (line[i] == '.') tiles.push_back(0);
+				if (line[i] == '>') tiles.push_back(1);
+				if (line[i] == 'v') tiles.push_back(2);
+			}
+			sx = line.size();
+			sy ++;
+		}
+	}
+
+	int get (int i, int j) const { return tiles[at(i, j)]; }
+	void set (int i, int j, int v) { tiles[at(i, j)] = v; }
+
+	friend std::ostream& operator<< (
+			std::ostream& stream, const Board& board) 
+	{
+		stream << "Board (" 
+			<< board.sx << ", " << board.sy << ")" << std::endl;
+		for (int j=0; j<board.sy; j++) {
+			for (int i=0; i<board.sx; i++) {
+				int tile = board.get(i, j);
+				if (tile == 0) stream << ".";
+				if (tile == 1) stream << ">";
+				if (tile == 2) stream << "v";
+			}
+			stream << std::endl;
+		}
+		return stream;
+	}
+};
+
+TEST (board, exist) {
+	Board b { 4, 4 };
+}
+
+TEST (board, modify) {
+	Board b { 4, 4 };
+	b.set(3, 3, 1);
+	ASSERT_EQ(1, b.get(3, 3));
+}
+
+TEST (board, donut) {
+	Board b { 4, 4 };
+	b.set(4, 4, 1);
+	ASSERT_EQ(1, b.get(0, 0));
+}
+
+TEST (board, parse_ez) {
+	Board b { ".>v" };
+	ASSERT_EQ(0, b.get(0, 0));
+	ASSERT_EQ(1, b.get(1, 0));
+	ASSERT_EQ(2, b.get(2, 0));
+}
+
+TEST (board, parse_test_txt) {
+	std::string raw;
+	std::getline(std::ifstream("test0.txt"), raw, '\0');
+	Board b { raw };
+	ASSERT_EQ(0, b.get(0, 0));
+	ASSERT_EQ(1, b.get(3, 0));
+	ASSERT_EQ(2, b.get(0, 3));
+	ASSERT_EQ(2, b.get(4, 6));
+}
+
+
+class Engine {
+	private:
+	int t;
+
+	public:
+	Engine (Board b): board(b), t(0) { }
+
+	Board board;
+
+	friend std::ostream& operator<< (
+			std::ostream& stream, const Engine& e) 
+	{
+		stream << "Engine (step: " << e.t << ")" << std::endl;
+		stream << e.board;
+		return stream;
+	}
+
+	int step_herd(int h, int move) {
+		int changes = 0;
+		Board next { board }; 
+		for (int j=0; j<board.sy; j++) {
+			for (int i=0; i<board.sx; i++) {
+				if (board.get(i, j) == h) {
+					if (move == 0) {
+						if (board.get(i+1, j) == 0) {
+							next.set(i+1, j, board.get(i, j));
+							next.set(i, j, 0);
+							changes ++;
+						}
+					} 
+					if (move == 1) {
+						if (board.get(i, j+1) == 0) {
+							next.set(i, j+1, board.get(i, j));
+							next.set(i, j, 0);
+							changes ++;
+						}
+					}
+				}
+			}
+		}
+		board = next;
+		return changes;
+	}
+
+	int step () {
+		t++;
+		int changes = 0;
+		changes += step_herd(1, 0);
+		changes += step_herd(2, 1);
+		return changes;
+	}
+
+	void run () {
+		int changes = step();
+		if (changes > 0) run();
+	}
+
+	int get_t() { return t; }
+};
+
+TEST (engine, step_ez) {
+	Engine engine { Board { "...>>>>>..." } };
+	engine.step();
+	ASSERT_EQ(1, engine.board.get(8, 0));
+	engine.step();
+	ASSERT_EQ(0, engine.board.get(8, 0));
+}
+
+TEST (engine, step_blocking) {
+	std::string raw;
+	std::getline(std::ifstream("test1.txt"), raw, '\0');
+	Engine engine { Board { raw } };
+	engine.step();
+	ASSERT_EQ(2, engine.board.get(7, 2));
+}
+
+TEST (engine, step_run) {
+	std::string raw;
+	std::getline(std::ifstream("test2.txt"), raw, '\0');
+	Engine engine { Board { raw } };
+	engine.run();
+}
+
+
+int main (int argc, char *argv[]) {
+	if (argc > 1 && std::string { argv[1] } == "-t") {
+		testing::InitGoogleTest(&argc, argv);
+		return RUN_ALL_TESTS();
+	}
+
+	std::string raw;
+	std::getline(std::ifstream("day25_input.txt"), raw, '\0');
+	Engine engine { Board { raw } };
+	engine.run();
+	std::cout << "steps: " << engine.get_t() << std::endl;
+
+	return 0;
+}
diff --git a/2021/day25/day25_input.txt b/2021/day25/day25_input.txt
new file mode 100644
index 0000000..374d6db
--- /dev/null
+++ b/2021/day25/day25_input.txt
@@ -0,0 +1,137 @@
+.>vv....vv>.v.vv....v>vv>.v>..vv.>.v...v...>v>v.>.>.>..>..>.>v...>>v.v>...vv.v.>.>.vv.vv.v...v.>vvv>>.>...v>..>.>..>v.>.>.v.>...>.>.v..v.>v
+>........v>...>>..vv>v>v.v.....v.>>...>>v>>.vv....>.>...v>v>vvv....>.....>.v....vvv.>...v>.>>.>>..>...v..>.>....>>.v>.>.v..>...>.>>..v..vv.
+>.>...v..>..v.vv.v>.>.>>v.vvvvv.vv..vv.....v.vv..>.vv>v..>.>.......>...>>>.vvvv>>....v>v.>...>>vv....vv.>........>>..>>..v..>...>..vv>.....
+....v.>v>v>v>>..>v.>>..v....>>>...>>.v.>>v>..vv.>....v>.vv.v.v.>.>.v>.v>.vv.vv>>v.vv.v.>..>v...>>v....v>.....v>.....v>..>.>.>.>>>.>.>>>..>>
+.>>...>.vv.v....>.vv.v>>..>.>.>>..>.>v.>vv...v.>.>...v>>.>...>.>>>.>........>.vv.v.>vv>v...>v.>.v....v..v.......vvv.>.>v...vv>.v>>>.v.>v...
+.v.....>>....v.>v.>>....>v>>...v>>..v..v.v...v..>>..v>....v...>.>>>.v>>>.v.vv.v..>>.vvv..>>v>>..v>v....>v.v>.v>.v.>....>..>>.v.v..>.>>v....
+.>..v.vv..vv>vv..>.>v>>..>.>v>..>>...>.>..v.vv>v.v>....>.vv.vv>>>.>..v.>v.v..>v.vv..>vvv.....vv>v>.vvv.>>>..>>.>>>...>vv>v>..v.>....>...vv>
+..>.>>.....>...>..v>...>v>...>v.v.>>..>>>.vv>>>...>>>.>vv....>...>..>..v>.>v....vv>.v.vvv...>>.vv>...>>.>.v.v>>>>>.v>>.v.>..v.v.>>..v.v..>v
+....v...>>v.v.vv..>vv.v.>....>>...>>>v..>.>vv..vv>>v>.>>>v>...v..v>..>..v.v.vvv....v....>.>.>.vv...v.vvv.>...>.v>.>>...v>>>>vv...v....v...>
+v.v.>v..v>>....v.vvv....v...>>.v.>>.>..vv.>.v.>>.v>>v>v>>>..vv>..>..>>>v>.>>v..>..>>.v....v>>.v>...>>.>.>.vv..v>..v.>..>>.>vvv.v...>..v.>.>
+>v>>vv.>.>>v>...>>.>..>..vv..>.v.....v>.>...vv.>>...>.>.>>...v..>v......v.>>v>.>..v...v>v.>v....>v>v.>>.v>>>.>..>....vv...v.v.>vv>.v>.vv.>v
+v.vv...>v....>.>.v>..>v...vv.....v>>.....v>..>>>.v>.>>vvv.v..>...>v>v>v.>>.....v...vvv>>.v..>>.v>v...v>...v.v..v..>>.>..v.v>...>....v......
+>..v>>......>v.v.v.v>v..v..v.>>vv....>v..vv>v...>.v...>v.>>.>v.>..>.v.v.vv>>.>.vv.>>.vv.>v..>>...v>.vv>..v.>vvv..>....>...v..v..v.v>..>>..>
+v..>.v....>>...vvv.vv.>.vv>>v.>>v..v...>.>..v.v..v..>..>>...v>...v>.....>>.vvv>....>>.>>.>v>v.......>..>...vv.............v>vv>...v.v.>>..>
+.v..>>v.>..>vv.v...v>>>>..>.v..v...v.>>>>v.>>>.>..v>....v....>..v..>.v>..>v.v....>.v..v.v..v...>v>v.>vv.....v.....>...>>.>.v.>vv>>>..v.>>.v
+vv...v...vv>.>v...v...v>.v.v.>>..v.>....>...............>vvv.v>v..>>....>.>>...vvv...v.vv..v.v.v...vv.>.v.v>v>>>v......>v..v>>...v>.v>vv>..
+.>..v.vv.....>>vv.vv>v..>v>>>.vv>.v.>>>>.v>>.v.v>v..>v..>.>vv>..vv>v>.>vv>v>......>vv.....v.v.>v>.>...v..v.vv...>v..vv.v..>vvv.>.>v>.>v..>.
+>.v>v....>...v>>v.vv.v.>..>>>.v.vv.vv.v.>..>>v.>.>......vv.v.>.vv.>v>>..v....vvv>.v.>v...v....vv>.>>>>v.>>>>..v.>v.>v.v.>vv>..vv.v.>.>>.>>v
+v.>v>vvv.vv.v..v>v>>.vv..vv.....>.>.>>..v.......>.....>.>.v..>>..>..v>>>.>.>....>>....v.>..>...vv>v..v>v>>vv...>...>>...>...>.v.v.....v>>..
+....v>>v.v>>..v>>.>vv.v>>.>vvvv.....v>..>.>..v..>.>..v.>...>>>v..>.>>.>v>>>vvv.........v.vv....v>.>v..>..v.>.v.v>...vv.>...>.v..v>>....>v>>
+....>.>..v>v.v>.v..>v.>.>.vv>>v.v>vv..v...>..>>.v>.v>v...v..vv>..v.v..>...v>>>.v..vv>>.>.vvv>>>>.>.>vv.v.>.>.v>v>>.v..v>>>...>vv>>.>..>>.>.
+....v......>vvv>v>>>....v>vv>.>.vv>vv.>.vvv>.v..v.....v>>.v..v.v..>...vv>.>.>....>.>.>vv..v...>..v.>.>..v>..>..>.>v...>>.>v..v>v.>>>v>..vv.
+>v>.>....>>>.v.v....v.....v...>..>vv.v.>.v>v.>v>v...>>>v.>vvv>.....v>..v.>.>v...vv..v.vv>v..vvv>v...v...>.>..>.v..>>.>>....v....>.v.v.v>>v>
+...>..v>>.>>>.v>.>v..>.v>>>v...vv.>v>>v.v>.v.....v.vv...v>vv.vv.>>.>>v...v>.>.>..>.v..>.>v.>>v.>>>v.>.....v.....v..v.v.v>.>v.v...>vv>>>vv>.
+.>v.v>.v>.v>.v>>.vv>>.>v>v.....v...v..v..v...>>v.v.>v.>...>..>..v>>.>.>>....vv>...v...v>v..v>v..>>.vv..>v>v>.v...v>>...>>>v.v.vvvvvv>>v.vvv
+>vv>.v.>.v..v>vv.vv>>>>.....v.v>..v...v>v>v.>.>>>.>.v>>..>...>..vv>.>..v....v.v>.>..>.v.v......v....>v.>.vv>.vv......v>>...v>....vvv..vvv>v
+.v.v...>>v>.>v...vv..v..>>.v..v>v....v..vv..vv..>v...>.>..vv>v.>>v>v..>v.vvv..v>.v>>.v......>..v>>.>>..>v>.v>v..>....v....v.v.>>v>...v.>v..
+vv....v>v..>v>.>v>v>..vvvv..>>v..>v.....>.vv....v.>.>.v.v.v...>....>>v...v...v...v.v.v...v..v...vv.v..vv..v.v>>.>vvvv>.v..v.v>.v.>>...vv>v.
+.v..vv>...>...>>..v.>.>>>.v>vv>>>vv>>.vvv...>>v..>vvv..v>...v>v.>.vvvv.>v.>...v..v.v.v.....>>.>.v..>v..vv>v.>..>..v>>>v>.v>>...>>>...v..vv>
+vv>vv.v>.>..vv.>...v..v...v>>>.vvv..v.>..>>.v>v>..v>.vvv>vv>..>v>>....>....>v>vv>>v>v>v..v...vvv.v.v>.>.v>v.>v.v.>v.vv.>v..>v.v..>>>.v.v>v.
+..>.v.v..>..>.>.v.v>..v>..v>.>.>>vv...>vv..v.>v..v.v..v....>.>.>>.........v>vvv.v.v...v........v....>v.>>>.......v>..>>>v>>>.>.v......>..>>
+v.>...v.>>.vv.........v.v.>.v..>v..>v>v.vv>....v>vv>.v>v..>v>..vv...>>v.v....v....>.v.....v..v.....>vvvvv.>...v>>>v...v>.v>..>>>>...vvvv>..
+vv.>....v>v>>v>..v.>>v>..>..>...>>>v.v>>vv.v..>..vvv.>.....>vv.>>.>>v.v..v>vvv..>...v>>......>..v..v.v>>......>v>.v....>..>v...>......>v>>.
+.v.v.>.>>......>vv>>>.v........v>v..>>....>.v..>...v>>vv..v..>.>v...>...v.vv>>.>vv>>v>vvv.>..v.>.>>v..>..v>..>.vvv.v..>.>>>>..v...>v....v>>
+.>vv>>>>....>....>..v...vvv.v.vvv.vv.v.....>>v...vvvv.>v.v..>.......v..v>...v.....vvv>.>v...v>v>.>.v.v.>v.vv.v>.>..>.>.......vvv.>>..v>.>..
+..v......>>.vv>vv.vv>.v.>>..>v>v>>...vv...>.v...>>.>..vvv>vv.vvv.v...v>v...v...>v.>..>..>v.>v..vv..>..>.>v..v.>...>..>>>...>.........v.>.>v
+>vv..>.>..v.>vv.>>>..>..>vvvv.>v>>v..vvv>..>.v..>..v.vv..v>>.>vv.>v.>>v...>..v>.v.>v...v...vv..vvv>>v>.v>.v..>..>>.>.>>.v....v..>>.>...>.>v
+v.>>.>>>v.v...v>v.v>....vv>.v>..v.v>.>..v......v>.>....>>..vv....v>...>>>.v......>.vv>>>v>.>vvvvv.v....v>..v>vv>.v>.>...vv.v>vv>v..>>.vv>.v
+.v.........v.vv..>..v....>v....>...>v......>...v.v>v..>.v.>...>vv..v...>.>.v>>..v.v>v>.v>>.v......>vv..v>v...v.v.>.>.v>.>v....vvv..>.v.v>.v
+..v..v.>>...>.vvv.vv.>....v..>..vv.>v.>>v..v..>.v>v>.v>.v.....>.vv.>.>v.>..v>..v..>v>v..>.>.v..v>.v>..v>...v.>v..>v..>....v...>>>...v..>...
+..>.v.>.vv..>v.>>.>.v.v..v>v....>.v.......>.>..>.>.>v>.v..>.>>.>v.>.>v>v..v.>..v>...>..v.>v>>>...>v...........>>...v.vv..v.v.......>v..v.v.
+>>v..v..>>v.v..v..v>.v>.vv.v>v..v.>..>v>>v..>>v...v>>vv>...>>>...>...v.v.vv....>.vvv.>.......>.>..>v..v..>.v>...>vv>v...v.>.v..>vv>.>>>v...
+vvv.....>.>v.>v>v.v.......>...v..>.vv>>.>>....v...v.vvv...>.vv>>v>.vv..v.v..vv>.>..v.vv>>>...v..>v.v.vv..v.>..>.>...v>....>vvv..>v....vv>..
+>v>>>vv.v...v>.vv>...v..>>.>>>v>>v.>vvv..>.v.v>>..v>...>.v.>>.>v........v.vv>v.>.v.>.>v>vv..>>.vv....>...>>>.>>..v>.vvv>>.>.>v...>>v>v.>>v.
+>>>>v.>...v...>..vvv.v......>>v.>v.v>.vvv..v>>>.>.>..vv..v..>>..v..>..>v.v.>.>...v>vv..vv.>>......>>>.>.>>v..>>...>.v.....v..>..>>..v>>vv..
+..v....>.>v>>...>..>>>......v>.....v..>........>>>>vv.>>v.v..v>.>>>>v..>>....v...v.>.vv.....v....>.v>vv.>....v>vv..v.....v.v>>v..vvv.v.v..v
+...>v....v>>.v.vv..>..>>>.v.vv>.>...>vv....v.v>.>>v..>>..>.......v.v.v>..v......>>.....>....>...>.vv>.>.>..>...v>.v.>vv>>>>v..>.vv.v.>>..>>
+..>v>v..v.>.v.v.....>v...>vv..v>v.>v>.vvvv>...v.>>.v>.>v>v.>v>..>...>>...v.vv>.>.>...>.>>.v>>>>vv.>vv>>.>.>>v..>.>.>>vv>.>>.>..>v.v.>..>v..
+>...v.v.v..v.v>v.>>v>v..>vv>v.>.vv>...v>.....vv>.......>...v>.>...v..vv>.vv.vv>.........>..v>>.v>v.>.>v.v>>v>..>>..>.......>>.>>>.>..v>v>.v
+....>..v....vv>....vvv.v.>..v.v>vv..vv...v..vv..vvv...>v>....v.vv.>...v>v....v..>.>>>vv..>....>...v>>>.>vv.>.vv>.v>.>.v....v.vv....>v>.v...
+..>.vv.vv.>....>.>>..vv>..v...vv.>>vv>>>.>>>.....vv.....v.....v>>.>>>v>v.v>.>>..v.v...v.v....vv.>..>>...v.>>.v.v.>....>>..>.>>......vv..>>>
+v....v>..>>...>.v.v>..>..v>.>.>...........>>..v....vv.v...>v.vv..>>.....>..v.vv...>v..v>v...v.v>>.....>.>..v.>>.v..v.v>v>>>.v......v.v.....
+.>..v..>.>..>vv>.v>.vvv.....v..>>>.....v.>v.>v>.>>.>v.>.>vv>.v.....vv.>.v.>...v>.>v...v>.v.vvv>.v...v.v>..v.>v..>...v>v>...>>v....vv...>>vv
+v>v....v..>.>v>.v.v.>.v..v..>>vv.v.>...>>.>....v>..>.v>v.>vv>....v..v>.vv.>v.>.v.v....>.v>.vv..>.>..v.v....>.vv...>.v>vv..v>v.v>v..v.>>>vv.
+>>...>v.v.>v>>.vv.v.>>v.>>v..>.>vv>.>.>>..>..>...>...>vv..vvv.>v.>vv.v.>.>v..v...vv>..v.>...vv..>v..>.v..>.v.v.....>..v.v.>....>.>v>...v.v>
+v>.>>v.......>.>......v...>>.>v>vv....>....v.>vv.>..>.v...>.>v..v>...>>.vv.>.v.vv..v.>v.....vv...>...v.>...v.>..vv>>>>v.>.v.>...v>.>.v>>...
+>.>.vv>>>.v>.v....>vv.vv.>...>.>.>.>>.v.>.v...v...>vv...>..vvv....v>.vv..>>..>..v...>>.v.v..>...v...>.>....>>.>..>v>v>.v>>..vv.>v>.>.v..>>.
+...>.v.>>.....v...v...vvv...>>.vv>v>.>...v..v>.>.v...>>>.v.>>..vv>.v>vvv....>...v>>.v>.>>>.v.>vv...v.v.>..>>v>v.>....>.....>.>>...>........
+.....>..v>vvv>>>v....v>....v.>v..v.v..>..v.....vv..>.>.vv..v..v.....v>.v..>v.v...>.....vv.v.v.>...v.v.v..>..>>....>.>..........v.>>>.v.>v.v
+..v.vv>.>v.v>..>vv..vvvvv..>...v....v.....v>>..>...>...>.....vv>.>v.>....v>>..v..v..v.>>.>>.v.>v.vv.>vv>.>>.....>.>>...>..v.>vvv.v....v.v..
+>>>>...v...>>v..>>>>v>>>>.vv..v>v.v.>.v.>v..>>v.>>vvvv>v>vv..vv>.>>.v>>>.>>..v.v.vv.>vv>vv.>vv>>.....>.>>.vv....vv.....v..v...>.....vv>.>.>
+vv..>...v.v>v>...vvv>.>...v>..vvvv.v.vv>>.....vv>....>vvvv>.>..>.v>.>.>.v>>.>>v..v>v..v.>v>.>...v......vv>.v...vv...>.>v>.>v>v.v>v.vvv.....
+.v>vv>..>.v..>>..v..v..v.v>.v>v...>...>....>..>>v.>>.vv>v>.v...>>.v.>..v>.....>v>v>v.v.>>...v.>v.v>.v>v>..>.v>.>vv>.vv>..v>....v.v.>.>..vvv
+v..>>.>>>........>...>v...v>..>>....v.>..>...>..v...v.>>.......v..>>v.v..>v..>v>vvv>..>v..>>v>>>....>..v...v.>...v...v>....>v>.>>.>vv...>.v
+v>v..>vv.vv...v>...v.v.v.vvv>v>>v>..>..vv...>v...vv...v.>v..v.v..v..>v.v.vv...v.v..>.v>>v>..>>vv.>.v.>v>v>.>>...v>v>..v.>>....v>.v..v.>.v..
+.....v.>..>..v>.v...>.....v>..>.v..v.>v>.>v..v..>..>>v...vv.vvvv.>...>vv.v>>v..>v.>.>.>vv..>.v..vv>>..>>v.v.>v.v>>v>..>v.v.v...vv.>..>>.v..
+>...>v....>..vvv.>..>>>..v>.>.v...>.v>>..v.>..>..>v.v>.>>...>>>.v..>.v...>.>vvv.v.>v...v>..v.>v.....>.v>.v....v>.........v>v...v.>v......>.
+>>.vv>.>...v.v.vv.vvvv...v....>.>.>..>.>>.v..vvv..v.>>>.>>..>v....>.vv>v.vv..v...>>.v>>.>.>vv.>.>v...vv..>.>.v>...>v.v.>v.v.>.>>.....v.>...
+.v.v.v...v.v..>..v>..>.v.>....>.>.vv...>>.>..>.>>...v....>>.>........v>v...vv>>>....>.>.>.....v.v....>.>>.>.v.....v....>.v>....>>.>v..>.>..
+..v.>..v.v..vvv>.>..>v....>vv>v.......v>vv>>.>>..vvv.>>>v...v>.vv..v.v>..vvv..v.v>..>.v.v>v>...v...>..>>....>....>>..>....vvvv.>..>v...v>vv
+.>.v>>>.v.>..v.v...>.>>...>>v>>.>.vv.>>.>...>..>.vvv.....>>.v..........>..>vvvv.>v>.vvv.>v.v..>.>>...vvv.v.>v..>>.v>v>>.v>..vv...>>.....>.v
+v...v>.....>.v>.v.v.>>v>.vv.v>>.v...vv.>..>....v.>.>v...>...>.v.v..v>.>>>>vv..>..>.>vv>...v>>v>.>>>.>.>.>>>>v..vv>>vv.v.>...>vvv>..v>.v.vv.
+.>>.vv....>vvvvv..>>v.>.>>...v..v..v>v>>.v..vv.v>.v.v>vvvv>.vvv.>v>vvvv...............v.v.>..v.>vvv..v..>...vv>.>..v.......vv...>v.>.>v....
+v.v.v.vvv.v..>v.>>v....v>.v>>>v>v...vv>..vv>....v>..>vv.>>vvv.>.vv>..v..v....vv.v>v>v>>...v>>.v.v>..>...v.>.>>.........v.>.v>.>...v.v.v>.>v
+v>.v>.....v..>..v.vv.vvvv..v.....v....>.>>.>>v>v.>v.v>..v....v..v..vv.>..vv.v.vv>....>vv.v.>..v..vv>..>v.>.vv.>v>v>.>vv>>..>..v..v...>....>
+v......v>..>....>....>>...>......>...v.v.>..>>.>.>>.v.v>.>v>vv...v>..>.vv...>>v..v.....v>>.v....v..>v>vv.......vv...>>>..>>>v..>.v>.>>.>...
+..>..>v....v>.vv>v...>>.>v...>>v..>vv.>...>.>.v....>.v.>v..>.v>>...v.v.v>...>....v.v..>v>>>vv...v>vvv..v.v>v>..>>..v>.v..>....v>.>..v.v.>..
+vv>>>..>.>v..>>.>..v.>v.>vv..v..v..>v...>.>>v..>>.v>..v.>>.>>.>v.>v.v..>v.>>.v.....v.....v....>.>...v..vv.>..>v...>.v....v.v..v.>.>vv...>.>
+v.vv.vv>v>.v.>.....v..vv..v....>v.vv>>..>....v.>.v>>..vv....>v..v>>.>v.>...vv.v>.>..v..v>>..>...v.>.v.v>.>..vvv.>.>.>.vv>vv.v.v..vv..>>>...
+.>..vvv....>...v>.>.v..v...>.v>...v.v..v>.>..v..>v..v.vv>..>.>.v>>>.v>.>...v...>>.>.v>.>v.v.>>v..>vv>...>>.>>>>...>.>.>...>...>>>..>.v>v..v
+vv..>.v..v.>>..v>>..>..vvv.v..>v>>>...>>.vvv>>v>.>.v.>..>v>vv.v...>>v.>>>>v...>>>.vv.>>.>.>>.v.....v.v>.v>>.v.>vv>>>>.vv..v>..>>..>.>>.v...
+>.v>...>...v>>.>>vv>..>.vv..vv>>.>v.>.>....>>>.v>>.v.v.>>.v.>v.>>.>.vvv..........>.>vvv.>>.>.v>vv>v..>.....v..>>..v>.>v>>>v>.v.....v.>.....
+.>.v>>.>....v.v>....>>>.>..v>.>..>......>...v..>.vv>.>.v>..v>.vv.v..v...v>>>..>>...>vv.>v>.vv.>vvv....vv.>>>>.>>v...>.>>..v..v>>..>.>>.v.>.
+>>..>vv>>.>v.v.>v.>..vv....v>v...vvvvv..vv>v.v..>v.v>>>vv..v.>..v.v.v.v>.v........>.>>vv....v.v..v...vv.>>.v>>>>..v>.>..>>...>..v...>.>..>v
+...>....>vv.vvv...v>.v...v>v>v.v.v.vvv.>vv..vvvv.v>...>........vvv.>...v.>.>vv>>.....>vv>.>...v.vv>....>>.v>>vv>>.v.>v......vv>.v>v.v.v.>>>
+.vv.>..>v.v.>>.>v.>v..v..>.>..>.v>>v.>v......v...vv..>v>.vv.v>....>vvv....>>...v.vv..v>v....v.v.>>.v.v.>vv..v.>v>.v........v..vv>...vvvv>.v
+>.>v.v...>..v.>.>.>..>.....v.>.vvv..>>>....>vv...v>..>v...>..>>.v.>>>v.>.>....>>.v>.>>>>v>v.vvvv.v...v>>.>.....>vvvvv.v>>v.vv....v>.>..v>>>
+.>..v.v.>.....>vv>>.>.>v..vv..vv.......v.>v..>>.>v>...v.>.....>....>..v..>>....>.v...>.>.v.>>.....>v....v.v>vvv.>vv.v...>.vv..v.>...v>.v.>v
+.v..v>.vv>v....>..v..v.>..>...>>..v>v.v.....>.v>v.v.>>>v>v.>>....>>.>>.>.>>...vv.v.>>..>v...>>vv.v...>..>>.>>.>..>..>..>.>>v.>..>>....v>v>>
+.>...>.>..v....>>..>>vvv>..>>>.v.>.>v...>.vv>.>.v>..>....>..v>..v.>>.>>.>>v>.>.v>..>..vv>>..vvv..v..v.vv>>..>.>v.v..>v.........v....>.v>.>>
+>.v>.>...vv>...>>v>..v..v..>vv..vv.....v>>>v>.vvv>v>v>.>v..v.v.v..>.v.vv>v....>>......>.>>...>.>>>....>.v...v>..>..v>>>>.>..v.vv.>v..>.vvvv
+>.>>.>>>v>vv.v>.v>.v>>>>>....>v.>>>..>.v>vvvv>v>........v.v>v>.v>.vv...v>>....v..>>v.>>>.vv>>.v.>v..>>.vv.vv>...v.>..v...>..v>..>>vv.v.v.v.
+.vv>...>.vv.v>>>.>vv>v..>.>>>...>...>>.>.v..v>....v>>>.v.vv.......v>..>vvv>...>..v>>>..vv.v....v.>>v.>..>v>.vv.>>.v.v>v...v>>v.>vv.>..v>>vv
+....>...v>v.>..>v>vv>...v.v>.v.v..>.v..>.>>vv..>.v.>.......>.>v>v..>...v...v.v.......>....v>..>.>vv>..vvv>>>v.v>vvv.vvv.v.v>v>>>vv..vv..vvv
+.......v>>>.v......v..v>>v.v>..v.vv..>.>.>v.....>v>>>.v>..v..>.>.v..v>....v.>v>........v>...vvv..v.>...v.vv.vvv>...v.v.v.>.v>v>>>>>..v....v
+..v.>...vv.vvvvv>>.>.>.>...>>>....>..>.v>>vv...>..>...>v..>.....vv..>v>>.v...v....>v.....v.......v..v...vv>v.>.v>...>v>v.>.>>v>.v.>........
+.>..v..vv.>....>>v.......>..v.....v..>.>..>v>.>>..>>.v.v.v.>.v..v.v.v>.>.>.vv>>....v.vv>>..>.v....>..v..>..v>..vv.>.>v.>>..>v.>.v>v>v..v.>.
+>..>>.v.v.>v..v.v>.v...>......vv>>v..v.>v...v>.>>>v....>.>>v.v..v..vv.vv.vv.v...>..vvv.>..>>.v.>.v>..>.>>>...v.>..>.....v.>.v>..>....>>v.>.
+...v>v...v...v.v>>>..>>...>.>>....>v.v..>vvv..>.vv>>>>.v.vv>v.>>.v.>v.........v.>>.v>>.>v>v..>v....>>...v.....>.>>.....>>>vv>>>.>v.v...>...
+..vv....v.>v..v...>>>>v>>...v>...>v.v>.>.v..v>..>..v..v.v>>>.vvv>.>.....vv.v.....vv..v>....v.>v..>>>.vv>...>...>vv>....v>v..>v.vv>..v..vv>v
+..>>vv.>v.v..v>.v..>.v>.>.>v...v.v.v.v>.>.v..v>..>vv.v>>>vv>.>v.v>>.>>..>.v.v>v..v>>.>.v.v.>v.>.>..>>vv>.....>v.v...>v.>v.v....v.>>.v>.>.>.
+..>...v.>vv>>v..v>......>v....v.vvv.>..>.v>v>..v...v>v.v>>vv>>..v.>..>...>>.>vvv.....>.v.........>v.>>.>..v.>...>>.>.>.>v>v.........v.>v.>>
+..>v.v.>>>>...v..>.v>.v>.>v>v..vv.>.>..>..>v..v.....>.v..v>....>v..v..v.>>..>vv.v>v...>v>>>>>.>>v...>.vv....>>v....v.>v....vv..v...vvv..v..
+>>>.>v.v.vv>..v>.v>.>.>>.>v.....v..v...v>.>.vvv..>>...>>>v..vv>.>.>.v>.>.....v..v>v.v..>>v.v>vv.>>.vv.>.vv>>.v>..v.v>..>vv...>.....v>>>v..v
+...>v.v.>v.v>..v>v..>.>v>>v.vv>.>v.v.>>.>>..>..>v.....v.>v.v..>>vv..v>...>>v....vv..v.>..>.>.v.v.>.>..v.v>>.vvv>v..v...v>>>..v....vv..>..>>
+.....vv>>>.>>v>.>>>>>.vv....v..>..v..>>v.v>..>.vv>>..v.v.>..>>.>..>.v...vv>>vv.v.vv.vv...>>vv.>v...v.>>v.>>>>>>..>..>.v>.....vv>v.v....vv..
+>vv.vv>vvv..>..v>v>v>v..>>>v>..>>v.>v>v..vv.>v.>>vv.>>>..v.....v...v.>.v>v.v......v.vv....>.vv>...>v...>v.v...>>vv...v>.....>.vv>>>..v>.v.>
+v>>.>v...>v>..v.>.v>v..vv>..vvv..>..>..v>vv.....>>v>..>..>..>...vvvv>>....v.>.>vvv.>.v>>>....>v>.>v>v>.............v>..v.v>.v.v.......v.>v.
+.vv....v>.vv>vv>..>.>....>...v>>vv.....vv..v.v>.>>.>>....v..v.>>v>>.....v.>v>.....>>...>>>....v.>>..vv>>>>>vv..vv....v>..>v.v..vv.v..v..vvv
+>v.>>.v.>.>>v>>...v...v.......vv....vvv.v>.>..vv.v...vv>>.v..>>.>......>..v..vvv>>>v...vv.>...v...>v..>.v...>v>v...>>.>...v..>.v.>vv>....v.
+>...>v>....>.>.v.vv>..>.>v..>..v.>v>v>..>v.v..>>vv.>>..v>>>vvvvv.>..v..>v.v..>>vvv..v>...v>>v.>..>.v.>.>...v...>...>.v>.>..vv..vv.>v...v>.v
+..>>v.>.>..v.v.v..vvv..v.v>..v.vvv..v>.>v.v..>.....v>.v>..>...vv..v.......v.>v..>.>.>v.>..v.v......>...>v..>v.>>v..v.v..vv......v>>..>>v>..
+>.>>v.v>>...v..>vv.>.v>>.v.v>>.v>..>>>..>..>.....vv......>v>.....>vv..v.>v...v>.vv..vv.v>..v.v..v...v>....>...v>>v...>.>>.v>...v>.>>.>v.v.>
+..>v..v>>.....>>>..vv>v..v>v>vv.v.>v.>v.>.v.vvv..>.>......v...v...>...>.>.v>>v.>.vv.>..>...vv..>..v..v.vvv..v.vv>vv>>.v....v.v>..v..>....vv
+..>v>...v...>.v.v..v.v>..v>>.v>...>.v>....v>v..>>>..v>.v.v>>>>.vv>..>>.>.v.>.v>...>.vvvv..v.v.vvv.>>>>...>v>>.....v..>..>vv.v.vvv>.>..v.>.>
+.>..v....v.v>>.>....>>>v.>v>>..>.v.vv.>v..v..>>vv>>..v.v>.vv>>.v.>..>>>v...>...>>>v..v>>>.v..v...v..v..v.v>.v.....vvv>..v...v.>>v>v.>>>vv>.
+v..vv.vv.v..v.v..v>..>v.vvvv>.......>v>v..>........>v.>...v..vvv>>.v..v.>....>>vv.v>...>vv>...>..v....v...vvv.>....>....v>>.>.v..>...v>....
+v.vv>>>v.v..>v.v>.>>.v.v..>..>>v....v>.vv.>>v..>..>...>.>>..>....>>.>>v....v..v>..>.v..>.v..v..>>.>>>>..>v...v.v>v>v.>v.>..vv.>..>.vv..>.v>
+.>>>vv>>.v.vv.v>.vvv.>...v>..>v.>..>vv.>>vvvv.vv.>v>v...v.v>.>>.v.>..vv>.v....v>vv>>>v>v.>..>..vvvvv.>v...>>>v>>.v>.>.>..v>.vvv..vvv.>..v..
+.............v>v>....vv.v.>.v.>>...v.>>...>.v>.v>v>>...>>...v.v..v>v>...v..>v>..v....>.v..v>..vv.>>.>..vv>..v>v..vvv....v.>vvv..v.....>v>.>
+.v...>..v>..v>>.v.>.vv..v.>>...v>..v.>...>>vv>vv>..>..v..v>>.>v.v.>vv>.>v.v>..v.>v>..v..>...v....>v.>vv>v>..vvvv>....v>.>v.>..>>v.v.v.v>>v.
+>...>.>.........>vv......v..>v.>v>>.>..>.v..>>...v.v>v..>>..>vv>...vv>.v.>v...>...>vvv>..v..v.v..v....>....>v>..>v.>..>..>>>....>vvvvv..v..
+vv>>...>>.v>>>v..>.vv.>>>>.>.v>v>vv>..>.>vv>>v..v.>......vv.v.v..>..>...>..v>>v.v.v>...>>>v>...>>v..v>.v..v.>>>vv.>>vv...>>........>vv....v
+....vv>.....vv.v>.vv.vvv>vv....>>>.v...v>v........>..>....>>.v>..>v>>.v..v..>.vv.>.v.v>>>>..>>.>.>.>.>.vv..>v>.v>...vv.>>v>v.>>.v>v>vv>>>..
+>.v.>...v.>>>..>vv..>.v.vvvv.v>v.>>.>....>>.>>v.....>.v>....v..v.>>>....vvv>.v>...v>>.>v...>v..>..vvv>.v.v.vv>v.v..>v>..>.>..>..vvv.v.vv>v.
+v>...v..>>>v..v.>..>..v.>.>.vvv.v.>>.v>v..>.v>.v..>>>.vvv.>v..vvv..v.>.vv>.......>.>..>.v.vv>....vv>..>>.vv..v>v.>.v>>..v.vv>..vv.vv.....>>
+vvv.>>v>>v..>>....vv.vv.vv.....v..>.>..v>>......vv.>v.>>vv...>v.......v.>>v.v..v...>..vvv....vvv...>..>vv.....v.v>.>..>v...>v.>.v.vvv...>>>
+.>v.>..vvv.>>..>.v.....>.>vv>.vvv..v.v.....>>.>....>>vv.vvv>>...v....v..v>.....>.vv>vvv...>.>v>>>..>......vv...>>...>>.v.....>.v>>vv>.v>>.v
+>v.v.vv>v>v..>>v.v....v>>>.>...>v.v>v.v.vv>.v>.vv..>.>..v.......>.v>v.vvvv..vv.>>.vv.vvv...v..>...>....>v..>>>..>....>..v..v>..v..vvv..v...
+>.vv.v>v.v>..v..v.........>.....>...>v>.v>>.v>>...>..vv.>>.>vv.v.v.....>.v...>vv>>v......>.>.>v>...>.....>>..v......v.vv>vv>v>...v>v>....vv
+v>>vv.v>.>>v.>v>...>.>..v.vv..>>..v.v..>v>.v>.v.v..>...>...>>..v>>>v.>.......vv.>v.>>.>>......v..>>.>..>>...v>>>v.>v.v.>vvv....>vvv>>..>...
+>v>..v>......v..vvv.....>.>>v..v..v....>>.vvvv.>>v>vvv.v.v.v>>>v.>v.>>.v....v.>>.>..>..v.....v>.vv....v.>v.v>..v.....v.vv.>>vv>...vv.>>.>.v
+.v.>.v......v....v>v.>.>v.v>.>.v...v...>.vv..v.vv..v.v..v..v...>.>>.vv.v.>vv.....v..v.>>.>.v.....>.>.v.v>.>v>.>>>..>.>...v>.>>.>>..>>.v.v.>
+..vvv.v..>>..>v...>vv...>>.v.>>v...>>..>.>>..>vv>..>.>>..>..>..>>>....>.>.>vv.vv...v.v.....v>v..>.>...vv>>>>v>vvv............>v..>v.v.>.>v>
+......>..vv.....>>.>..vv.>vv...v.v...v>v.>.>v>.>v..>.>..vv.>.......>v....v..>....>v..v.vv.>.v.vv..v.v.>.v....>v.vv....>..>vvvv...>>.>.vv...
+>...>>>vv...v.v.v...>>vv.>v.>.>v>.>v..>>..v..v..>..>.>..v>.vv>...v..vv>>vv..>..>>v.>..v.>..v>..>.....>.vv>..>>>.>.>vvv.vv.......vv>vv>.>.v>
+vv.vvv..v...>vv...v.vvv.>v...vvv....>v>.vvv>v>..v..>.>>>>>.vvv..>...>..>.>..>v>.....v.....v.v>>>>.>vv.v..>>>.>>.v>..>..>....>..v.>>.>>.>.>.
diff --git a/2021/day25/makefile b/2021/day25/makefile
new file mode 100644
index 0000000..63a19d9
--- /dev/null
+++ b/2021/day25/makefile
@@ -0,0 +1,2 @@
+all:
+	g++ -std=c++20 -lgtest day25.cpp -o day25
diff --git a/2021/day25/test0.txt b/2021/day25/test0.txt
new file mode 100644
index 0000000..76296ab
--- /dev/null
+++ b/2021/day25/test0.txt
@@ -0,0 +1,7 @@
+...>...
+.......
+......>
+v.....>
+......>
+.......
+..vvv..
diff --git a/2021/day25/test1.txt b/2021/day25/test1.txt
new file mode 100644
index 0000000..5e9a19e
--- /dev/null
+++ b/2021/day25/test1.txt
@@ -0,0 +1,4 @@
+..........
+.>v....v..
+.......>..
+..........
diff --git a/2021/day25/test2.txt b/2021/day25/test2.txt
new file mode 100644
index 0000000..0f3c0cd
--- /dev/null
+++ b/2021/day25/test2.txt
@@ -0,0 +1,9 @@
+v...>>.vv>
+.vv>>.vv..
+>>.>v>...v
+>>v>>.>.v.
+v>v.vv.v..
+>.>>..v...
+.vv..>.>v.
+v.v..>>v.v
+....v..v.>