aoc

commit ecb8bdb0b63536916a3a3d55fd4ebbf7aeb21997
parent 3c8331701f9f77c28847d678b935d5efb9a5d575
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date:   Fri, 20 Dec 2024 07:06:29 +0100

Day 20 2024

Diffstat:
A
2024/20/Makefile
 | 
11
+++++++++++
A
2024/20/day20a.cpp
 | 
108
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
2024/20/day20b.cpp
 | 
114
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

3 files changed, 233 insertions(+), 0 deletions(-)
diff --git a/2024/20/Makefile b/2024/20/Makefile
@@ -0,0 +1,11 @@
+CC=g++ -std=c++20 -g -Wall
+
+a:
+	${CC} -o a.out day20a.cpp
+	./a.out
+
+b:
+	${CC} -o b.out day20b.cpp
+	./b.out
+
+.PHONY: a b
diff --git a/2024/20/day20a.cpp b/2024/20/day20a.cpp
@@ -0,0 +1,108 @@
+#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;
+
+class Map {
+public:
+	int N, M, L;
+	int *cell;
+
+	Map(const vector<string>& lines) 
+	    : N{(int)lines.size()}, M{(int)lines[0].size()}, cell{new int[M*N]}
+	{
+		for (int i = 0; i < N; i++) {
+			for (int j = 0; j < N; j++) {
+				cell[M*i+j] = lines[i][j] == '#' ? -1 : 0;
+				if (lines[i][j] == 'S') {
+					is = i;
+					js = j;
+				}
+				if (lines[i][j] == 'E') {
+					ie = i;
+					je = j;
+				}
+			}
+		}
+		findpath();
+	}
+
+	~Map() {
+		delete[] cell;
+	}
+
+	int& operator()(int i, int j) {
+		if (i < 0 || i >= N || j < 0 || j >= M)
+			return out_of_bound;
+		return cell[M*i+j];
+	}
+
+	const int& operator()(int i, int j) const {
+		if (i < 0 || i >= N || j < 0 || j >= M)
+			return out_of_bound;
+		return cell[M*i+j];
+	}
+
+	int cheat(int i, int j) {
+		if ((*this)(i, j) != -1)
+			return -1;
+		if ((*this)(i+1, j) >= 0 && (*this)(i-1, j) >= 0)
+			return abs((*this)(i+1, j) - (*this)(i-1, j)) - 2;
+		if ((*this)(i, j+1) >= 0 && (*this)(i, j-1) >= 0)
+			return abs((*this)(i, j+1) - (*this)(i, j-1)) - 2;
+		return -1;
+	}
+private:
+	int is, js, ie, je;
+	int out_of_bound = -1;
+	vector<pair<int, int>> directions {{0,1}, {0,-1}, {1,0}, {-1,0}};
+
+	void findpath() {
+		int i, j, k;
+		for (i = is, j = js, k = 1; i != ie || j != je; step(i, j, k))
+			(*this)(i, j) = k;
+		(*this)(ie, je) = k;
+		L = k-1;
+	}
+
+	void step(int& i, int& j, int& k) {
+		k++;
+		for (auto p : directions) {
+			if ((*this)(i+p.first, j+p.second) == 0) {
+				i = i+p.first;
+				j = j+p.second;
+				return;
+			}
+		}
+		cout << "Error! at " << i << ", " << j << endl;
+	}
+};
+
+int main() {
+	string line;
+	vector<string> lines;
+	while (getline(cin, line))
+		lines.push_back(line);
+	Map m(lines);
+
+	int count = 0;
+	for (int i = 0; i < m.N; i++) {
+		for (int j = 0; j < m.M; j++) {
+			int c = m.cheat(i, j);
+			if (c >= 100)
+				count++;
+		}
+	}
+
+	cout << count << endl;
+
+	return 0;
+}
diff --git a/2024/20/day20b.cpp b/2024/20/day20b.cpp
@@ -0,0 +1,114 @@
+#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;
+
+class Map {
+public:
+	int N, M, L;
+	int *cell;
+
+	Map(const vector<string>& lines) 
+	    : N{(int)lines.size()}, M{(int)lines[0].size()}, cell{new int[M*N]}
+	{
+		for (int i = 0; i < N; i++) {
+			for (int j = 0; j < N; j++) {
+				cell[M*i+j] = lines[i][j] == '#' ? -1 : 0;
+				if (lines[i][j] == 'S') {
+					is = i;
+					js = j;
+				}
+				if (lines[i][j] == 'E') {
+					ie = i;
+					je = j;
+				}
+			}
+		}
+		findpath();
+	}
+
+	~Map() {
+		delete[] cell;
+	}
+
+	int& operator()(int i, int j) {
+		if (i < 0 || i >= N || j < 0 || j >= M)
+			return out_of_bound;
+		return cell[M*i+j];
+	}
+
+	const int& operator()(int i, int j) const {
+		if (i < 0 || i >= N || j < 0 || j >= M)
+			return out_of_bound;
+		return cell[M*i+j];
+	}
+
+	int cheats(int x, int y, int k, int p) {
+		// Cheats <= p starting at x, y saving at least k picoseconds
+
+		int count = 0;
+		for (int i = 0; i < N; i++)
+			for (int j = 0; j < M; j++)
+				if ((*this)(i, j) != -1)
+					count += saved(i, j, x, y, p) >= k;
+
+		return count;
+	}
+private:
+	int is, js, ie, je;
+	int out_of_bound = -1;
+	vector<pair<int, int>> directions {{0,1}, {0,-1}, {1,0}, {-1,0}};
+
+	void findpath() {
+		int i, j, k;
+		for (i = is, j = js, k = 1; i != ie || j != je; step(i, j, k))
+			(*this)(i, j) = k;
+		(*this)(ie, je) = k;
+		L = k-1;
+	}
+
+	void step(int& i, int& j, int& k) {
+		k++;
+		for (auto p : directions) {
+			if ((*this)(i+p.first, j+p.second) == 0) {
+				i = i+p.first;
+				j = j+p.second;
+				return;
+			}
+		}
+		cout << "Error! at " << i << ", " << j << endl;
+	}
+
+	int saved(int i, int j, int x, int y, int p) {
+		if (int d = abs(i-x) + abs(j-y); d > p)
+			return 0;
+		else
+			return abs((*this)(i, j) - (*this)(x, y)) - d;
+	}
+};
+
+int main() {
+	string line;
+	vector<string> lines;
+	while (getline(cin, line))
+		lines.push_back(line);
+	Map m(lines);
+
+	int count = 0;
+	for (int i = 0; i < m.N; i++)
+		for (int j = 0; j < m.M; j++)
+			if (m(i, j) != -1)
+				count += m.cheats(i, j, 100, 20);
+
+	cout << count / 2 << endl;
+
+	return 0;
+}