commit 443d5279ed7f62916a1f62c7b4ffec5bda471bd5
parent 8d33eef329a433ee50a7c045cb3e9091b5febf90
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Mon, 16 Dec 2024 09:33:38 +0100
Day 16 2024
Diffstat:
6 files changed, 582 insertions(+), 0 deletions(-)
diff --git a/2024/16/Makefile b/2024/16/Makefile
@@ -0,0 +1,24 @@
+CC=g++ -std=c++20 -g -Wall
+
+a:
+ ${CC} -o a.out day16a.cpp
+
+b:
+ ${CC} -o b.out day16b.cpp
+
+clean:
+ rm -f a b
+
+atest: a
+ ./a.out
+
+btest: b
+ ./b.out
+
+arun: a
+ ./a.out < input
+
+brun: b
+ ./b.out < input
+
+.PHONY: a b clean atest btest arun brun
diff --git a/2024/16/day16a.cpp b/2024/16/day16a.cpp
@@ -0,0 +1,180 @@
+#include <algorithm>
+#include <cstdint>
+#include <iostream>
+#include <queue>
+#include <string>
+#include <string_view>
+#include <vector>
+#include <set>
+using namespace std;
+
+class Direction {
+public:
+ int U, R;
+
+ Direction(char c) :
+ U{c == 'v' ? 1 : (c == '^' ? -1 : 0)},
+ R{c == '>' ? 1 : (c == '<' ? -1 : 0)} {}
+
+ Direction(const int i, const int j) : U{i}, R{j} {}
+
+ Direction turnright() const {
+ return turn(-1, 0);
+ }
+
+ Direction turnleft() const {
+ return turn(1, 0);
+ }
+
+ bool operator<(const Direction& d) const { // For set<Direction>
+ return this->U < d.U || (this->U == d.U && this->R < d.R);
+ }
+
+ int index() const {
+ if (U == 1 && R == 0) return 0;
+ if (U == -1 && R == 0) return 1;
+ if (U == 0 && R == 1) return 2;
+ if (U == 0 && R == -1) return 3;
+ return -1;
+ }
+private:
+ Direction turn(int64_t sin, int64_t cos) const {
+ return Direction(cos * U - sin * R, sin * U + cos * R);
+ }
+};
+
+class Position {
+public:
+ int64_t i, j;
+
+ Position() : Position(0, 0) {}
+
+ Position(int64_t a, int64_t b) : i{a}, j{b} {}
+
+ Position step(const Direction d) const {
+ return Position(i+d.U, j+d.R);
+ }
+};
+
+const Direction all_directions[] = {
+ Direction(1, 0), Direction(-1, 0), Direction(0, 1), Direction(0, -1)
+};
+
+class Qelem {
+public:
+ int64_t distance;
+ Position p;
+ Direction d;
+
+ Qelem(int dis, Position pp, Direction dd) :
+ distance{dis}, p{pp}, d{dd} {}
+
+ bool operator<(const Qelem& other) const {
+ return distance > other.distance;
+ }
+};
+
+class Board {
+public:
+ int64_t N, M;
+
+ Board(const vector<string>& lines) :
+ N{static_cast<int64_t>(lines.size())},
+ M{static_cast<int64_t>(lines[0].size())},
+ cells(M*N), visited(4*M*N)
+ {
+ for (int64_t i = 0; i < N; i++)
+ for (int64_t j = 0; j < M; j++)
+ cells[M*i+j] = lines[i][j];
+ }
+
+ char& operator[](const Position p) {
+ if (const auto c = coord(p); c == -1)
+ return out_of_bound;
+ else
+ return cells[c];
+ }
+
+ Position find_S() {
+ for (Position p(0, 0); p.i < N; p.i++)
+ for (p.j = 0; p.j < M; p.j++)
+ if ((*this)[p] == 'S')
+ return p;
+ return Position(-1, -1);
+ }
+
+ int shortest_path(Position p, Direction d) {
+ clear_visited();
+ priority_queue<Qelem> q;
+
+ q.push(Qelem(0, p, d));
+
+ while (!q.empty()) {
+ auto e = q.top();
+ q.pop();
+
+ if ((*this)[e.p] == 'E')
+ return e.distance;
+
+ if (is_visited(e.p, e.d) || (*this)[e.p] == '#')
+ continue;
+ set_visited(e.p, e.d);
+
+ q.push(Qelem(e.distance+1000, e.p, e.d.turnright()));
+ q.push(Qelem(e.distance+1000, e.p, e.d.turnleft()));
+ q.push(Qelem(e.distance+1, e.p.step(e.d), e.d));
+ }
+ return 999999999;
+ }
+
+ void print() {
+ for (Position p(0, 0); p.i < N; p.i++) {
+ for (p.j = 0; p.j < M; p.j++)
+ cout << (*this)[p];
+ cout << endl;
+ }
+ }
+private:
+ char out_of_bound = '$';
+
+ vector<char> cells;
+ vector<bool> visited;
+
+ int64_t coord(const Position p) const {
+ auto [i, j] = p;
+ return i >= N || i < 0 || j >= M || j < 0 ? -1 : M * i + j;
+ }
+
+ void clear_visited() {
+ for (int64_t i = 0; i < 4*M*N; i++)
+ visited[i] = false;
+ }
+
+ bool is_visited(const Position p, const Direction d) {
+ if (const auto c = coord(p); c == -1)
+ return false;
+ else
+ return visited[4*c + d.index()];
+ }
+
+ void set_visited(const Position p, const Direction d) {
+ if (const auto c = coord(p); c != -1)
+ visited[4*c + d.index()] = true;
+ }
+};
+
+int main() {
+ string line;
+ vector<string> lines;
+
+ while (getline(cin, line))
+ lines.push_back(line);
+
+ Board board(lines);
+ Direction d('>');
+ Position p = board.find_S();
+
+ cout << board.shortest_path(p, d) << endl;
+
+ return 0;
+}
diff --git a/2024/16/day16b.cpp b/2024/16/day16b.cpp
@@ -0,0 +1,219 @@
+/*
+This solution is bad, it runs in 45 minutes or so. Baiscally I find the
+distances between all pairs of valid (position, direction) pairs; a position p
+is on a valid shortest path if and only if for any direction d in {>, <, v, ^}
+the distance from (S, >) to (p, d) plus the distance from (p, d) to E is
+equal to the shortest path distance.
+
+I tried to do smarter things but I kept making mistakes. This one is
+inefficient, but it has the advantage of requiring minimal changes from part 1.
+*/
+
+#include <algorithm>
+#include <cstdint>
+#include <iostream>
+#include <queue>
+#include <string>
+#include <string_view>
+#include <vector>
+#include <set>
+using namespace std;
+
+#define INF 999999999
+
+class Direction {
+public:
+ int U, R;
+
+ Direction(char c) :
+ U{c == 'v' ? 1 : (c == '^' ? -1 : 0)},
+ R{c == '>' ? 1 : (c == '<' ? -1 : 0)} {}
+
+ Direction(const int i, const int j) : U{i}, R{j} {}
+
+ Direction turnright() const {
+ return turn(-1, 0);
+ }
+
+ Direction turnleft() const {
+ return turn(1, 0);
+ }
+
+ bool operator<(const Direction& d) const { // For set<Direction>
+ return this->U < d.U || (this->U == d.U && this->R < d.R);
+ }
+
+ int index() const {
+ if (U == 1 && R == 0) return 0;
+ if (U == -1 && R == 0) return 1;
+ if (U == 0 && R == 1) return 2;
+ if (U == 0 && R == -1) return 3;
+ return -1;
+ }
+private:
+ Direction turn(int64_t sin, int64_t cos) const {
+ return Direction(cos * U - sin * R, sin * U + cos * R);
+ }
+};
+
+class Position {
+public:
+ int64_t i, j;
+
+ Position() : Position(0, 0) {}
+
+ Position(int64_t a, int64_t b) : i{a}, j{b} {}
+
+ Position step(const Direction d) const {
+ return Position(i+d.U, j+d.R);
+ }
+};
+
+const Direction all_directions[] = {
+ Direction(1, 0), Direction(-1, 0), Direction(0, 1), Direction(0, -1)
+};
+
+class Qelem {
+public:
+ int64_t distance;
+ Position p;
+ Direction d;
+
+ Qelem(int dis, Position pp, Direction dd) :
+ distance{dis}, p{pp}, d{dd} {}
+
+ bool operator<(const Qelem& other) const {
+ return distance > other.distance;
+ }
+};
+
+class Board {
+public:
+ int64_t N, M;
+
+ Board(const vector<string>& lines) :
+ N{static_cast<int64_t>(lines.size())},
+ M{static_cast<int64_t>(lines[0].size())},
+ cells(M*N), visited(4*M*N)
+ {
+ for (int64_t i = 0; i < N; i++)
+ for (int64_t j = 0; j < M; j++)
+ cells[M*i+j] = lines[i][j];
+ }
+
+ char& operator[](const Position p) {
+ if (const auto c = coord(p); c == -1)
+ return out_of_bound;
+ else
+ return cells[c];
+ }
+
+ Position find_S() {
+ for (Position p(0, 0); p.i < N; p.i++)
+ for (p.j = 0; p.j < M; p.j++)
+ if ((*this)[p] == 'S')
+ return p;
+ return Position(-1, -1);
+ }
+
+ int shortest_path(Position p, Direction d, vector<int>& shortest, bool save) {
+ clear_visited();
+ if (save)
+ for (int i = 0; i < 4*M*N; i++)
+ shortest[i] = INF;
+
+ priority_queue<Qelem> q;
+
+ q.push(Qelem(0, p, d));
+
+ while (!q.empty()) {
+ auto e = q.top();
+ q.pop();
+
+ if ((*this)[e.p] == 'E')
+ return e.distance;
+
+ if (is_visited(e.p, e.d) || (*this)[e.p] == '#')
+ continue;
+ set_visited(e.p, e.d);
+
+ if (save)
+ shortest[4*coord(e.p) + e.d.index()] = e.distance;
+
+ q.push(Qelem(e.distance+1000, e.p, e.d.turnright()));
+ q.push(Qelem(e.distance+1000, e.p, e.d.turnleft()));
+ q.push(Qelem(e.distance+1, e.p.step(e.d), e.d));
+ }
+ return 999999999;
+ }
+
+ void print() {
+ for (Position p(0, 0); p.i < N; p.i++) {
+ for (p.j = 0; p.j < M; p.j++)
+ cout << (*this)[p];
+ cout << endl;
+ }
+ }
+
+ int64_t coord(const Position p) const {
+ auto [i, j] = p;
+ return i >= N || i < 0 || j >= M || j < 0 ? -1 : M * i + j;
+ }
+private:
+ char out_of_bound = '$';
+
+ vector<char> cells;
+ vector<bool> visited;
+
+ void clear_visited() {
+ for (int64_t i = 0; i < 4*M*N; i++)
+ visited[i] = false;
+ }
+
+ bool is_visited(const Position p, const Direction d) {
+ if (const auto c = coord(p); c == -1)
+ return false;
+ else
+ return visited[4*c + d.index()];
+ }
+
+ void set_visited(const Position p, const Direction d) {
+ if (const auto c = coord(p); c != -1)
+ visited[4*c + d.index()] = true;
+ }
+};
+
+int main() {
+ string line;
+ vector<string> lines;
+
+ while (getline(cin, line))
+ lines.push_back(line);
+
+ Board board(lines);
+
+ vector<int> v(4*board.N*board.M);
+ int sh = board.shortest_path(board.find_S(), Direction('>'), v, true);
+
+ int count = 0;
+ for (Position p(0, 0); p.i < board.N; p.i++) {
+ for (p.j = 0; p.j < board.M; p.j++) {
+ cout << "Checking intermediate position "
+ << p.i << ", " << p.j << endl;
+ if (board[p] == '#') continue;
+ for (auto d : all_directions) {
+ int i = 4*board.coord(p) + d.index();
+ if (v[i] == INF) continue;
+ int ssh = board.shortest_path(p, d, v, false);
+ if (ssh + v[i] == sh) {
+ count++;
+ break;
+ }
+ }
+ }
+ }
+
+ cout << count+1 << endl;
+
+ return 0;
+}
diff --git a/2024/16/input b/2024/16/input
@@ -0,0 +1,141 @@
+#############################################################################################################################################
+#...........#...........#.....#.......#.......#...#.......#.................#...............................#.........#.......#...#...#...#E#
+#.#.#######.#.#####.#####.#.#.#.#####.###.###.#.#.#.#####.#.#######.#####.###.#######.#########.###########.#.#######.#.#####.#.#.#.#.#.#.#.#
+#.#.......#.#...#...#.....#.#...#.........#.....#...................................#.....#...#.....#.......#.......#...#...#.#.#...#...#.#.#
+#.#.#.#.###.#.###.#.#.#.###.#####.#################.###.###.#.#.#.#####.#.#.###.###.#####.#.#.#.###.#.#.#.###.#####.#####.#.#.#.#####.#.#.#.#
+#.#...#.#...#.#...#.#...#.#.#.....#...#.......#.........#...#...#.................#.....#.#.#.......#.......................#...#...#.#.#...#
+#.#.#.#.#.#.#.#.#.#.###.#.#.#######.#.#.#####.#####.#.###.#####.#.#.#.#######.###.#####.###.###.#####.#.#.#.#####.###.#.#.#######.###.#.###.#
+#...#...#.................#.........#...#...#.#.....#.#...................#...#.#...#...#...#.....#.#.#.#.#.#...#.....#.#.............#...#.#
+###.#.#.#.###.#.###.#.#.#.###############.#.#.#.###.#.#.###.#.###.###.#.#.#.###.###.#.###.###.#.#.#.#.#.#.###.#.###.#.#.#.#######.#####.#.###
+#...#.#.#.#...#.............................#...#.................#...#.#...#...#...#.........#.#.#...#.#.#...#.....#.#.#.#.....#.......#...#
+#.#.#.#.#.#.###########.#.#.###.#.#.#.#.###.#####.#.#.#########.#.#.###.#####.#.#.#########.###.#.#####.#.#.#######.#.#.#.###.#.#.#########.#
+#.....#.#.#.....#...............................#...#.....#...#.#.#.#...#.....#.......................#.#...#.....#.....#...#.#.#...#.#.....#
+#.#.#.###.#####.###.###.#.###########.###.#########.#####.###.#.#.#.#.###.#####.#.#.#####.#.#########.#.#.###.###.###.#####.###.#.#.#.#.#.#.#
+#...........#.#.....#...............#...#.#.........#...#...#.#.#.#...#...#.....#.#.#...#...#.......#.#.......#...#.....................#.#.#
+#.#.#.#.#.#.#.#######.#.#.#########.###.#.#.#########.#####.#.#.#.#########.###.#.#.#.#####.#.#####.#.#######.#.###.#.#######.###.#.###.#.#.#
+#.#.#.....#...#...#.......#.........#.......#.#.......#...#.#.#.#.........#...#.#...#.#...#.#.#.#...#.....#...#...#.....#...#.....#.........#
+###.#.#########.#.#.#####.###.#######.#####.#.#.#.###.#.#.#.#.#.#####.###.###.#######.#.#.###.#.#.#######.#.#####.#####.#.#.#####.#.#.###.###
+#...#...........#.#.........#.#...#.....#...#.#.#...#.#.#.#.#.#.....#...#...#.#.....#.#.#.....#.#.#.......#.#.......#.....#.#...#...#.#...#.#
+#.#.#.###########.###.#.###.#.#.#.#.###.#.###.#.###.###.#.#.#.#####.###.###.#.#.#.#.#.#.###.#.#.#.#.#######.#.#.###.#.###.#.#.#.#.###.###.#.#
+#.#...#.......#.....#.#.....#.#.#...#...#...#.#...#.....#...#.....#.#...#.#.#...#.#...#.#.....#...#.#.#...#...#...#.#.....#...#.#.#.#...#...#
+#.#.#.###.###.#.###.#.#.###.###.#####.#.###.#.#.#.###############.#.#.###.#.###.#.###.#.#######.###.#.#.#.#.#####.#############.#.#.###.#.#.#
+#.#.........#.#...#.#.#.#...#...#.....#...#.#.................#...#...#...#...#.#.#...#...#.....#...#...#...#...#.#.......#...#.#.....#.....#
+#.#.#.#.###.#####.###.#.#####.###########.#.###.#####.#######.#.#######.#####.#.#.###.###.#.#####.###.#########.#.#.###.###.#.#.#.###.###.#.#
+#.....#...#...#...#...#.......#...#.......#...#.#...#.#.....#.#...........#.....#...#...#.#.#.....#.#.....#...#.#...#...#...#...........#.#.#
+#.#######.#.#.#.###.###########.#.#.#####.###.###.#.###.###.#.###########.#.#######.#####.#.#.#####.#####.#.#.#.#####.###.###.###.###.#.#.###
+#.......#.....#...........#.....#.#.#.....#...#...#...#...#...............#.#.......#.....#...#.........#.....#.#...#.....#.#.......#...#...#
+#.#####.#####.###########.#.#####.#.#.#####.###.#####.#.###.###.#########.#.#.#####.#.###.###.#######.#######.#.#.#.#######.#.###.###.###.#.#
+#...#.#.................#.#.#.#.....#.#...#...#.#...#...#.......#.......#.#.#...#.#.#.#...#.....#...#.......#.#.#.#.....#...#.......#.#.....#
+###.#.#########.#######.#.#.#.#.#######.#.#.#.#.###.#####.###.###.#.###.#.#.#.#.#.#.#.#.#.#.###.#.#.#####.#.#.#.#.###.#.#.#######.#.#.###.#.#
+#...#.....#...#.#.#.....#.#.#...#.#.....#...#.#.....#.#...#.....#.....#.#.#.#.#.#...#...#.#...#...#.#.....#.#.#.....#.#.#.....#.....#...#.#.#
+#.###.###.#.#.#.#.#.#####.#.#.###.#.#####.###.#####.#.#.#####.###.#####.###.###.#####.#.#.###.#.###.#.#######.#######.#.#####.#.###.#.#.#.#.#
+#.#...#.#.#.#...#.......#...#.....#.#...#.....#.....#.#.....#.#...#.....#...#...#.......#.#...#...#.#...#...#.........#.....#.#...#...#...#.#
+#.#.###.#.#.#.#########.#####.#####.#.#.#.#####.#####.#####.#.#.#.#.###.#.###.###.#######.#.###.#.#.#.#.#.#.#######.#######.#.###.###.###.#.#
+#...#...#.#.#.#...#...#...#...#...#.#.#...#.....#.#.......#.#.#...#.#...#...#...#.#.#.........#.#.#.#.#...#.#.......#.....#.#...............#
+#######.#.#.###.#.#.###.#.#####.#.#.#######.#####.#.###.#.#.#.#.###.#######.###.#.#.#.#######.#.###.#.#####.#.#.#.###.#.###.#.#.###.#.#.#####
+#.......#.#...#.#.#.....#.#...#.#...#.....#.#.......#.#.#.#.#.#.#...#.....#.....#.#...#.......#.#...#.#...#...#.#.....#...#...#...#.#.#.#...#
+#.#####.#.#.#.#.#.#####.#.#.#.#.#.###.###.#.#.#.#####.#.###.###.#.#.#.#.#####.#.#.#####.#######.#.#.###.#.###.#.#########.###.###.#.#.#.###.#
+#.#.....#.#.#...#.#.....#.......#.#...#.#.#.#.#.#.....#...#...#.#.#.#.#.....#.#.#.....#.#.......#.#.#...#...#...#...#...#.......#.#...#.....#
+#.###.###.#.#####.#.#########.#.###.###.#.#.#.#.###.#.###.###.#.#.#.#.#####.#.#.#####.#.#.#####.#.###.#####.###.#.#.#.#.#####.###.#.#######.#
+#...#.#.#...#.#...#...#.........#...#...#...#.#...#.#...#...#.#.#.#.#...#...#.....#.#...#.#.....#.....#.....#...#...#.#...#.......#.......#.#
+###.#.#.###.#.#.###.#.#.#######.#.###.#.#####.###.#.#######.#.#.#.###.###.#.#####.#.#####.#.###########.#####.###.###.#.###.#####.#######.#.#
+#...#...#.#.#.#...#.#.#.#.....#.#.....#.#.#.....#.#.......#.#...#...#.#...#.#...#.....#...#.#.........#...#.#...#.....#...#.#...#...#.....#.#
+#.#####.#.#.#.###.#.#.#.#.###.#########.#.#.###.#.#####.###.#######.#.#.###.#.#######.#.#.###.###.###.###.#.###.#####.###.#.#.###.#.#.###.#.#
+#...#.....#...#...#.#...#.#.#.#.........#...#...#.....#.#.....#...#.#.#.#.....#.....#.#.#.#.....#...#...#.#...#.....#.#...#.#.....#.....#...#
+###.#########.#.#####.###.#.#.#.#############.#.#####.#.#.###.#.#.#.#.#.#######.###.#.#.###.#######.#####.#.#######.#.#.###.#.###.#######.###
+#...#.........#.........#...#...#.............#...#...#.#.#...#.#.#...#.........#.#...#.....#.....#.......#...#...#...#.#...#...#...#.....#.#
+#.###.#################.###.#####.#####.#.#.#######.###.#.###.#.###.###.#.#######.#########.#.###.#.#.#####.#.#.#.###.#.#.#####.#.###.###.#.#
+#.#...#.....#...#.......#...#...#...#...#...#.....#.#...#...#.........#...#...#...#.......#.#...#...#.#.....#.#.#...#...#.....#.#...#...#...#
+#.#.###.###.#.#.#.#####.#.###.#####.#.#.#####.#.#.#.###.###.#####.###.#####.#.#.#.#.#.###.#####.###.#.#####.#.#.###.###.#####.#.#.#.###.#.#.#
+#.#...#...#.#.#.......#.#.#.....#...#.#.#.....#...........#.#.....#...#.....#...#.#.#...#.....#...#.#.......#.....#.........#.#.#.#...#...#.#
+#.###.###.#.#.#.#####.#.#.#####.#.###.#.#.#.###.#####.#####.#.#####.###.#.#######.#####.#####.###.#.#######.#####.#########.#.#.#.###.###.#.#
+#...#...#.#.#.#.#...#...#...#...#.#...#.#.#.....#...#.#.....#...#.#.....#.......#.....#...#.......#.#...........#.#.....#...#.#.....#...#...#
+#.#.###.#.#.#.###.#.#######.#.###.#.#.#.#.###.#.#.#.###.#.#####.#.#############.#####.###.#########.#.#.#######.#.#.#.#.#.###.###.#.###.#.###
+#.#...#.#.#.#...#.#...#.....#.....#.#...#.#...#.#.#...#.#.#.....#.......#.....#...#.#...#...#.......#.#.......#.#.#.#.#.#...#...#.......#.#.#
+#.#####.#.#.###.#.###.#.#####.#####.#.###.#.#.#.#.###.#.###.#######.#.#.#.#.#.###.#.###.#.#.#.#########.#.#####.###.#.#.###.###.#.#####.#.#.#
+#...#...#.#.#.#...#.#...#...#.......#...#...#...#...#.#...#.#.......#.#.......#.#.#.....#.#.#.#.......#.#.#...#.#.....#.#.#...#.#.....#.#.#.#
+#.#.#.#.#.#.#.#####.#######.#.#.#########.#########.#.#.#.#.###.#####.#######.#.#.#.###.###.#.#.#####.#.#.#.#.#.#.#####.#.###.#.#.###.#.#.#.#
+#.#.#...#.#.....#.....#.....#.#...#.......#.....#...#.#.#.#...#.#...#.......#...#.#.........#...#...#.#.#...#.#.#.#.#...#.#...#...#.#.#.#...#
+#.#.###.#.#####.#.#####.#.###.###.#.#######.###.#.###.###.#.#.#.#.#.#.#####.#.###.#.#.#.###########.#.#.#####.#.#.#.#.###.#.#######.#.###.#.#
+#.#.#...#.#...#.#.......#.#...#.#.#.#...#.#.#.#.#.#.#...#...#.#...#.#.......#.#...#.#.#.#...#.......#.#.#.#...#...#.#...#.#.....#...#.......#
+#.#.#.#.#.###.#.#######.#.#.###.#.#.#.#.#.#.#.#.#.#.###.#.#.#.###.#.#.###.###.#.###.#.###.#.#.###.###.#.#.#.#######.###.#.#####.#.#######.###
+#.#.#.....#...#.......#.#.#.....#.....#...#.#.#...#.#...#.#.#...#.#.#...#.....#.....#...#.#.#...#.....#...#...........#.#.............#...#.#
+#.#.#.#.###.#########.#.#.#####.###########.#.#####.#.###.#.###.#.#.#####.#############.#.#.###.###.#########.###.###.#.#####.#.###.#.#.#.#.#
+#.#.......#.........#.#.#...#.....#.........#.......#.....#.#...#.#.....#...#.....#.....#.#.#.#...#.........#.......#.#.#...#.......#...#...#
+#.#####.###.###.#####.###.#.#.#####.#####.#.#.#####.#.#######.#########.###.#.###.#.###.#.#.#.#.#.###.#####.#######.#.#.#.#.###############.#
+#...#.#...#...#.#.....#...#.#.#.....#...#.#.#.#.....#.#.........#...#...#...#...#...#...#.#.#.........#...#.#...#...#.#...#...#.....#.#.....#
+###.#.#.#.###.#.#.#####.###.#.#.#####.#.#.#.#.#######.#.#######.#.#.#.#.#####.#.#.###.#.#.#.###########.###.#.#.#.###.#######.#.###.#.#.#####
+#.#.#...#...#.#.#...#...#...#.#.#...#.#.....#...........#.....#.#.#...#.#...#.#.........#.#.....#.....#.......#.....#.......#.#...#.#.#...#.#
+#.#.###.#.###.#.###.#.#.#.###.#.###.#.#####.###.###.###.#.###.#.#.#######.#.#########.#.#.#####.#.###.#.###########.###.#####.###.#.#.###.#.#
+#.#...#.#.....#.....#.#.#.#.#.#...#...#...#.#.....#.#...#.#...#...#.......#...........#.#...#.#...#...#...#...#.........#.....#...#.#.#.....#
+#.###.#.#############.#.#.#.#.###.#####.#.###.###.#.#.###.#.#######.#.###############.#####.#.#####.#######.#.###########.#####.###.#.#.#####
+#...#...#.....#.....#...#...#...#.#.....#.#...#.#.#.#.#.#.#.........#.#.#.....#.......#.....#.#.....#.......#...........#.......#...#...#...#
+#.#####.#.###.#.#.#.###.#######.#.#.#####.#.###.#.###.#.#.###########.#.#.#####.#######.#####.#.#######.###############.#.#####.#.#######.#.#
+#...#...#...#...#.#.....#.....#.#...#...#.#...#.......#.#.#.....#...#.#.#.............#...#...#...#.....#.............#.#.#.....#...........#
+#.#.#.#####.#####.#######.###.#.#####.#.#.###.#.#######.#.###.###.#.#.#.#########.#####.#.###.###.###.###.#######.###.#.#.#.#.#.#####.#.###.#
+#.#.#...........#.#...#.....#.#.#.....#.#.....#.#.......#...#.#...#...#...#.....#.#...#.#.#...#.#.....#.........#...#.#.#...#.#.#...#...#...#
+#.#.#####.#######.#.#.#.#####.#.#.#####.#######.#.#.#######.#.#.#########.#.###.###.#.###.#.#.#.###############.###.###.###.#.#.#.#######.#.#
+#.#.....#.......#...#...#.#...#.#.#...#.#...#...#.........#.#.............#...#.......#...#.#...#...#.......#.....#.#...#.#...#...#.....#.#.#
+#.#####.#######.#.#######.#.#.#.#.#.#.#.#.#.#.###.#######.#.#########.#.###.#.#######.#.###.###.#.#.#.#####.#######.#.###.###.#.###.###.#.#.#
+#.#...#.....#...#.#...#...#.#.#...#.#.....#.#...#.......#.#...#...#...#...#...#.#.....#.#.....#...#...#...#.....#...#.#.....#.....#...#...#.#
+#.###.#.#####.###.#.#.#.###.#.#######.#####.#.#.#.#######.###.#.#.#.#####.#.###.#.#####.#####.###.#####.#.#####.#.#.#.#.###.#.#.#.###.#####.#
+#...#.#.#.....#.....#.#...#.#.#...........#.#.#.#.#...#...#.#...#.#.#...#...#.....#.........#.#.........#...#.#...#.#.........#.....#.#.#...#
+###.#.#.#.###########.###.#.###.#.#########.#.#.#.#.#.#.#.#.#####.#.###.#####.#.#.#####.###.#.#.###########.#.###.###.#####.###.###.#.#.#.###
+#.....#.#...#...#.#.......#...#.#.....#.....#.#...#.#...#...#.....#.....#.....#.#.....#...#.#.#.#...#.......#.....#...#...#.#...#.....#.#...#
+#.#####.###.#.#.#.#.###.#.###.#.#####.#.#####.#####.#######.#.###.#######.#####.#####.#####.#.#.###.#.#######.#####.#.#.#.###.#.#######.###.#
+#.#.....#.#...#.#.#.#...#.#.#.#.#.#...#.#...#.....#.#.....#.#...#...#.....#.#...#...#...#...#...#...#...#...#...#...#...#.....#.#...#.....#.#
+#.#.###.#.#####.#.#.#.###.#.#.#.#.#.###.#.#.###.###.#.###.#.###.###.#.#####.#.###.#.###.#.###.#.#.#.###.#.#.###.#.###.#.#######.#.#.#.#.###.#
+#.#...#...#...#.#.....#.....#...#.#.....#.#.....#.......#.#.....#...#.....#.#.....#...#.#.....#.#.#.#.#.#.#.#...#.#...#...........#.#.#.....#
+#.###.###.###.#.###.#########.#.#.#######.#####.#.###.#.#####.#.#.#######.#.#########.#.###.#.#.#.#.#.#.#.#.#####.#########.#.#####.#.#######
+#.#...#.#...#.#...#.#.......#.#.....#.....#.......#...#.#.....#.#.......#...#.......#.#...#.#.#.#.#.#.#...#.......#.....#...#.#...#.#.......#
+###.###.###.#.###.###.#####.#.#####.###.###.#######.###.#.#####.#######.###.#.###.###.###.###.#.#.#.#.#####.#.#####.###.#.#.#.###.#.#########
+#.........#.....#.....#...#.#.........#.#.#...#...#.#...#.......#.#...#...#...#...#.....#.....#.#.#.....#.#...#.....#.#...#.#.....#...#.....#
+#.#####.#######.#######.#.#.#.#.#####.#.#.###.#.#.###.#.#####.#.#.#.#.#.###.#######.###########.#.#####.#.#########.#.#####.#########.#.###.#
+#.#.....#.....#...#...#.#.#.#.#...#...#...#...#.#.....#...#...#.#...#.#...#.#.....#.........#...#.#...#...#.........#.....#.#...#.....#.#.#.#
+#.#.#####.###.###.#.#.#.#.#.#.#.#.#.###.###.###.#########.###.#.#####.###.#.#.###.#.#####.#.#.#.#.#.#.###.#.#.#########.###.#.#.#.#.###.#.#.#
+#.#.#...#...#.....#.#...#.#...#.#...#...#...............#.....#.#.......#...#...#.#.....#.#.#.#.....#...#.......#.....#.....#.#...#.#.....#.#
+#.#.#.#.###.###.#######.#.###.#.#####.###.###.#########.#####.#.#.#############.#.#######.###.#.#######.###.###.#.###.#.#####.#######.#####.#
+#.#...#.........#.....#.#...#.#.....#.#...#.#.........#.#...#.#.#...#.........#.#.........#...#.....#.#.....#.#.....#.#...#...#.......#.#...#
+#.###.#####.###.#.#.#.###.#.#.#####.#.#.###.#####.#####.#.#.#.#.###.#.#######.#.#######.###.#######.#.#######.#######.###.###.#.#######.#.###
+#...#...#.....#...#...#...#.#.#.....#.#...#.......#...#.#.#...#.....#.#.#.......#...#...#...#.....#...#...........#...#.......#...#.....#...#
+#.#.###.#.#.#.#####.###.#.#.#.#.#####.#.#.#.#######.#.#.#.#######.###.#.#.#########.#.###.#####.#.###.#.#.#########.#.###########.#.#.#####.#
+#.#...#.#.#.#.#.....#...#...#.#.#.....#.#.#...#.....#...#...#...#.#...#...#...#...#...#...#.....#...#...#.#.......#.#.#.........#...#.#.....#
+#.###.###.#.#.###.#.###.#####.#.#.###.###.###.#.###########.#.#.#.#.###.###.#.#.#.#####.#####.#####.#######.#####.#.###.#######.#####.#.###.#
+#.#.#.......#...#.#...#.#.....#...#.......#.#.#...#.......#.#.#.#.#...#...#.#...#.....#.#.....#.....#.....#.#...#.#.......#.#...#...#.#.#.#.#
+#.#.#######.###.#.###.#.#.###########.#####.#.###.###.#.#.#.###.#.###.#####.#########.#.#.#####.#####.###.#.#.#.#.#######.#.#.###.#.#.#.#.#.#
+#.#...#...#.....#...#...#.#...........#.......#.#...#...#.#.......#...#...#...#.......#...#.#...#.....#...#.#.#.........#.#.#.....#...#.#...#
+#.#.#.###.#.#####.#.#.#.#.###.#######.#.#######.###.###.#.#####.#.#.###.#.###.#.#.#########.#.#######.#.###.###########.#.#.#######.###.#.###
+#...#...#.#.....#.#.....#...#.#.......#...#...........#.....#...#.#...#.#...#.#.#...........#.........#.#...#.....#...#.#.....#...#.#...#.#.#
+#######.#.#.###.#.#########.#.#.#########.#.#####.###.#.#.###.###.###.#.###.#.#.###.#####.#.###########.#.#.#.###.#.#.#.#.#####.#.###.###.#.#
+#.....#.....#...#.#.......#...#.#.......#...#.......#.#.#.......#.....#...#...#.....#.....#.......#.....#.#.#...#.#.....#.#.....#...#.#.#...#
+#.#.#.#####.#.###.#####.#.#####.#.###########.#######.#############.#.###.###########.#.#.#######.#.#####.#####.#.#####.#.#.#.#####.#.#.###.#
+#.#.#.#.....#.#.#.....#.#...#...#...........#...#.....#.............#.....#.....#...#.#.#...#...#.#...#...#.....#.....#.#...#...............#
+###.#.#.###.#.#.#####.#####.#.###.#####.#.###.###.#####.#####.#.###########.#.#.#.#.#.#.###.#.###.###.#.#.#.#########.#.#.###.#########.#####
+#...#...#...#.#.......#...#.....#.#...#.#.#...#...#...#.....#.#.#.........#.#.....#...#.#...#.#...#...#.#.#.#.......#.#...#...........#.#...#
+#.###.#####.#.#####.###.#.#.###.#.###.#.###.###.#.#.#.#.###.#.#.#.#######.#.###########.#.#.#.#.#.#.###.###.#####.#.#.#####.#####.#####.#.#.#
+#.....#.....#.....#.....#...#...#.....#.......#.#.#.#.......#.#.#.......#.#...#...#...#.#.....#.#.#...#...#.#...#.#.#.#.....#...#.#.....#.#.#
+#.###.#.###.#####.#########.#.#######.#########.#.#.#########.#.###.###.#.###.#.#.#.#.#.#.#####.#.###.#.#.#.#.#.#.#.#.#.#####.#.#.#.#####.###
+#.#.......#.#...#.........#.#.....#.#...#.#...#.....#.#.....#.#.......#.#.#...#.#.#.#...#.#.#.......#.#.#.#.#.#...#.#.#.......#.#...#.......#
+#.###.###.#.#.#.#########.#######.#.###.#.#.#.#.#####.#.###.#.###.###.#.###.#####.#.#####.#.#.#.#####.###.#.#.#.###.#.#.###.###.#######.#.#.#
+#.#.......#...#.#.#...#...........#...#.#.#.#.#.#.....#.#.#.#.......#.#.........#.#...#.....#.#.#.....#...#.#...#.#.#.#.#...#.......#...#.#.#
+#.#.#.#########.#.#.#.#.#.#.###.#.###.#.#.#.#.#.###.###.#.#.#######.#.#########.#.###.#####.#.###.#####.###.###.#.#.#.###.#.#######.#.#.###.#
+#.#...#.......#.#...#.#.#.#...#.#.#...#...#.#.#.....#.....#.....#...#.#...#...#.....#...#...#...#...#...#.......#...#.#...#...#...#...#...#.#
+#.###.#.#.#####.#.###.#.###.###.#.#.#####.#.#.#######.###.#####.#.#.###.#.#.#.#####.###.###.###.###.#.###.#########.#.#.#####.#.#.#####.#.#.#
+#.....#.#...#...#...#.#.....#...#.#.......#.#.#.....#.....#.....#.#.....#...#.....#...#.#...#.....#.#.......#.....#.#.#.#...#.#.#.#...#.#...#
+#####.#.###.#.#######.#######.###.#########.#.#.###.###.#.#.#####.###############.###.#.#.#.#.#####.#########.###.#.#.#.#.#.#.#.#.#.#.#.###.#
+#.......#...#.......#.#.....#.....#.........#...#...#...#.#.....#.#.....#.........#...#...#.#.....#...........#.#.#.#.....#.#.#.#...#.#.#...#
+#.###.###.#########.#.#.###.#######.#######.#####.#.#.###.#.#.#.#.#.###.#.#################.#####.#########.#.#.#.#########.#.#.#####.#.#.###
+#.................#.#.#.#...#.....#.....#.........#...#.#...#.#...#...#.........................#.........#.#.#...........#.#.#...#...#.#.#.#
+#.#.#.#.###.#####.#.#.#.#.#.#.###.#.###.###.#.#########.#.###.#####.#.###.###.#.#.###################.#.###.#.###########.###.###.#.###.#.#.#
+#.#.#...#.....#...#.#...#.#...#.#.#...#.#...#...#.......#...#.#.....#...#...#.#...#...#...#.....#...#.#.#...#...#.......#...#...#.#...#.#...#
+#.###.#.#.###.#.###.#.###.#####.#.#####.#.#.###.#.#####.###.#.#.###.###.#.#.#.###.#.#.#.#.#.###.#.#.###.#.#####.#.###.#####.#.#.#.###.#.###.#
+#.....#.#.#...#...#.#...#.#.....#.....#...#.#...#.....#...#.....#...#.#.#.#...#...#.#...#...#.#.............................#.#.#...#.....#.#
+#.#####.#.###.###.#.#.#.#.#.#########.#.###.#.###.#####.###.#.#.#.#.#.#.#.#####.###.#########.#########.#########.#.###.#####.#.###.#.#.###.#
+#.#.....#...#.#...#.#...#.#.......#...#.#...#.#...#...#...#...#.#.#...#...#.....#.....................#.#.......#.#.....#...#.#.#...#.#.....#
+###.###.###.#.#.###.#.###.#.#####.#.###.#.###.#.###.#.###.###.#.#.#####.#.#####.#.#####.#.#####.#.#.###.#.#####.#.#.###.#.###.#.#.#####.#####
+#...#.#.....#...#...#.#...#.#...#...................#.....#...#.#.......#.....#.......#.#.....#...#.#...#.....#...#...#.#.#...#.#.....#.....#
+#.###.#.#######.#.###.#.###.#.###########.#.#.###.###.#####.#.###########.###.#######.#.###.#.###.###.#######.#######.#.#.#.###.#####.#.###.#
+#.#...................#.#.#.#.............................#.............#.#...#.....#.#...#.#.#...#...#.....#...#.....#.#.....#.#.....#...#.#
+#.#####.#########.#.#.#.#.#.#########.#.#.#.#.#.###.###.#.###.#########.#.#.###.###.#####.#.#.#####.#####.#.#.#.#.#####.#######.#.#####.#.#.#
+#S..................#...#.............#...#.......#.....#.......................#.........#.#.............#...#...#.............#.......#...#
+#############################################################################################################################################
diff --git a/2024/16/test2 b/2024/16/test2
@@ -0,0 +1,17 @@
+#################
+#...#...#...#..E#
+#.#.#.#.#.#.#.#.#
+#.#.#.#...#...#.#
+#.#.#.#.###.#.#.#
+#...#.#.#.....#.#
+#.#.#.#.#.#####.#
+#.#...#.#.#.....#
+#.#.#####.#.###.#
+#.#.#.......#...#
+#.#.###.#####.###
+#.#.#...#.....#.#
+#.#.#.#####.###.#
+#.#.#.........#.#
+#.#.#.#########.#
+#S#.............#
+#################
diff --git a/2024/template.cpp b/2024/template.cpp
@@ -2,6 +2,7 @@
#include <cstdint>
#include <iostream>
#include <map>
+#include <queue>
#include <ranges>
#include <set>
#include <sstream>
