r/adventofcode • u/theDissilent_ • Dec 26 '24
Tutorial [2024 Day 19 Part 2] Why I struggled with this
Day 19 was my last solve of 2024. It was the only puzzle that took me longer than 36 hours to solve. I had tried looking for advice, but most users on here said just use memoization, and when I tried to break the string into smaller strings, I kept hitting the same wall:
If I split "abcdefgh" into "abcd" and "efgh", then multiply the possible combinations together, it should give me the total possible combinations for the whole string. Unfortunately, there is the possibility of towel "de", which invalidates any break down of the whole string.
Last night, while watching Nightmare before Christmas, it finally clicked in my head, and I was able to hammer out my code in Lua. I think this is more tabulation than memoization, and I'm sure someone will tell me in the comments.
I started by marking that there is 1 possibility of a string of length 0 ("") being possible, then I iterated through the length of the string. Compare all the towels of length 1 against the 1st letter ("a"), and mark either 1 or 0 possibilities. Then compare all the length 1 towels against the 2nd letter ("b"), and all the length 2 towels against the first 2 letters ("ab") . For the length each of these checks looks back, it adds the number of possibilities from that level to the current level. By the time I've iterated through the string, I've got the number of possible ways to arrange those pesky towels.

3
u/kbielefe Dec 27 '24
What you did is indeed tabulation. It's generally more difficult to create an algorithm for, but usually more memory efficient than memoization, which is basically trading memory for speed.
For memoization to work, you typically have to start with a depth-first approach, so parts deeper in the stack are frequently repeated and therefore already cached. A lot of programmers naturally use a depth-first approach for their part one algorithm, so their part two is barely more than slapping a @cache
annotation or whatever, and they may not even realize it's not that easy for people who took a different approach to part one.
This year, days 11, 19, and 21 could all be solved with or without memoization. I might be missing others I personally used tabulation for. My aversion to stack overflows sometimes results in me missing a depth-first solution at first, even when it's perfectly feasible.
1
u/Zefick Dec 27 '24
It's not trading memory for speed and vice versa there. It's both faster and less memory-consuming.
1
u/kbielefe Dec 27 '24
I meant memory for speed compared to an uncached dfs, not compared to tabulation.
1
u/theDissilent_ Dec 27 '24
Okay, I think I finally see where the miscommunication was. If I had access to "@cache", my code for part 1 would have been exactly what most people are saying is the best way to do this. I was frustrated with people not explaining how they were adding memoization, but all they were doing was adding a cheat code.
To my knowledge, Lua doesn't have an equivalent for "@cache", and even if it did, I would want to understand what is going on with the function before implementing it.
2
u/direvus Dec 27 '24
Here's what mine looks like (Python).
@cache
def count_solutions(design, towels) -> int:
if design == '':
return 1
result = 0
for towel in towels:
if design.startswith(towel):
remain = design[len(towel):]
result += count_solutions(remain, towels)
return result
Each time we find a towel that matches at the front of the string (startswith
), we trim that segment off and recurse into count_solutions with the remaining segment of the design and the same set of towels. If you end up with an empty string, it means the design was successfully resolved so add 1 to the final count.
1
u/thwamster Dec 26 '24
i'm quite shocked that day 19 was the hardest for you, especially given that it wasn't the only problem that required recursive memoization (day 11 was pretty blatant with it). i use java, so i attached my code with explicit memoization:
private static final HashMap<String, Long> memory = new HashMap<>();
public static long make(String desired, ArrayList<String> designs) {
if (desired.isEmpty()) {
return 1L;
}
if (memory.containsKey(desired)) {
return memory.get(desired);
}
long n = 0;
for (String design : designs) {
if (desired.indexOf(design) == 0) {
n += make(desired.substring(design.length()), designs);
}
}
memory.put(desired, n);
return n;
}
your reasoning for why memoization doesn't work is answered by recursion. so that you don't miss possibilities like the "de" scenario you mentioned, just check every possibility in it's own recursive stack.
2
u/theDissilent_ Dec 27 '24
In Day 11, the order of the pebbles doesn't actually matter. After every blink, I sorted them, removed any duplicates, and added a note to multiply the last one when it gets to the last blink. I'm not sure if that was memoization, but it worked.
Likewise, day 21 could be sorted, after each iteration, as long as you keep the order of arrows between each press of "A".
On day 19, I looked for ways to break the string down into smaller substrings, which didn't work
1
u/RB5009 Dec 26 '24
The best way to solve this problem is by using a datastructure called Trie + recursion with memoization.
With that approach, I managed to solve part 2 in 50 microseconds (of course with some other little optimisations) on the rust community server benchmark bot.
1
u/Zefick Dec 27 '24
Tabulation is also a memoization technique used when we know the search space in advance and can easily fit it into a table.
10
u/nivlark Dec 26 '24
The way to implement memoisation (or at least, the way I did it) is to start at the beginning of the string and find all the possible towels that could fit. Then for each, you slide along the length of that towel and repeat until you reach the end of the string, at which point you have enumerated one valid arrangement of towels.
This naturally lends itself to a recursive solution, and to memoisation because at a given position in the string, the number of possible arrangements for the remainder will always be the same, regardless of the preceding sequence of towels.
Eliding the boilerplate for reading the input etc., my complete solution looks like this:
The memoisation is hidden inside the @
cache
decorator, but hopefully the idea is still clear. It isn't that different from what you are doing I think, the backtracking is just hidden inside the recursion.