Line data    Source code

       1              : #include "PuzzleImpl.h"
       2              : 
       3              : #include "LinewiseInput.h"
       4              : #include "Parsing.h"
       5              : 
       6              : #include <algorithm>
       7              : #include <string_view>
       8              : #include <vector>
       9              : 
      10              : namespace {
      11              : 
      12              : struct Range {
      13              :   uint64_t begin;
      14              :   uint64_t end;
      15              : 
      16            0 :   [[nodiscard]] bool contains(uint64_t value) const { return value >= begin && value < end; }
      17            0 :   [[nodiscard]] bool intersects(Range const &other) const {
      18            0 :     return begin < other.end && end > other.begin;
      19            0 :   }
      20           78 :   [[nodiscard]] uint64_t size() const { return end - begin; }
      21              : };
      22              : 
      23              : auto parse(std::string_view const input) {
      24              :   LinewiseInput lines{input};
      25              :   auto blankLineIt = std::ranges::find(lines, "");
      26              :   std::vector<Range> ranges;
      27              :   ranges.reserve(std::distance(lines.begin(), blankLineIt));
      28              :   for (auto it = lines.begin(); it != blankLineIt; ++it) {
      29              :     auto dashIt = std::ranges::find(*it, '-');
      30              :     ranges.emplace_back(parseInt<uint64_t>({it->begin(), dashIt}),
      31              :                         parseInt<uint64_t>({std::next(dashIt), it->end()}) + 1u);
      32              :   }
      33              :   std::vector<uint64_t> ids;
      34              :   ids.reserve(std::distance(std::next(blankLineIt), lines.end()));
      35              :   for (auto it = std::next(blankLineIt); it != lines.end(); ++it) {
      36              :     ids.push_back(parseInt<uint64_t>(*it));
      37              :   }
      38              :   return std::make_tuple(std::move(ranges), std::move(ids));
      39              : }
      40              : 
      41            2 : void sortAndMergeRanges(std::vector<Range> &ranges) {
      42            2 :   std::ranges::sort(ranges, {}, &Range::begin);
      43              : 
      44            2 :   auto outIt = ranges.begin();
      45          158 :   for (auto it = ranges.begin(); it != ranges.end();) {
      46          156 :     *outIt = *it++;
      47          374 :     for (; it != ranges.end() && it->begin <= outIt->end; ++it) {
      48          218 :       outIt->end = std::max(outIt->end, it->end);
      49          218 :     }
      50          156 :     ++outIt;
      51          156 :   }
      52              : 
      53            2 :   ranges.erase(outIt, ranges.end());
      54            2 : }
      55              : 
      56              : } // namespace
      57              : 
      58            1 : template <> std::string solvePart1<2025, 5>(std::string_view const input) {
      59            1 :   auto [ranges, ids] = parse(input);
      60            1 :   sortAndMergeRanges(ranges);
      61            1 :   std::ranges::sort(ids);
      62            1 :   uint64_t cnt = 0;
      63            1 :   auto rangeIt = ranges.begin();
      64            1 :   auto idIt = ids.begin();
      65         1078 :   while (rangeIt != ranges.end() && idIt != ids.end()) {
      66         1077 :     if (*idIt < rangeIt->begin) {
      67          138 :       ++idIt;
      68          939 :     } else if (*idIt >= rangeIt->end) {
      69           77 :       ++rangeIt;
      70          862 :     } else {
      71          862 :       ++cnt;
      72          862 :       ++idIt;
      73          862 :     }
      74         1077 :   }
      75            1 :   return std::to_string(cnt);
      76            1 : }
      77              : 
      78            1 : template <> std::string solvePart2<2025, 5>(std::string_view const input) {
      79            1 :   auto [ranges, _] = parse(input);
      80            1 :   sortAndMergeRanges(ranges);
      81              : 
      82            1 :   return std::to_string(std::ranges::fold_left(ranges | std::views::transform(&Range::size),
      83            1 :                                                uint64_t{0}, std::plus{}));
      84            1 : }