Line data    Source code

       1              : #include "IntegerCast.h"
       2              : #include "LinewiseInput.h"
       3              : #include "PuzzleImpl.h"
       4              : 
       5              : #include <libassert/assert.hpp>
       6              : 
       7              : #include <algorithm>
       8              : #include <cctype>
       9              : #include <cstdint>
      10              : #include <iostream>
      11              : #include <numeric>
      12              : #include <string_view>
      13              : 
      14              : namespace {
      15              : 
      16          300 : char commonElement(std::string_view const contents) {
      17          300 :   auto middle = std::next(contents.begin(), integerCast<int64_t>(contents.size() / 2u));
      18          300 :   std::string a{contents.begin(), middle};
      19          300 :   std::string b{middle, contents.end()};
      20          300 :   std::ranges::sort(a);
      21          300 :   std::ranges::sort(b);
      22          300 :   auto aIt = a.begin();
      23          300 :   auto bIt = b.begin();
      24         4686 :   while (aIt != a.end() && bIt != b.end()) {
      25         4686 :     if (*aIt < *bIt)
      26         2210 :       ++aIt;
      27         2476 :     else if (*bIt < *aIt)
      28         2176 :       ++bIt;
      29          300 :     else
      30          300 :       return *aIt;
      31         4686 :   }
      32          300 :   PANIC("No common element!");
      33            0 : }
      34              : 
      35          100 : char findBadge(std::span<std::string_view const, 3u> const contents) {
      36          100 :   std::string result{contents.front()};
      37          100 :   std::ranges::sort(result);
      38              : 
      39          300 :   for (size_t i = 1; i < contents.size(); ++i) {
      40          200 :     std::string tmp{contents[i]};
      41          200 :     std::ranges::sort(tmp);
      42          200 :     result.erase(std::ranges::set_intersection(result, tmp, result.begin()).out, result.end());
      43          200 :   }
      44          100 :   ASSUME(!result.empty(), contents, result);
      45          100 :   ASSUME(result.front() == result.back(), contents, result);
      46          100 :   return result.front();
      47          100 : }
      48              : 
      49          400 : size_t priority(char const c) { return (std::islower(c)) ? 1u + c - 'a' : 27u + c - 'A'; }
      50              : 
      51              : } // namespace
      52              : 
      53            1 : template <> size_t part1<2022, 3>(std::string_view const input) {
      54            1 :   LinewiseInput const lines(input);
      55            1 :   return std::transform_reduce(
      56            1 :       lines.begin(), lines.end(), size_t(0), std::plus{},
      57          300 :       [](std::string_view const line) { return priority(commonElement(line)); });
      58            1 : }
      59              : 
      60            1 : template <> size_t part2<2022, 3>(std::string_view const input) {
      61            1 :   LinewiseInput const lines(input);
      62              : 
      63            1 :   std::vector<std::span<std::string_view const, 3u>> groups;
      64            1 :   groups.reserve(lines.size() / 3u);
      65          101 :   for (auto it = lines.begin(); it < lines.end(); it += 3) {
      66          100 :     groups.emplace_back(it, std::next(it, 3));
      67          100 :   }
      68              : 
      69            1 :   return std::transform_reduce(
      70            1 :       groups.begin(), groups.end(), size_t(0), std::plus{},
      71          100 :       [](std::span<std::string_view const, 3u> const group) { return priority(findBadge(group)); });
      72            1 : }