advent2024

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

main.cpp (3280B)

      1 #include <inttypes.h>
      2 #include <iostream>
      3 #include <filesystem>
      4 #include <fstream>
      5 #include <vector>
      6 #include <cstring>
      7 #include <cstdio>
      8 #include <tuple>
      9 #include <algorithm>
     10 #include <thread>
     11 #include "utils.hpp"
     12 
     13 struct Vec2 {
     14     int64_t x;
     15     int64_t y;
     16     void fromStr(const std::string &s) {
     17         [[ maybe_unused ]] char btn;
     18         std::sscanf(s.c_str(), "Button %c: X+%" SCNi64 ", Y+%" SCNi64, &btn, &x, &y);
     19     }
     20     bool operator==(const Vec2 &other) const {
     21         return this->x==other.x && this->y==other.y;
     22     }
     23     bool operator!=(const Vec2 &other) const {
     24         return this->x!=other.x || this->y!=other.y;
     25     }
     26 };
     27 
     28 struct Machine {
     29     Vec2 btnA;
     30     Vec2 btnB;
     31     Vec2 prize;
     32     void setPrize(const std::string &s) {
     33         std::sscanf(s.c_str(), "Prize: X=%" SCNi64 ", Y=%" SCNi64, &prize.x, &prize.y);
     34     }
     35 };
     36 
     37 struct State {
     38     const Machine &m;
     39     int pressesA;
     40     int pressesB;
     41 };
     42 
     43 typedef std::vector<Machine> Data;
     44 
     45 template<typename T>
     46 T read_file(const std::string &path) {
     47     std::ifstream ifs(path, std::ios::binary);
     48     if (!ifs.is_open()) {
     49         throw std::runtime_error(path+":"+std::strerror(errno));
     50     }
     51     T buf;
     52     int lines = 0;
     53     while (1) {
     54         std::string str;
     55         std::getline(ifs, str);
     56         if (!str.empty()) {
     57             int c = lines % 4;
     58             if (c==0) {
     59                 Machine m;
     60                 m.btnA.fromStr(str);
     61                 buf.push_back(m);
     62             }
     63             if (c==1) buf.back().btnB.fromStr(str);
     64             if (c==2) buf.back().setPrize(str);
     65         }
     66         if (!ifs) break;
     67         lines++;
     68     }
     69     return buf;
     70 }
     71 
     72 bool simulate(const Machine &m, int64_t pA, int64_t pB, std::vector<int64_t> &out) {
     73     int64_t curX = m.btnA.x*pA + m.btnB.x*pB;
     74     int64_t curY = m.btnA.y*pA + m.btnB.y*pB;
     75     if (curX>m.prize.x||curY>m.prize.y) return false;
     76     if (curX==m.prize.x&&curY==m.prize.y) {
     77         out.push_back(pA*3+pB);
     78     }
     79     return true;
     80 }
     81 
     82 int64_t part1(const Data &input [[ maybe_unused ]]) {
     83     int64_t res = 0;
     84     for (auto &m:input) {
     85         std::vector<int64_t> runs;
     86         for (int a=0;a<100;a++) {
     87             for (int b=0;b<100;b++) {
     88                 if (!simulate(m, a, b, runs)) break;
     89             }
     90         }
     91         std::sort(runs.begin(), runs.end());
     92         if (!runs.empty()) res += runs.back();
     93     }
     94 
     95     return res;
     96 }
     97 
     98 int64_t part2(Data input [[ maybe_unused ]]) {
     99     int64_t res = 0;
    100     for (auto &m:input) {
    101         m.prize.x += 10000000000000;
    102         m.prize.y += 10000000000000;
    103         int64_t pA = (m.prize.x*m.btnB.y-m.prize.y*m.btnB.x)/(m.btnA.x*m.btnB.y-m.btnA.y*m.btnB.x);
    104         int64_t pB = (m.prize.y*m.btnA.x-m.prize.x*m.btnA.y)/(m.btnA.x*m.btnB.y-m.btnA.y*m.btnB.x);
    105         Vec2 c;
    106         c.x = m.btnA.x*pA + m.btnB.x*pB;
    107         c.y = m.btnA.y*pA + m.btnB.y*pB;
    108         if (c==m.prize) {
    109             res += pA*3+pB;
    110         }
    111     }
    112     return res;
    113 }
    114 
    115 int main(int argc, char **argv) {
    116     Performance perf;
    117     const std::string fname = argc>1 ? argv[1] : "test1.txt";
    118     std::cout << "AoC 2024 day 13 " << fname << std::endl;
    119     Data input = read_file<Data>(fname);
    120     std::cout << "part1: " << part1(input) << std::endl;
    121     std::cout << "part2: " << part2(input) << std::endl;
    122     return 0;
    123 }