Modern C++ in Advent of Code: Day 1

It is that time of year again, so let's help the elves with Modern C++.

Before you read my solutions, I recommend you try to solve the problems yourself: https://adventofcode.com.

Input

Our input is a series of numbers separated by empty lines. To have a simple interface for our C++ solution, let's take it as a std::vector<std::string>, where empty strings serve as our delimiters.

Part1: elf with the most calories

Our goal for the first part is to determine the elf carrying the highest calories. Let's think about what we need to do to get there from our input std::vector.

1. split the input by-elf

2. translate each string into a number (now that the delimiters are gone)

3. sum up the numbers, so we have a total for each elf

4. pick the elf with the highest total

We can achieve all of this using views and algorithms.

1. use std::views::lazy_split to make a view of ranges, one for each elf

2. use std::views::transform to transform each of these ranges into a single number (the number of calories)

3. use std::max_element to pick the elf carrying the most calories

To transform a range into a single number, we can again use views and algorithms:

1. use std::transform with std::stoull to transform each std::string into a number

2. use std::reduce to sum up the numbers

Putting this together, we end up with this solution:

uint64_t max_calories(const std::vector<std::string>& data) {
  auto by_elf = data |
      // group by elf: range{range{string}}
      std::views::lazy_split(std::string{}) | 
      // sum up the calories for each elf: range{uint64_t}	
      std::views::transform([](const auto& elf) -> uint64_t {
          // std::string -> uint64_t
          auto to_unsigned = 
            [](const auto& in) { return std::stoull(in); };
          // make a view of uint64_t: range{string} -> range{uint64_t}
          auto rng = elf | 
            std::views::transform(to_unsigned) | 
            std::views::common; // std::reduce requires a common range
          // reduce into the sum: range{uint64_t} -> uint64_t
          return std::reduce(rng.begin(), rng.end());
      });
  // find the elf with the maximum number of calories
  auto it = std::ranges::max_element(by_elf);
  return *it; // and return
}

Part2: top three elves with the most calories

Our second goal is to instead of finding the top elf (e.g. max_element) to find the top three elves and return the sum of all the calories they are carrying.

We can reuse almost all of our previous solution. The main change is that we need to determine the top three elements in our transformed range.

To pick the top three elements, we would need a sort. However, we cannot sort a view (std::views::lazy_split only models an input range). Fortunately, we have std::partial_sort_copy which can operate with an input range as long as the destination is random-access.

Once we have the top three elements, we can use std::reduce again to obtain the sum.

Putting this together, we end up with the following solution:

uint64_t top_three(const std::vector<std::string>& data) {
  auto by_elf = data |
      // group by elf: range{range{string}}
      std::views::lazy_split(std::string{}) |
      // sum up the calories for each elf: range{uint64_t}	
      std::views::transform([](const auto& elf) -> uint64_t {
          // std::string -> uint64_t
          auto to_unsigned = 
            [](const auto& in) { return std::stoull(in); };
          // make a view of uint64_t: range{string} -> range{uint64_t}
          auto rng = elf | 
            std::views::transform(to_unsigned) | 
            std::views::common; // std::reduce requires a common range
          // reduce into the sum: range{uint64_t} -> uint64_t
          return std::reduce(rng.begin(), rng.end());
      });
  std::vector<uint64_t> top(3);
  // We cannot sort a view, however, partial_sort_copy only requires
  // the destination range to be random-access.
  std::ranges::partial_sort_copy(by_elf, top, std::greater<>{});
  // Sum up the top three
  return std::reduce(top.begin(), top.end());
}

Links

The repository with a complete solution (including input parsing) is available here: https://github.com/HappyCerberus/moderncpp-aoc-2022.

I post daily Modern C++ content on Twitter, LinkedIn, Mastodon, Medium and Substack.