advent2024

main.cpp (4633B)

---

 #include <iostream>
 #include <filesystem>
 #include <fstream>
 #include <vector>
 #include <cstring>
 #include <cstdio>
 #include <tuple>
 #include <algorithm>
 #include <deque>
 #include <iterator>
 #include <chrono>
 #include "utils.hpp"
 
 enum class SlotType {
     file,
     space
 };
 
 class Slot {
 public:
     SlotType type;
     int len;
     int id;
     bool moved = false;
 
     Slot(SlotType _type, int _len, int _id=-1):type(_type),len(_len),id(_id) {}
 
     bool isSpace() const { return type==SlotType::space; }
     bool isFile() const { return type==SlotType::file; }
 };
 
 typedef std::vector<Slot> 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));
     }
     std::uintmax_t size = std::filesystem::file_size(path);
     std::vector<char> buf(size);
     if (!ifs.read((char *)buf.data(), buf.size())) {
         throw std::runtime_error(path+":"+std::strerror(errno));
     }
     T out;
     int id=0;
     for (int i=0; i<(int)buf.size(); ++i) {
         char c = buf[i];
         if (c-'0'>=0) {
             if (i%2==1) {
                 out.push_back(Slot(SlotType::space, c-'0'));
             } else {
                 out.push_back(Slot(SlotType::file, c-'0', id++));
             }
         }
     }
     return out;
 }
 
 bool checkEmptySpaces(const Data &input) {
     for (auto it=input.rbegin(); it!=input.rend(); ++it) {
         if (it->isSpace() && it->len>0) return true;
     }
     return false;
 }
 
 void cleanEmptySpaces(Data &input) {
     for (auto it=input.begin(); it!=input.end();) {
         if (it->isSpace() && it->len==0) {
             it = input.erase(it);
         } else {
             it++;
         }
     }
 }
 
 void trimSpace(Data &input) {
     if (input.back().isSpace()) {
         //std::printf("trimSpace()\n");
         input.pop_back();
     }
 }
 
 void printInput(const Data &input) {
     for (auto &s:input) {
         if (s.isSpace()){
             std::printf("[ :%d]", s.len);
         } else {
             std::printf("[%d:%d]", s.id, s.len);
         }
     }
     std::cout << std::endl;
 }
 
 int64_t checksum(const Data &input) {
     int64_t sum = 0;
     int64_t i = 0;
     for (auto s:input) {
         int64_t im = i+s.len;
         for (; i<im; ++i) {
             if (s.isFile()) sum+=(s.id*i);
         }
     }
     return sum;
 }
 
 void mergeSpaces(Data &input) {
     for (auto its=input.begin(); its!=input.end();) {
         auto itn = std::next(its, 1);
         if (its->isSpace() && itn!=input.end() && itn->isSpace()) {
             its->len += itn->len;
             its = input.erase(itn);
         } else its++;
     }
 
 }
 
 int64_t part1(Data input) {
     while (checkEmptySpaces(input)) {
         trimSpace(input);
         for (auto it=input.begin(); it!=input.end(); ++it) {
             if (it->isSpace()&&it->len>0) {
                 if (it->len>=input.back().len) {
                     auto tr = input.insert(it, input.back());
                     it = std::next(tr, 1);
                     it->len -= tr->len;
                     input.pop_back();
                 } else {
                     auto tr = input.insert(std::next(it, 1), input.back());
                     it = std::prev(tr, 1);
                     input.back().len -= it->len;
                     tr->len = it->len;
                     it->len = 0;
                 }
                 break;
             }
         }
         cleanEmptySpaces(input);
     }
     cleanEmptySpaces(input);
     return checksum(input);
 }
 
 int64_t part2(Data input) {
     for (auto itf=input.rbegin(); itf!=input.rend(); itf=std::find_if(input.rbegin(), input.rend(), [](auto s){ return s.isFile()&&!s.moved; }))
     {
         auto its = std::find_if(input.begin(), input.end(), [&itf](auto s){
             return s.isSpace() && s.len>=itf->len;
         });
         if (its!=input.end()&&std::distance(its, itf.base())>0) {
             Slot fc = *itf;
             itf->type = SlotType::space;
             itf->id = -1;
             its->len -= itf->len;
             auto tr = input.insert(its, fc);
             tr->moved = true;
         } else {
             itf->moved = true;
         }
         cleanEmptySpaces(input);
         mergeSpaces(input);
     }
 
     return checksum(input);
 }
 
 int main(int argc, char **argv) {
     Performance perf;
     const std::string fname = argc>1 ? argv[1] : "test1.txt";
     std::cout << "AoC 2024 day 09 " << fname << std::endl;
     Data input = read_file<Data>(fname);
     std::cout << "part1: " << part1(input) << std::endl;
     std::cout << "part2: " << part2(input) << std::endl;
 
     return 0;
 }