Line data    Source code

       1              : #include "PuzzleImpl.h"
       2              : 
       3              : #include <algorithm>
       4              : #include <ranges>
       5              : #include <vector>
       6              : 
       7              : namespace {
       8              : 
       9              : struct File {
      10              :   int idx;
      11              :   int size;
      12              :   int pos;
      13              : };
      14              : 
      15              : struct FreeSpace {
      16              :   int size;
      17              :   int pos;
      18              : };
      19              : 
      20              : } // namespace
      21              : 
      22            1 : template <> size_t part1<2024, 9>(std::string_view const input) {
      23            1 :   int constexpr FREE = -1;
      24              : 
      25            1 :   std::vector<int> deflated;
      26            1 :   int fileIdx = 0;
      27        10000 :   for (auto it = input.begin(); it != input.end(); ++it) {
      28        10000 :     deflated.insert(deflated.end(), *it++ - '0', fileIdx++);
      29        10000 :     if (it == input.end())
      30            1 :       break;
      31         9999 :     deflated.insert(deflated.end(), *it - '0', FREE);
      32         9999 :   }
      33              : 
      34        44797 :   auto notFree = [](int const i) { return i != FREE; };
      35            1 :   auto left = std::ranges::find(deflated, FREE);
      36            1 :   auto right = std::ranges::find_last_if(deflated, notFree).begin();
      37              : 
      38        23779 :   while (left < right) {
      39        23778 :     std::iter_swap(left, right);
      40        23778 :     left = std::ranges::find(std::next(left), deflated.end(), FREE);
      41        23778 :     right = std::ranges::find_last_if(deflated.begin(), right, notFree).begin();
      42        23778 :   }
      43              : 
      44            1 :   size_t checksum = 0;
      45        94972 :   for (size_t i = 0; i < deflated.size(); ++i) {
      46        94971 :     if (deflated[i] != FREE)
      47        50175 :       checksum += i * static_cast<size_t>(deflated[i]);
      48        94971 :   }
      49              : 
      50            1 :   return checksum;
      51            1 : }
      52              : 
      53            1 : template <> size_t part2<2024, 9>(std::string_view const input) {
      54            1 :   std::vector<File> fileList;
      55            1 :   std::vector<FreeSpace> freeList;
      56              : 
      57            1 :   int fileIdx = 0;
      58            1 :   int pos = 0;
      59        10000 :   for (auto it = input.begin(); it != input.end(); ++it) {
      60        10000 :     int size = *it++ - '0';
      61        10000 :     fileList.emplace_back(fileIdx++, size, pos);
      62        10000 :     pos += size;
      63        10000 :     if (it == input.end())
      64            1 :       break;
      65         9999 :     size = *it - '0';
      66         9999 :     if (size > 0) {
      67         9008 :       freeList.emplace_back(size, pos);
      68         9008 :       pos += size;
      69         9008 :     }
      70         9999 :   }
      71              : 
      72            1 :   size_t checksum = 0;
      73        10000 :   for (auto &file : fileList | std::views::reverse) {
      74        10000 :     auto it = freeList.begin();
      75      1462121 :     while (it->pos < file.pos && it->size < file.size)
      76      1452121 :       ++it;
      77              : 
      78        10000 :     if (it->pos < file.pos) {
      79         4901 :       file.pos = it->pos;
      80         4901 :       it->pos += file.size;
      81         4901 :       it->size -= file.size;
      82         4901 :     }
      83        10000 :     if (it->size == 0)
      84         4614 :       freeList.erase(it);
      85              : 
      86        60175 :     for (int i = 0; i < file.size; ++i)
      87        50175 :       checksum += static_cast<size_t>((file.pos + i)) * static_cast<size_t>(file.idx);
      88        10000 :   }
      89              : 
      90            1 :   return checksum;
      91            1 : }