blob: 659251894fd132c1f93603882c9ceb21476e6fee (
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
|
#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 };
return { istream_iterator<string>{ file }, {} };
}
void
part1(const vector<string>& grid)
{
set<size_t> curr{ 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 col: curr ) {
if ( row[col] == '^' ) {
next.erase(col);
next.insert({ col - 1, col + 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 }));
};
cout << "Part 2: " << walk(Pos{ grid[0].find('S'), 0 }) << '\n';
}
} // namespace
int
main()
{
auto grid = read_file("data/day07.txt");
part1(grid);
part2(grid);
}
|
