aoc

commit d92b565634adb2737af9b0d1f8b243da0c206335
parent 104f717c4e86bb537db84a8e9e4fc4c2272dece3
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
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
2024/10/input
 | 
41
+++++++++++++++++++++++++++++++++++++++++

4 files changed, 290 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;
+}
diff --git a/2024/10/input b/2024/10/input
@@ -0,0 +1,41 @@
+21056789894321015012980123498787601045687
+32346543765601156703474544567896012138796
+10107632659892349821563678989345643029655
+23218101256781015430412101071234754910544
+14569870345432016321003012560109867801033
+05678963256789127879854303456078105932122
+18723450109898038910765210010563254541001
+69011201298788945125898998323454569679852
+78760345345654876034787677401235378089760
+89456896012503876965014586512765432123601
+32387987003412965872123298703890101984512
+01291876121101234989456107654965278854603
+00180145030980325678327890217874369763254
+14343232145671013454310691307893454610169
+23432165430110302169234582456732108905678
+96547078923231231078105673454321097214523
+87678432214348940987017894765870986341014
+96589541009857654320123765891963475498765
+01434630111766789010432143210452560167876
+32345721210951999016549054789301001456965
+21076890129810878321678945643219812332109
+78789001234723765430321238756106734323458
+09654160345654210389210109987005125010767
+12323271657601345678780125678014056541893
+25414987798542343456690034329123987932012
+56905677810439652987501145016510345801101
+67856298923128721987432156987421256789210
+22347107654098910876543087870330107654301
+11298231012347654305678898981278798987652
+00109545691056763211219767874569678690343
+12065456783345894320105656913450569541289
+43874321092132101899234541002321256632176
+54930010561001234788765432211056746789045
+67821123472390545654123101347849839874330
+78934010589487698763034567456931028765221
+67785697696590101672105698741022210540100
+58696788787781234589789789012013307632101
+49545459810170301075674654323454458989032
+30432365923965432165463210498569567976543
+21021876854876523678354112347678678875301
+30010966763987014589210001456565589765432