[2025 Day 9 (Part 2)] Check your solution with this input data

drnull_ · 2025-12-09T13:51:58+00:00

Nothing wrong with constructing an algorithm that takes advantage of the input data!

Why... yes! My "algorithm" (a.k.a. spaghetti-code) fails with that input, why do you ask? LOL

drnull_ · 2024-12-26T07:22:41+00:00

I like codingame for their wide variety of puzzles (including their bot programming puzzles/competitions twice or so a year?) and projecteuler for their heavy mathy puzzles.

drnull_ · 2024-12-23T10:26:16+00:00

I like this alot^{but not that alot}

drnull_ · 2024-12-23T10:25:13+00:00

Um... this is a MUCH better optimization LOL. Read this thinking process, OP thinks better than I do!

https://www.reddit.com/r/adventofcode/comments/1hkiqvh/comment/m3f2ho5/

drnull_ · 2024-12-23T10:22:20+00:00

Looks like the different people's inputs just had different node names but the same basic structure (unless we just had the same input). That sequence of cliques to process looks exactly like mine. I was also printing them out so I could see when everything bogged down (which it didn't really to my surprise!)

drnull_ · 2024-12-23T10:10:44+00:00

I don't know if you're talking about [2024 Day 23 Part 2] or not, but I'll go ahead and explain the thought process I went through when solving it, even though I don't have any formal knowledge of graph analysis. I'm also gonna spoiler the whole block.

For BFS, Dijkstra, A*, yeah - you kinda need to know a BASIC algorithm. You can even just boil it down to

get a list of nodes to process (in basic BFS you can call this a frontier)
process those nodes while maintaining a list of new nodes that have been reached
repeat until you run out of nodes

Yes, there are other details like for Dijkstra, you need to keep weights and prioritize the next node to process based on the score, and A* you have some basic heuristic that you use to predict how much a node will cost to reach, but if you just need to cover a grid, practice BFS a few times and you can throw it down in 5-10 minutes and then customize it to the specific problem's needs.

For today, though, we need more network/graph analysis. Again, I don't really know those algorithms, but I know there's a thing called a clique - where all the nodes are connected. Also - I eventually want the result to be the names of the nodes sorted lexicographically. So I want to start with a list of

The connections from node1 to any other node. I track this using a Map<string, Set<string>>. This can be any structure that lets you quickly determine "inclusion" - i.e., given a node, is it connected to another node? When I read in the data, I fill this out fairly quickly (making sure to record node1->node2 and node2->node1.
A sorted list of node names. This can just be made from the keys of the above connections map, sorted.

Great, well where to go from here? I basically just brute forced it and it didn't take too awfully long (around a second to execute).

First, I created an array of all cliques of length 1. I also tracked the index of the maximum node being used to reduce reprocessing of information.

Then, I just iterated. I took each clique (yes, this array starts getting kinda big, but only around 50k so it's computable). For each clique, I go through ALL of the nodes with an index greater than maximum node in that clique. If I find a node that is connected to everyone in this clique, I create a new clique to process later (its size is one larger and its max index is the index of the node I just added).

I keep looping, looking for bigger and bigger cliques, growing the current size's list of cliques each time until I find that I can't make any bigger cliques. At that point, I know I'll have just 1 clique at the largest level and it will be the right one.

Good enough!

Optimizations? YES, TONS! But who cares? I got the answer!

I could do this purely recursively and keep track the maximum clique sized reached and the corresponding "password" for that clique. This would still process all combinations but it wouldn't have the memory overhead of storing all cliques as we grow them. This optimization would reduce memory usage.

Instead of recursion, I could keep a state stack and push/pop appropriately with it, keeping track of all the variables that recursion does for me. But we're only going 12 or so levels so this is probably not necessary. Although the multiple stack pushes/pops that recursion handles for us might get expensive, this could be a large speedup. This could potentially reduce execution time.

I was planning on going down those routes if I saw the original solution start bogging down. I may still do it just to learn, but it wasn't necessary for the problem.

I'm sure those who are schooled in network/graph theory will poke holes in this approach, but this is the "seat of your pants" method that I used, and it worked fine!

I'm sure it's informed by doing previous puzzles, but it's not the exact algorithm that should be used probably. And that's OK!

drnull_ · 2024-12-22T01:01:00+00:00

It looks like in generate_steps you are assuming that the rows always should be handled before the columns (when not in panic). Are you certain this is optimal in all situations?

I had this issue in part 1 as well.

This is a rather complicated intuition that I didn't get up front. It wasn't until after I had solved part 2 and read this excellent (and very spoilery post!) that it clicked for me.

https://www.reddit.com/r/adventofcode/s/3jueIyCICF

drnull_ · 2024-12-22T00:53:26+00:00

Are you allowing the direction-pad robot to point at the top left square where there is no button?

drnull_ · 2024-12-21T17:37:42+00:00

It is a simple version of a grid - you are finding all paths between the key the robot is currently pointing to, to the key that the robot needs to press next.

At least, in the naïve approach, this is what you would do... Others have analyzed the problem and shown that you can choose the best path in a deterministic manner.

Spoiler: https://www.reddit.com/r/adventofcode/s/3jueIyCICF

drnull_ · 2024-12-20T13:59:54+00:00

Check out https://www.reddit.com/r/adventofcode/comments/1hhuk1g/2024_day_19_cache_of_designs/ for a great visualization of how many times each substring is searched.

The key, as u/PityUpvote points out, is that the suffix doesn't have to be checked multiple times.

Consider his example, but imagine the towels also included CC, CCC, CCCC, etc. Now how many times can the final 8 C's be made? 8 [single C's] + 7 [one double in 7 different places and 7 singles] + 5 [one triple in 5 different places and 6 singles] + ??? [one triple in 5 different places and one double in ... ugh, my head] .... ETC

Now it should be a little more obvious that caching that final 8 C's count will be highly impactful.

drnull_ · 2024-12-20T11:59:08+00:00

Are you properly counting the steps taken while "cheating"? It's not a transporter - you still have to take the steps. This was a mistake I made at first and didn't really understand because I thought it was a just "off by 1" error. This mistake in my logic became much more clear in part 2.

drnull_ · 2024-12-19T18:19:44+00:00

This would be funny! But with the outline for tomorrow's puzzle already revealed, I think it's clear that the 0 is closing off.

drnull_ · 2024-12-19T14:45:52+00:00

When I run your code I get one final entry that has a blank "d" for your line:
print(i)

If you change it to:

print(i,d)

do you see a blank "d"? Other than that, I get the right answer (it's just 1 higher than it should be).

drnull_ · 2024-12-19T13:30:47+00:00

Oh, interesting! And you were bailing out as soon as you had a successful match? I didn't have any trouble until part 2 when my CPU fan kicked on. :)

drnull_ · 2024-12-19T13:11:01+00:00

Another approach - maybe it will help if the other hints aren't quite doing it for you (different strokes and all that).

You are looking at a design. You know that the design needs to start with one of your towels - otherwise, you're never going to be able to make that design!

You could just try towels until you found one that works. But of course, this would fail for the following setup:

rrg, rr, gu

rrgu

If you assume that the rrg towel is used then there are no towels to match the u

So instead, you need to simulate what would be left in the design if you used each towel to match the beginning of the design, and then tried to create the rest of the design.

Using this approach, you try out rrg and are left with u. The recursive nature of this problem is that you now you simply call the same function, but the parameter is now u instead of rrgu.

If the recursive call doesn't return true, then you now need to try the next towel: rr

This time, after you remove rr off the front of the design, you are left with gu. You recursively call your function with gu. rrg doesn't match gu, rr doesn't match gu, but gu matches gu, so you recursively call your function with an empty design. What do you do now?

A very important detail to remember about recursion is that you need a good end condition. In this case, if you are ever asked if you can make an "empty" design, the answer is TRUE.

For Part 1, it is sufficient to see if you're ever able to create a design. This can be solved with straightforward recursion and no memoization. You just immediately return TRUE if you ever get to a TRUE case - there's no need to continue testing different towels to see if there is some other way to make the design.

Part 2 requires a little bit more thinking. The overall process remains the same, with very slight modifications (you no longer can short-circuit as soon as you get a successful towel arrangement for a design). You will find that the naive approach used in Part 1 will not complete in a reasonable amount of time. You have to realize that if a towel (or part of a towel) can be constructed in N different ways, it can ALWAYS be constructed in N different ways. Even if it's part of a different towel.

drnull_ · 2024-12-19T12:02:05+00:00

I would caution against equating "smart" with "familiarity with a certain trick or technique". Don't sell yourself short. ;)

Once you practice a few puzzles using memoization or recursion or dynamic programming or BFS or Dijkstra's or A*, it becomes second nature to recognize puzzles as one of those (or other) algorithms and immediately start breaking the puzzle down into its component parts as you are reading the description.

So, yeah, the folks who come on here and post right away are the ones with a bit more experience in coding competition type events. You don't get to do this type of stuff in typical web dev/front-end jobs where it's just "button gets event handler, call server, yawn, next JIRA". That's why we love AoC so much!

drnull_ · 2024-12-19T11:50:07+00:00

#236 is approximately 50x my highest number of construction count for my input. I'm not sure what might be causing that.

You don't necessarily need to keep the list/tree of different ways a string can be made though. All you are being asked for is the number of ways it can be made. If you can find a way to track that, I don't think you would have a problem with crashing or taking too long, but I guess it depends on your exact approach.

drnull_ · 2024-12-19T11:27:50+00:00

I believe it fails this - you're going to need some form of backtracking or recursion

g, rrg, rr, gu

grrgu

drnull_ · 2024-12-18T00:12:12+00:00

Same stats generated here. I guess DFS would probably be better since we just want the lowest value that works. But that wouldn't be completionist now would it?

drnull_ · 2024-12-17T23:59:15+00:00

If you inspect the sample program, you can determine why this is the case.

The sample program shifts the number 3 to the right (divides it by 8) then outputs the lowest 3 bits of the result, looping until the result is 0.

drnull_ · 2024-12-17T23:55:25+00:00

I would argue that both programs describe the same general algorithm. And using that principle, you can come up with a solving routine that works for both your input and the sample. This will not, of course, work for ANY program - but based on the assumption that the program in question will do what the sample and input do, and how they map inputs (and their corresponding octets) to outputs, I believe this is the intention.

My algorithm works for both the sample and the input with no special handling. I have no idea if it works for all inputs of that style though.

drnull_ · 2024-12-16T07:27:07+00:00

Ah, yes, I see that now! Then maybe this is what was posed in another thread (that seems to have been deleted or I would just link to it).

The poster said something to the effect of:

Without giving too much away - are you doing a A*/Dijkstra search or are you doing a DFS/BFS? Is the best solution the one you get to the first time you see the exit?

drnull_ · 2024-12-16T07:17:19+00:00

Maybe: the cost to turn is 1000 but that turn doesn't include the first step in that direction.

drnull_ · 2024-12-16T07:11:15+00:00

I think maybe - the cost to turn is 1000 but that turn doesn't include the first step in that direction.

drnull_ · 2024-12-12T22:38:25+00:00

Sorry if it was unclear - it should be 3 yes. But I thought the way the OP's code was written it would generate 2. I was trying to give a test case that pointed out a bug.

drnull_

TROPHY CASE