advent2024

Advent of Code 2024
git clone git://bsandro.tech/advent2024
Log | Files | Refs

main.cpp (2349B)

      1 #include <iostream>
      2 #include <filesystem>
      3 #include <fstream>
      4 #include <vector>
      5 #include <cstring>
      6 #include <cstdio>
      7 #include <tuple>
      8 #include <algorithm>
      9 #include "utils.hpp"
     10 
     11 class Tree {
     12 public:
     13     std::string root;
     14     std::vector<Tree> branches;
     15 };
     16 
     17 typedef std::pair<std::vector<std::string>, std::vector<std::string>> Data;
     18 
     19 template<typename T>
     20 T read_file(const std::string &path) {
     21     std::ifstream ifs(path, std::ios::binary);
     22     if (!ifs.is_open()) {
     23         throw std::runtime_error(path+":"+std::strerror(errno));
     24     }
     25     T buf;
     26     bool is_patterns = true;
     27     while (1) {
     28         std::string str;
     29         std::getline(ifs, str);
     30         if (str.empty()) {
     31             is_patterns = false;
     32         } else if (is_patterns) {
     33             std::istringstream ss(str);
     34             for (std::string s; std::getline(ss, s, ',');) {
     35                 std::erase(s, ' ');
     36                 buf.first.push_back(s);
     37             }
     38         } else {
     39             buf.second.push_back(str);
     40         }
     41         if (!ifs) break;
     42     }
     43     static auto sorter = [](const std::string &l, const std::string &r) -> bool {
     44         return l.size() < r.size();
     45     };
     46     std::sort(buf.first.begin(), buf.first.end(), sorter);
     47     std::sort(buf.second.begin(), buf.second.end(), sorter);
     48     return buf;
     49 }
     50 
     51 void patterns_match(const std::vector<std::string> patterns, const char *s, int64_t &cnt) {
     52     const std::string ss(s);
     53     for (const auto &ps:patterns) {
     54         if (ss.starts_with(ps)) {
     55             const char *ns = s+ps.size();
     56             if (*ns=='\0') {
     57                 cnt++;
     58             } else {
     59                 patterns_match(patterns, ns, cnt);
     60             }
     61         }
     62     }
     63 }
     64 
     65 std::pair<int64_t, int64_t> solve(Data &input) {
     66     int64_t r1 = 0;
     67     int64_t r2 = 0;
     68     for (const std::string &v : input.second) {
     69         int64_t cnt = 0;
     70         patterns_match(input.first, v.c_str(), cnt);
     71         if (cnt>0) r1++;
     72         r2+=cnt;
     73     }
     74     return std::make_pair(r1, r2);
     75 }
     76 
     77 int main(int argc, char **argv) {
     78     Performance perf;
     79     const std::string fname = argc>1 ? argv[1] : "test1.txt";
     80     std::cout << "AoC 2024 day 19 " << fname << std::endl;
     81     Data input = read_file<Data>(fname);
     82     auto [p1, p2] = solve(input);
     83     std::cout << "part1: " << p1 << std::endl;
     84     std::cout << "part2: " << p2 << std::endl;
     85 
     86     return 0;
     87 }