Line data    Source code

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