aboutsummaryrefslogtreecommitdiff
path: root/src/day23.cpp
diff options
context:
space:
mode:
authorThomas Schmucker <ts@its1.de>2024-01-03 23:35:54 +0100
committerThomas Schmucker <ts@its1.de>2024-01-03 23:35:54 +0100
commit56e890cec0a28c0a485212ccebfaf774235a79a2 (patch)
treed9c6241a1aa247e06ab5ba2f6f11967b77d458ec /src/day23.cpp
parente9a1cb0441d137d7a26cb303b7e72d3424b7392d (diff)
downloadadvent-of-code-56e890cec0a28c0a485212ccebfaf774235a79a2.tar.gz
advent-of-code-56e890cec0a28c0a485212ccebfaf774235a79a2.tar.bz2
advent-of-code-56e890cec0a28c0a485212ccebfaf774235a79a2.zip
prepare for more puzzles ... :)
Diffstat (limited to 'src/day23.cpp')
-rw-r--r--src/day23.cpp152
1 files changed, 0 insertions, 152 deletions
diff --git a/src/day23.cpp b/src/day23.cpp
deleted file mode 100644
index d8c20d3..0000000
--- a/src/day23.cpp
+++ /dev/null
@@ -1,152 +0,0 @@
1#include <algorithm>
2#include <array>
3#include <fstream>
4#include <functional>
5#include <iostream>
6#include <iterator>
7#include <map>
8#include <queue>
9#include <set>
10#include <string>
11#include <vector>
12using namespace std;
13
14using position_t = tuple<size_t, size_t>;
15
16vector<string>
17read_file(string_view filename)
18{
19 fstream input{ filename };
20 vector<string> data;
21
22 for ( string line; getline(input, line); ) {
23 data.emplace_back(line);
24 }
25
26 return data;
27}
28
29set<position_t>
30get_neighbours(const vector<string>& maze, position_t possition)
31{
32 static const position_t deltas[] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } }; // NOLINT
33
34 static const auto SYM_UP = '^';
35 static const auto SYM_RIGHT = '>';
36 static const auto SYM_DOWN = 'v';
37 static const auto SYM_LEFT = '<';
38
39 const auto [row, col] = possition;
40
41 switch ( maze[row][col] ) {
42 case SYM_UP:
43 return { make_tuple(row - 1, col) };
44 case SYM_RIGHT:
45 return { make_tuple(row, col + 1) };
46 case SYM_DOWN:
47 return { make_tuple(row + 1, col) };
48 case SYM_LEFT:
49 return { make_tuple(row, col - 1) };
50 }
51
52 set<position_t> positions;
53
54 for ( const auto& delta: deltas ) {
55 const auto new_row = row + get<0>(delta);
56 const auto new_col = col + get<1>(delta);
57
58 if ( new_row >= maze.size() || new_col >= maze[0].size() ) {
59 continue;
60 }
61
62 if ( maze[new_row][new_col] == '#' ) {
63 continue;
64 }
65
66 if ( new_row < row && maze[new_row][new_col] == SYM_DOWN ) {
67 continue;
68 }
69 if ( new_row > row && maze[new_row][new_col] == SYM_UP ) {
70 continue;
71 }
72 if ( new_col < col && maze[new_row][new_col] == SYM_RIGHT ) {
73 continue;
74 }
75 if ( new_col > col && maze[new_row][new_col] == SYM_LEFT ) {
76 continue;
77 }
78
79 positions.emplace(new_row, new_col);
80 }
81
82 return positions;
83}
84
85set<position_t>
86get_neighbours2(const vector<string>& maze, position_t possition)
87{
88 static const position_t deltas[] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } }; // NOLINT
89
90 const auto [row, col] = possition;
91
92 set<position_t> positions;
93
94 for ( const auto& delta: deltas ) {
95 const auto new_row = row + get<0>(delta);
96 const auto new_col = col + get<1>(delta);
97
98 if ( new_row >= maze.size() || new_col >= maze[0].size() ) {
99 continue;
100 }
101
102 if ( maze[new_row][new_col] == '#' ) {
103 continue;
104 }
105
106 positions.emplace(new_row, new_col);
107 }
108
109 return positions;
110}
111
112void
113solve(const vector<string>& maze, function<set<position_t>(const vector<string>&, position_t)> neighbours)
114{
115 const position_t start = { 0, maze[0].find('.') };
116 const position_t end = { maze.size() - 1, maze[maze.size() - 1].find('.') };
117
118 vector<vector<bool>> visited(maze.size(), vector<bool>(maze[0].size()));
119
120 function<long(position_t, long)> find_longest_path = [&](position_t position, long current) -> long {
121 const auto [row, col] = position;
122
123 if ( visited[row][col] ) {
124 return 0;
125 }
126
127 if ( position == end ) {
128 return current;
129 }
130
131 long value = 0;
132
133 visited[row][col] = true;
134 for ( const auto& neighbour: neighbours(maze, position) ) {
135 value = max(value, find_longest_path(neighbour, current + 1));
136 }
137 visited[row][col] = false;
138
139 return value;
140 };
141
142 auto value = find_longest_path(start, 0);
143 cout << value << endl;
144}
145
146int
147main()
148{
149 const auto maze = read_file("data/day23.txt");
150 solve(maze, get_neighbours);
151 solve(maze, get_neighbours2);
152}