commit b6ae7104a0902d039a5a49cabafe4ba08d9c17c1
parent cb7dbf3f56543193e07157543f486741477dd320
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Fri, 6 Dec 2024 07:20:50 +0100
Day 6 2024
Diffstat:
5 files changed, 522 insertions(+), 0 deletions(-)
diff --git a/2024/06/Makefile b/2024/06/Makefile
@@ -0,0 +1,24 @@
+CC=g++ -std=c++20 -g -Wall
+
+a:
+ ${CC} -o a.out day06a.cpp
+
+b:
+ ${CC} -o b.out day06b.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/06/b.out b/2024/06/b.out
Binary files differ.
diff --git a/2024/06/day06a.cpp b/2024/06/day06a.cpp
@@ -0,0 +1,152 @@
+#include <iostream>
+#include <algorithm>
+#include <string>
+#include <string_view>
+#include <vector>
+using namespace std;
+
+enum class Direction { U, 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);
+}
+
+Direction turn(Direction d) {
+ switch (d) {
+ case Direction::U:
+ return Direction::R;
+ case Direction::D:
+ return Direction::L;
+ case Direction::R:
+ return Direction::D;
+ case Direction::L:
+ return Direction::U;
+ }
+
+ return Direction::U;
+}
+
+class Board {
+public:
+ const char out_of_bound = '$';
+ int M, N;
+
+ Board(vector<string> &lines) {
+ N = lines.size();
+ M = 0;
+ for (string l : lines)
+ M = max(M, (int)l.size());
+ cells = new char[M * N];
+ for (int i = 0; i < N; i++)
+ for (int j = 0; j < M; j++)
+ cells[N*i + j] = j < (int)lines[i].size() ?
+ lines[i][j] : out_of_bound;
+ }
+
+ ~Board() {
+ delete []cells;
+ }
+
+ char operator[](pair<int, int> p) {
+ int c = coord(p);
+ return c == -1 ? out_of_bound : cells[c];
+ }
+
+ bool is_obstruction(pair<int, int> p) {
+ return (*this)[p] == '#';
+ }
+
+ bool is_visited(pair<int, int> p) {
+ return (*this)[p] == 'x';
+ }
+
+ void set_visited(pair<int, int> p) {
+ int c = coord(p);
+ cells[c] = 'x';
+ }
+
+private:
+ char *cells;
+
+ int coord(pair<int, int> p) {
+ auto [i, j] = p;
+ return i >= N || i < 0 || j >= M || j < 0 ? -1 : N*i + j;
+ }
+};
+
+Direction guard_direction(char c) {
+ switch (c) {
+ case '^':
+ return Direction::U;
+ case 'v':
+ return Direction::D;
+ case '>':
+ return Direction::R;
+ case '<':
+ return Direction::L;
+ }
+
+ return Direction::U;
+}
+
+pair<pair<int, int>, Direction> find_guard(Board &board) {
+ pair<int, int> p(0, 0);
+ for (p.first = 0; p.first < board.N; p.first++) {
+ for (p.second = 0; p.second < board.M; p.second++) {
+ if (board[p] != '.' && board[p] != '#') {
+ Direction d = guard_direction(board[p]);
+ return make_pair(p, d);
+ }
+ }
+ }
+
+ return make_pair(make_pair(-999, -999), Direction::U);
+}
+
+int main() {
+ string line;
+ vector<string> lines;
+ while (getline(cin, line))
+ lines.push_back(line);
+
+ Board board(lines);
+
+ int tot = 1;
+ auto [p, d] = find_guard(board);
+ board.set_visited(p);
+
+ while (true) {
+ auto q = step(p, d);
+ if (board[q] == board.out_of_bound)
+ break;
+ if (board.is_obstruction(q)) {
+ d = turn(d);
+ } else {
+ p = q;
+ if (!board.is_visited(p)) {
+ board.set_visited(p);
+ tot++;
+ }
+ }
+ }
+
+ cout << tot << endl;
+
+ return 0;
+}
diff --git a/2024/06/day06b.cpp b/2024/06/day06b.cpp
@@ -0,0 +1,216 @@
+/*
+This is quite inefficient, but it still gives the right answer in less
+than a minute (25 seconds on my old laptop).
+*/
+
+#include <iostream>
+#include <algorithm>
+#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);
+}
+
+Direction turn(Direction d) {
+ switch (d) {
+ case Direction::U:
+ return Direction::R;
+ case Direction::D:
+ return Direction::L;
+ case Direction::R:
+ return Direction::D;
+ case Direction::L:
+ return Direction::U;
+ }
+
+ return Direction::U;
+}
+
+class Board {
+public:
+ const char out_of_bound = '$';
+ int M, N;
+
+ Board(vector<string> &lines) {
+ N = lines.size();
+ M = 0;
+ for (string l : lines)
+ M = max(M, (int)l.size());
+
+ cells = new char[M * N];
+ visited = new int[M * N];
+ for (int i = 0; i < N; i++) {
+ for (int j = 0; j < M; j++) {
+ cells[N*i + j] = j < (int)lines[i].size() ?
+ lines[i][j] : out_of_bound;
+ visited[N*i + j] = 0;
+ }
+ }
+ }
+
+ ~Board() {
+ delete []cells;
+ delete []visited;
+ }
+
+ char operator[](pair<int, int> p) {
+ int c = coord(p);
+ return c == -1 ? out_of_bound : cells[c];
+ }
+
+ bool is_visited(pair<int, int> p, Direction d) {
+ return get_vmask(p) & (1 << d);
+ }
+
+ void set_visited(pair<int, int> p, Direction d) {
+ toggle_vmask(p, d);
+ }
+
+ void clear_visited() {
+ for (int i = 0; i < N; i++)
+ for (int j = 0; j < M; j++)
+ set_vmask(make_pair(i, j), 0);
+ }
+
+ bool is_obstruction(pair<int, int> p) {
+ return (*this)[p] == '#';
+ }
+
+ void set_obstruction(pair<int, int> p) {
+ set_cell(p, '#');
+ }
+
+ void set_clean(pair<int, int> p) {
+ set_cell(p, '.');
+ }
+
+private:
+ char *cells;
+ int *visited;
+
+ int coord(pair<int, int> p) {
+ auto [i, j] = p;
+ return i >= N || i < 0 || j >= M || j < 0 ? -1 : N*i + j;
+ }
+
+ void set_cell(pair<int, int> p, char c) {
+ int i = coord(p);
+ cells[i] = c;
+ }
+
+ int get_vmask(pair<int, int> p) {
+ int i = coord(p);
+ return visited[i];
+ }
+
+ void set_vmask(pair<int, int> p, int x) {
+ int i = coord(p);
+ visited[i] = x;
+ }
+
+ void toggle_vmask(pair<int, int> p, Direction d) {
+ int i = coord(p);
+ visited[i] ^= 1 << d;
+ }
+};
+
+Direction guard_direction(char c) {
+ switch (c) {
+ case '^':
+ return Direction::U;
+ case 'v':
+ return Direction::D;
+ case '>':
+ return Direction::R;
+ case '<':
+ return Direction::L;
+ }
+
+ return Direction::U;
+}
+
+pair<pair<int, int>, Direction> find_guard(Board &board) {
+ pair<int, int> p(0, 0);
+ for (p.first = 0; p.first < board.N; p.first++) {
+ for (p.second = 0; p.second < board.M; p.second++) {
+ if (board[p] != '.' && board[p] != '#') {
+ Direction d = guard_direction(board[p]);
+ return make_pair(p, d);
+ }
+ }
+ }
+
+ return make_pair(make_pair(-999, -999), Direction::U);
+}
+
+bool isloop(pair<int, int> i, pair<int, int> p, Direction d, Board &board) {
+ bool ret = false;
+
+ board.set_obstruction(i);
+
+ while (true) {
+ auto q = step(p, d);
+ if (board.is_visited(p, d)) {
+ ret = true;
+ break;
+ }
+ board.set_visited(p, d);
+
+ if (board[q] == board.out_of_bound)
+ break;
+
+ if (board.is_obstruction(q)) {
+ d = turn(d);
+ } else {
+ p = q;
+ }
+ }
+
+ board.clear_visited();
+ board.set_clean(i);
+
+ return ret;
+}
+
+int main() {
+ string line;
+ vector<string> lines;
+ while (getline(cin, line))
+ lines.push_back(line);
+
+ Board board(lines);
+
+ int tot = 0;
+ auto [p, d] = find_guard(board);
+
+ 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] == '.')
+ tot += isloop(i, p, d, board);
+
+ cout << tot << endl;
+
+ return 0;
+}
diff --git a/2024/06/input b/2024/06/input
@@ -0,0 +1,130 @@
+#.............#.#...........................................................#..........#...........................#..........#...
+............#......................#.......#..#.........#...................##....................................................
+..............#...........#..#.......#.........#.#...........................#................................#......#............
+.....#......................................#......#..#...................#....................#......................#...........
+...#............................#................................#................................................................
+..........#..................#.....#......................................................#.......................................
+..#........#.......#.#...............................................................#......#.................................#...
+.#....#................#................#.....#...................#...............................................#..#............
+.......................................................................................#...#.#....#........##......#........#.#.##
+............................................#.................#.....................#..........................#..................
+....#..........##......................#.................................................................................#........
+......#.............##.........#.......#.........#.......#.............#...#.......#..............................................
+.#............................................................................#..........#....#...................................
+...#..#....#..............................#...........................................................................#...........
+.............#....................................................................................................................
+................................#..................##...................................#...............................#......#..
+..........#.........#.................#..........###...........................................#............#...#.................
+.............#....................................#.......#.#.#............#............................................#.........
+......#.#..............................................................................................#.........................#
+...#...#.........#.........#..#......#................##.................#........................................................
+.................................#......................#........#................#........................#......................
+.......................##..............#................#................#..............................#.........................
+.......#...#.....#.....##........................#..................##.....#......................................................
+.............................................#...........................#..........................................#.....#.......
+.........................#...............#....#..............#.......#...............#.#.................#.................#......
+...........................................................#....#..................................#..............................
+..........................#.................................................#............................##....#..................
+.................#...#.........................................................#........................#.....#..#................
+.........................#....#................................................#...#.....................#....#...........#.......
+................................................##.......#.#....................................#.......##........................
+..........##...#.......................#....#..#....................#........................#....................................
+#......#.......................#............#.....................................................................#...............
+.......#.......#...#..#..........#.......................................#.............#......#...................................
+...............#............#..................#.................................................................................#
+.......#...........#.......................##.....#.........#...........#...................#......#.........#.............##....#
+...................#.........................#......#..........................................#..........#.........#......#......
+.....#............#..............#...#......#....................#.............#..................................................
+................................................#........#.....#...................#.....................................#.....#..
+......................#.#...##......................##...............................................#.................#..........
+#...................#.........................#...........#.....#................#.....................#...................#......
+....#................#.....#.............#.....................................#....#...#.................................#.......
+.........#.....................................................................................................#.#.......#........
+.........#..........##..............................#............................#.#.............................#................
+#....#.#..............................................##...#...#...............#.............#....................................
+........#..#.#...................#.......................................................................#.............#..#.#...#.
+.................................................................................................................#.......#........
+............................................#..#...............##........#..........#.......................................#....#
+........#...........................#............................#.....#........................#..........#...#..........#.......
+.#...........#...................................................#...........................................#................#.#.
+............#...............................#........#...........#..........#...........#.#..............#........................
+...............................................................................##.#................#..............................
+.#.......................#.#...........#..................................#.......................................................
+..#..............................................##................#.......#....#..............#.....................#...#........
+...................#.....#................................................#..........#.........#.........#.....................#..
+........#................#................................................................................#......#................
+...................#...#....#.........................#.........................#....................#..........................#.
+.................#.......................................................#................................................#.......
+..#...........................##.#.............#..#............................................#.......................#.#........
+..#......#.........................................................................#.......................#......................
+...........................................................................................................#............#......#..
+............................................................^..........................................#..........#...............
+..#.........#....................#..........................................#........#.........................................#..
+........#...............#....#.............#......#.........................................................................#.....
+.........#......#.....#..............#...........................................................#..............#.................
+.........#...................................................#...###...........#.......#.##.......................................
+.....................##.................#.........##.....................#................#................#.........#............
+.......................................................................#..............#..............#.................#..........
+.##.........#..........................................................................#....................................#.....
+.........................#.............................#........................................................................#.
+........#.............................................#......#....#.....................................#....................#....
+........#...#..............................................................................#.........#............................
+..............................#................................#..........#..............#..................................#.....
+........##..#...................................#................................#.................#.........#......#..#........#.
+..................#......#...................................................................#....................................
+..........#.............#..............#........#............#...............#..#..........#..............#.#...#............#....
+............................##....#..............#......................................................................#.........
+...............................................#.....#...........#.....##...............#..#......................................
+.........................#.......#...............................#...........#.........#...........#....#.........................
+.#............#...#...............#..............................................................#..........................#....#
+#...........#......................................................#.............................#......#.........................
+..................................................#....#...............#.........................#................................
+................................................#..........................#.......#..............................#....##.......#.
+........#......#..#............#................#............................#......#.##.........#....................#..#........
+.......................................................#..#.#....................#..#......................................#......
+.....................#.......................................................................#............#.......................
+.....................##........................#...................#.....................#........................................
+..........................#...........................................................................................#...........
+..#..........#...................#..............##..#.....................#...................#..............#...........#........
+#................................#....##......#.............#..............#.......................#.........#...........#........
+..................#................#...............................#.....#..........#................#..............#.............
+................#.#.........#.....##...............................................................#..............#...............
+..#...............................................................................................#...............................
+..........#.................#...........#.......#.........................#...#.......#...........................................
+..##....#......................................#.#.......................................#.................#......................
+.......................#..#...#.##......................................................................#.........#...#...........
+...............#.........#..............#.....................................................#...................#...............
+......#.................#............#......#...................#..#.........................#........................#........#..
+......................................................................#...........................#........#......................
+..........#..........#........................#.............##....................................................................
+....#................................................#.......................#................#...............#...................
+.................#....................................................#......#....................................................
+.#........#.......................................................................................................................
+......##..................#....#......#.................#....................#.....................#..#...........#...............
+#...#...#...#..............#........#.......................#.#..........#...............................#......#.................
+#...#...................#.............#........#..........#...............................................................#...#...
+..#................................#...#.........................#...................#......#.....................................
+...#...###..........#............#...............................................................#..........#.....................
+............#..............#.......#.....#..........#.....#.........................................................#............#
+..#......................#..#...#................................#......#.......#.....#..................#.........#..............
+....##......#.......................................................#..............................................#..............
+...............................#.....#....#.................................................#.......#............#................
+..........#....#......................#........#..........................#......#................................................
+......#.............................#...........#..................#...........................#................................#.
+...........................##..........................................#.....#.#.....................#................#...........
+..#..............#.........................................................#........................#.........#.................#.
+#.....#.....#......................#....................#........................................#...........#...........#......#.
+.......................................#..#................................#.........#.......#..#.....#..........................#
+..........#..............##...............#..........................................................#......#......#......#....#..
+.............#..............#..#......#........#..#......##.......................#...........#.......#...........................
+......................#.......................................#.......#..#.....................................#.........#...##...
+...........................#...........................#......#....#.............................#.............................#..
+..................#............................#....#........##.........................#..............#.............#............
+.......#....................#.....#........#.......#.#...#...............#.....#.#.........................#.......#.#............
+.....#.........#.......#..........#.................#..#...#..................................................##..................
+................#........................................................#........................................................
+....##......#........#..................#.........................#...................................#...#...................#...
+..............#....................#.......#.......................#.............#......#..............#..........................
+...........................#..............#.....#............#.....................#........#....#.......................#........
+........#..##................#.....#.#..............#..............................#........................#.........#...........
+.........................................................#...........................##..........#........#.##....................
