I haven't timed it, but easily below a second.
Could that be optimised? Most certainly.
Due to the ranges being in a set, rather than a list, the input order doesn't matter anyway. And the set really does a lot of heavy lifting for making the code so concise. You'll need a bunch of boilerplate for list maintenance, especially if you continuously keep it sorted.
The set also removed 8 duplicates I had in the input.
That is nice and simple, power of python I guess. How quick was the pt2 solve? I could imagine that being pathalogically slow with the wrong ordering of inputs?
Eg: (99,100),(0,1),..., (95,96), (96,97), (97,98), (98,99)
Managed to keep it compact, but boy, do I hate cephalopod math >_<
from csv import reader
from functools import reduce
from itertools import pairwise
from operator import mul
from pathlib import Path
from typing import Any, List, Sequence
def _calc(values: List[str]) -> int:
match values[-1]:
case "+":
return sum(map(int, values[:-1]))
case "*":
return reduce(mul, map(int, values[:-1]))
case _:
return 0
def _transpose(values: Sequence[Sequence[Any]]) -> List[List[Any]]:
return [[values[row][col] for row in range(len(values))] for col in range(len(values[0]))]
def part_one(input: str) -> int:
def _parse_input(input: str) -> List[List[str]]:
return _transpose(list(map(lambda r: list(filter(None, r)), reader(input.splitlines(), delimiter=" "))))
return sum(map(_calc, _parse_input(input)))
def part_two(input: str) -> int:
def _parse_input(input: str) -> List[List[str]]:
data = list(input.splitlines())
columns = [t[0] for t in filter(lambda t: t[1] != " ", enumerate(data[-1]))] + [len(data[0])]
numbers = [[line[a:b] for line in data[:-1]] for a, b in pairwise(columns)]
numbers = [list(filter(None, ["".join(num).strip() for num in column])) for column in map(_transpose, numbers)]
return list(map(lambda t: t[0] + [t[1]], zip(numbers, list(filter(None, data[-1].split(" "))))))
return sum(map(_calc, _parse_input(input)))
if __name__ == "__main__":
input = Path("_2025/_6/input").read_text("utf-8")
print(part_one(input))
print(part_two(input))
Again part 2 took me way longer than I would've liked and also than feels appropriate for the simplicity of the solution I finally came up with.
Turned out quite fast, thanks to the ranges.
from pathlib import Path
from typing import List
from itertools import combinations
def parse_input(input: str) -> tuple[set[range], list[int]]:
parts = input.split("\n\n")
fresh = set((lambda r: range(int(r[0]), int(r[1]) + 1))(line.split("-")) for line in parts[0].splitlines())
return (fresh, list(map(int, parts[1].splitlines())))
def merge_ranges(a: range, b: range) -> List[range]:
if a.stop <= b.start or b.stop <= a.start:
return [a, b]
return [range(min(a.start, b.start), max(a.stop, b.stop))]
def part_one(input: str) -> int:
fresh, available = parse_input(input)
return len(list(filter(None, [any(i in r for r in fresh) for i in available])))
def part_two(input: str) -> int:
fresh, _ = parse_input(input)
while True:
for a, b in combinations(fresh, 2):
if len(m := merge_ranges(a, b)) == 1:
fresh.remove(a)
fresh.remove(b)
fresh.add(m[0])
break
else:
break
return sum(map(len, fresh))
if __name__ == "__main__":
input = Path("_2025/_5/input").read_text("utf-8")
print(part_one(input))
print(part_two(input))
I broke down the outline into a set of boxes by scanning over them.
type Box = (C, C) -- inclusive coordinates
makeBoxes :: [C] -> [Box]
makeBoxes cs =
let cs' = sort cs -- left-to-right first, top-to-bottom second
scanLines = cs' & groupOn fst
in scanOver 0 [] scanLines
where
scanOver lastX currentYs [] = []
scanOver lastX currentYs (new : rest) =
let newX = new & head & fst
closedBoxes = do
[y1, y2] <- currentYs & chunksOf 2
pure ((lastX, y1), (newX, y2))
newYs =
-- Take the new column and remove anything that
-- corresponds to a y value that appears in both
merge currentYs (map snd new)
in -- Close the current boxes
closedBoxes ++ scanOver newX newYs rest
merge [] ns = ns
merge ms [] = ms
merge (m : ms) (n : ns)
| m < n = m : merge ms (n : ns)
| m > n = n : merge (m : ms) ns
| otherwise = merge ms ns
The fiddly bit was handling all the cases for shape subtraction. I don't give it here because it's just a slog, but the gist is this:
type Shape = [Box]
subtractBox :: Box -> Box -> Shape -- returns whatever's left
subtractShape :: Shape -> Shape -> Shape -- this is just a fold.
The idea: take a bounding box that's just large enough to cover all coordinates. From that, subtract the set of boxes above. You get a set of boxes that are in the "outside", ie, illegal region. [I did it this way because managing shape subtraction from the set of "inside" boxes is just more work.]
Then for each candidate rectangle, if it overlaps with any of the "out-of-bounds" boxes, it's not a solution.
This might be the actual culprit; I don't think I have any swap space allocated (htop always displays 0/0 for it). I have 48 gigs of RAM, and the "out of memory" error I got on a previous day's problem didn't provoke a single slowdown, freeze, or program crash...
Possibly using up swap space first?
Naw, linux. I had a Youtube video running in the background that might have made the problem worse. I could switch desktops and move the mouse (albeit with a lot of lag and jitter) but not close the tab or even hard-close the browser.
Running the same code on my macbook triggered the "a script on this page is slowing down firefox, do you want to wait some more or pause and debug it?" prompt.
Either the OOM killer is not properly set up on my desktop, or it was actually a hot CPU loop that caused the lock-up and not memory pressure. Or some sort of hybrid cpu+mem problem? The code was cloning ever-longer arrays in a for-loop, and from my understanding the event loop for a browser page/tab is not only single-threaded but contains both UI events and script execution (unless you explicitly/specifically shell out to a web worker or the like).
Surprised you didn't trigger the OOM killer. Windows?
I got lazy for part 1 and stuffed the beam head's coordinates into a string instead of reusing my implementation that puts them into an int, gambling on part 1 not needing that extra bit of speed.
I did a similar mistake for part 2 as I did on day 6; I wrote a(n overkill) solution for keeping track of the entire path each beam/split follows - which involved cloning each array-storing-a-beam's-path at each split. Whereas on day 6 I got an "out of memory" error, this time I locked up my computer ๐ช ๐ฅ (Control+C doesn't exist in the browser console, and Control+W to close the tab wasn't getting through). Was very disappointed to realize we only need to keep track of the number of beams present at each position/index/abscissa without caring about which path they took to reach said index.
Code
function part1(inputText) {
let beams = new Set([inputText.indexOf('S')]);
const beamSplits = new Set();
const lines = inputText.trimEnd().split('\n');
for (let y = 1; y < lines.length; y++) {
const nextBeams = new Set();
for (const beamX of beams) {
if (lines[y][beamX] === '.') {
nextBeams.add(beamX);
} else if (lines[y][beamX]) {
beamSplits.add([beamX, y].toString());
nextBeams.add(beamX + 1);
nextBeams.add(beamX - 1);
}
}
beams = nextBeams;
}
return beamSplits.size;
}
{
const start = performance.now();
const result = part1(document.body.textContent);
const end = performance.now();
console.info({ day: 7, part: 1, time: end - start, result });
}
function part2(inputText) {
let beams = new Map([
[inputText.indexOf('S'), 1]
]);
const lines = inputText.trimEnd().split('\n');
for (let y = 1; y < lines.length; y++) {
// console.debug({ y, beams })
const nextBeams = new Map();
for (const [beamHeadX, beamCount] of beams) {
if (lines[y][beamHeadX] === '.') {
nextBeams.set(beamHeadX, (nextBeams.get(beamHeadX) ?? 0) + beamCount);
} else if (lines[y][beamHeadX] === '^') {
nextBeams.set(beamHeadX + 1, (nextBeams.get(beamHeadX + 1) ?? 0) + beamCount);
nextBeams.set(beamHeadX - 1, (nextBeams.get(beamHeadX - 1) ?? 0) + beamCount);
}
}
beams = nextBeams;
}
return beams.entries().reduce((accu, [_, count]) => accu + count, 0);
}
{
const start = performance.now();
const result = part2(document.body.textContent);
const end = performance.now();
console.info({
day: 7,
part: 2,
time: end - start,
result
})
}
After reading multiple papers on stuff like polyomino and coverings etc over the weekend, I sat down to formulate an ILP approach. All the way through I had at the back of my mind "surely he would not expect people to solve something which requires reading research papers, there must be some angle to this which makes it easier". I don't think I have ever been more right in my life and I am really glad I made the obvious fail and succeed checks based on areas lol.
import numpy as np
import itertools as it
from pathlib import Path
from time import time
cwd = Path(__file__).parent.resolve()
def timing(f):
def wrap(*args, **kw):
ts = time()
result = f(*args, **kw)
te = time()
print(f"func{f.__name__} args: {args} took: {te-ts:.4f} sec")
return result
return wrap
def parse_input(file_path):
with file_path.open("r") as fp:
data = list(map(str.strip, fp.readlines()))
objects = []
for i in range(6):
i0 = data.index(f"{i}:")
obj = np.array(list(map(list, data[i0+1:i0+4])))
obj[obj=='#']=1
obj[obj=='.']=0
objects.append(obj.astype(int))
i0 = data.index("5:")+5
placements = []
for line in data[i0:]:
dims = list(map(int, line.split(':')[0].split('x')))
nobjs = list(map(int, line.split(': ')[-1].split(' ')))
placements.append((dims, nobjs))
return objects, placements
@timing
def solve_problem(file_name):
ref_objects, placements = parse_input(Path(cwd, file_name))
areas = [np.count_nonzero(obj==1) for obj in ref_objects]
counter_succesful = 0
for grid_shape, nobjs in placements:
obj_area = np.sum(np.array(nobjs)*areas)
grid_area = np.prod(grid_shape)
worse_area = np.sum(np.array(nobjs)*9)
if worse_area<=grid_area:
counter_succesful += 1
continue
if obj_area>grid_area:
continue
return counter_succesful
if __name__ == "__main__":
assert solve_problem("input") == 583
using System.Collections;
using System.Collections.Generic;
namespace ConsoleApp1
{
public static class Program
{
public static void Part1()
{
var lines = File.ReadAllLines("C:\\Users\\aman\\RiderProjects\\ConsoleApp1\\ConsoleApp1\\input.txt");
var dialReading = 50;
int result = 0;
foreach (var line in lines)
{
if (dialReading == 0)
{
result += 1;
}
char dir = line[0];
int rotation = int.Parse(line.Substring(1));
if (dir == 'R')
{
dialReading += rotation;
dialReading %= 100;
}
else
{
int diff = dialReading - rotation;
if (diff > 0)
{
dialReading -= rotation;
dialReading %= 100;
}
else
{
dialReading = dialReading + 100 - rotation;
dialReading %= 100;
}
}
}
Console.WriteLine(result);
}
public static void Part2()
{
var lines = File.ReadAllLines("C:\\Users\\aman\\RiderProjects\\ConsoleApp1\\ConsoleApp1\\input.txt");
var dialReading = 50;
int result = 0;
foreach (var line in lines)
{
char dir = line[0];
int rotation = int.Parse(line.Substring(1));
if (dir == 'R')
{
while (rotation > 0)
{
if (dialReading == 0)
result += 1;
dialReading += 1;
dialReading %= 100;
rotation -= 1;
}
}
else
{
while (rotation > 0)
{
if (dialReading == 0)
result += 1;
dialReading -= 1;
if ( dialReading < 0)
dialReading += 100;
dialReading %= 100;
rotation -= 1;
}
}
}
Console.WriteLine(result);
}
public static void Main(string[] args)
{
Part1();
Part2();
}
}
}
I got lazy and lucky writing the first part; hard-coded the number of lines / operands and it worked on the first try! I didn't factor in the final block not being padded by spaces on both sides for part 2, and so needed to test on the example code โ which has 3 lines of operands instead of the problem input's 4 lines, so I had to properly solve the problem across all possible amounts of lines of input ๐ฉ.
I am very jealous of all y'all who have a transpose function available in your language of choice.
Code
function part1(inputText) {
const [firstArgs, secondArgs, thirdArgs, fourthArgs, operators] = inputText.trim().split('\n').map(line => line.trim().split(/\s+/));
let totalSum = 0;
for (let i = 0; i < firstArgs.length; i++) {
if (operators[i] === '+') {
totalSum += Number.parseInt(firstArgs[i], 10) + Number.parseInt(secondArgs[i], 10) + Number.parseInt(thirdArgs[i], 10) + Number.parseInt(fourthArgs[i], 10);
} else if (operators[i] === '*') {
totalSum += Number.parseInt(firstArgs[i], 10) * Number.parseInt(secondArgs[i], 10) * Number.parseInt(thirdArgs[i], 10) * Number.parseInt(fourthArgs[i], 10);
}
}
return totalSum
}
{
const start = performance.now();
const result = part1(document.body.textContent);
const end = performance.now();
console.info({
day: 6,
part: 1,
time: end - start,
result
})
}
function part2(inputText) {
const lines = inputText.trimEnd().split('\n');
const interBlockIndices = [];
for (let i = 0; i < lines[0].length; i++) {
let allEmpty = true;
for (let j = 0; j < lines.length; j++) {
if (lines[j][i] !== ' ') {
allEmpty = false;
break;
}
}
if (allEmpty) {
interBlockIndices.push(i);
}
}
interBlockIndices.push(lines[0].length);
let totalSum = 0;
let blockStart = 0;
for (const interBlockIndex of interBlockIndices) {
// compute calculation of block [blockStart, interBlockIndex - 1]
const operands = [];
for (let i = interBlockIndex - 1; i >= blockStart; i--) {
// parse operands
let operand = 0;
for (let j = 0; j < lines.length - 1; j++) {
if (lines[j][i] !== ' ') {
operand *= 10;
operand += Number.parseInt(lines[j][i], 10);
}
}
operands.push(operand)
}
if (lines.at(-1)[blockStart] === '+') {
totalSum += operands.reduce((accu, next) => accu + next, 0);
} else if (lines.at(-1)[blockStart] === '*') {
totalSum += operands.reduce((accu, next) => accu * next, 1);
}
// console.debug({ totalSum, operands, blockStart, interBlockIndex });
blockStart = interBlockIndex + 1;
}
return totalSum;
}
{
const example = `123 328 51 64
45 64 387 23
6 98 215 314
* + * +
`;
const start = performance.now();
const result = part2(document.body.textContent);
// const result = part2(example);
const end = performance.now();
console.info({
day: 6,
part: 2,
time: end - start,
result
})
}
I'm still attempting to make "no lib" solution using matrices and Gaussian elimination. It definitely reduces my solution space, but I'm still struggling to find a good approach to search the space.
My next step is gonna be somehow extracting inequality boundaries, lock a variable at the boundary and solve that reduced equation system. Unfortunately I have no good way to get lower bounds like I do on paper (by default lower bounds for all variables are 0).
After looking at examples of graphical linear system solutions my hope is that optimal solutions will sit on these intersections between equations. The idea hinges on these equations being linear, meaning that without curves there should be no other optimum solutions.
On paper, looking at the inequality ranges, one variable maximum seems imply a minimum for another (in case there are two variables). Searching for solutions by solving smaller and smaller systems with these locked variables feels like a probable approach.
Nice job! I initially thought about using reduced-row echelon form, but the matrices all had infinitely many real solutions so I couldn't figure out how to proceed. Instead, I scanned Wikipedia for a bit, found the two-phase simplex algorithm, spent two days getting it to work on paper and another day implementing it.
And the reward?
I'm not even done because ~10% of the systems have non-integer optima, so I still need to use cutting planes to add extra constraints to get the integer optima.
Congrats! I'll try not to peek at your code, but will definitely try to repeat your process. I want to remove z3 from my solution.
Only took four days, but I made it, and without any maths libraries. I tried lots of unsuccessful searches (including A*) before realizing part 2 is a linear equation system. Then I tried to find all solutions by just going row by row, guessing all but one unknown variable and finding the smallest solution, but this was still way too slow due to the high amount of variables guessed.
By looking around on Wikipedia I found that the problem could be simplified by turning the matrix into Smith Normal Form or Hermitian Normal Form, but couldn't find any Rust library implementing these. Their algorithms looked just a bit too complicated to implement myself. Maybe I would have used Python, because sagemath has everything, but the problem of ultimately finding the smallest integer solution still remained, and I already had the search code in Rust without simplifying the matrix.
So put the matrix into echelon form by implementing Gaussian elimination, which wasn't too bad, and it significantly reduced the number of variables to guess. Now part 2 runs in 70ms.
For the test cases (ironically, the only difficult ones) it finds the solution for 1 basically instantly, 2 in 0.2 seconds, and checks all possibilities for 3 in about 18 seconds before rejecting it.
For the thousand 'puzzle' cases, about half are rejected since the area is simply too small for the presents in an instant. A possible solution is found for all of them in about 80 seconds, so about five per second.
I was concerned that the puzzle cases were about four times the area, and some of them had 255 presents (which might be the maximum stack depth in some languages - not C++, though). So maybe some of them would find a solution quickly, and excluding the worst might take ~ 4 times the size * 30 times the presents * 20 seconds = the best part of an hour. Multithreading it and hoping not too many of them were 'worst case', and I could leave my computer on overnight number-crunching it. Box packing is NP-complete and we need a 'true' answer rather than an approximation, so I couldn't see any better way of doing it than checking every possibility. Sorting the list didn't really show any evidence of puzzles that could be 'pruned' - areas that were the same but with increasing numbers of presents, say, so that you could reject the larger ones after the first failure.
Was kicking myself when it ran so quickly.
How would you then distinguish between the situations in these two examples?
...#x
-> .###x
.#xxx
.....
-> .###.
.#x#.
Last year there was the graph one that was easiest to solve by drawing the graph and manually solving.
And one of the early ones could be done by hand with some mild effort, I did it in excel.
Ha, that is beautiful. How long did it run for?
The good ol' range merge is back! I've done the past few years in Rust, which has first-class "support" for inclusive ranges, so I was dreading having to re-implement things. Turns out when you can ignore lifetimes things get simpler.
Code
function part1(inputText) {
const [freshRangeDefs, availableIds] = inputText.trim().split('\n\n');
const parsedIds = new Set(availableIds.trim().split('\n').map(strId => Number.parseInt(strId, 10)));
const parsedRanges = freshRangeDefs.trim().split('\n').map(rangeDef => rangeDef.split('-').map(strBound => Number.parseInt(strBound, 10)));
for (const id of parsedIds) {
let fresh = false;
for (const [lowerBound, upperBound] of parsedRanges) {
if (lowerBound <= id && id <= upperBound) {
fresh = true;
break;
}
}
if (!fresh) {
parsedIds.delete(id)
}
}
return parsedIds.size;
}
{
const start = performance.now();
const result = part1(document.body.textContent);
const end = performance.now();
console.info({
day: 5,
part: 1,
time: end - start,
result
});
}
function part2(inputText) {
const [freshRangeDefs] = inputText.trim().split('\n\n');
const parsedRanges = freshRangeDefs.trim().split('\n').map(rangeDef => rangeDef.split('-').map(strBound => Number.parseInt(strBound, 10)));
parsedRanges.sort(([lowerA, upperA], [lowerB, upperB]) => lowerA - lowerB);
const merged = [parsedRanges[0]];
for (const [parsedLower, parsedUpper] of parsedRanges) {
let inserted = false;
for (let mIndex = 0; mIndex < merged.length; mIndex++) {
const [mLower, mUpper] = merged[mIndex];
if (mUpper < parsedLower) {
// parsed is completely "above" merged
continue
} else if (parsedUpper < mLower) {
// parsed is completely "below" merged
merged.splice(mIndex, 0, [parsedLower, parsedUpper]);
inserted = true;
break;
} else {
// parsed and merged intersect somehow/somewhere)
merged[mIndex][0] = Math.min(parsedLower, mLower)
merged[mIndex][1] = Math.max(parsedUpper, mUpper)
inserted = true;
break;
}
}
if (!inserted) {
// parsed is completely "above" ALL already-merged ranges
merged.push([parsedLower, parsedUpper]);
}
}
return merged.reduce((accu, [lower, upper]) => accu + upper - lower + 1, 0)
}
{
const exampleText = `3-5
10-14
16-20
12-18
1
5
8
11
17
32
`
const start = performance.now();
// const result = part2(exampleText);
const result = part2(document.body.textContent);
const end = performance.now();
console.info({
day: 5,
part: 2,
time: end - start,
result
});
}
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);
}
I struggled with optimizing this puzzle and had to go online to figure it out too, so I'm glad my hint helped you out.
On the line -> inside. The calculation I've done is a bit tricksy - vertical lines include the endpoints but horizontal lines exclude them, so that the even-odd rule is followed properly if you're on the same row as corners. No lines overlap.
I'd considered using the dot product to work out whether the line turned left or right, but there's a lot of cases to consider and get right. Fair play on computing the normals.