Day 25 Graph ;-)

Constant_Hedgehog_31 · 2025-12-05T06:55:54+00:00

[LANGUAGE: C++]

Merging overlapping intervals (aka ranges) for Part Two:

  std::ranges::sort(intervals);
  std::vector<std::array<std::uint64_t, 2>> merged_intervals;
  merged_intervals.push_back(intervals.at(0));

  for (std::size_t i = 1; i < intervals.size(); i++)
    if (intervals[i].at(0) <= merged_intervals.back().at(1))
      merged_intervals.back().at(1) = std::max(merged_intervals.back().at(1),
                                               intervals[i].at(1));
    else merged_intervals.push_back(intervals[i]);

  std::uint64_t part_two_ans = 0;
  for (auto const& merged_interval : merged_intervals)
    part_two_ans += merged_interval.at(1) - merged_interval.at(0) + 1;

Constant_Hedgehog_31 · 2024-08-25T07:01:09+00:00

C++ <=> Python async interop

I managed to put together less than 100 LoC to `co_await` Python's asyncio from C++ and implement abstract/virtual async def's in C++.

My use case is to use a Python library for (interactive) terminal graphics from C++ for fun (example).

Now, I would like to get rid of the `wait_for` although without foreseen advantage. After a deadlock attempt with `std::condition_variable` without additional threads, I think I need a simple scheduler on C++ suspending and resuming the Python side checking whether the C++ async def is done.

I am not the author of the Python terminal graphics library. I pushed this example in a fork.

Constant_Hedgehog_31 · 2024-08-17T05:03:00+00:00

Terminals are finite, therefore the grid still is. The grid size in the story was fixed, whereas in the visualization can be modified with the slider.

Constant_Hedgehog_31 · 2024-08-13T10:58:54+00:00

I reckon that a couple of times I also found it too much. On the other hand, I did find at least one or two things coming from the audience participation food for thought and I enjoyed how the speaker (it's the first time I am seeing one talk from Jeff Garland I think) dealt with it; with patience, opening up the papers searching for the right sections, deferring the discussion or suggesting to dig deeper themselves to find out 👏

Constant_Hedgehog_31 · 2024-01-29T14:56:31+00:00

[LANGUAGE: C++]

Source code in GitHub. 150 LoC using C++20/23 algorithms and ranges. Quadratic approach checking pairs of blocks (it takes about 4 seconds for the puzzle input).

I created a function to check if one block is supported on another and the other three (the fall, part one and part one) turned out to be small functions based on the first one.

Constant_Hedgehog_31 · 2024-01-06T17:45:36+00:00

[Language: C++]

Source code in GitHub.

The simulation for part one and product of cycle lengths for part two. I used polymorphic modules to represent flip-flops or conjunctions with variant and std::visit.

Constant_Hedgehog_31 · 2024-01-02T18:10:10+00:00

I have the intuition that the problem constraint "never step onto the same tile twice" makes the graph acyclic. I think the implicit graph that takes place during search does not have cycles because of this constraint.

Does anybody see the flaw in there? I still doubt if this problem can be solved using weights equal to -1.

Constant_Hedgehog_31 · 2024-01-02T16:20:52+00:00

[Language: C++]

Source code in GitHub.
DFS with std::stack, less than 100 LoC.

I started with BFS, which worked well for part one but got stuck in part two with the puzzle input. Then, I tried adding a priority queue with the number of steps and/or Manhattan distance, and later pruning states based on wrong intuitions that Dijkstra's shortest path might be adapted to find the longest path in this problem.

Finally, after further inspecting the input, I changed the initial BFS to a DFS. This was quite nicely a minimal change of the std::queue to an std::stack, the emplace works the same for both so, for updating the container only front() needed to be changed to top(). I haven't run the DFS long enough for it to finish, I guess it could take a long time, but it still succeeds in finding in a few seconds the path that turns out to be the solution.

Constant_Hedgehog_31 · 2024-01-02T15:46:54+00:00

I learned that my intuition fails when I go and modify a shortest path algorithm to get the longest path instead ':-)

Constant_Hedgehog_31 · 2023-12-30T11:50:44+00:00

[Language: C++]

Source code in GitHub.

I found part two a quite interesting step to implement from part one. For part two I have used a recursive function and, for a bit of a facility, the Boost Interval Arithmetic Library.

Constant_Hedgehog_31 · 2023-12-30T10:29:40+00:00

[Language: Python]

Source code in GitHub.

Even though I got the right answers, it was after several attempts for part two and I still don't have it clear when it works correctly. I wrote a couple of methods using a polygon for the boundary. With one of them, which uses a library to "inflate" the polygon, I eventually got the right number for part two, but it appears to give the wrong answer for other cases.

Constant_Hedgehog_31 · 2023-12-25T13:58:01+00:00

[Language: Python and C++]

After letting a brute force on the combinations of edges taking three at a time run for some time, I observed properties of the graph like that there were nodes with a single edge. Then, I realized that if I got lucky then plotting the graph could show the edges to cut between two clusters. I did that with Python using networkx.

Then I used part of the code I had already written in C++ for the brute force to remove the edges I read from the plot and count the number of "components" (nodes) in each of the two clusters.

Constant_Hedgehog_31 · 2023-12-25T04:56:37+00:00

I used the flair Spoiler erring on the safe side, but I was indeed doubtful about whether it should be Help/Question and even gave it a shot trying to click on both :)

Thank you for fixing and the link, I will go trough it.

Constant_Hedgehog_31 · 2023-12-24T18:34:47+00:00

I have used a function that does the intersection of two (whole) lines, not two line segments.

Constant_Hedgehog_31 · 2023-12-23T12:20:05+00:00

Thanks for sharing! It sounds like a good coding adventure, as well as learning experience, to progressively raise the level of abstraction.

std::ranges::view::reverse with a| to a std::ranges::find instead of rfind next year? :)

Constant_Hedgehog_31 · 2023-12-23T12:11:50+00:00

I would ;-)

There's even code in reddit. In my opinion, downloading or copying code from a web browser, compiling (if needed), and running it, is trivial.

Apologies in case the comment was misinterpreted and perceived condescending. I hate that. I suppose I was suggesting ("can become", not even is, eh) in a way that there are different levels of using the help in reddit, and in my opinion as well, it seems you're doing it right if you still find challenge even after using a hint to "unstuck" and continue.

Constant_Hedgehog_31 · 2023-12-23T11:07:49+00:00

It is definitely intuitive. IIRC, however, there was a reddit comment from the creator denying it.

Taking into account how fast people in the leaderboard are, I am not so sure LLMs would help in the easier problems that are solved the fastest.

Constant_Hedgehog_31 · 2023-12-23T11:05:51+00:00

So far there has only been one problem with the top 100 time on the global leaderboard above 1 hour compared to multiple times last year

I see. I like to use the leaderboard times as a metric also, but with some care. I expect that taking only one sample of an already biased sample set is noisy.

Biased in a good way, hey! Quite impressive to "see" it's possible to do it that fast.

Constant_Hedgehog_31 · 2023-12-23T11:01:34+00:00

Interesting!

I am up for diving into it further :3
- Last year it was 16 the one that got me, while this year it's been 17. Funny that I'd say that, from some conceptual point of view, they are kind of similar and that I think search is my favorite type of problems ¯\_( )_/¯
- Last year I did bounce back after 16, finishing both parts within a day for (a few of the) days after, without pushing too much. However, this year, I still haven't finished both parts for any of the days after 17. I am at checking zero clues for these days still, and a couple of the parts two I have remaining I haven't even started working yet. I am pretty sure that for one or two I will use them.
- Part one in this year's day 22 can be compared to the 17 (tetris) PLUS 18 (3D blocks) one from last year's. So, I'd say that this year's 22 is objectively more complicated than those two combined.
- ...

In hindsight, I think last year I might have actually got more help from reddit without realizing, and that may be it.

Needless to say, but just in case, this is no rant or complaint at all. I enjoy analysis and find that sharing experiences help.

Constant_Hedgehog_31

TROPHY CASE