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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
|
#include <array>
#include <fstream>
#include <functional>
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;
using puzzle_t = vector<vector<int>>;
puzzle_t
read_file(string_view filename)
{
fstream input{ filename };
puzzle_t data;
for ( string line; getline(input, line); ) {
puzzle_t::value_type numbers;
for ( auto chr: line ) {
numbers.emplace_back(chr - '0');
}
data.emplace_back(numbers);
}
return data;
}
int
solve(const puzzle_t& puzzle, size_t min_steps, size_t max_steps)
{
using pos_t = tuple<size_t, size_t>;
using dir_t = tuple<size_t, size_t>;
using entry = tuple<int, pos_t, dir_t>;
static const array<pos_t, 4> directions = {
make_tuple(0, 1),
make_tuple(0, -1),
make_tuple(1, 0),
make_tuple(-1, 0)
};
priority_queue<entry, vector<entry>, greater<>> queue;
set<tuple<pos_t, dir_t>> seen;
const pos_t target = { puzzle.size() - 1, puzzle[0].size() - 1 };
queue.emplace(0, pos_t(0, 0), dir_t(0, 0));
while ( !queue.empty() ) {
const auto [heat, pos, dir] = queue.top();
queue.pop();
if ( pos == target ) {
return heat;
}
const auto key = make_tuple(pos, dir);
if ( seen.contains(key) ) {
continue;
}
seen.emplace(key);
const dir_t inv_dir = { -get<0>(dir), -get<1>(dir) };
for ( const auto& next_dir: directions ) {
if ( next_dir == dir || next_dir == inv_dir ) {
continue;
}
auto heat_so_far = heat;
for ( size_t steps = 1; steps <= max_steps; ++steps ) {
const pos_t next_pos = { get<0>(pos) + get<0>(next_dir) * steps,
get<1>(pos) + get<1>(next_dir) * steps };
if ( get<0>(next_pos) >= puzzle.size() || get<1>(next_pos) >= puzzle[0].size() ) {
continue;
}
heat_so_far += puzzle[get<0>(next_pos)][get<1>(next_pos)];
if ( steps >= min_steps ) {
queue.emplace(heat_so_far, next_pos, next_dir);
}
}
}
}
return -1;
}
void
part1(const puzzle_t& puzzle)
{
cout << solve(puzzle, 1, 3) << endl;
}
void
part2(const puzzle_t& puzzle)
{
cout << solve(puzzle, 4, 10) << endl;
}
int
main()
{
const auto puzzle = read_file("data/day17.txt");
part1(puzzle);
part2(puzzle);
}
|
