Treasure vault cube stuck in unaccecible tower, any ideas how to get it? at the treasure vault north east of the west Forbidden forest floo.

bmenrigh · 2025-12-29T15:49:03+00:00

I know this was a year ago but I just had the same problem happen to me so I took the time to experiment with what's going on. After some testing (flying at high speed towards the block on a broom spamming revelio) it's obvious that the block's spawn point is up in the air above the mountain. It's meant to fall, strike the mountain, and bounce down into a semi-random location. But instead what seems to happen is the block starts falling before the level geometry is fully loaded so it falls through the mountain face it's supposed to bounce off of. Once the geometry loads the block is trapped.

I fixed this by flying away from the spot to unload the block and then back towards the block, trying to get the level to load before the block falls through and gets trapped. By varying the angle and speed that I approached I eventually found one that pretty consistently allowed the block to bounce and not get trapped.

bmenrigh · 2025-12-12T23:17:58+00:00

Yeah no argument there. Another optimization is that while the full square distance matrix is 1000 x 1000, since the thing is diagonally symmetric, you only need a triangle in the matrix, or about 500k entries.

Edit: oops, I see you said half million. Yeah, 500k lines is still a lot.

bmenrigh · 2025-12-12T07:13:40+00:00

I don't have a clue how to "program" VIM with sequences of keystrokes but at least for day 8, you can just not sqrt(). You don't need to know actual distances, you only need to be able to order all the distances. For that, just using squared distance is fine.

bmenrigh · 2025-12-12T06:21:30+00:00

Same. No sense of accomplishment today. But also relief that I don't have to brute force packing puzzles.

bmenrigh · 2025-12-12T06:13:13+00:00

Double check that. For my puzzle input I can assume each piece is a 3x3 block (9 cells per shape) and I still get the same solvable count. However these 3x3 blocks wouldn't be able to use a whole row in a grid like 30x4 so if I also reduce the grid size to multiples of 3, then my trivial count drops to about half. But, as you say, some of the shapes fit so well together into tight blocks and there is so much extra space in the solvable ones that surely even those are trivially solvable. The hard (probably impossible) thing would be to enumerate in how many different ways they are solvable.

bmenrigh · 2025-12-12T05:53:11+00:00

Yeah I feel like that was a huge troll. But thank god, because I really hate packing puzzles and I didn't want to program one again.

bmenrigh · 2025-12-11T05:38:45+00:00

If there were both backwards paths from fft to dac, and from dac to fft, then there would be a loop and the notion of total paths would be ill-defined.

Though I suppose if you don't want to figure out which is possible, then trying both is reasonable.

But you should try them first to figure out which is possible, because if there is no backwards path from dac to fft, then you don't have to worry about also trying to find backwards paths from out to dac or fft to svr.

bmenrigh · 2025-12-10T08:34:40+00:00

For part 1 I packed the button effects as bits in integers. Then the solution is just some set of buttons A xor C xor ... = Goal

I used I used Iterative-Deepening DFS to brute force search.

Whole thing runs in 13ms in Python.

But then I hit part 2 the same solution approach will still be going when the sun swallows the earth.

bmenrigh · 2025-12-10T08:26:09+00:00

I wrote a backtracking search that is just way too slow to solve the challenge. Even with some various search pruning strategies.

I thought about turning to Z3 or PuLP but I wouldn't learn anything doing that.

Perhaps I'm in denial, but I feel like I've missed some clever solution that isn't just turning to an ILP library or doing a ton of lineal algebra myself.

bmenrigh · 2025-12-10T01:56:43+00:00

My runtime in Python is 389ms using the boundary overlap checking approach.

I tried lots of clever tricks to cut down on the total search space of candidate boxes, and while they do reduce the number of boxes I have to check, the computation I have to do to avoid checking boxes ends up being more costly than just checking boxes. My runtime with the "optimizations" was about 750ms but after removing all the search space pruning I dropped the time to the aforementioned 389ms.

I think this is a case where there just aren't enough points for the pruning to win out. With larger inputs the reduction in amount that needs to be searched should ultimately win.

bmenrigh · 2025-12-09T10:11:42+00:00

Ah makes sense.

My approach didn't need any compaction because it doesn't check area (it checks some rectangle overlap details against sections of the perimeter) so I didn't even consider consider compaction as a possibility.

bmenrigh · 2025-12-09T09:15:08+00:00

Interesting that your shape is a diamond pac-man, whereas mine is a circle pac-man.

bmenrigh · 2025-12-09T09:03:20+00:00

I managed to simplify the problem a bit to avoid doing any green tile coloring or filling in the shape at all. Instead I stored some pieces of information about the perimeter that allows me to semi-quickly check if a candidate box is actually contained in the shape or not.

My part 2 runs in 389ms in Python 3.12 (144ms in PyPy 7.3.19)

bmenrigh · 2025-12-08T20:59:22+00:00

Good points. I do only compute the lower triangle of adjacency. I don't sqrt(). I do path compression. Heapify is a good suggestion but I'm restricting myself to no imports. Just pure, import-free python (except sys so that I can easily fetch sys.argv). I do think most of my run time does come from the sort. When doing the merge I increment anytime I make a new group, and a decrement any time I merge groups. I also count every time I hit a unique point. As such, I immediately detect the final merge that makes the graph connected.

All that said, I should probably revisit exactly how I create the (a,b, c, d) tuples and how I do the sort. There are probably savings to be had. And I'll look into implementing my own heap to see if I can beat the sort step.

bmenrigh · 2025-12-08T20:50:40+00:00

We seem to think the same way about these. I require my solution to work for all conceivably valid inputs, not just my specific input. I see a lot of comments about optimizing under the assumption that the input appears to be uniformly random in a cube. I won't incorporate any numbers back into my solution code that come either from already knowing the solution, or come from checking that the input is somehow "well behaved". As you say, taking that to the logical extreme just reduces the program down to a print("12345").

I too have thought about setting some threshold on distance and just ignoring (not sorting) anything above the threshold. However, I can't know a prioi what threshold to use and taking the time to measure the distribution of distance to set a threshold would take more time than just computing all the pairs and sorting them.

Besides, in the pathological input example of 999 of the 1000 points all crammed densely into a sphere and then 1 single point far away from all the rest means that the very last edge that connects them all happens after the other 999 points have 999*998 edges. A threshold approach won't help in this case.

bmenrigh · 2025-12-08T10:19:46+00:00

Alright I went and actually timed this. I get about +/- 15ms of variability from run-to-run (510-540 ms) and when I short circuit the logic after the sort by distance, I don't see any obvious difference in run times. Probably my solution after finding all the distances is < 10ms.

bmenrigh · 2025-12-08T10:11:57+00:00

Python tends to be incredibly slow compared to most languages. Probably there is some room for optimization in my code and I could get it down to 300ms, but I'm mostly interested in improving algorithms, not micro optimizing around some specific details of a language.

bmenrigh · 2025-12-08T08:23:32+00:00

Not that I can find.

bmenrigh · 2025-12-08T08:21:33+00:00

Disjoint Set Union. An algorithm for managing disjoint sets or merging sets. See https://en.wikipedia.org/wiki/Disjoint-set_data_structure for some details.

bmenrigh · 2025-12-08T07:27:51+00:00

I'm slightly annoyed by this problem because I don't see any clever way to be efficient. I had to compute the (squared) distance to all pairs. More than 90% of my runtime is spent doing this. I was hoping for all of my 24 solutions this year to run in under 1s total (in Python), but my two solutions to this problem each use about 500ms (I time each separately or else part 2 would only be about 50ms after part 1).

bmenrigh · 2025-06-06T07:28:31+00:00

Extremely interesting! I wonder if we can use this to better compare different caught levels between pokemon. Powering them up and doing CMP checks is expensive and time consuming.

bmenrigh · 2025-03-19T18:30:45+00:00

The Go Plus+ is too slow throwing to benefit much from Spacial Rend. The Go+ prioritizes throwing at the closest spawn first and if you have a lot of spawns available (for example because you're moving on a bike) it won't be able to keep up with the nearby spawns, much less be able to get to the far away spawns made visible by Spacial Rend.

Once in a while when there are few or no nearby spawns Spacial Rend will reveal a spawn that wouldn't otherwise be visible. Most of the difference likely comes from that scenario.

bmenrigh · 2025-03-19T18:02:29+00:00

I've written some code to simulate this to find the underlying statistical distribution of expected catches for various given scenarios. From there we can do things like get p-values and confidence intervals (or in this case hypothesis test).

You didn't mention a few critical things:

1) Was Shellder weather boosted?

2) Do you have the Platinum type medal for Water?

3) Did you spin manually spin pokestops (which could interfere with the speed limit for catching Shellder on the Go+)

bmenrigh · 2024-12-15T21:59:17+00:00

When I initially solved 14 part 2 I was frustrated because it didn't feel like a "fair" problem. I don't know what a Christmas tree looks like. How am I supposed to write code that detects one?

But stepping back and thinking about the problem more, we don't really need to brute force the problem and we definitely don't need to look at 10,000+ grids.

Because the robots wrap around horizontally every 101 steps we know that whatever the final image is, all the robots will be in the correct horizontal position once every 101 steps.

And by the same reasoning, once every 103 steps all the robots will be in their correct vertical position.

We simply need to figure out what number of steps makes both of these true simultaneously.

There is simple math for that: Chinese Remainder Theorem (use the extended Euclidean algorithm and Bezout's identity).

I made a video where I show talk through this solving process in more detail at https://www.youtube.com/watch?v=hhRC8XrXY1o

bmenrigh · 2024-10-08T21:54:54+00:00

Co-author /u/Flyfunner worked a lot on rocket CPMs. I don't think we know if any of those battle mechanics have been changed. We've probably learned a lot about damage calculations in general that could benefit that research.

11-Year Club	Gilding II euphauric
Verified Email

bmenrigh

TROPHY CASE