Line data    Source code

       1              : #include "IntegerCast.h"
       2              : #include "LinewiseInput.h"
       3              : #include "Parsing.h"
       4              : #include "PuzzleImpl.h"
       5              : 
       6              : #include <libassert/assert.hpp>
       7              : #include <re2/re2.h>
       8              : 
       9              : #include <algorithm>
      10              : #include <cstdint>
      11              : #include <vector>
      12              : 
      13              : namespace {
      14              : 
      15              : // interval [begin, end)
      16              : struct ValueRange {
      17              :   uint64_t begin = 0;
      18              :   uint64_t end = 0;
      19              : };
      20              : 
      21              : class Map {
      22              : public:
      23           14 :   Map(auto begin, auto end) {
      24           14 :     static RE2 const headerPattern = R"((\w+)-to-(\w+) map:)";
      25           14 :     ASSUME(RE2::FullMatch(*begin, headerPattern, &_srcCategory, &_dstCategory));
      26           14 :     _ranges.assign(std::next(begin), end);
      27         5428 :     std::ranges::sort(_ranges, std::ranges::less{}, [](auto const &r) { return r.src.begin; });
      28           14 :   }
      29              : 
      30          140 :   uint64_t operator()(uint64_t const i) const {
      31          140 :     auto it = std::ranges::upper_bound(_ranges, i, std::ranges::less{},
      32          721 :                                        [](auto const &r) { return r.src.end; });
      33          140 :     if (it < _ranges.end() && i >= it->src.begin) {
      34          134 :       return i + it->offset;
      35          134 :     } else {
      36            6 :       return i;
      37            6 :     }
      38          140 :   }
      39              : 
      40          681 :   void operator()(ValueRange const r, auto out) const {
      41         1103 :     for (uint64_t i = r.begin; i < r.end;) {
      42         1067 :       auto it = std::upper_bound(_ranges.begin(), _ranges.end(), i,
      43         5734 :                                  [](uint64_t const x, Range const &r) { return x < r.src.end; });
      44         1067 :       if (it == _ranges.end()) {
      45            0 :         out++ = ValueRange(i, r.end);
      46            0 :         break;
      47         1067 :       } else if (i >= it->src.begin) {
      48         1021 :         if (r.end <= it->src.end) {
      49          645 :           out++ = ValueRange(i + it->offset, r.end + it->offset);
      50          645 :           break;
      51          645 :         } else {
      52          376 :           out++ = ValueRange(i + it->offset, it->src.end + it->offset);
      53          376 :           i = it->src.end;
      54          376 :         }
      55         1021 :       } else {
      56           46 :         out++ = ValueRange(i, it->src.begin);
      57           46 :         i = it->src.begin;
      58           46 :       }
      59         1067 :     }
      60          681 :   }
      61              : 
      62              : private:
      63              :   struct Range {
      64          464 :     Range(std::string_view const s) {
      65          464 :       static RE2 const rangePattern = R"((\d+) (\d+) (\d+))";
      66          464 :       uint64_t dstStart = 0;
      67          464 :       uint64_t size = 0;
      68          464 :       ASSUME(RE2::FullMatch(s, rangePattern, &dstStart, &src.begin, &size));
      69          464 :       src.end = src.begin + size;
      70          464 :       offset = integerCast<int64_t>(dstStart) - integerCast<int64_t>(src.begin);
      71          464 :     }
      72              : 
      73              :     ValueRange src;
      74              :     int64_t offset = 0;
      75              :   };
      76              : 
      77              :   std::string _srcCategory;
      78              :   std::string _dstCategory;
      79              :   std::vector<Range> _ranges;
      80              : };
      81              : 
      82            1 : std::vector<uint64_t> parseSeeds(std::string_view s) {
      83            1 :   ASSUME(RE2::Consume(&s, "seeds: "));
      84            1 :   s.remove_prefix(s.find(':') + 1u);
      85            1 :   return parseRange<uint64_t>(s);
      86            1 : }
      87              : 
      88            1 : std::vector<ValueRange> parseSeedRanges(std::string_view s) {
      89            1 :   static RE2 const numberPattern = R"((\d+) (\d+) ?)";
      90              : 
      91            1 :   ASSUME(RE2::Consume(&s, "seeds: "));
      92            1 :   std::vector<ValueRange> seeds;
      93            1 :   ValueRange seedRange;
      94            1 :   uint64_t size = 0;
      95           11 :   while (RE2::Consume(&s, numberPattern, &seedRange.begin, &size)) {
      96           10 :     seedRange.end = seedRange.begin + size;
      97           10 :     seeds.push_back(seedRange);
      98           10 :   }
      99            1 :   return seeds;
     100            1 : }
     101              : 
     102            2 : std::vector<Map> parseMaps(auto begin, auto end) {
     103            2 :   std::vector<Map> maps;
     104              : 
     105           30 :   for (auto it = begin; it != end;) {
     106           28 :     if (it->empty()) {
     107           14 :       ++it;
     108           14 :       continue;
     109           14 :     }
     110           14 :     auto rangeBegin = it;
     111          476 :     it = std::find_if(std::next(it), end, [](std::string_view s) { return s.empty(); });
     112           14 :     maps.emplace_back(rangeBegin, it);
     113           14 :   }
     114              : 
     115            2 :   return maps;
     116            2 : }
     117              : } // namespace
     118              : 
     119            1 : template <> size_t part1<2023, 5>(std::string_view const input) {
     120            1 :   LinewiseInput const lines(input);
     121              : 
     122            1 :   auto it = lines.begin();
     123            1 :   std::vector<uint64_t> seeds = parseSeeds(*it++);
     124            1 :   std::vector<Map> maps = parseMaps(it, lines.end());
     125              : 
     126            1 :   std::vector<ValueRange> tmp;
     127            7 :   for (auto const &map : maps) {
     128            7 :     std::ranges::transform(seeds, seeds.begin(), map);
     129            7 :   }
     130              : 
     131            1 :   return *std::ranges::min_element(seeds);
     132            1 : }
     133              : 
     134            1 : template <> size_t part2<2023, 5>(std::string_view const input) {
     135            1 :   LinewiseInput const lines(input);
     136              : 
     137            1 :   auto it = lines.begin();
     138            1 :   std::vector<ValueRange> seedRanges = parseSeedRanges(*it++);
     139            1 :   std::vector<Map> maps = parseMaps(it, lines.end());
     140              : 
     141            1 :   std::vector<ValueRange> tmp;
     142            7 :   for (auto const &map : maps) {
     143            7 :     tmp.reserve(seedRanges.size() * 2u);
     144          681 :     for (auto const &seedRange : seedRanges) {
     145          681 :       map(seedRange, std::back_inserter(tmp));
     146          681 :     }
     147            7 :     seedRanges.swap(tmp);
     148            7 :     tmp.clear();
     149            7 :   }
     150              : 
     151            1 :   auto minIt = std::ranges::min_element(seedRanges, std::ranges::less{}, &ValueRange::begin);
     152              : 
     153            1 :   return minIt->begin;
     154            1 : }