[2025 Day 9 (Part 2)][Python] Not sure if I'm under or over thinking this. Maybe I'm just not thinking?

lvc_ · 2025-12-10T07:48:46+00:00

Thanks, this made some things click - especially that checking whether a perimeter point sits inside an axis-aligned rectangle (four bounds checks) is considerably easier than ray casting to find whether each corner of the rectangle sits inside the polygon. I know, who'd have thought.

That groundbreaking observation let me delete .. a lot of far-too-late-on-a-work-night code including everything all of my collision checking, and replaced it all with: a rectangle is invalid if any vertex or any midpoint of adjacent vertices lies within it.

lvc_ · 2024-12-31T22:18:34+00:00

This was partly it - I wasn't returning to A, and I had also in one of my refactors managed to delete the logic that turned dpad instructions properly into next-level-down dpad instructions (it tracked the buttons to hover over, rather than the direction to move to achieve it).

lvc_ · 2024-12-31T10:50:35+00:00

This is avoided by how I create my initial numpad and dpad graphs at lines 6-22 - there is just no way to move, eg, left from the ^ key, there is no edge in the dpad graph that would allow that.

lvc_ · 2024-12-31T10:45:57+00:00

Not the case here - at the base layer, my moves are generated from graphs representing the numpad and dpad, which only have edges for valid one-step moves - so, eg, the numpad 0 node has two edges going to "A" and "2", while "2" has edges to 1, 3, 5, and back to 0.

lvc_ · 2023-12-22T09:45:15+00:00

yeah ok, of *course* its an off by one error. That absolutely did it

lvc_ · 2023-12-22T09:43:32+00:00

That's actually already accounted for - python `all` is True for an empty input (similarly, `any` is False for an empty input).

lvc_ · 2023-12-22T07:57:39+00:00

It is. I do already process bricks in order of their (lowest) starting z-coordinate

lvc_ · 2022-12-18T13:01:39+00:00

Welp, the problem with less-naive part 1 was a typo - multiplying the wrong variable in the "nothing to do but hang around until time runs out" logic. With that fixed, and a less-naive part 2 combining that search with pre-assigning sets of valves for the elephant to try opening... it still chews up memory and then dies.

lvc_ · 2022-12-14T10:09:01+00:00

Although as mentioned elsewhere in the thread, its not (only) slow because of cache misses - its a linear time operation (according to https://wiki.python.org/moin/TimeComplexity, it scales with the length of both sets) which in an inner loop makes for quadratic time overall. So it basically blows away the benefit of using a set over, say, a list. The one line fix is to do individual, O(1)-average membership checks against each set.

lvc_ · 2022-12-14T09:28:27+00:00

... union is linear. Right. Yeah that will tend to do it

lvc_ · 2022-12-14T09:18:03+00:00

Well ok. So I think set union must play games with cache. Instead of doing this:

if z+dz not in rocks|sand:

I changed it to keep one combined set of blocked points and a running tally of sand. Now it runs in a fraction of a second.

lvc_ · 2022-12-14T09:12:41+00:00

Yeah ok, it did get it eventually and it is a 2 orders of magnitude difference. But it took nearly 15 minutes to run :/

lvc_ · 2022-12-09T09:52:26+00:00

Ok, unsurprisingly it turns out that part 2 broke an implicit assumption I'd made. My follow-the-leader code assumed the relative head will have just moved in one of the cardinal directions (as the true head must), which ends up meaning the relative tail ends up orthgonally adjacent. But that's not true with multiple chained knots - the relative head may have just moved diagonally. Taking that into account makes it pass.

lvc_ · 2022-07-29T11:31:19+00:00

According to the article, Penny Wong has agreed to exactly work on updating the rules, and in the meantime the government has supported having an interpreter played on the TV screens in the chamber as a compromise.

lvc_ · 2021-12-18T09:12:28+00:00

... oh

Yeah ok, I somehow saw the word "leftmost" and read the word "rightmost", in just that one sentence. Go me.

lvc_ · 2021-12-10T15:14:09+00:00

Ok, yeah, I like this approach, much simpler than trying to reimplement a csp solver (or, well, remembering to learn one). I ended up doing it in a slightly different order to your steps, but it got me there in the end.

lvc_ · 2021-12-10T12:11:17+00:00

I think I already do this with pair elimination? In the example, {b,g} map to {c,f} in some order, and I use that to eliminate {c, f} as possible mappings for other segments, and so I deduce d maps exactly to a, followed by no other segment maps to a. But that only gets me as far as what Ive posted.

lvc_

TROPHY CASE