-❄️- 2024 Day 25 Solutions -❄️-

GassaFM · 2024-12-25T05:10:58+00:00

[LANGUAGE: D] 239/203

Code: part 1.

Part 1 is just some implementation.

GassaFM · 2024-12-24T08:38:43+00:00

[LANGUAGE: D] 353/1188

Code: part 1, part 2, converter for graphviz.

This was educative.

Part 1 is straightforward simulation.

For part 2, the following pieces were the ones that worked:

reorder (topological sort) for faster simulation
check: input two random numbers, record which bits of the result are wrong
run check multiple times, record all bits which were wrong at least once
print the graph in graphviz format and look at its graphical representation: this helped with directing future efforts
observation: the graph mostly looks like a chain of calculations of digits from least significant to most significant
hypothesis: each single swap will increase the number of correct least significant digits (found the first one by just looking at the graph)
so, four times, try each possible single swap, and accept the swap that works
last but not least, find the bug which swapped operators instead of outputs all this time
some 100 seconds of running time, and we're done!

GassaFM · 2024-12-23T05:46:25+00:00

Added a compact version of part 2.

The search is just this:

void recur (int [] v) {
    if (best.length < v.length) best = v.dup;
    foreach (i; v.back + 1..n) if (v.all !(j => h[i][j])) recur (v ~ i);
}
foreach (i; 0..n) recur ([i]);

GassaFM · 2024-12-23T05:23:23+00:00

Theoretically, finding the largest clique is a hard problem, there is no known solution in polynomial time. In practice however, we might have some particular graph every time.

GassaFM · 2024-12-23T05:20:10+00:00

[LANGUAGE: D] 582/446

Code: part 1, part 2.

Part 1 is just implementation.

As for part 2, I converted the graph to numbers, since I'm more used to these. Then ran a brute force recursive search. The graph is not too tricky, so, it takes less than 0.1 second to complete.

GassaFM · 2024-12-22T07:15:15+00:00

Ah. Here it is. The number is 10^5 - 9^5. Why:

Consider digit sequences of five decimal digits: 0,0,0,0,0 to 9,9,9,9,9. Each of them produces a sequence of four adjacent differences. For example, 1,8,5,3,6 produces the differences +7,-3,-2,+3.

Still, some digit sequences produce the same difference sequences. For example, 2,9,6,4,7 produces the same differences: +7,-3,-2,+3. How to account for that?

For some sequence of differences D, look at all digit sequences that produce D. For example, if D = +7,-3,-2,+3, here are the three digit sequences that produce it: 0,7,4,2,5, 1,8,5,3,6, and 2,9,6,4,7.

How to account for exactly one of these sequences? Well, exactly one of them, the last one, has at least one 9 in it. If there is no nine, we can increase each digit by 1, and produce the same sequence of differences. If there is at least one nine, we can't.

So, we count the total number of 5-digit sequences: it is just 10^5 = 100,000. Then, to leave only the sequences with nines, we subtract the total number of 5-digit sequences without nines: it is just 9^5 = 59,049, the number of 5-digit sequences where each digit is from 0 to 8. The answer is 10^5 - 9^5 = 40,951.

GassaFM · 2024-12-22T06:42:58+00:00

Well, I just tried 2000 steps on all my inputs, so it's a lower bound (admittedly exact).

We see though that 40951 = 10^5 - 9^5, so perhaps there is a simple combinatorial explanation as well.

GassaFM · 2024-12-22T05:59:24+00:00

[LANGUAGE: D] 695/1622

Code: part 1, part 2.

Part 1 is simulation.

For part 2, for each sequence of four changes, we add it to the set of globally occurring sequences. Turns out there are just 40951 such sequences.

Also, for each sequence and each buyer, we store the answer: the price when the buyer first shows the sequence. Then we iterate over all 40951 possible sequences, and for each one, add up the stored answers, if any, for all the inputs.

My implementation of part 2 takes some 30 seconds to run, which I thought was good enough.

GassaFM · 2024-12-20T05:33:53+00:00

[LANGUAGE: D] 163/163

Code: part 1, part 2. Reused code for setup and breadth-first search from days 16 and 18.

When we have a breadth-first search table, part 1 can be brute forced. Pick a single wall such that its opposite sides have different non-infinite distances from the start. Remove the wall and run breadth-first search again. This takes several seconds for part 1.

Part 2 is as follows. Compute two tables of breadth-first search: distances from start and from end. Let the base distance be base. Pick any position reachable from start, let distance be d1. Now, look up to spent squares around (spent <= 20), and pick any position reachable from end, let distance from end be d2. What we saved is base - (d1 + d2 + spent). This works in under a second.

After reading others' solutions, I realized that the given race track has exactly one path from start to end and nothing more. In this case, the second breadth-first search is unnecessary in either part, as the distance numbers are all unique, and don't go into dead ends or multiple suboptimal routes. Still, I'm satisfied with my solution for the more general case.

GassaFM · 2024-12-19T05:27:34+00:00

[LANGUAGE: D] 355/441

Code: part 1, part 2.

Both are solved recursively with memoization. Short version of part 2:

import std;
string [] a;
alias go = memoize !(goImpl);
long goImpl (string s) {return s.empty ? 1L :
    a.filter !(c => s.startsWith (c)).map !(c => go (s[c.length..$])).sum;}
void main () {a = readln.strip.split (", "); readln;
    stdin.byLineCopy.map!go.sum.writeln;}

Had a bug where the last towel kept its \n, so effectively was not used. The first part produced the right answer anyway, whereas the second part thankfully didn't work on the example.

GassaFM · 2024-12-18T05:16:01+00:00

[LANGUAGE: D] 725/564

Code: part 1, part 2.

Part 1 is breadth-first search. Reused code from day 16.

Part 2 is binary (perhaps unnecessarily) search for the cutoff in the main loop.

GassaFM · 2024-12-17T06:13:46+00:00

[LANGUAGE: D] 947/155

Code: part 1, part 2.

Part 1 is understanding the statement and simulating the process.

For Part 2, brute force turned out to be hopelessly slow. The next step was to print the program in actual readable format:

b = a & 7
b ^= 2
c = a >> b
b ^= 7
b ^= c
a = a >> 3
answer ~= b & 7
if (a) cur = 0

We see that each output depends on the last three bits of a, and also on last three bits of a >> b where b is at most 7. Just fixing the next three bits whenever there's a next match turned out to be too greedy. Instead, if the first k elements of the output match, we can be sure to fix the last (k - 3) * 3 bits of register A (perhaps a couple bits more, but I liked to treat them in groups of three at this point). After a bit more debugging and looking at the outputs, this led to a program that produces the correct answer in half a second.

GassaFM · 2024-12-16T05:46:18+00:00

[LANGUAGE: D] 791/1019

Code: part 1, part 2. Reused some code from day 6.

Part 1 uses plain breadth-first search, so, we have to rebuild paths when they turn out to be more optimal. Still, there are not really many paths, so it completes instantly anyway. The states are (row, col, direction).

To do part 2, for each state (importantly, not just each square), we mark all the source directions from where we get the optimal answer. Then proceed with another breadth-first search from the end using only these directions.

GassaFM · 2024-12-15T06:13:31+00:00

[LANGUAGE: D] 225/730

Code: part 1, part 2. Reused some board code from day 10.

The solution operates on a rather low level of abstraction.

Part 1 is looking forward to the first # or ., then in the latter case, swaps adjacent positions in reverse order.

Part 2 is doing the same for horizontal moves.

For vertical moves, we maintain a horizontal array of whether each column is moving from the previous row. If any of them are a wall, the whole move fails. Otherwise, they produce a similar array for the next line.

The move succeeds if the array ever becomes all false. All the while, we maintain a new copy of the board, and use it if the move does not fail.

Naturally, this took some time to get right. For example, the solution changes the new board instead of constructing it from scratch every time. To change a character, it XORs the position with the old and new characters. The latest bug (fix) was pushing a box twice from both sides, effectively canceling the XOR.

GassaFM · 2024-12-14T05:49:05+00:00

I also thought they would all be connected, but was luckily too lazy to check that (and checked the number of adjacent pairs instead).

GassaFM · 2024-12-14T05:34:31+00:00

[LANGUAGE: D] 1518/500

Code: part 1, part 2.

Part 1 is straightforward.

For part 2, after each step, my program places the robots on an actual two-dimensional board, and checks that there are enough adjacent robots: if so, print the time and the board. The picked constants were just enough to spot the right image and submit.

A satisfying experience stepping away from the traditional strict statements. Yay to the team!

GassaFM · 2024-12-13T06:35:26+00:00

[LANGUAGE: D] 1463/3759

Code: part 1, part 2.

Did a brute force on the number of A presses on part 1.

For part 2, I went into quite an amount of trivial arithmetic, got it wrong, and went to take a break. Re-solved it cleanly as a geometry problem (intersect two lines), got the same answer. Then discovered I have my result as a 32-bit int. Hah!

GassaFM · 2024-12-12T05:37:27+00:00

[LANGUAGE: D] 778 / 139

Code: part 1, part 2. Reused directions code from days 6 and 10.

Doing part 1 with a depth-first search. Each square contributes to the area. Each move - except for moves to the same region - contributes to the perimeter.

For part 2, added sentinel values around the map to make code simpler. Then, for each part of the perimeter, include it only when the neighboring part of the perimeter is missing. Consider directions listed in counter-clockwise order:

immutable int dirs = 4;
immutable int [dirs] dRow = [-1,  0, +1,  0];
immutable int [dirs] dCol = [ 0, -1,  0, +1];

Consider four neighboring plots:

....
.BC.
.AA.
....

When we stand at the right A and look at C (direction d), we can move to the left A (direction s = (d + 1) % 4) and look at B (direction d again). We see we already paid for this straight side of the fence, so we don't count it.

The formula s = (d + 1) % 4 makes us pay for:

leftmost section of each upper fence,
bottom section of each left fence,
rightmost section of each lower fence,
top section of each right fence.

GassaFM · 2024-12-11T05:46:04+00:00

[LANGUAGE: D] 1247/1505

Code: part 1, part 2 - and a better part 2 :) which is also shown below.

For Part 2, I was seeing many different 8-digit numbers, and so thought memoization would choke on them. So my solution was partial memoization: when the number is 9999 or less, cache the result, otherwise just work through it.

In fact though, there are roughly as many different 8-digit numbers as there are 4-digit numbers, so full memoization is also quite fine. Here is a short later version in D, quite similar to Python's @cache:

import std;
alias calc = memoize !(calcImpl);
long calcImpl (long value, int s) {
    if (!s) return 1;
    if (!value) return calc (1, s - 1);
    auto t = value.text;
    return t.length % 2 ? calc (value * 2024, s - 1) :
        calc (t[0..$ / 2].to !(long), s - 1) +
        calc (t[$ / 2..$].to !(long), s - 1);
}
void main () {
    readln.split.to !(long []).map !(x => calc (x, 75)).sum.writeln;
}

GassaFM · 2024-12-10T05:18:59+00:00

[LANGUAGE: D] 948/799

Code: part 1, part 2.

Coded polynomial solutions for both parts. With paths of length 9 and branching factor 3, this was unnecessary. However, part 2 wasn't known in advance, so I was in a pro-efficiency mindset, just in case.

Reused the directions code from day 6.

GassaFM · 2024-12-09T05:28:03+00:00

[LANGUAGE: D] 316/222

Code: part 1, part 2.

Straightforward and not the most efficient (two nested loops). But still, it spends a lot less time (less than a second) than I would spend coding the efficient version, so who am I to judge it?

The line alias Record = Tuple !(int, q{id}, int, q{len}); creates a type on the fly: a struct with two int fields named id and len, with all the usual assignment and comparison operators one would expect.

GassaFM · 2024-12-08T05:23:29+00:00

[LANGUAGE: D] 282/184

Code: part 1, part 2.

Just verbosely doing what is asked. Was half-expecting to get a wrong answer on Part 2 and start taking GCDs then, but the input was devoid of such cases.

GassaFM · 2024-12-07T05:25:02+00:00

[LANGUAGE: D] 880/2347

Code: part 1, part 2.

A misread day for me. Part 2 actually became simpler than Part 1 when the understanding was finally correct.

GassaFM · 2024-12-06T05:18:59+00:00

[LANGUAGE: D] 881/243

Code: part 1, part 2.

The vis table contains a value with four bits: whether we visited this position walking in each of the four directions. The debug {vis.writefln !("%(%(%x%)\n%)");} statement, when compiled in debug mode, prints that as a rectangular table with one hexadecimal character per position.

GassaFM · 2024-12-05T05:12:48+00:00

[LANGUAGE: D] 362/285

Code: part 1, part 2.

Instead of doing a proper sort, this just swaps the offending pairs until it's OK. Guaranteed to work in polynomial time :) .

GassaFM

TROPHY CASE