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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
|
#include "aoc.h"
#include <deque>
// F4 . . . . . . . . . . .
// F3 . . . . . . . HG HM RG RM
// F2 . . . . PM . SM . . . .
// F1 E TG TM PG . SG . . . . .
//
// F4 . . . . .
// F3 . . . LG .
// F2 . HG . . .
// F1 E . HM . LM
//
// 0.
// take everythong to the forth floor
//
// 1.
// there is an elevator that can move between the four floors.
// When you enter the containment area, you and the elevator will start on the first floor.
//
// 2.
// Its capacity rating means it can carry at most yourself and two RTGs or microchips in any combination.
//
// 3.
// As a security measure, the elevator will only function if it contains at least one RTG or microchip.
//
// 4.
// The elevator always stops on each floor to recharge,
// Each elevator stop counts as one step, even if nothing is added to or removed from it
//
// 5.
// if a chip is ever left in the same area as another RTG,
// and it's not connected to its own RTG, the chip will be fried.
//
namespace aoc2016 {
int next_floor(int f) {
static int df = 1;
if (f == 1)
df = 1;
if (f == 4)
df = -1;
return f + df;
}
void setup_demo(std::vector<ritem>& rs) {
rs.emplace_back(2, 1);
rs.emplace_back(3, 1);
}
void setup_input(std::vector<ritem>& rs) {
rs.emplace_back(1, 1);
rs.emplace_back(1, 2);
rs.emplace_back(1, 2);
rs.emplace_back(3, 3);
rs.emplace_back(3, 3);
}
bool all_at(const std::vector<ritem>& rs, int f) {
for (auto& r : rs) {
if (r.fs[0] != f || r.fs[1] != f) {
return false;
}
}
return true;
}
bool any_at(const std::vector<ritem>& rs, int f) {
for (auto& r : rs) {
if (r.fs[0] == f || r.fs[1] == f) {
return true;
}
}
return false;
}
bool empty(const std::vector<ritem>& rs, int f) { return !any_at(rs, f); }
// 1. in every step, modify fs[0] or fs[1] in each ritem
// 2. at minimal 1 must be modified, at most, 2 can be modified
// 3. chip fs[1] can only be modified if
// 3.1 fs[0] == next_floor(fs[1])
// 3.2 or empty == next_floor(fs[1])
// 4. only increase fs[0] ??
// 5. gen fs[0] can only be modified if
// 5.1 fs[1] == next_floor(fs[0])
// 5.2 or empty == next_floor(fs[0])
// 6. either modify fs[0] and fs[1] of the same ritem
// or modify two fs[0] or two fs[1]
// 7. GGM is ok, GMM is not
struct ritem_f {
std::vector<ritem> rs;
int f;
};
std::vector<ritem_f> choices(const ritem_f& r) {
// int nf = next_floor(r.f);
return {};
}
// bfs
// goal is to get every ritem in rs with value (4,4)
int move_ritem(int f, const std::vector<ritem>& r) {
int step = 0;
std::deque<ritem_f> q;
q.push_back({r, f});
while (!q.empty()) {
auto s = q.size();
while (s-- > 0) {
auto r0 = q.front();
q.pop_front();
if (all_at(r0.rs, 4)) {
return step;
} else {
// push to q every other next possible state of r0
auto nexts = choices(r0);
for (auto& n : nexts) {
q.push_back(n);
}
}
}
step++;
}
return INT32_MAX;
}
std::pair<int64_t, int64_t> day11(line_view) {
std::vector<ritem> rs;
setup_demo(rs);
int min = move_ritem(1, rs);
printf("%d\n", min);
return {0, 0};
}
} // namespace aoc2016
|
