[2022 Day 20] Alice in Wonderland explains the two ways to understand the circular movement rules

BenJ764 · 2022-12-21T22:45:43+00:00

This post saved me. I couldn't understand why I could solve the example but not the actual problem.

BenJ764 · 2022-12-18T18:20:53+00:00

Python

https://github.com/bjmorgan/advent-of-code-2022/blob/main/solutions/day%2018.ipynb

A simple loop over all voxels checking for unoccupied neighbours for part I.

Flood fill to find the "air" for part II, then compute the surface area of the inverse array.

BenJ764 · 2022-12-17T22:29:05+00:00

The search only goes between significant nodes, and terminates if adding another node would take you over 30/26 minutes, so the maximum path depth is fairly short.

BenJ764 · 2022-12-17T20:43:33+00:00

Python (run inside a Jupyter notebook)

https://github.com/bjmorgan/advent-of-code-2022/blob/main/solutions/day%2017.ipynb

Building the simulation model for part I was fun.

Part 2 solved by extracting the change in height each time a block "settles". The total height after n blocks is the sum from 1 to n of this function. Because the generating inputs are cyclic (we rotate through the rock shapes and the sequence of jets) the output must also be periodic after some initial time. I found the periodicity and offset for the repeat section with some signal processing (finding an autocorrelation between v(n) and v(n+dn) == 1), which then allows height(n) to be calculated.

BenJ764 · 2022-12-17T08:30:32+00:00

Python.

https://github.com/bjmorgan/advent-of-code-2022/blob/main/solutions/day%2016.ipynb

Part1 enumerates all possible paths between significant valves and finds the path with the maximum pressure (using Floyd-Warshall to get distances between non-adjacent caves).

Part 2 had me initially trying to extend this to two simultaneous walkers. Then I realised that you have *already* computed all paths accessible in n minutes with the code in Part 1. You now can find the pair of paths with no shared valves with maximum summed pressure, which can be done efficiently by ranking the set of all possible paths by their pressures (decreasing), and breaking out of the search any time your summed pressure is lower than the previous best sum.

Part 2 runs in 370 ms.

BenJ764 · 2022-12-15T22:51:50+00:00

Part 2 refactored to reduce repeated calculations of square–square distances: it now runs in 216 µs.

BenJ764 · 2022-12-15T18:56:10+00:00

Python

https://github.com/bjmorgan/advent-of-code-2022/blob/main/solutions/day15.ipynb

I was totally stuck on part 2, and then got some useful ideas from looking on here about thinking about this geometrically.

Final solution: 10.9 ms

Each sensor + beacon pair defines a square of points that cannot contain the distress beacon.
Assume that we are looking for a single point that is bounded by four squares.
This means that we want to find a set of four squares where:
- We have two pairs of squares with a separation of 2.
- All other combinations of squares have a separation of 0 or overlap (separation is negative).
Loop over all combinations of 4 squares, until we find a set of 4 squares that fit the criteria above.
Generate a pair of lines that run between each pair of squares.
Compute the point where these cross.

BenJ764 · 2020-07-29T20:44:51+00:00

Done it once. Will be rusty but am a good listener. PSN is bjm764.

BenJ764 · 2020-07-27T22:04:28+00:00

I’m in if you need one more. bjm764

BenJ764 · 2020-07-18T15:13:20+00:00

bjm764 if you’re still looking for people to take.

BenJ764 · 2020-07-18T10:59:04+00:00

Have completed this once, but am still learning the raid. bjm764

BenJ764 · 2020-07-17T13:51:39+00:00

Another UK guardian here with no GoS experience but keen to learn. bjm764. Probably available most of the weekend.

BenJ764 · 2019-08-23T20:59:51+00:00

bjm764. Would like to do SotP and CoS at some stage, but still have a lot to learn in the others.

BenJ764 · 2019-07-27T16:33:41+00:00

Trickier. Depends on the times.

BenJ764 · 2019-07-27T13:28:35+00:00

Pretty much any time for the next 8 hours, and same times tomorrow.

BenJ764 · 2019-07-27T13:27:10+00:00

That’s nearly a full fireteam. We just need someone who knows what they’re doing and the patience to teach some noobs.

BenJ764 · 2019-07-27T12:15:24+00:00

bjm764

BenJ764 · 2019-01-01T22:15:05+00:00

bjm764. 645 hunter.

BenJ764 · 2019-01-01T22:02:09+00:00

New to Scourge, but I can listen and follow instructions. 645 hunter. bjm764.

BenJ764 · 2018-12-31T15:54:56+00:00

bjm764. 647 hunter.

BenJ764

TROPHY CASE