aoc2024/day21/find_shortest_sequences.cc

#include "find_shortest_sequences.h"
#include "find_shortest_sequences_from_to.h"

#include <iostream>

std::vector<std::string> FindShortestSequences(
    std::string_view code,
    std::function<std::optional<char>(char, char)> apply_cmd) {
  std::vector<std::string> results;
  char from = 'A';
  for (char to : code) {
    auto sub_results = FindShortestSequencesFromTo(from, to, apply_cmd);
    from = to;

    if (results.empty()) {
      results = std::move(sub_results);
      continue;
    }

    std::vector<std::string> new_results;
    for (size_t i = 0; i < results.size(); ++i) {
      for (size_t j = 0; j < sub_results.size(); ++j) {
        new_results.emplace_back(results[i] + sub_results[j]);
      }
    }
    results = std::move(new_results);
  }

  size_t min_size = results[0].size();
  for (const auto &r : results) {
    if (r.size() < min_size) {
      min_size = r.size();
    }
  }

  std::vector<std::string> min_results;
  for (auto &r : results) {
    if (r.size() == min_size) {
      min_results.emplace_back(std::move(r));
    }
  }

  return min_results;
}