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