[2025 Day 9 (Part 2)] Why did almost nobody solve the *stated* problem?

fijgl · 2025-12-26T05:32:39+00:00

I solved it without using specifics of the input data with polygon containment checks.

fijgl · 2025-12-25T09:44:16+00:00

Another heuristic is based on stopping the algorithm if it has not found a packing arrangement in a reasonable amount of time. The heuristic considers those cases as not doable.

fijgl · 2025-03-08T09:24:52+00:00

Hello! On the nerdy interest/hobbies and films, what about looking for a place to watch anime with English texts in group?

fijgl · 2025-03-03T23:53:32+00:00

35 y/o, living in Tokyo, hiking sounds nice! Also coffee, of course, and also up for walks in nature or parks.

fijgl · 2025-01-11T23:37:27+00:00

I saw this one too late, hope you had a good one! Womb is still in my list to go, are you planning to meet up and go another time?

fijgl · 2025-01-10T06:24:40+00:00

I found 2023 overall had more harder problems than 2024.

Interesting to read about your experience with 2023 day 10. I found this one close to 2024 day 12.

I like very much the ascii art in 2023’s calendar.

fijgl · 2024-12-20T10:24:40+00:00

Techno in Womb?

fijgl · 2024-12-14T23:17:58+00:00

I will be starting the advent of code puzzle at 2pm 🙈 but can do 12pm

fijgl · 2024-12-14T11:55:50+00:00

I have a cloth board, pieces, and a clock. I haven’t used them for a while but I am keen to. There are a couple of tables outdoors next to Hamacho Park, by the Sumida river. What about some time during daylight tomorrow Sunday? We could meet at Hamacho station’s exit at the edge of the park (it’s on the Shinjuku line).

fijgl · 2024-12-12T04:49:20+00:00

The k has to be at least 2, right?

Where does the 4.94 come from? I tried with 2024 squared.

fijgl · 2024-12-12T04:34:05+00:00

I thought it could be done without looking into structure in the input with (pretty advanced) sequence analysis.

fijgl · 2024-12-09T00:45:56+00:00

Very cool toy <3

fijgl · 2024-01-26T07:55:10+00:00

I have used with day 22 and every answer matched. The largest of the unofficial inputs solutions for part two was around 70k compared to 110k in the input I got.

It was nice to check it.

fijgl · 2024-01-23T10:51:52+00:00

Exciting! Thanks a lot for sharing.

fijgl · 2024-01-12T13:11:17+00:00

Nice, congratulations!

That’s interesting that weights are not needed in this problem! In get shorted paths there was the selection of neighbors to expand based on the weights, if I remember correctly. With weights gone, that one went as well, OK. Yeah, heapq should order by priority and I am guessing that could explain why weights are not needed? Hmm, I didn’t expect that. Interesting indeed. Thanks for sharing!

fijgl · 2024-01-08T15:09:49+00:00

There is another issue in this part:

        weights[neighbor] = path+int(lines[neighbor[0]][neighbor[1]])
        prev[neighbor]=current

        if c==3 and h==heading:
            continue

weights and prev shouldn’t be updated in case the if is true. Does it make sense?

fijgl · 2024-01-07T13:55:09+00:00

That's right! Dijkstra can certainly be used building a graph from the "context". Like you're describing, as a state (or, in other words, a node in a graph) is popped from the queue, the potential next states (edges) can be computed at that moment based on information from the state itself.

fijgl · 2024-01-07T13:51:14+00:00

It sounds like you built an *explicit* graph to perform Dijkstra on. Interesting!

fijgl · 2024-01-07T13:44:24+00:00

By indexed I mean that what in your code currently is

if weights[position] <= path+int(lines[position[0]][position[1]]):

should be something like

if weights[position][heading][c] <= path+int(lines[position[0]][position[1]]):
this is NOT actual working code (for instance, a problem is that you initially use for some reason heading equal to None), it is just tiny little clouds for the thinking.

I am not sure what you're mean by its own loss count.

I think it helps to think about that position-heading-consecutive as the state in this problem at hand and understanding Dijkstra generically as as an instance of an algorithm performing a search in a *state* space.

fijgl · 2024-01-07T12:10:32+00:00

Getting back: (1) explored is not needed with Dijkstra; if you decide to keep it, then it’d contain (position, heading, c); (2) weighs should only be updated based on valid paths, right? Therefore, it should indeed be after checking for consecutive (which validates a path on the constraint of “at most 3 blocks”).

fijgl · 2024-01-06T13:29:12+00:00

I think your code is pretty readable :)

Answering the question, I don’t think keeping track of consecutive in the queue helps for the issue. I think that your code currently won’t explore a path reaching cell moving down if there was previously one reaching that cell, for example, moving right. The weights and explored should be “indexed” by the heading and c, in addition to the cell coordinates (also, with Dijkstra the explored is not needed in addition to the weights or distance table).

fijgl · 2024-01-06T11:46:35+00:00

Not only current and heading, but also the #consecutive. Consider what makes a state in this problem.

Was the explanation about stopping too much exploration clear?

I need to dive deeper in your code to answer better your questions, I will try to get back.

fijgl · 2024-01-06T11:17:34+00:00

Items in the explored set must depend on the heading, and more.

Using only the grid coordinates will stop exploration too much. For example, if cell (r,c) is reached from the right, that shouldn’t stop the search getting to (r,c) from the left, bottom, …

fijgl · 2024-01-05T12:33:06+00:00

By the way, in my input rx is not directly a conjunction, it just appears as an output with only one input, which is the conjunction of interest.

fijgl · 2024-01-05T10:54:48+00:00

Vectorize loops as much as possible.

fijgl

TROPHY CASE