From ecb8bdb0b63536916a3a3d55fd4ebbf7aeb21997 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Fri, 20 Dec 2024 07:06:29 +0100 Subject: Day 20 2024 --- 2024/20/Makefile | 11 ++++++ 2024/20/day20a.cpp | 108 ++++++++++++++++++++++++++++++++++++++++++++++++++ 2024/20/day20b.cpp | 114 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 233 insertions(+) create mode 100644 2024/20/Makefile create mode 100644 2024/20/day20a.cpp create mode 100644 2024/20/day20b.cpp (limited to '2024') diff --git a/2024/20/Makefile b/2024/20/Makefile new file mode 100644 index 0000000..0fd3d80 --- /dev/null +++ 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 new file mode 100644 index 0000000..8837de7 --- /dev/null +++ b/2024/20/day20a.cpp @@ -0,0 +1,108 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +using namespace std; + +class Map { +public: + int N, M, L; + int *cell; + + Map(const vector& 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> 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 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 new file mode 100644 index 0000000..dc55cc0 --- /dev/null +++ b/2024/20/day20b.cpp @@ -0,0 +1,114 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +using namespace std; + +class Map { +public: + int N, M, L; + int *cell; + + Map(const vector& 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> 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 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; +} -- cgit v1.3