Line data    Source code

       1              : #include "Parsing.h"
       2              : #include "PuzzleImpl.h"
       3              : 
       4              : #include <libassert/assert.hpp>
       5              : #include <re2/re2.h>
       6              : 
       7              : #include <algorithm>
       8              : #include <iostream>
       9              : #include <numeric>
      10              : #include <string>
      11              : #include <string_view>
      12              : 
      13              : namespace {
      14              : 
      15        31645 : size_t hash(size_t h, char const c) {
      16        31645 :   h += static_cast<size_t>(c);
      17        31645 :   h *= size_t(17);
      18        31645 :   h %= size_t(256);
      19              : 
      20        31645 :   return h;
      21        31645 : }
      22              : 
      23         8000 : size_t hash(std::string_view const s) {
      24         8000 :   size_t h = 0;
      25         8000 :   for (char const c : s)
      26        31645 :     h = hash(h, c);
      27         8000 :   return h;
      28         8000 : }
      29              : 
      30              : class HashMap {
      31              :   using Bucket = std::vector<std::pair<std::string_view, unsigned>>;
      32              : 
      33              : public:
      34         2007 :   void emplace(std::string_view const label, unsigned value) {
      35         2007 :     Bucket &bucket = _buckets[hash(label)];
      36              : 
      37         2289 :     auto it = std::ranges::find_if(bucket, [label](auto const &p) { return label == p.first; });
      38              : 
      39         2007 :     if (it == bucket.end())
      40         1136 :       bucket.emplace_back(label, value);
      41          871 :     else
      42          871 :       it->second = value;
      43         2007 :   }
      44              : 
      45         1993 :   void erase(std::string_view const label) {
      46         1993 :     Bucket &bucket = _buckets[hash(label)];
      47              : 
      48         2188 :     auto it = std::ranges::find_if(bucket, [label](auto const &p) { return label == p.first; });
      49              : 
      50         1993 :     if (it != bucket.end())
      51          889 :       bucket.erase(it);
      52         1993 :   }
      53              : 
      54            0 :   [[maybe_unused]] friend std::ostream &operator<<(std::ostream &oss, HashMap const &map) {
      55            0 :     for (size_t i = 0; i < map._buckets.size(); ++i) {
      56            0 :       if (map._buckets[i].empty())
      57            0 :         continue;
      58            0 :       oss << "Box " << i << ": ";
      59            0 :       for (auto const &[k, v] : map._buckets[i]) {
      60            0 :         oss << "[" << k << " " << size_t(v) << "] ";
      61            0 :       }
      62            0 :       oss << "\n";
      63            0 :     }
      64            0 :     return oss;
      65            0 :   }
      66              : 
      67            1 :   [[nodiscard]] size_t focussingPower() const {
      68            1 :     size_t r = 0;
      69            1 :     size_t i = 1;
      70          256 :     for (Bucket const &bucket : _buckets) {
      71          256 :       size_t j = 1;
      72          256 :       for (auto const &[k, v] : bucket) {
      73          247 :         r += i * j * static_cast<size_t>(v);
      74          247 :         ++j;
      75          247 :       }
      76          256 :       ++i;
      77          256 :     }
      78            1 :     return r;
      79            1 :   }
      80              : 
      81              : private:
      82              :   std::array<Bucket, 256u> _buckets;
      83              : };
      84              : 
      85         4000 : void performOperation(std::string_view const input, HashMap &map) {
      86         4000 :   static RE2 const pattern = R"(([a-z]+)([-=])(\d?))";
      87         4000 :   std::string_view label;
      88         4000 :   char op = 0;
      89         4000 :   std::optional<unsigned> value;
      90         4000 :   RE2::FullMatch(input, pattern, &label, &op, &value);
      91              : 
      92         4000 :   switch (op) {
      93         2007 :   case '=':
      94         2007 :     if (!value)
      95         2007 :       PANIC(input);
      96         2007 :     else
      97         2007 :       map.emplace(label, *value);
      98         2007 :     break;
      99         1993 :   case '-':
     100         1993 :     map.erase(label);
     101         1993 :     break;
     102            0 :   default:
     103            0 :     PANIC(input);
     104         4000 :   };
     105         4000 : }
     106              : 
     107              : } // namespace
     108              : 
     109            1 : template <> std::string solvePart1<2023, 15>(std::string_view const input) {
     110            1 :   std::vector<std::string_view> inputs = split(input, ',');
     111              : 
     112            1 :   return std::to_string(std::transform_reduce(inputs.begin(), inputs.end(), size_t(0),
     113            1 :                                               std::plus<>(),
     114         4000 :                                               [](std::string_view const s) { return hash(s); }));
     115            1 : }
     116              : 
     117            1 : template <> std::string solvePart2<2023, 15>(std::string_view const input) {
     118            1 :   std::vector<std::string_view> inputs = split(input, ',');
     119              : 
     120            1 :   HashMap map;
     121         4000 :   for (auto const &in : inputs) {
     122         4000 :     performOperation(in, map);
     123         4000 :   }
     124              : 
     125              :   // std::cout << map;
     126              : 
     127            1 :   return std::to_string(map.focussingPower());
     128            1 : }