aoc

commit 6cee2c54045d253dc14c808f1e4f25765a675a56
parent 9a1f073f8e33e8b0d6c97332f51161683cfc6e58
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date:   Tue, 10 Dec 2024 06:13:42 +0100

Day 10 2024

Diffstat:
A
2024/10/Makefile
 | 
24
++++++++++++++++++++++++
A
2024/10/day10a.cpp
 | 
113
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
2024/10/day10b.cpp
 | 
112
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

3 files changed, 249 insertions(+), 0 deletions(-)
diff --git a/2024/10/Makefile b/2024/10/Makefile
@@ -0,0 +1,24 @@
+CC=g++ -std=c++20 -g -Wall
+
+a:
+	${CC} -o a.out day10a.cpp
+
+b:
+	${CC} -o b.out day10b.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/10/day10a.cpp b/2024/10/day10a.cpp
@@ -0,0 +1,113 @@
+#include <iostream>
+#include <algorithm>
+#include <set>
+#include <string>
+#include <string_view>
+#include <vector>
+using namespace std;
+
+enum Direction { U = 0, D, R, L };
+Direction all_directions[] = {
+	Direction::U, Direction::D, Direction::R, Direction::L,
+};
+
+pair<int, int> step(pair<int, int> p, Direction d) {
+	auto [i, j] = p;
+
+	switch (d) {
+	case Direction::U:
+		return make_pair(i-1, j);
+	case Direction::D:
+		return make_pair(i+1, j);
+	case Direction::R:
+		return make_pair(i, j+1);
+	case Direction::L:
+		return make_pair(i, j-1);
+	}
+
+	return make_pair(-999,-999);
+}
+
+class Board {
+public:
+	const int out_of_bound = -1;
+	int M, N;
+
+	Board(vector<string> &lines) {
+		N = lines.size();
+		M = 0;
+		for (string l : lines)
+			M = max(M, (int)l.size());
+
+		cells = new int[M * N];
+		for (int i = 0; i < N; i++)
+			for (int j = 0; j < M; j++)
+				cells[N*i + j] = lines[i][j] - '0';
+	}
+
+	~Board() {
+		delete []cells;
+	}
+
+	int operator[](pair<int, int> p) {
+		int c = coord(p);
+		return c == -1 ? out_of_bound : cells[c];
+	}
+
+private:
+	int *cells;
+
+	int coord(pair<int, int> p) {
+		auto [i, j] = p;
+		return i >= N || i < 0 || j >= M || j < 0 ? -1 : N*i + j;
+	}
+};
+
+void reachable9(pair<int, int> p, Board& board, set<pair<int, int>>& s) {
+	if (board[p] == 9) {
+		s.insert(p);
+		return;
+	}
+
+	auto q = step(p, Direction::U);
+	if (board[q] == board[p]+1)
+		reachable9(q, board, s);
+
+	q = step(p, Direction::D);
+	if (board[q] == board[p]+1)
+		reachable9(q, board, s);
+
+	q = step(p, Direction::R);
+	if (board[q] == board[p]+1)
+		reachable9(q, board, s);
+
+	q = step(p, Direction::L);
+	if (board[q] == board[p]+1)
+		reachable9(q, board, s);
+}
+
+int main() {
+	string line;
+	vector<string> lines;
+	while (getline(cin, line))
+		lines.push_back(line);
+
+	Board board(lines);
+
+	int tot = 0;
+
+	pair i(0, 0);
+	for (i.first = 0; i.first < board.N; i.first++) {
+		for (i.second = 0; i.second < board.M; i.second++) {
+			if (board[i] == 0) {
+				set<pair<int, int>> s;
+				reachable9(i, board, s);
+				tot += s.size();
+			}
+		}
+	}
+
+	cout << tot << endl;
+
+	return 0;
+}
diff --git a/2024/10/day10b.cpp b/2024/10/day10b.cpp
@@ -0,0 +1,112 @@
+#include <iostream>
+#include <algorithm>
+#include <set>
+#include <string>
+#include <string_view>
+#include <vector>
+using namespace std;
+
+enum Direction { U = 0, D, R, L };
+Direction all_directions[] = {
+	Direction::U, Direction::D, Direction::R, Direction::L,
+};
+
+pair<int, int> step(pair<int, int> p, Direction d) {
+	auto [i, j] = p;
+
+	switch (d) {
+	case Direction::U:
+		return make_pair(i-1, j);
+	case Direction::D:
+		return make_pair(i+1, j);
+	case Direction::R:
+		return make_pair(i, j+1);
+	case Direction::L:
+		return make_pair(i, j-1);
+	}
+
+	return make_pair(-999,-999);
+}
+
+class Board {
+public:
+	const int out_of_bound = -1;
+	int M, N;
+
+	Board(vector<string> &lines) {
+		N = lines.size();
+		M = 0;
+		for (string l : lines)
+			M = max(M, (int)l.size());
+
+		cells = new int[M * N];
+		for (int i = 0; i < N; i++)
+			for (int j = 0; j < M; j++)
+				cells[N*i + j] = lines[i][j] - '0';
+	}
+
+	~Board() {
+		delete []cells;
+	}
+
+	int operator[](pair<int, int> p) {
+		int c = coord(p);
+		return c == -1 ? out_of_bound : cells[c];
+	}
+
+private:
+	int *cells;
+
+	int coord(pair<int, int> p) {
+		auto [i, j] = p;
+		return i >= N || i < 0 || j >= M || j < 0 ? -1 : N*i + j;
+	}
+};
+
+int reachable9(pair<int, int> p, Board& board) {
+	if (board[p] == 9)
+		return 1;
+
+	int ret = 0;
+	auto q = step(p, Direction::U);
+	if (board[q] == board[p]+1)
+		ret += reachable9(q, board);
+
+	q = step(p, Direction::D);
+	if (board[q] == board[p]+1)
+		ret += reachable9(q, board);
+
+	q = step(p, Direction::R);
+	if (board[q] == board[p]+1)
+		ret += reachable9(q, board);
+
+	q = step(p, Direction::L);
+	if (board[q] == board[p]+1)
+		ret += reachable9(q, board);
+
+	return ret;
+}
+
+int main() {
+	string line;
+	vector<string> lines;
+	while (getline(cin, line))
+		lines.push_back(line);
+
+	Board board(lines);
+
+	int tot = 0;
+
+	pair i(0, 0);
+	for (i.first = 0; i.first < board.N; i.first++) {
+		for (i.second = 0; i.second < board.M; i.second++) {
+			if (board[i] == 0) {
+				tot += reachable9(i, board);
+			}
+		}
+	}
+
+	cout << tot << endl;
+
+	return 0;
+}