Line data    Source code

       1              : #include "Grid2d.h"
       2              : #include "LinewiseInput.h"
       3              : #include "Parsing.h"
       4              : #include "PuzzleImpl.h"
       5              : 
       6              : #include <absl/container/flat_hash_set.h>
       7              : #include <libassert/assert.hpp>
       8              : #include <re2/re2.h>
       9              : 
      10              : #include <cstdint>
      11              : #include <iostream>
      12              : #include <limits>
      13              : #include <string>
      14              : #include <string_view>
      15              : 
      16              : namespace {
      17              : 
      18              : using Coord = Vec2<int64_t>;
      19              : 
      20              : enum Dir : uint8_t { R = 0, D = 1, L = 2, U = 3 };
      21              : 
      22         1248 : Coord stencil(Dir dir) {
      23         1248 :   switch (dir) {
      24          303 :   case R:
      25          303 :     return {1, 0};
      26          318 :   case D:
      27          318 :     return {0, -1};
      28          321 :   case L:
      29          321 :     return {-1, 0};
      30          306 :   case U:
      31          306 :     return {0, 1};
      32            0 :   default:
      33            0 :     UNREACHABLE();
      34         1248 :   };
      35            0 : }
      36              : 
      37            1 : std::vector<std::pair<Dir, int>> parsePt1(std::string_view const input) {
      38            1 :   LinewiseInput lines(input);
      39              : 
      40            1 :   std::vector<std::pair<Dir, int>> result;
      41            1 :   result.reserve(lines.size());
      42              : 
      43            1 :   std::array<Dir, 128u> dirMap{};
      44            1 :   dirMap['R'] = R;
      45            1 :   dirMap['D'] = D;
      46            1 :   dirMap['L'] = L;
      47            1 :   dirMap['U'] = U;
      48              : 
      49            1 :   static RE2 const pattern = R"(([RLUD]) (\d+) \(#[a-z0-9]{6}\))";
      50              : 
      51          624 :   for (std::string_view line : lines) {
      52          624 :     char d = 0;
      53          624 :     int length = 0;
      54          624 :     ASSUME(RE2::FullMatch(line, pattern, &d, &length));
      55          624 :     result.emplace_back(dirMap[d], length);
      56          624 :   }
      57              : 
      58            1 :   return result;
      59            1 : }
      60              : 
      61            1 : std::vector<std::pair<Dir, int>> parsePt2(std::string_view const input) {
      62            1 :   LinewiseInput lines(input);
      63              : 
      64            1 :   std::vector<std::pair<Dir, int>> result;
      65            1 :   result.reserve(lines.size());
      66              : 
      67            1 :   static RE2 const pattern = R"([RLUD] \d+ \(#([a-z0-9]{5})([0-3])\))";
      68              : 
      69          624 :   for (std::string_view line : lines) {
      70          624 :     std::string_view lengthHexStr;
      71          624 :     int d = 0;
      72          624 :     ASSUME(RE2::FullMatch(line, pattern, &lengthHexStr, &d));
      73          624 :     result.emplace_back(Dir(d), parseHexInt<int>(lengthHexStr));
      74          624 :   }
      75              : 
      76            1 :   return result;
      77            1 : }
      78              : 
      79              : struct Horiziontal {
      80              :   int line;
      81              :   int offset;
      82              :   int length;
      83              : };
      84              : 
      85            2 : std::vector<Coord> getVertices(std::vector<std::pair<Dir, int>> const &digInstructions) {
      86              : 
      87            2 :   Coord pos{0, 0};
      88              : 
      89            2 :   std::vector<Coord> result;
      90            2 :   result.reserve(digInstructions.size());
      91              : 
      92            2 :   result.push_back(pos);
      93         1248 :   for (auto const &instruction : digInstructions) {
      94         1248 :     pos += instruction.second * stencil(instruction.first);
      95         1248 :     result.push_back(pos);
      96         1248 :   }
      97              : 
      98            2 :   return result;
      99            2 : }
     100              : 
     101            2 : size_t gaussianArea(std::vector<Coord> const &coords) {
     102            2 :   int64_t area = 0;
     103         1250 :   for (size_t i = 0; i < coords.size() - 1u; ++i) {
     104         1248 :     area += (coords[i].y() + coords[i + 1].y()) * (coords[i].x() - coords[i + 1].x());
     105         1248 :   }
     106            2 :   area = std::abs(area / 2);
     107              : 
     108            2 :   int64_t perimeter = 0;
     109         1250 :   for (size_t i = 0; i < coords.size() - 1u; ++i) {
     110         1248 :     perimeter +=
     111         1248 :         std::abs(coords[i].y() - coords[i + 1].y()) + std::abs(coords[i].x() - coords[i + 1].x());
     112         1248 :   }
     113              : 
     114            2 :   return integerCast<size_t>(area + perimeter / 2 + 1);
     115            2 : }
     116              : 
     117              : } // namespace
     118              : 
     119            1 : template <> std::string solvePart1<2023, 18>(std::string_view const input) {
     120            1 :   auto digInstructions = parsePt1(input);
     121            1 :   auto vertices = getVertices(digInstructions);
     122            1 :   return std::to_string(gaussianArea(vertices));
     123            1 : }
     124              : 
     125            1 : template <> std::string solvePart2<2023, 18>(std::string_view const input) {
     126            1 :   auto digInstructions = parsePt2(input);
     127            1 :   auto vertices = getVertices(digInstructions);
     128            1 :   return std::to_string(gaussianArea(vertices));
     129            1 : }