blob: e902a43d31dcc5c777a63f5ce6606ac6cea173e8 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
|
#include <filesystem>
#include <fstream>
#include <functional>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
using namespace std;
namespace {
vector<string>
read_file(const filesystem::path& filename)
{
ifstream file{ filename };
vector<string> grid;
for ( string line; getline(file, line); ) {
grid.emplace_back(line);
}
return grid;
}
void
part1(const vector<string>& grid)
{
set<size_t> curr;
curr.insert(grid[0].find('S'));
int count = 0;
for ( size_t i = 1; i < grid.size(); ++i ) {
const auto& row = grid[i];
auto next = curr;
for ( const auto pos: curr ) {
if ( row[pos] == '^' ) {
next.erase(pos);
next.insert(pos - 1);
next.insert(pos + 1);
++count;
}
}
curr = next;
}
cout << "Part 1: " << count << '\n';
}
void
part2(const vector<string>& grid)
{
using Pos = tuple<size_t, size_t>;
map<Pos, long> cache;
function<long(const Pos&)> walk = [&](const Pos& pos) {
if ( cache.contains(pos) ) {
return cache.at(pos);
}
const auto [col, row] = pos;
if ( row == grid.size() ) {
return (cache[pos] = 1L);
}
if ( grid[row][col] == '^' ) {
const auto left = walk({ col - 1, row });
const auto right = walk({ col + 1, row });
return (cache[pos] = left + right);
}
return (cache[pos] = walk({ col, row + 1 }));
};
const auto col = grid[0].find('S');
cout << "Part 2: " << walk(Pos{ col, 0 }) << '\n';
}
} // namespace
int
main()
{
auto grid = read_file("data/day07.txt");
part1(grid);
part2(grid);
}
|
