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