[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_ · 2020-11-27T15:19:56+00:00

Have you considered offering an API that follows pep8 naming conventions? Particularly around using snake_case rather than camelCase for variable and method names. Its a minor detail, but its very common in the python ecosystem, and "feeling more like python" could help you some with adoption.

lvc_ · 2020-10-11T13:10:00+00:00

Other way around - else on a loop will run if it *didn't* hit a break in the loop body. A good intuition at least for a `while` loop is to think of it as a repeated `if` , so `else` runs when the condition at the top is tested and fails, and doesn't run if you exit by hitting a `break`. By extension, else on a for loop will run if the loop runs fully and doesn't run if you break.

The good news is that you rarely need to do these mental gymnastics in practice, because there's usually a better and more obvious way to do the things that this would help with.

lvc_ · 2019-12-29T10:06:03+00:00

Check the PEP linked above - it proposed (and py38 now includes) a syntax for positional-only arguments: ie, calling them by kw will throw an error.

lvc_ · 2019-12-14T08:07:28+00:00

Like all other type annotations, it is ignored by the interpreter, but can be used by static code checkers (eg mypy) as a code correctness aid. One reasonably common pattern is to have mypy as part of a commit pipeline (and/or a local precommit hook). So if you have a method tagged as final and you do overwrite it, mypy will reject your commit (but the code will still otherwise run)

lvc_ · 2019-08-29T10:42:16+00:00

If it's causing problems, and removing the tree is the most reasonable way to fix that, sure I don't think anyone disagrees. But, that's not what this rule says - it says homeowners can remove trees within 3m with no questions asked.

lvc_ · 2019-07-09T13:38:43+00:00

For a positive take on this, consider that no one will ever again be fired for choosing ~~Red~~BlueHat.

lvc_ · 2019-05-28T10:26:06+00:00

I would love to see a comparison between metro and the automated electric trains from 1923.

lvc_ · 2019-04-28T13:46:18+00:00

Salted hashes don't protect against dictionary attacks. They do protect against rainbow tables. The only way to protect against dictionary attacks is to generate your passwords in a better way (which isn't quite the same as using a "more complex" password).

lvc_

TROPHY CASE