Line data    Source code

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