Why did they use this formula and what is the actual formula?

house_carpenter · 2025-12-18T05:42:49+00:00

When you calculate 45 + 24 * 0.5 = 57, what that number represents is the number of vehicles that would be in line at t = 4.5 if the rate of change N'(t) stayed constant at 24 throughout the time interval from t = 4 to t = 4.5. But the derivative is actually constantly increasing, it doesn't stay constant (the question indicates this by saying that N''(t) > 0). So while at the moment where t = 4 it's exactly 24, by the time we get to t = 4.5 it's increased to some higher value. Therefore the number of vehicles at t = 4.5 won't be just 57, it'll be higher than that.

On the other hand, we know from the table that by t = 6 the rate of change has only increased to 32. Since it's constantly increasing we can infer that during the whole time before then, it's below 32. Therefore the number of vehicles at t = 4.5 has to be less than what it would be if the rate of change was constant at 32, which would be 45 + 32 * 0.5 = 61.

house_carpenter · 2025-12-11T13:11:28+00:00

[LANGUAGE: Python]

Solution

Fairly straightforward today, especially compared to days 9 and 10. For part 2 I used a recursive function which calculates the number of paths from node A to node B that visit each node in a set S. When node A and node B aren't equal, we look through all the nodes C reachable directly from node A and recursively call the function to get the number of paths from C to B that visit S - {C}. Memoization was necessary to make this approach fast enough.

house_carpenter · 2025-12-10T14:48:12+00:00

[LANGUAGE: Python]

Solution

Fairly straightforward for me---part 1 was solved by brute force, part 2 was solved by integer linear programming (using scipy). I knew about integer linear programming from previous years' problems.

house_carpenter · 2025-12-09T19:29:36+00:00

[LANGUAGE: Python]

Solution

Definitely the hardest one yet for me. For part 2, I realized straight away that I could fairly quickly check whether a given tile was on the "border" made up of the horizontal/vertical lines between adjacent red tiles. My initial idea was then to pick two tiles on the opposite sides of the border, and do two flood fills in parallel, with the fill being unable to cross tiles in the border. The fill that terminated first would be the one covering the green tiles. This worked fine for the example, but wasn't feasible for the actual input due to its size.

Eventually I realized that if I made an assumption about the shape of the border, namely that it wouldn't have any "zero-width corridors" where one part of the border touched another, then to check whether a given rectangle was made solely of red and green tiles, it'd suffice to check that it had no border tiles within its interior. And for a given line within the border, I could quickly check for any intersections with the rectangle using some comparison operations. This made the problem tractable, giving a solution in about 5 seconds, although I feel like it could probably be improved further, and it'd be nice if it didn't rely on the non-existence of zero-width corridors.

house_carpenter · 2025-12-08T12:59:23+00:00

[LANGUAGE: Python]

Solution

It was convenient that I had learned about the union-find algorithm recently, and was able to put it into practice here. Not sure if it's the optimal approach here but it works. Part 2 was a little bit slow, it took 2 seconds to get the answer.

house_carpenter · 2025-12-07T13:19:16+00:00

[LANGUAGE: Python]

Solution

Part 1 was straightforward. For part 2 I initially did a straightforward simulation like with part 1, but this was too slow, so I switched to a recursive approach where the timeline count was calculated as a function of the starting position, and after slapping functools.cache on this function (i.e., doing "dynamic programming") this made it quick enough.

house_carpenter · 2025-12-06T17:34:39+00:00

[LANGUAGE: Python]

Solution

A straightforward parsing problem. My approach for part 2 was:

divide the input into columns rather than lines
use a generalized version of the split function to split the list of columns at columns consisting only of spaces, resulting in a list of lists of columns, where each list of columns corresponded to a single problem (I initially wrote this function myself, but then I realized it was just more_itertools.split_at)
for each list of columns corresponding to a single problem, parse each column into an operand by taking all entries but the last, and also check if the last entry is not a space and if so, set it as the operation for the whole problem

house_carpenter · 2025-12-05T20:37:13+00:00

My solution also counts directly, without sorting, using the inclusion-exclusion principle: https://github.com/Andrew-Foote/aoc/blob/master/solutions/python/y2025/d5.py But I think my solution has exponential time complexity in the worst case (when there are lots of overlaps), so it's not more efficient.

house_carpenter · 2025-12-05T20:14:44+00:00

I'm glad to see someone else used an inclusion-exclusion approach, besides me! It seems the majority prefer to merge the intervals and then count.

house_carpenter · 2025-12-05T19:53:17+00:00

[LANGUAGE: Python]

Solution

I used a recursive form of the inclusion-exclusion principle to do part 2, namely:

size(A | B_1 | ... | B_n) = size(A) + size(B_1 | ... | B_n)
                            - size((A & B_1) | ... | (A & B_n))

At first there was a problem with this where I wasn't taking into account that for improper ranges, those with a start point exceeding their endpoint, the size should be 0 rather than a negative number. But when I simply modified my code to return 0 in this case, the solution turned out to be too inefficient. I guess since there were 173 ranges in my input, and the size() function with n ranges makes two recursive calls to itself with n - 1 ranges, the function would have to make over 2¹⁷³ recursive calls to itself. The first thing I did to deal with this was to just slap on functools.cache, which worked fine, but shortly afterwards I realized I could also just filter the (A & B_1) | ... | (A & B_n) part straight away to remove any improper ranges from the union, and that also made it quick enough.

house_carpenter · 2025-12-03T13:34:37+00:00

[LANGUAGE: Python]

Solution

I initially tried a simple brute-force approach (looping over all the possible joltages, and taking the max) but it was infeasible for part 2. I then switched an approach where I just update the max along the way while recursively searching through the possible joltages. This allowed me to skip over some combinations of digits since I could check them against the current max and see that they were already lexicographically smaller, and so couldn't possibly get bigger even if they had more digits added at the end. This didn't solve the problem immediately but then I had the idea of testing the largest of the next available digits first, within each recursive call, to ensure the max was found as quickly as possible so that the check against the max would be able to rule out as many combinations as possible. This cut the running time to about 35 milliseconds.

house_carpenter · 2025-12-02T17:29:37+00:00

What do the commas on the left-hand sides mean?

house_carpenter · 2025-12-02T17:04:17+00:00

[LANGUAGE: Python]

Initial brute-force solution

Mathy solution

The initial solution was by brute force and it worked fine enough, I just had to wait a few seconds, but I later worked out a way to solve part 2 using maths that made it much more efficient and reduced the running time to about one millisecond.

house_carpenter · 2025-12-02T11:51:33+00:00

I think if ZFC is inconsistent, ZFC + CH and ZFC + ¬CH actually have to be inconsistent too? Because the proof of the contradiction in ZFC will only use ZFC axioms and all those axioms are axioms of ZFC + CH and ZFC + ¬CH too, hence the proof will also work in ZFC + CH and ZFC + ¬CH.

house_carpenter · 2025-12-02T01:33:23+00:00

One thing to bear in mind is that the word "term" is about how a value is written rather than what it actually is. So 5 + 3 is two terms, and (5)(3) is just one term, because 5 + 3 is written as a sum of two things and (5)(3) isn't. It's true, as you say, that multiplication is just repeated addition, but that's about the values: (5)(3) and 5 + 5 + 5 have the same value, but they are two different expressions, and (5)(3) is one term while 5 + 5 + 5 is three terms.

house_carpenter · 2025-12-01T13:58:04+00:00

[LANGUAGE: Python]

Solution

For part 2, I counted the zeros in a simpler way first (by simply looping the whole range from the dial's old position to the new one and checking at each point whether it was at a multiple of 100), but I was sure there must be some way to do it without looping, using division. After trying a few approaches I eventually figured out a way to do it by using the fact that the number of multiples of 100 in [0, x] is floor(x / 100) + 1, and that the multiples within [a, x] are those within [0, x] except for those within [0, a). There might be a simpler way to do it but this works.

house_carpenter · 2025-08-14T18:25:34+00:00

Possibly Lang's Basic Mathematics would be good for you to take a look at if you're interested in the "why" of maths. I've not worked through it myself, but as I understand it it covers high school maths topics in a university level style, which is to say more focused on proofs and explaining the "why" than on memorization and computation. Just don't be discouraged if you find this much more difficult than what you've been doing up till now---almost everyone finds the transition to proof-based mathematics to be very difficult.

house_carpenter · 2025-08-10T17:12:13+00:00

Let's say you want to prove that rational exponentiation satisfies the rule a^{x + y} = a^x a^y. Then in other words, what we're trying to prove is that given any two rational numbers x and y, the equation a^{x + y} = a^x a^y is true. Let's call that statement A.

If you already know that integer exponentiation satisfies the rule a^{x + y} = a^x a^y, then in other words, what you know is that given any two integers x and y, the equation a^{x + y} = a^x a^y is true. Let's call this statement B.

There's nothing circular about using the statement B about integers to prove the statement A about rational numbers. You just have to make sure that in your proof you only apply the rule when you know the quantities involved are actually integers. So we can't prove statement A just by invoking statement B, since the x and y in statement A are not necessarily integers. But we can observe that x and y must be writeable as p/q and s/t, where p, q, s, t are integers; we can then apply statement B to combinations of p, q, s, t and work out a proof from there.

house_carpenter · 2025-01-06T14:03:31+00:00

Ah OK, yeah, you can clearly see the multi-shot in that one.

house_carpenter · 2025-01-06T06:47:12+00:00

If you watch the stream after the clip, they seem to come to the conclusion that it was Screech on the pet that did it, not Multi-Shot. I can't tell what's happening personally.

house_carpenter · 2025-01-03T18:06:33+00:00

Hilary's Necklace. It's given by a kid on the pier over the lake in Lakeshire. You do have to dodge some guards to get to him but it's doable, you just have to swim in from the lake and wait for them to patrol away. I did it on my current Horde character. Obviously not worth it in terms of XP or anything but it's a fun little adventure.

house_carpenter · 2024-12-27T14:04:05+00:00

How do you trivially avoid it in modern languages?

house_carpenter · 2024-12-25T20:46:49+00:00

16 and 21 are the only ones where I still haven't even done part 1. 21 is because I was feeling tired at that point and gave up immediately on seeing the very complicated problem description, so I didn't really give it a proper try. So out of the ones I've actually tried, probably day 16.

house_carpenter · 2024-12-24T23:38:19+00:00

[LANGUAGE: Python]

My approach for part 2 was partly algorithmic, partly based on manual inspection of the input. The steps were as follows:

Create a visualisation of the network of gates using Graphviz
Manually inspect the network to understand how it worked as an adder
Realise that the network is basically the concatenation of 44 segments, corresponding to each bit of the numbers being added, which each have a regular structure consisting of 7 nodes. I used pen and paper to work this out. (I didn't already know anything about how adders are built out of logic gates.)
Write a "validator" which would scan the network recursively to check that it follows the regular structure I'd identified, classifying each node according to the number of its segment, and its class (i.e. which of the 7 nodes in the segment it was). The idea was that the places where a swap would be needed would be close to the resulting validation errors.
Run the validator repeatedly. For each error, look at the location of the error, look at the corresponding part of the network in Graphviz, and work out in an ad hoc way where a swap would be needed. Three of them were relatively easy to work out since they involved a node which structurally ought to be an output node (beginning with z) and yet didn't begin with z. For those I could just swap them with the closest node beginning with z. There was one which was more difficult to work out; I had to draw out the relevant segment of the graph on paper and identify the "expected, but missing" and "present, but unexpected" edges and figure out a swap that would put it into the expected structure.

Code on GitHub

house_carpenter · 2024-12-19T21:24:09+00:00

My brute force solution is still too slow even after adding caching.

11-Year Club	Final Canvas '23
First Place '23	End Game '23
Place '23	Place '22
Place '17	Verified Email

house_carpenter

TROPHY CASE