C++

Hah, got me good too Mr Wastl. Was wondering how long this could possibly take to run - the worst-case is very bad indeed. This prints out the first “fit” it finds, for verification purposes, and keeps the successful ones in case they’re needed for “part 2”.

Merry Xmas, everyone.

#include <boost/describe.hpp>
#include <boost/describe/operators.hpp>
#include <boost/log/trivial.hpp>
#include <boost/unordered/unordered_flat_set.hpp>
#include <fstream>
#include <iostream>
#include <ostream>
#include <sstream>
#include <string>
#include <vector>

namespace {

struct Point {
  int x, y;
};
BOOST_DESCRIBE_STRUCT(Point, (), (x, y))
using boost::describe::operators::operator==;

using Present = boost::unordered::unordered_flat_set<Point>;
using PresentList = std::vector<size_t>;

struct Tree {
  int width;
  int height;
  PresentList presents;
};
auto operator<<(std::ostream &o, const Tree &t) -> std::ostream & {
  o << t.width << 'x' << t.height << ": ";
  auto total = size_t{};
  for (auto &p : t.presents) {
    o << p << ' ';
    total += p;
  }
  return o << "(" << total << ")";
}

auto copy_if(const Present &in, Present &out, const Point &a, const Point &b) {
  if (in.contains(a))
    out.insert(b);
}

auto rotate(const Present &in) {
  auto out = Present{};
  copy_if(in, out, {0, 0}, {2, 0});
  copy_if(in, out, {1, 0}, {2, 1});
  copy_if(in, out, {2, 0}, {2, 2});
  copy_if(in, out, {0, 1}, {1, 0});
  copy_if(in, out, {1, 1}, {1, 1});
  copy_if(in, out, {2, 1}, {1, 2});
  copy_if(in, out, {0, 2}, {0, 0});
  copy_if(in, out, {1, 2}, {0, 1});
  copy_if(in, out, {2, 2}, {0, 2});
  return out;
}

auto hflip(const Present &in) {
  auto out = Present{};
  for (auto x = 0; x < 3; ++x)
    for (auto y = 0; y < 3; ++y)
      copy_if(in, out, {x, y}, {2 - x, y});
  return out;
}

auto vflip(const Present &in) {
  auto out = Present{};
  for (auto x = 0; x < 3; ++x)
    for (auto y = 0; y < 3; ++y)
      copy_if(in, out, {x, y}, {x, 2 - y});
  return out;
}

struct Puzzle {
  std::vector<Present> presents;
  std::vector<Tree> trees;
};

auto read() {
  auto rval = Puzzle{};
  auto ih = std::ifstream{"12.txt"};
  auto line = std::string{};
  for (auto i = 0; i < 6; ++i) {
    std::getline(ih, line); // number
    auto present = Present{};
    for (auto y = size_t{}; y < 3; ++y) {
      std::getline(ih, line);
      for (auto x = size_t{}; x < 3; ++x) {
        if (line.at(x) == '#')
          present.emplace(x, y);
      }
    }
    std::getline(ih, line); // following space
    rval.presents.push_back(std::move(present));
  }
  while (std::getline(ih, line)) {
    auto tree = Tree{};
    auto times = line.find('x');
    auto colon = line.find(':');
    tree.width = std::stoi(line.substr(0, times));
    tree.height = std::stoi(line.substr(times + 1, colon - times - 1));
    auto count = size_t{};
    auto ss = std::istringstream{line.substr(colon + 1)};
    while (ss >> count)
      tree.presents.push_back(count);
    rval.trees.push_back(std::move(tree));
  }
  return rval;
}

using Occupied = boost::unordered::unordered_flat_set<Point>;
using PresentFlips = boost::unordered::unordered_flat_set<Present>;
using PresentFlipsList = std::vector<PresentFlips>;

auto place_present(
    Occupied occupied,
    const Present &present,
    const Point &origin
) -> std::optional<Occupied> {
  for (const auto &point : present) {
    auto px = origin.x + point.x;
    auto py = origin.y + point.y;
    if (occupied.contains({px, py}))
      return {};
    occupied.insert({px, py});
  }
  return {occupied};
}

auto draw_occupied(const Tree &t, const Occupied &occupied) {
  for (auto x = 0; x < t.width; ++x) {
    for (auto y = 0; y < t.height; ++y) {
      if (occupied.contains({x, y}))
        std::cout << '#';
      else
        std::cout << '.';
    }
    std::cout << '\n';
  }
}

auto can_place(
    const Tree &tree,
    const PresentFlipsList &flips,
    Occupied occupied,
    PresentList list
) -> bool {
  auto j = size_t{};
  for (; j < list.size(); ++j) {
    if (list.at(j) > 0)
      break;
  }
  if (j == list.size()) {
    draw_occupied(tree, occupied);
    return true; // yeah!
  }
  list[j]--;

  for (auto x = 0; x < tree.width - 2; ++x)
    for (auto y = 0; y < tree.height - 2; ++y) {
      for (auto &flip : flips.at(j)) {
        auto test = place_present(occupied, flip, {x, y});
        if (!test.has_value())
          continue;
        auto works = can_place(tree, flips, test.value(), list);
        if (works)
          return true;
      }
    }
  return false;
}

auto part1(const Puzzle &puzzle) {
  auto possible = std::vector<Tree>{};
  for (const auto &tree : puzzle.trees) {
    auto area = size_t(tree.width * tree.height);
    auto used = size_t{};
    for (auto present = size_t{}; present < puzzle.presents.size(); ++present) {
      used += tree.presents.at(present) * puzzle.presents.at(present).size();
    }
    if (used > area)
      continue;
    possible.push_back(tree);
  }
  auto flips = PresentFlipsList{};
  for (auto j = size_t{}; j < puzzle.presents.size(); ++j) {
    auto flip = PresentFlips{};
    auto rotation = puzzle.presents.at(j);
    for (auto i = 0; i < 4; ++i) {
      flip.insert(rotation);
      flip.insert(hflip(rotation));
      flip.insert(vflip(rotation));
      flip.insert(hflip(vflip(rotation)));
      rotation = rotate(rotation);
    }
    BOOST_LOG_TRIVIAL(debug) << j << " has " << flip.size() << " flips";
    flips.push_back(std::move(flip));
  }
  auto confirmed = std::vector<Tree>{};
  for (auto &tree : possible)
    if (can_place(tree, flips, Occupied{}, tree.presents)) {
      BOOST_LOG_TRIVIAL(debug) << tree << " can be placed";
      confirmed.push_back(std::move(tree));
    } else {
      BOOST_LOG_TRIVIAL(debug) << tree << " can't be placed";
    }
  return confirmed.size();
}

} // namespace

auto main() -> int {
  auto puzzle = read();
  BOOST_LOG_TRIVIAL(info) << "Day 12: read " << puzzle.presents.size() << " / "
                          << puzzle.trees.size();
  BOOST_LOG_TRIVIAL(info) << "1:" << part1(puzzle);
}