commit fefd390804d34ac89197d30d464e427df833a85b
parent 4f5bb0681794bfa82e526a5e8c7837dd81da9023
Author: bsandro <email@bsandro.tech>
Date: Sun, 8 Dec 2024 02:01:02 +0200
Day 06 p2 works
Diffstat:
2 files changed, 49 insertions(+), 43 deletions(-)
diff --git a/day06/main.cpp b/day06/main.cpp
@@ -9,6 +9,7 @@
#include <algorithm>
#include <expected>
#include <ranges>
+#include <thread>
enum class Dir {
up,
@@ -108,77 +109,70 @@ std::expected<Vec3, std::string> get_next(const Data &m, const Vec3 &p) {
}
break;
}
- //printf("%d,%d(%s) -> %d,%d(%s)\n", p.first, p.second, str(d), np.first, np.second, str(nd));
return Vec3(x,y,d);
}
// works only on square input
-void traverse(const Data &m, std::vector<Vec3> &visited, const Vec3 &p) {
+void traverse(const Data &m, std::vector<Vec3> &visited, const Vec3 &p, bool &loop) {
visited.push_back(p);
auto np = get_next(m, p);
- if (np.has_value()) traverse(m, visited, np.value());
-}
-
-std::expected<Vec2, bool> find_wall(const Data &m, Vec2 p, Dir d) {
- auto [x, y] = p;
- switch (d) {
- case Dir::up:
- while (--y>=0) {
- if (m[y][x]=='#') return Vec2(x,y+1);
- }
- break;
- case Dir::down:
- while (++y<(int)m.size()) {
- if (m[y][x]=='#') return Vec2(x,y-1);
- }
- break;
- case Dir::left:
- while (--x>=0) {
- if (m[y][x]=='#') return Vec2(x+1,y);
- }
- break;
- case Dir::right:
- while (++x<(int)m.size()) {
- if (m[y][x]=='#') return Vec2(x-1,y);
+ if (np.has_value()) {
+ if (std::count(visited.begin(), visited.end(), np.value())>0) {
+ loop = true;
+ } else {
+ traverse(m, visited, np.value(), loop);
}
- break;
- default:
- return std::unexpected(false);
}
- return std::unexpected(false);
}
-
+[[maybe_unused]] void print_map(const Data &m) {
+ std::cout << "---------------------" << std::endl;
+ for (auto &s : m) {
+ std::cout << s << std::endl;
+ }
+ std::cout << "---------------------" << std::endl;
+}
Vec2 solve(const Data &input [[ maybe_unused ]]) {
std::vector<Vec3> visited;
if (auto g=find_guard(input); g.has_value()) {
- traverse(input, visited, g.value());
+ bool loop = false;
+ traverse(input, visited, g.value(), loop);
}
std::set<Vec2> p1;
int p2 = 0;
for (auto it=visited.begin(); it!=visited.end(); ++it) {
auto [x, y, d] = *it;
- //std::printf("[%d,%d,%s]\n", x, y, str(d));
Vec2 p(x, y);
p1.insert(p);
- /*if (std::count_if(visited.begin(), it, [&x,&y,&d](auto v) {
- auto [vx, vy, vd] = v;
- return vx==x && vy==y && vd==dir_shift(d);
- })>0) {
- printf("found intersection at %d:%d\n", x, y);
- p2++;
- continue;
+ // p2 - put obstacles on every walked tile and traverse everything all over again
+ std::vector<Vec3> visited1;
+ std::copy(visited.begin(), it+1, std::back_inserter(visited1));
+ // obstacle will be placed at the next tile
+ Data input1;
+ std::copy(input.begin(), input.end(), std::back_inserter(input1));
+ auto it1 = it+1;
+ if (it1!=visited.end()) {
+ auto [x1, y1, d1] = *it1;
+ bool on_path = std::count_if(visited1.begin(), visited1.end(), [&x1, &y1](const Vec3 &v1){
+ auto [x2,y2,d2] = v1;
+ return x1==x2 && y1==y2;
+ })>0;
+ if (input[y1][x1]=='#' || (x==x1&&y==y1) || on_path) {
+ continue;
+ }
+ input1[y1][x1] = '#';
+ bool loop1 = false;
+ traverse(input1, visited1, *it, loop1);
+ if (loop1) p2++;
}
- }*/
}
- printf("\n");
return {(int)p1.size(), p2};
}
-// 1103 too low
+
int main(int argc, char **argv) {
const std::string fname = argc>1 ? argv[1] : "test1.txt";
std::cout << "AoC 2024 day 06 " << fname << std::endl;
@@ -187,5 +181,7 @@ int main(int argc, char **argv) {
std::cout << "part1: " << p1 << std::endl;
std::cout << "part2: " << p2 << std::endl;
+ std::cout << std::jthread::hardware_concurrency() << " threads supported" << std::endl;
+
return 0;
}
diff --git a/day06/test2.txt b/day06/test2.txt
@@ -0,0 +1,10 @@
+....#.....
+.........#
+..........
+..#.......
+.......#..
+......#...
+.#..^.....
+........#.
+#.........
+......#...