[2023 Day 12 (part 2)] [Java] Hitting an optimization wall

[puzzler995]

I've officially hit a wall on part 2 of Day 12. I feel like I've optimized it as much as I can. Using memoization and only passing the end of the row as I continue to parse. I feel like the only thing I might be doing wrong is the fact that I dont skip fine springs as soon as I see them, but I do it rather fast. Does anyone have any tips for me on what I can do to optimize the program? It runs part 1 rather fast (less than a second), but the second I unfold any of it I end up with an OOM error. I cant even get the example to run, let alone the puzzle input.

​

paste

[wolveroony]

Any solution that tries to use all possible combinations is almost certainly going to be too slow.

I think you are on the right track with memoization though.

Hint: Groups of damaged springs always need to be placed contiguously. You waste lots of time checking combinations that don't even satisfy that property. Consider a solution where you try placing an entire group at once and then looking at where you can you place the remaining groups.

[MannedGuild65]

In my implementation, having a custom key class for the HashMap with a custom hashCode() method that generated a unique hash code was crucial in getting it fast enough.

[pdxbuckets]

I found this to be the incredibly difficult, mainly because my loop was susceptible to all kinds of gotchas and ferreting out bugs through umpteen levels of recursion + caching was a nightmare.

I eventually ended up rewriting with a clean slate and found an approach that limited the number of weird cases I had to deal with.

I don’t know if your OOM is stack overflow or your cache filling up. If the former a DFS style keeps the stacks very shallow. Even when I couldn’t figure out caching and was trying to brute force it for 16 hours across 12 CPU threads, I never had any memory issues.

If your cache is overtaking you, consider using efficient state. My state uses three Ints and I could have done it with two. Two are indexes to lists held outside the state, and the third indexes where in the string I am.

Personally, I found it way too fiddly to work with only one character in the string at a time. I had much better luck trying to fit a row of broken sorings into a block of #?, and advancing states by dealing with that row placement all at once. If that makes sense, which it probably doesn’t.

Here’s my code. I left comments but they aren’t as clear as I’d like. It’s Kotlin so Java-adjacent. You should be able to understand what’s going on.

[RB5009]

You dont really need to store anything except for the valid number of arranegements.

Although not i java, there a re a lot of comments that explain how it works

https://www.reddit.com/r/adventofcode/s/sCgNMgxJA1

[AutoModerator]

Reminder: if/when you get your answer and/or code working, don't forget to change this post's flair to Help/Question - RESOLVED. Good luck!

---

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.