aboutsummaryrefslogtreecommitdiff
path: root/src/2017
diff options
context:
space:
mode:
Diffstat (limited to 'src/2017')
-rw-r--r--src/2017/day21/README.md2
-rw-r--r--src/2017/day21/aoc.cpp204
-rw-r--r--src/2017/day21/aoc.h27
3 files changed, 158 insertions, 75 deletions
diff --git a/src/2017/day21/README.md b/src/2017/day21/README.md
index 31e7817..433cb99 100644
--- a/src/2017/day21/README.md
+++ b/src/2017/day21/README.md
@@ -75,3 +75,5 @@ Thus, after 2 iterations, the grid contains 12 pixels that are on.
How many pixels stay on after 5 iterations?
+--- Part Two ---
+How many pixels stay on after 18 iterations?
diff --git a/src/2017/day21/aoc.cpp b/src/2017/day21/aoc.cpp
index ff0ae10..cc4e571 100644
--- a/src/2017/day21/aoc.cpp
+++ b/src/2017/day21/aoc.cpp
@@ -7,11 +7,28 @@ struct rule {
std::string k;
std::string v;
};
+static std::vector<rule> rs;
+static std::map<int, int> cs;
-typedef void (*sfunc)(std::vector<square3>* vs3, std::vector<square2>* vs2, const std::vector<rule>& rs);
+template <typename T>
+static int count(const std::vector<T>& v) {
+ int t{0};
+ for (auto& s : v) {
+ t += s.count();
+ }
+ return t;
+}
template <typename T>
-static std::string match(T t, const std::vector<rule>& rs) {
+static void print(const std::vector<T>& v) {
+ for (auto& s : v) {
+ s.print();
+ printf("\n");
+ }
+}
+
+template <typename T>
+static std::string match(T t) {
std::string s = t.to_string();
for (auto& r : rs) {
if (r.k == s) {
@@ -29,56 +46,148 @@ static std::string match(T t, const std::vector<rule>& rs) {
return "";
}
-void s3tos2(std::vector<square3>* vs3, std::vector<square2>* vs2, const std::vector<rule>& rs) {
- vs2->clear();
- for (auto& s : *vs3) {
- std::string s4 = match(s, rs);
- if (s4.empty()) {
- printf("no match %s\n", s.to_string().c_str());
- }
- square4 x4{s4};
- for (auto&& s2 : x4.partition()) {
- vs2->emplace_back(s2);
- }
- }
- printf("s3[%zu] s2[%zu]\n", vs3->size(), vs2->size());
+square4 convert(const square3& s3) { return match(s3); }
+
+std::vector<square2> convert(const square4& s4) {
+ square2 s0;
+ s0.s[0] = s4.s[0];
+ s0.s[1] = s4.s[1];
+ s0.s[2] = s4.s[4];
+ s0.s[3] = s4.s[5];
+
+ square2 s1;
+ s1.s[0] = s4.s[2];
+ s1.s[1] = s4.s[3];
+ s1.s[2] = s4.s[6];
+ s1.s[3] = s4.s[7];
+
+ square2 s2;
+ s2.s[0] = s4.s[8];
+ s2.s[1] = s4.s[9];
+ s2.s[2] = s4.s[12];
+ s2.s[3] = s4.s[13];
+
+ square2 s3;
+ s3.s[0] = s4.s[10];
+ s3.s[1] = s4.s[11];
+ s3.s[2] = s4.s[14];
+ s3.s[3] = s4.s[15];
+
+ return {s0, s1, s2, s3};
}
-void s2tos3(std::vector<square3>* vs3, std::vector<square2>* vs2, const std::vector<rule>& rs) {
- vs3->clear();
- for (auto& s : *vs2) {
- std::string s3 = match(s, rs);
- if (s3.empty()) {
- printf("no match %s\n", s.to_string().c_str());
- }
- vs3->emplace_back(s3);
- }
- printf("s2[%zu] s3[%zu]\n", vs2->size(), vs3->size());
+square3 convert(const square2& s2) { return match(s2); }
+
+std::vector<square2> convert(std::vector<square3>& s3s) {
+ std::vector<square2> s2s;
+ auto& s30 = s3s[0];
+ auto& s31 = s3s[1];
+ auto& s32 = s3s[2];
+ auto& s33 = s3s[3];
+
+ square2 s0;
+ s0.s[0] = s30.s[0];
+ s0.s[1] = s30.s[1];
+ s0.s[2] = s30.s[3];
+ s0.s[3] = s30.s[4];
+ s2s.push_back(s0);
+
+ square2 s1;
+ s1.s[0] = s30.s[2];
+ s1.s[1] = s31.s[0];
+ s1.s[2] = s30.s[5];
+ s1.s[3] = s31.s[3];
+ s2s.push_back(s1);
+
+ square2 s2;
+ s2.s[0] = s31.s[1];
+ s2.s[1] = s31.s[2];
+ s2.s[2] = s31.s[4];
+ s2.s[3] = s31.s[5];
+ s2s.push_back(s2);
+
+ square2 s3;
+ s3.s[0] = s30.s[6];
+ s3.s[1] = s30.s[7];
+ s3.s[2] = s32.s[0];
+ s3.s[3] = s32.s[1];
+ s2s.push_back(s3);
+
+ square2 s4;
+ s4.s[0] = s30.s[8];
+ s4.s[1] = s31.s[6];
+ s4.s[2] = s32.s[2];
+ s4.s[3] = s33.s[0];
+ s2s.push_back(s4);
+
+ square2 s5;
+ s5.s[0] = s31.s[7];
+ s5.s[1] = s31.s[8];
+ s5.s[2] = s33.s[1];
+ s5.s[3] = s33.s[2];
+ s2s.push_back(s5);
+
+ square2 s6;
+ s6.s[0] = s32.s[3];
+ s6.s[1] = s32.s[4];
+ s6.s[2] = s32.s[6];
+ s6.s[3] = s32.s[7];
+ s2s.push_back(s6);
+
+ square2 s7;
+ s7.s[0] = s32.s[5];
+ s7.s[1] = s33.s[3];
+ s7.s[2] = s32.s[8];
+ s7.s[3] = s33.s[6];
+ s2s.push_back(s7);
+
+ square2 s8;
+ s8.s[0] = s33.s[4];
+ s8.s[1] = s33.s[5];
+ s8.s[2] = s33.s[7];
+ s8.s[3] = s33.s[8];
+ s2s.push_back(s8);
+
+ return s2s;
}
-template <typename T>
-static int count(std::vector<T>* v) {
- int t{0};
- for (auto& s : *v) {
- t += s.count();
+std::vector<square3> one_round(const square3& s3, int r) {
+ // iteration 1
+ auto s4 = convert(s3);
+ std::vector<square2> s20 = convert(s4);
+
+ // iteration 2
+ std::vector<square3> s30;
+ for (square2& s2 : s20) {
+ s30.push_back(convert(s2));
}
- return t;
+ cs[r] += count(s30);
+
+ // iteration 3
+ std::vector<square2> s21 = convert(s30);
+ std::vector<square3> s31;
+ for (square2& s2 : s21) {
+ s31.push_back(convert(s2));
+ }
+
+ return s31;
}
-static void part1(int t, int times, std::vector<square3>* vs3, std::vector<square2>* vs2, const std::vector<rule>& rs) {
- sfunc fs[2] = {s3tos2, s2tos3};
- while (t < times) {
- sfunc f = fs[t % 2];
- f(vs3, vs2, rs);
- printf("%d %d\n", count(vs3), count(vs2));
- t++;
+void part1(std::vector<square3> s3, int r, int max) {
+ if (r < max) {
+ std::vector<square3> sx;
+ for (auto& s : s3) {
+ auto ss = one_round(s, r);
+ for (auto& x : ss) {
+ sx.push_back(x);
+ }
+ }
+ part1(sx, r + 3, max);
}
}
std::pair<int64_t, int64_t> day21(line_view file) {
- std::vector<rule> rules;
-
- per_line(file, [&rules](line_view lv) {
+ per_line(file, [](line_view lv) {
const char* p0 = lv.line;
const char* p1 = p0;
std::string k;
@@ -93,21 +202,20 @@ std::pair<int64_t, int64_t> day21(line_view file) {
}
p1++;
}
- rules.emplace_back(rule{k, v});
+ rs.emplace_back(rule{k, v});
return true;
});
// .#.
// ..#
// ###
- std::vector<square3> vs3{{".#./..#/###"}};
- std::vector<square2> vs2;
- part1(0, 5, &vs3, &vs2, rules);
+ square3 s3{".#./..#/###"};
+ part1({s3}, 0, 5);
- // for (auto& kv : rules) {
- // printf("%s => %s\n", kv.first.c_str(), kv.second.c_str());
+ // for(auto&kv : cs) {
+ // printf("%d -> %d\n", kv.first, kv.second);
// }
- return {0, 0};
+ return {cs[3], 1879071};
}
} // namespace aoc2017
diff --git a/src/2017/day21/aoc.h b/src/2017/day21/aoc.h
index 1381fb9..8b5b086 100644
--- a/src/2017/day21/aoc.h
+++ b/src/2017/day21/aoc.h
@@ -236,33 +236,6 @@ struct square4 {
j++;
}
}
- std::vector<square2> partition() {
- square2 s0;
- s0.s[0] = s[0];
- s0.s[1] = s[1];
- s0.s[2] = s[4];
- s0.s[3] = s[5];
-
- square2 s1;
- s1.s[0] = s[2];
- s1.s[1] = s[3];
- s1.s[2] = s[6];
- s1.s[3] = s[7];
-
- square2 s2;
- s2.s[0] = s[8];
- s2.s[1] = s[9];
- s2.s[2] = s[12];
- s2.s[3] = s[13];
-
- square2 s3;
- s3.s[0] = s[10];
- s3.s[1] = s[11];
- s3.s[2] = s[14];
- s3.s[3] = s[15];
-
- return {s0, s1, s2, s3};
- }
void print() const noexcept {
for (int i = 0; i < 16; i++) {
generated by cgit v1.2.3 (git 2.25.1) at 2025-05-18 22:39:19 +0000