commit b6f9dc14bb9a6f80e9af14d20cc68fe3a0208b6c
parent 57a6036c30e6fc36f06cb5bb484ed6f8b51b1798
Author: bsandro <email@bsandro.tech>
Date: Sat, 7 Dec 2024 10:19:54 +0200
Day 06 p1, p2 doesn't work yet
Diffstat:
4 files changed, 453 insertions(+), 0 deletions(-)
diff --git a/day06/Makefile b/day06/Makefile
@@ -0,0 +1,28 @@
+NAME=$(shell basename ${PWD})
+SRC=$(wildcard *.cpp)
+DEPS:=$(wildcard *.hpp)
+OBJ:=$(SRC:.cpp=.o)
+CXXFLAGS=-O2 -std=c++23 -Werror -Wall -Wextra -I.
+LDFLAGS=-lstdc++
+
+all: $(NAME)
+
+.PHONY: clean run
+
+clean:
+ rm -f $(OBJ) $(NAME)
+
+%.o : %.c $(DEPS)
+ @$(CC) $(CFLAGS) -c $< -o $@
+
+$(NAME): $(OBJ)
+ @$(CC) $(OBJ) -o $@ $(LDFLAGS)
+
+run: $(NAME)
+ @./$(NAME) input.txt
+
+test1: $(NAME)
+ @./$(NAME) test1.txt
+
+test2: $(NAME)
+ @./$(NAME) test2.txt
diff --git a/day06/input.txt b/day06/input.txt
@@ -0,0 +1,130 @@
+......#.......#...................................................................................##......#..............#........
+........................#....................................#....................................................................
+...#.........#...#.....##..#...#......#..........................................#................#...................#....#....#.
+....................#...#...#.#............#..................................#..............#....#...............................
+.....................................................................#................................#...........................
+........#............#......#................#..................#................................................#...............#
+...................#.........#............................................................##......................................
+.........#..........#......##.............#.#...............#................................##.................#.................
+...........................................................#...............................#..................##......##.....#....
+...................#...........................................##...............#.....#......#............#..........#............
+...............#........................#...#....#..............................................#.#......#............#...........
+........#.............#...........................#..#.....................................#......................................
+......#......#....#..............#...............#...#...............#.......#...................................................#
+..........#............#..#.....#......................#.........#...........................#..........#.........................
+#...............................................................................#.#....#.............###..................#.......
+.....#.#....#....................................#............................#...............#........................#....#.....
+....#......#................#....................#...................#............#................#..............................
+#...................#.............................#.#...#.............#......................#.....................#..............
+.................#...............#................................#..##..#..............#.......#.................................
+.....................................................##.#.....................................#.............#.....................
+...#.............................#................................................................................................
+#.##.........................................#....#..#..............................#......#..................................#...
+......................#.........##.....................................#......................#..#..........#...............#....#
+.#......................................................#....#......................................#...............#....#........
+............#...............................#.......................................................#.............................
+.............................................................................#....................................................
+..#...#.....#...............................................................................................#.....................
+................................................#.#.......................#..................#............#.......................
+...............#.............#.....................#........................................................#..........#.......#..
+...................................#..........#......#............................................#.....#.........................
+.............#..............#...........##..........................................................................#.....#.......
+.............#...............#........#.................................................................#.......#.................
+.#...............................................................#..............................................................#.
+.#......#...........#..............................................................##.............................................
+...................#.....................................#....#........................#............................#.......###...
+.....#...#.....#......................#.....................................#...............................#.....................
+......................#....#...#........#........#...........................#...............#...........................#....#...
+..#..#................................................................................#...........................................
+.....#......#.#.......................................#..........#................................................................
+..........#.......................#.............#.#........##.........................................................#...........
+##........##.#....................#...#...................................................#.##......#...................#.........
+...........#................#.#...........#......................#..................#......#......................................
+...#..............................#......#...............#.................#.#............................................#.....#.
+...#..................#...............#.........#..#.............................#..........#...................#.......#.........
+.....................................................................................................#.......................#....
+....................................##.#.................................#......##................................#.#.............
+..................#.............................................................................................#............#....
+............#........#...#.....#.....#........................................#....#..............#..............................#
+....................................#...........................................................................................#.
+............................#.#....#.....................#........................................................................
+........#....#......#.......#................................................................##............................#......
+....#...................#....#.............................................................................................#......
+....................#......#.........................#..................#.........#....................#..........................
+#........#.....#.......#....................................#.....#...........................................#...................
+.....#....................................................................................................#.#....#................
+....#....................................................................#.......#........................................#.......
+#...........................#.#....#......#................................................................................#......
+.#..........................................................#...............#......................#.............................#
+..#..#.#...................................#.......#...............#....#....................#................................#...
+.........................#........................................................................................................
+...................................#...........................#...........#..#...........#................#.........#............
+......................................#...............#.................#..#............................#.....#..#...#............
+#.......................#.........#..#...............................................................#.......................#....
+............#............................#..#.....................................................................................
+................#............#..................#....#........#...............................#....#.#.......................#.#..
+.........................................................................#....................#..........................#........
+.....................................................#...............#........................................#......#............
+..........##..................##...............................................................................................#..
+..................#.........................................#..#......................#.........#.....#.....#.....................
+..#.........................................................................#...................................#................#
+...............................#..................................................................................................
+..#..........#..#..............................................................................#........................#.........
+...........#.#........................................................#.....#.........................#...........................
+...........................................#......#...............................................................................
+.......................#................................................................................................##........
+.....#...............#....................................................................................#.......#...............
+.#.#.................................#........................#................#...............#......#...........................
+........#........#...............#.........................^...........................#......#.................................#.
+.....................#.............#..#...........................................................................................
+...........#...........................................................................#.......##......#.............#............
+..........#..........................................#.................#....#......##.........#.................................#.
+...................#...#...................#....#...........#................................#.#..................................
+.......#....#...#..................#...............................................#.....#.........#......#.#.#.......#......#....
+.....#................................................#......................#...#.....................................#.#........
+.##........##.......#.........................................##..................................................................
+......................................#....#........#..........#..#...........................#....................#....#.........
+.......................#........................#..............................#.#.............................................#..
+..........................#....###......................................................................#...................#.....
+...........#..................#..............#....................................................................................
+......................#................#..#............................#............#.........................##...#..............
+.................#.......................................................................#....#...............................#...
+................................................#..............................................................................#..
+..#.......#....#................#...........................#..........#.#..#.......................#.#....................#......
+........#.............................#........................................#..................................................
+...........................#............................................................................#.............#....#......
+#...................#.......#............#..........................................................#..#....#......#..........#..#
+#..........#.................................#.........................#..................................#....................##.
+..........#..#...........................................................................#........................##..........#...
+.............#.#.......................................#.................................#..............#.......#.................
+.................#....#........#........#....#.................................#................................#.................
+...........................#..........#.#..#..#........#...#....................#...#........#.......................#............
+........#................................#...................................#.#...............#..................................
+............................................................#.......#......#.#..........................#..#....................#.
+.........#.#....................................#.....................#.....##.......#..................................#.........
+........#......................................#.......##............................................................##.....#.....
+.............#................................#....#..................##...........................#..#..#........................
+.......................................................#...#..........#...................................#.......#........#......
+.....#...........#...............................................................................................#................
+.......#..................#......#.....#............#..................#.......#.............#................#...................
+.....#.........................................................#...........................................#.............#.....#..
+...............#..................#...............................................#...................#...........................
+..#............#......#....#...#..............................#..#...................................#...#.............#..........
+.........#........#.....................................##.......................#.....................#..#.............#.........
+....................#....#......................#..#.##..................#................#...........#............#..............
+..........#..................................#............#..#...............#.................#..........#.......................
+..................#.........#........................#.........................#.........#..................................#.....
+...........#.#..............#........#.................................#............#............................#................
+.#.....#........................................................................................#....#........##..................
+.....................#....#.................#..........#............#............................#.............#.............#.#..
+................................#....#......................................................#....#............#.............#.....
+..............#..#.........#....................#.......................#.......#.........#..................#....................
+.............#.....#....................#.#.....................#................#...#.........................#........##........
+.......#.......................#.........................................#.........................##.....#...........#...#.....#.
+.....#.................#................................................................#.................................#....#..
+................#.......................#...........#........#................#.......#.#.#........................#........#.....
+......#..........................#......#............#.......#...#.............................#..........##.......#..........#...
+................#.....#...#..............................#......#..#..............................................................
+.............................#....#...............#..............#......................................#.......###..#.#..........
+..........#.......#...............#............................#........#.........................................................
+.................#.....................................#.......................................#................#........#.#..#...
diff --git a/day06/main.cpp b/day06/main.cpp
@@ -0,0 +1,285 @@
+#include <iostream>
+#include <filesystem>
+#include <fstream>
+#include <vector>
+#include <set>
+#include <cstring>
+#include <cstdio>
+#include <tuple>
+#include <algorithm>
+#include <expected>
+#include <ranges>
+
+typedef std::vector<std::string> Data;
+
+typedef std::pair<int,int> Vec2; // x, y
+
+enum class Dir {
+ up,
+ down,
+ left,
+ right,
+ out
+};
+
+//@todo implement a generic map<width, height> class
+
+template<typename T>
+T read_file(const std::string &path) {
+ std::ifstream ifs(path, std::ios::binary);
+ if (!ifs.is_open()) {
+ throw std::runtime_error(path+":"+std::strerror(errno));
+ }
+ T buf;
+ while (1) {
+ std::string str;
+ std::getline(ifs, str);
+ if (!str.empty()) buf.push_back(str);
+ if (!ifs) break;
+ }
+ return buf;
+}
+
+std::expected<Vec2, std::string> find_guard(const Data &m) {
+ for (int y=0; y<(int)m.size(); ++y) {
+ for (int x=0; x<(int)m[y].size(); ++x) {
+ if (m[y][x]=='^') return Vec2{x,y};
+ }
+ }
+ return std::unexpected("no guard found");
+}
+
+[[ maybe_unused ]]
+static const char * str(Dir d) {
+ switch (d) {
+ case Dir::up: return "up";
+ case Dir::down: return "down";
+ case Dir::left: return "left";
+ case Dir::right: return "right";
+ case Dir::out: return "out";
+ }
+ return "NULL";
+}
+
+bool dirs_angled(Dir d1, Dir d2) {
+ switch (d1) {
+ case Dir::up: return d2==Dir::right;
+ case Dir::down: return d2==Dir::left;
+ case Dir::left: return d2==Dir::up;
+ case Dir::right: return d2==Dir::down;
+ case Dir::out: return false;
+ }
+ return false;
+}
+
+std::pair<Vec2, Dir> get_next(const Data &m, const Vec2 &p, Dir d) {
+ Vec2 np = p;
+ Dir nd = d;
+ switch (d) {
+ case Dir::up:
+ if (np.second-1>=0) {
+ if (m[np.second-1][np.first]=='#') {
+ nd=Dir::right;
+ } else {
+ np.second--;
+ }
+ } else {
+ return {np, Dir::out};
+ }
+ break;
+ case Dir::down:
+ if (np.second+1<(int)m.size()) {
+ if (m[np.second+1][np.first]=='#') {
+ nd=Dir::left;
+ } else {
+ np.second++;
+ }
+ } else {
+ return {np, Dir::out};
+ }
+ break;
+ case Dir::left:
+ if (np.first-1>=0) {
+ if (m[np.second][np.first-1]=='#') {
+ nd=Dir::up;
+ } else {
+ np.first--;
+ }
+ } else {
+ return {np, Dir::out};
+ }
+ break;
+ case Dir::right:
+ if (np.first+1<(int)m.size()) {
+ if (m[np.second][np.first+1]=='#') {
+ nd=Dir::down;
+ } else {
+ np.first++;
+ }
+ } else {
+ return {np, Dir::out};
+ }
+ break;
+ case Dir::out:
+ return {p, d};
+ }
+ //printf("%d,%d(%s) -> %d,%d(%s)\n", p.first, p.second, str(d), np.first, np.second, str(nd));
+ return {np, nd};
+}
+
+// works only on square input
+void traverse(const Data &m, std::vector<std::tuple<int,int,Dir>> &visited, const Vec2 &p, Dir d) {
+ visited.push_back(std::make_tuple(p.first, p.second, d));
+ auto [np, nd] = get_next(m, p, d);
+ if (nd==Dir::out) return;
+ traverse(m, visited, np, nd);
+}
+
+//@todo make Data the proper class with methods
+template <typename Iter>
+bool find_line(const Data &m, const Iter &begin, const Iter &end, Vec2 p, Dir d) {
+ auto [x, y] = p;
+ //const auto [x1, y1, d1] = *begin;
+ //const auto [x2, y2, d2] = *end;
+ //std::printf("find_line(%d:%d:%s) %d:%d(%s) -> %d:%d(%s)\n\t",x,y,str(d),x1,y1,str(d1),x2,y2,str(d2));
+ switch (d) {
+ case Dir::up: { // look for path to the right
+ for (++x;x<(int)m.size();++x) {
+ if (m[y][x]=='#') return false;
+ return std::count_if(begin, end, [&x,&y](const auto &v){
+ auto [vx,vy,vd] = v;
+ return vx==x&&vy==y&&vd==Dir::right;
+ })>0;
+ }
+ }
+ break;
+ case Dir::down: {
+ for (--x;x>=0;--x) {
+ if (m[y][x]=='#') return false;
+ return std::count_if(begin, end, [&x,&y](const auto &v){
+ auto [vx,vy,vd] = v;
+ return vx==x&&vy==y&&vd==Dir::left;
+ })>0;
+ }
+ }
+ break;
+ case Dir::left: {
+ for (--y;y>=0;--y) {
+ if (m[y][x]=='#') return false;
+ return std::count_if(begin, end, [&x,&y](const auto &v){
+ auto [vx,vy,vd] = v;
+ return vx==x&&vy==y&&vd==Dir::up;
+ })>0;
+ }
+ }
+ break;
+ case Dir::right: {
+ for (++y;y<(int)m.size();++y) {
+ if (m[y][x]=='#') return false;
+ return std::count_if(begin, end, [&x,&y](const auto &v){
+ auto [vx,vy,vd] = v;
+ return vx==x&&vy==y&&vd==Dir::right;
+ })>0;
+ }
+ }
+ break;
+ case Dir::out:
+ break;
+ }
+ return false;
+}
+
+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);
+ }
+ break;
+ default:
+ return std::unexpected(false);
+ }
+ return std::unexpected(false);
+}
+
+//@todo class method
+Dir dir_shift(Dir d) {
+ switch (d) {
+ case Dir::up: return Dir::right;
+ case Dir::down: return Dir::left;
+ case Dir::left: return Dir::up;
+ case Dir::right: return Dir::down;
+ case Dir::out: return Dir::out;
+ }
+ return Dir::out;
+}
+
+Vec2 solve(const Data &input [[ maybe_unused ]]) {
+ std::vector<std::tuple<int, int, Dir>> visited;
+
+ if (auto g=find_guard(input); g.has_value()) {
+ traverse(input, visited, g.value(), Dir::up);
+ }
+
+ 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;
+ }
+ auto w = find_wall(input, p, dir_shift(d));
+ if (w.has_value()) {
+ auto [wx, wy] = w.value();
+ int valid = std::count_if(visited.begin(), it, [&](auto v) {
+ auto [x1, y1, d1] = v;
+ if (x1==wx&&y1==wy) {
+ std::printf("wall %d:%d(%s|%s) valid\n", wx, wy, str(d1), str(d));
+ return true;
+ } else return false;
+ });
+ if (valid>0) {
+ std::printf("wall found for %d:%d(%s) at %d:%d (valid=%d)\n", x, y, str(d), w.value().first, w.value().second,valid);
+ 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 2015 day 06 " << fname << std::endl;
+ Data input = read_file<Data>(fname);
+ auto [p1, p2] = solve(input);
+ std::cout << "part1: " << p1 << std::endl;
+ std::cout << "part2: " << p2 << std::endl;
+
+ return 0;
+}
diff --git a/day06/test1.txt b/day06/test1.txt
@@ -0,0 +1,10 @@
+....#.....
+.........#
+..........
+..#.......
+.......#..
+..........
+.#..^.....
+........#.
+#.........
+......#...
