Line data    Source code

       1              : #include "Grid2d.h"
       2              : #include "LinewiseInput.h"
       3              : #include "Parsing.h"
       4              : #include "PuzzleImpl.h"
       5              : 
       6              : #include <fmt/format.h>
       7              : #include <fmt/ranges.h>
       8              : 
       9              : #include <libassert/assert.hpp>
      10              : 
      11              : #include <ranges>
      12              : #include <vector>
      13              : 
      14              : namespace {
      15              : using Rules = Grid2d<char>;
      16              : using Update = std::vector<int>;
      17              : using Updates = std::vector<Update>;
      18              : 
      19            2 : Rules parseRules(std::string_view const input) {
      20            2 :   Grid2d<char> rules(100, 100, 0);
      21              : 
      22         2352 :   auto tuples = input | std::views::split('\n') | std::views::transform([](auto &&r) {
      23         2352 :                   return r | std::views::split('|') |
      24         4704 :                          std::views::transform([](auto &&s) { return parseInt<int>(s); }) |
      25         2352 :                          std::views::adjacent<2>;
      26         2352 :                 }) |
      27            2 :                 std::views::join;
      28              : 
      29         2352 :   for (auto [x, y] : tuples) {
      30         2352 :     rules[x, y] = 1;
      31         2352 :   }
      32              : 
      33            2 :   return rules;
      34            2 : }
      35              : 
      36            2 : Updates parseUpdates(std::string_view const input) {
      37            2 :   Updates updates;
      38              : 
      39          400 :   for (auto &&line : input | std::views::split('\n')) {
      40          400 :     updates.push_back(parseIntegerRange<int>(std::string_view{line}));
      41          400 :   }
      42              : 
      43            2 :   return updates;
      44            2 : }
      45              : 
      46            2 : std::tuple<Rules, std::vector<Update>> parse(std::string_view const input) {
      47              : 
      48            2 :   auto breaks = std::ranges::search(input, std::string_view("\n\n"));
      49              : 
      50            2 :   ASSUME(!breaks.empty());
      51              : 
      52            2 :   return std::make_tuple(parseRules({input.begin(), breaks.begin()}),
      53            2 :                          parseUpdates({breaks.end(), input.end()}));
      54            2 : }
      55              : 
      56          400 : bool isValid(Update const &update, Rules const &rules) {
      57         3754 :   for (auto it = update.begin(); it != update.end(); ++it) {
      58        29944 :     for (auto it2 = std::next(it); it2 != update.end(); ++it2) {
      59        26590 :       if (rules[*it2, *it] == 1)
      60          172 :         return false;
      61        26590 :     }
      62         3526 :   }
      63          228 :   return true;
      64          400 : }
      65              : 
      66           86 : void sort(Update &update, Rules const &rules) {
      67         1422 :   for (auto it = update.begin(); it != update.end(); ++it) {
      68        38143 :     for (auto it2 = std::next(it); it2 != update.end(); ++it2) {
      69        36807 :       if (rules[*it2, *it] == 1) {
      70         5495 :         std::iter_swap(it, it2);
      71         5495 :         it2 = it;
      72         5495 :       }
      73        36807 :     }
      74         1336 :   }
      75           86 : }
      76              : 
      77          200 : int middleElement(Update const &update) { return update[update.size() / 2]; }
      78              : 
      79              : } // namespace
      80              : 
      81            1 : template <> size_t part1<2024, 5>(std::string_view const input) {
      82            1 :   auto [rules, updates] = parse(input);
      83              : 
      84            1 :   uint64_t sum = 0;
      85          200 :   for (auto const &u : updates) {
      86          200 :     if (isValid(u, rules))
      87          114 :       sum += middleElement(u);
      88          200 :   }
      89            1 :   return sum;
      90            1 : }
      91              : 
      92            1 : template <> size_t part2<2024, 5>(std::string_view const input) {
      93            1 :   auto [rules, updates] = parse(input);
      94              : 
      95            1 :   uint64_t sum = 0;
      96          200 :   for (auto &u : updates) {
      97          200 :     if (!isValid(u, rules)) {
      98           86 :       sort(u, rules);
      99           86 :       sum += middleElement(u);
     100           86 :     }
     101          200 :   }
     102            1 :   return sum;
     103            1 : }