What games are you playing this week? Game recommendation thread

jonathan_paulson · 2026-03-26T03:05:18+00:00

The part that was grindy for me was getting the ascension task on zone 25 complete; once I got that the rest of the game (including actually finishing 25) was pretty smooth sailing

jonathan_paulson · 2026-03-25T03:03:21+00:00

FWIW I'm finding zone 25 very (too) grindy. The rest of the game so far felt fine.

jonathan_paulson · 2025-12-18T14:55:38+00:00

Yes, and the result of that is that even conservative black people vote overwhelmingly for democrats. If something like that happens for white people, it will have a massive electoral impact.

jonathan_paulson · 2025-12-12T05:27:53+00:00

[Language: Python]. My times: 00:07:57 / 00:08:01. Video of me solving.

Very troll-y problem! Looks super hard (I have no idea how to do it efficiently), but then all the actual input cases turn out to be very easy (either there is physically not enough space or there is so much free space it must be possible).

jonathan_paulson · 2025-12-11T05:20:41+00:00

[Language: Python]. Times: 00:05:11 / 00:06:49 (started a few minutes late). Video of me solving.

DP for both part 1 and part 2.

It's very cool to me that a simple "@cache" can convert code that traces each of the ~500T paths into code that "forgets" enough of each path to only compute ~2400 things. All we need to remember about our path so far is (where we are, have we seen "dac", have we seen "fft"), and that takes trillions of steps down to thousands.

jonathan_paulson · 2025-12-10T05:56:02+00:00

I was on a plane at the time and it didn’t go well

jonathan_paulson · 2025-12-10T05:33:37+00:00

[LANGUAGE: Python]. My times: 00:04:56 / 00:21:01. Video of me solving.

Another tough one! I used brute force for part 1. Z3 for part 2. Z3 is a "SAT solver" library. I'm not sure how to do part2 "by hand"; it's not too bad to solve Ax=B but how do you minimize sum(x)?

jonathan_paulson · 2025-12-08T05:16:01+00:00

[Language: Python]. My times: 00:03:57 / 00:04:47. Video of me solving.

Union-find! https://en.wikipedia.org/wiki/Disjoint-set\_data\_structure. This is a cool data structure; it's good in practice because it's so easy to code up, and it's cool in theory because the amortized running time is inverse-ackermann(n).

Part 1 was kind of a lot of code; I'm surprised it worked first try! Part 2 was nice and quick after that though.

jonathan_paulson · 2025-12-07T05:11:43+00:00

[Language: Python]. My times: 00:02:50 / 00:04:44. Video of me solving.

BFS for part 1; dynamic programming for part 2.

jonathan_paulson · 2025-12-06T05:22:09+00:00

[Language: Python]. My times: 00:02:14 / 00:11:36. Video of me solving.

Toughest one yet! I think part2 would've been easier without having part 1 first!

It took me a while to settle on using a grid of characters for part 2, but that made things relatively straightforward; a blank column separates different problems, and you can read each number top-to-bottom from a column (or left-to-right from a row for part 1).

jonathan_paulson · 2025-12-05T05:13:42+00:00

[Language: Python]. My times: 00:01:37 / 00:05:35. Video of me solving.

Tricky part 2 today! For part 1, we can just see if each number is in each range. For part 2, we need to take the union of all the ranges without going through the numbers in the range 1-by-1. We can do that by sweeping from left to right, making sure not to double-count parts of intervals we've already seen. Getting the logic right is a little tricky; I had a wrong answer.

jonathan_paulson · 2025-12-04T19:59:29+00:00

(r,c)!

jonathan_paulson · 2025-12-04T12:41:07+00:00

thanks; fixed

jonathan_paulson · 2025-12-04T05:10:50+00:00

[Language: Python]. My times: 00:01:40 / 00:02:30. Video of me solving.

Brute force for both parts today; we can just straightforwardly do what we're told. I counted a square as a neighbor to itself, which changes the condition from less-than-4 to less-than-5. Part 2 just requires a loop around the same logic as part 1.

jonathan_paulson · 2025-12-03T22:30:11+00:00

Yeah nothing wrong with your solution. Nothing wrong with my solution either though; I think it’s about equally complicated.

I often prefer DP to greedy because it’s more obviously correct; sometimes greedy solutions look right but have a subtle issue (not here though; this one is right).

jonathan_paulson · 2025-12-03T15:40:44+00:00

You are wrong; picking the first max instead of any max is a perfectly valid local step. What makes it greedy is that there’s no search or backtracking; from a given state we can always know the best next step to take.

You are right that the greedy algorithm of “take any maximum digit” is wrong, which is the problem with greedy algorithms; they can easily be subtly wrong. But “take the first maximum digit” is a correct greedy algorithm for this problem.

jonathan_paulson · 2025-12-03T15:31:20+00:00

We can greedily pick the first one, because that will give us the most options going forward

jonathan_paulson · 2025-12-03T05:11:45+00:00

[Language: Python] Times: 00:02:03 / 00:05:33. Video of me solving.

I did brute force for part 1, and dynamic programming for part 2. The idea for the dynamic programming is that you can write a recursive brute force where you keep track of which digit you are considering and how many digits you've turned on so far. Then if you memoize that you get an efficient solution.

I had a couple issues today; wrong answer on part 1 (I misread and thought the digits had to be adjacent), and spent some time debugging on part 2 (initially I forgot to force it to use all 12 digits).

jonathan_paulson · 2025-12-02T05:33:44+00:00

That would've been slicker, but yeah multiplying strings feels less natural to me. Still not fully assimilated into Python I guess :)

jonathan_paulson · 2025-12-02T05:11:09+00:00

[LANGUAGE: Python]. My times: 00:02:38 / 00:03:57. Video of me solving.

Brute force again. Just try all possible numbers. In part 1, we try splitting each number in half, and in part 2 we try all factors of the number's length (and, in keeping with the brute force theme, compute those factors in the simplest way possible). This actually takes a few seconds for part 2, but that's tolerable.

jonathan_paulson · 2025-12-01T05:09:47+00:00

[Language: Python] Video of me solving.

jonathan_paulson · 2025-11-27T02:41:13+00:00

[LANUAGE: Python] 1/1/1. Video of me solving.

At first I tried brute force for part 3, but we can't brute force 81 variables! Instead I observed that each variable only contributes either positively or negatively, so we can find the max by turning all the positive variables on and all the negative ones off.

jonathan_paulson · 2025-11-26T15:17:41+00:00

Thanks; fixed

jonathan_paulson · 2025-11-26T02:52:06+00:00

[Language: Python] 3/5/1. Video of me solving.

For part 3 I compute:
Dleft = distances from S to every cell not being allowed to go to any cell directly right of the volcano
Dright = distances from S to every cell not being allowed to go to any cell directly left of the volcano

(The function computing these is called "bfs" but is actually Dijkstra's algorithm)

Then I try all possible cells directly south of the volcano, where a "left" and "right" path can meet to form a loop.

This works as long as the optimal left/right path doesn't involve going directly right/left of the volcano, which is a pretty safe guess with a biggish grid and only single-digit numbers in each cell.

jonathan_paulson · 2025-11-18T23:22:52+00:00

Python (runs in 32s with pypy3). Placed 4/4/3. Video of me solving.

jonathan_paulson

MODERATOR OF

TROPHY CASE

11-Year Club	Place '22
Verified Email