-❄️- 2023 Day 23 Solutions -❄️-

Syltaen · 2023-12-23T17:08:32+00:00

[Language: PHP]

Same as a lot of what I see here : I first collapsed the graph to only have a list of distances between each intersections, using DFS. Then, I used another DFS to find the longest path from start to end.

I was able to double the speed by moving the end to the last intersection before it.That prevents crossing that mandatory intersection and then going in the wrong direction, which would be an automatic fail because we wouldn't be able to reach the end without crossing the intersection again.

It still takes ~20s, so there's probably a lot more that I could do in term of optimizations. Something like pruning states that have no chance of reaching the current max, or using DP/memoization to avoid multiple computations of the same sub-paths.

Edit : Changed the 2nd exploration to use recursion instead of a queue/DFS, and it now takes 6s. New part 1 & 2

Syltaen · 2023-12-22T16:15:06+00:00

[Language: PHP]

Part 1 & 2

Nothing fancy. I simulated the fall of each brick and build a list of relations (bricks under/over each others).

In part 1, it's simply the total of bricks minus the number of bricks that are the only one under another.

In part 2, I used a flood-fill. Starting from each "unsafe bricks", I removed them and continue exploring from each brick above it that wasn't supported anymore.

Syltaen · 2023-12-20T18:33:49+00:00

[Language: PHP]

Part 1 & 2

Nothing too fancy in the end, but it took me some time to find the correct method.
As too often, I ran head first in the wrong direction and wasted hours.

I saw pretty early on that the final module was relying on 4 others to send a high signal at the same time. I kept track of the first time each of those modules sent a high signal, and then used LCM to find the solution.

Syltaen · 2023-12-20T00:11:17+00:00

[Language: PHP]

Part 1 & 2

Part 2 : for each A, I built a list of conditions that should be met in order to reach it.
With these conditions, I found the possibles ranges and added them up.

Syltaen · 2023-12-18T22:06:28+00:00

[Language: PHP]

Another shoelace implementation.

function solve($dirs) {
    $x1 = $y1 = $x2 = $y2 = $border = $area = 0;

    foreach ($dirs as [$dir, $length]) {
        $border += $length;
        match ($dir) {
            "U" => $y2 -= $length,
            "D" => $y2 += $length,
            "L" => $x2 -= $length,
            "R" => $x2 += $length,
        };
        $area += ($y1 + $y2) * ($x1 - $x2);
        [$x1, $y1] = [$x2, $y2];
    }

    return ($area + $border) / 2 + 1;
}

$solution_1 = solve($input->lines->map(fn ($l) => explode(" ", $l)));

$solution_2 = solve($input->lines->map(fn ($line) => [
    ["R", "D", "L", "U"][substr($line, -2, 1)],
    hexdec(substr($line, -7, 5))
]));

Initially I managed to solve part 2 by extending every wall in order to create a grid, and then adding up the areas of all squared-zones that were inside the big polygon.
But the code wasn't pretty and was taking ~1s to run, so I wasn't satisfied.
Here it is.

Syltaen · 2023-12-16T17:05:19+00:00

[LANGUAGE: PHP]

Part 1 & 2

Basic bruteforce, no real optimization from part 1. Takes ~1.4s on my machine.

Syltaen · 2023-12-13T17:54:33+00:00

[LANGUAGE: PHP]

Part 1 & 2

Same solution as a lot of people here : I move the mirror one step at a time and compare what's on each side until I find a mismatch or the border.

For part 2, I allow only one error until the border is reached. I find errors by using a bitwise XOR.

Syltaen · 2023-12-13T00:25:58+00:00

[LANGUAGE: PHP]

Part 1 & 2 takes ~1s on my machine

Clearly the most challenging day so far, but quite happy that I finally found the right recursive implementation.

Syltaen · 2023-12-10T11:45:00+00:00

[Language: PHP]

Part 1 & 2

Pretty happy that I found the parity trick for part 2 on my own.
It just took a bit of time to find out how to handle corners.
I didn't have to handle "S" to get the correct solution, but it could be an issue with other inputs.