aoc

commit 6bf92f2a2517f8eebddbdb139a877dcffd381edc
parent a0e775b0a4805a7c1af12c1a956cd9fd74c54b2c
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date:   Wed, 18 Dec 2024 06:38:01 +0100

Day 18 2024

Diffstat:
A
2024/18/Makefile
 | 
24
++++++++++++++++++++++++
A
2024/18/day18a.cpp
 | 
63
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
2024/18/day18b.cpp
 | 
74
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

3 files changed, 161 insertions(+), 0 deletions(-)
diff --git a/2024/18/Makefile b/2024/18/Makefile
@@ -0,0 +1,24 @@
+CC=g++ -std=c++20 -g -Wall
+
+a:
+	${CC} -o a.out day18a.cpp
+
+b:
+	${CC} -o b.out day18b.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/18/day18a.cpp b/2024/18/day18a.cpp
@@ -0,0 +1,63 @@
+#include <algorithm>
+#include <cstdint>
+#include <iostream>
+#include <map>
+#include <queue>
+#include <ranges>
+#include <set>
+#include <sstream>
+#include <string>
+#include <string_view>
+#include <vector>
+using namespace std;
+
+#define N 71
+#define S 1024
+
+bool b[N][N];
+
+class Qelem {
+public:
+	int d, x, y;
+	Qelem(int dis, int xx, int yy) : d{dis}, x{xx}, y{yy} {}
+	bool operator<(const Qelem& other) const { return d > other.d; }
+};
+
+
+int coord(int x, int y) {
+	return N*x+y;
+}
+
+bool inrange(int x, int y) {
+	return x >= 0 && x < N && y >= 0 && y < N;
+}
+
+int shortest_path(bool b[N][N]) {
+	vector<bool> vis(N*N);
+
+	priority_queue<Qelem> q;
+	q.push(Qelem(0, 0, 0));
+
+	while (!q.empty()) {
+		auto v = q.top();
+		q.pop();
+		if (!inrange(v.x, v.y) || b[v.x][v.y] || vis[coord(v.x, v.y)])
+			continue;
+		if (v.x == N-1 && v.y == N-1) return v.d;
+		vis[coord(v.x, v.y)] = true;
+		q.push(Qelem(v.d+1, v.x+1, v.y));
+		q.push(Qelem(v.d+1, v.x-1, v.y));
+		q.push(Qelem(v.d+1, v.x, v.y+1));
+		q.push(Qelem(v.d+1, v.x, v.y-1));
+	}
+	return -1;
+}
+
+int main() {
+	int x, y;
+	for (int i = 0; i < S && (cin >> x >> y); i++)
+		b[x][y] = true;
+
+	cout << shortest_path(b) << endl;
+	return 0;
+}
diff --git a/2024/18/day18b.cpp b/2024/18/day18b.cpp
@@ -0,0 +1,74 @@
+/*
+I just look the shortest path after every byte drop and stop when there
+is none.  This code is not very fast (~25 seconds on my laptop), but it
+took just a couple of minutes to modify part 1 to get this.
+*/
+
+#include <algorithm>
+#include <cstdint>
+#include <iostream>
+#include <map>
+#include <queue>
+#include <ranges>
+#include <set>
+#include <sstream>
+#include <string>
+#include <string_view>
+#include <vector>
+using namespace std;
+
+#define N 71
+
+bool b[N][N];
+
+class Qelem {
+public:
+	int d, x, y;
+	Qelem(int dis, int xx, int yy) : d{dis}, x{xx}, y{yy} {}
+	bool operator<(const Qelem& other) const { return d > other.d; }
+};
+
+
+int coord(int x, int y) {
+	return N*x+y;
+}
+
+bool inrange(int x, int y) {
+	return x >= 0 && x < N && y >= 0 && y < N;
+}
+
+int shortest_path() {
+	vector<bool> vis(N*N);
+
+	priority_queue<Qelem> q;
+	q.push(Qelem(0, 0, 0));
+
+	while (!q.empty()) {
+		auto v = q.top();
+		q.pop();
+		if (!inrange(v.x, v.y) || b[v.x][v.y] || vis[coord(v.x, v.y)])
+			continue;
+		if (v.x == N-1 && v.y == N-1) return v.d;
+		vis[coord(v.x, v.y)] = true;
+		q.push(Qelem(v.d+1, v.x+1, v.y));
+		q.push(Qelem(v.d+1, v.x-1, v.y));
+		q.push(Qelem(v.d+1, v.x, v.y+1));
+		q.push(Qelem(v.d+1, v.x, v.y-1));
+	}
+	return -1;
+}
+
+int main() {
+	int x, y;
+	while (cin >> x >> y) {
+		b[x][y] = true;
+		if (shortest_path() == -1) {
+			cout << x << "," << y << endl;
+			exit(0);
+		}
+	}
+
+	cout << "Not found" << endl;
+
+	return 0;
+}