commit 485d0c28244aa1471467502a579ccf939b972dbe
parent e2e231b5acd86b067379109f9a877d01f4cb1e62
Author: bsandro <email@bsandro.tech>
Date: Tue, 10 Dec 2024 22:20:36 +0200
Day 10 p1+p2
Diffstat:
8 files changed, 198 insertions(+), 0 deletions(-)
diff --git a/day10/Makefile b/day10/Makefile
@@ -0,0 +1,34 @@
+NAME=$(shell basename ${PWD})
+SRC=$(wildcard *.cpp)
+DEPS:=$(wildcard *.hpp)
+OBJ:=$(SRC:.cpp=.o)
+CXXFLAGS=-O2 -std=c++23 -Werror -Wall -Wextra -I. -I../include
+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
+
+test3: $(NAME)
+ @./$(NAME) test3.txt
+
+test4: $(NAME)
+ @./$(NAME) test4.txt
diff --git a/day10/input.txt b/day10/input.txt
@@ -0,0 +1,45 @@
+981050112210121034565432321032103321234567567
+872341201014434921878891434549012310432198678
+765434318123567890989760023678543986501021549
+545985329854356792105654116707621677893430932
+456576416763447883498743209811030543082567801
+327676509823430976541050124322345892121078998
+218489678016521050132011267401276734289010867
+109345908987210763249121278569889825678123459
+543237817876345854358230989078778910107645678
+654106726541096981267345678123498723216530501
+761235430432387870301076521014567234345321432
+890144321001456765432189410019010121237876501
+781055697878921212345674321928723210345989432
+218966788965430101254789345839654234326710101
+109875692100123270163231236743010165019823321
+018754103018786789872100109852123278956754430
+325673214109695698987212121961094109849869543
+234981005234534321210103030878785603732778672
+189012346943413210321234549879676712011001981
+076321057892100110450321676566543893425652760
+325401069787012026565410789457012798534743854
+410512178976543237656998898308932687649887923
+567893467689854148997867891219801456308996310
+234554992501763056788950750304762343210105409
+147667881432612234563441065403451012308712358
+018589670109803189612532674312332305419654347
+189478521210789078703675689100123498569323256
+789767432345650876589986789210096567878012100
+679854343217821987676521654323487458901223321
+565943034506934910505430598714510329874341234
+450012129645445823412014567609621210965210585
+321101518789336798703123455418760145670195696
+234965400689221209654328954303210234987784787
+105874321678100118765017763214301001056653610
+876701234549010329870126894505212892347542123
+965891098238321234561235214676703083498230036
+874782347107630145490344305987894176580121545
+923690456016549854987432234589765237891234694
+012541219897896768876501105676894396790346787
+001432108766541089004321212988787781687656698
+123498789655432376113410145679695670521044567
+876567610141045645223567034034544321430123698
+965458901232038764344038123129632487654310432
+012307676540129854965129876038701898943216581
+103212789432100123876434565345612781012107890
diff --git a/day10/main.cpp b/day10/main.cpp
@@ -0,0 +1,89 @@
+#include <iostream>
+#include <filesystem>
+#include <fstream>
+#include <vector>
+#include <cstring>
+#include <cstdio>
+#include <tuple>
+#include <algorithm>
+#include <set>
+#include "utils.hpp"
+
+typedef std::pair<int, int> Vec2;
+typedef std::vector<std::string> Data;
+
+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::vector<Vec2> findTrailheads(const Data &input) {
+ std::vector<Vec2> out;
+ for (int y=0; y<(int)input.size(); ++y) {
+ for (int x=0; x<(int)input[y].size(); ++x) {
+ if (input[y][x]=='0') {
+ out.push_back(Vec2(x, y));
+ }
+ }
+ }
+ return out;
+}
+
+// works only with square maps
+void findTrail(const Data &input, const Vec2 &start, std::set<Vec2> &nines, int &rating) {
+ static const std::vector<Vec2> dirs = {Vec2(0, -1), Vec2(1, 0), Vec2(0, 1), Vec2(-1, 0)};
+ static const int sz = input.size();
+ for (auto &d:dirs) {
+ Vec2 p(start.first+d.first, start.second+d.second); // boundaries
+ if (p.first>=0&&p.first<sz&&p.second>=0&&p.second<sz) {
+ char h1 = input[start.second][start.first];
+ char h2 = input[p.second][p.first];
+ if (h2-h1==1) {
+ if (h2=='9') {
+ rating++;
+ nines.insert(p);
+ } else {
+ findTrail(input, p, nines, rating);
+ }
+ }
+ }
+ }
+}
+
+std::pair<int64_t, int64_t> solve(Data &input [[ maybe_unused ]]) {
+ std::vector<Vec2> trailheads = findTrailheads(input);
+ int count = 0;
+ int rating = 0;
+ for (auto &t:trailheads) {
+ std::set<Vec2> nines;
+ int localRating = 0;
+ findTrail(input, t, nines, localRating);
+ count += nines.size();
+ rating += localRating;
+ }
+
+ return std::make_pair(count, rating);
+}
+
+int main(int argc, char **argv) {
+ Performance perf;
+ const std::string fname = argc>1 ? argv[1] : "test1.txt";
+ std::cout << "AoC 2024 day 10 " << fname << std::endl;
+ Data input = read_file<Data>(fname);
+ auto [score, rating] = solve(input);
+ std::cout << "part1: " << score << std::endl;
+ std::cout << "part2: " << rating << std::endl;
+
+ return 0;
+}
diff --git a/day10/test1.txt b/day10/test1.txt
@@ -0,0 +1,7 @@
+.....0.
+..4321.
+..5..2.
+..6543.
+..7..4.
+..8765.
+..9....
diff --git a/day10/test2.txt b/day10/test2.txt
@@ -0,0 +1,8 @@
+89010123
+78121874
+87430965
+96549874
+45678903
+32019012
+01329801
+10456732
diff --git a/day10/test3.txt b/day10/test3.txt
@@ -0,0 +1,6 @@
+012345
+123456
+234567
+345678
+446789
+567898
diff --git a/day10/test4.txt b/day10/test4.txt
@@ -0,0 +1,7 @@
+..90..9
+...1.98
+...2..7
+6543456
+765.987
+876....
+987....
diff --git a/tpl/main.cpp b/tpl/main.cpp
@@ -6,6 +6,7 @@
#include <cstdio>
#include <tuple>
#include <algorithm>
+#include "utils.hpp"
template<typename T>
T read_file(const std::string &path) {
@@ -35,6 +36,7 @@ int64_t part2(Data &input [[ maybe_unused ]]) {
}
int main(int argc, char **argv) {
+ Performance perf;
const std::string fname = argc>1 ? argv[1] : "test1.txt";
std::cout << "AoC 2024 day $DAY " << fname << std::endl;
Data input = read_file<Data>(fname);
