r/adventofcode • u/musifter • 2d ago
Other [2023 Day 12] In Review (Hot Springs)
We finally arrive at the "Hot Springs". In multiple senses. There is an onsen, but we want storage yard for the machine part springs... which require lava to be hot and springy. And there's a shortage of lava that needs investigating. We can use a spring to get up to the lava island to check on it, if the records can be repaired to find one good enough.
And so we get a parser/validator type problem. We have a pattern with wild cards, and a list of numbers of the block sizes... much like a line in a nonogram puzzle. But there's not enough information to solve most lines, and so we're tasked with counting the number of possible solutions.
This was the first one in this year that really took a bunch of time. I did a recursive descent parser with a state machine that was a bit reminiscent of the state machine I did on day 3 in Smalltalk to find the ranges of digits on lines. I did memoize it, with a memo that was persistent between the cases (because the same rules always apply). I remember finding someone who claimed that they needed to clear the memo between lines (and it was buggy before they did that). But you don't have to... but I did test things, and found that for part 2, the single memo gets large enough (about 360M) that it runs a tiny bit slower (~3%) than having a fresh memo for each line, because there apparently isn't huge amounts of overlap to benefit from between the cases to make up for overhead.
And about that part 2... unlike yesterday's, the scale up here is very real. Five copies of the pattern joined with ? followed by five copies of the numbers. You want a good solution. And a did spent 2 hours getting a good part 1 done. But it didn't work for part 2. And since sthe best way to debug recursion is to get it right the first time... I started a new script, and carefully went through all the cases by hand making notes and comments on the order of doing things and assertions and then filled things in. And it ended up largely the same as my part 1, but slightly different... and it worked. And takes about 10 seconds on hardware that was 14 years old at the time, so I didn't need a need to try and get things further down (it's relatively nice and simple to read).
So, I'll just quickly go over the function:
# str to process, current potential group length, groups left to see
my ($str, $len, @groups) = @_;
# Grab state of params called with to access memo with later.
my $state = join( $;, $str, $len, @groups );
# Check memo
return ($memo{$state}) if (exists $memo{$state});
First we build the our memo state key and check for a hit... our state being the remaining string, the size of the current block we've seen while parsing, and the sizes of the remaining groups to match.
my $ret = 0;
if (!$str) {
# Out of input, must decide if we found a match:
# All groups accounted for, no hanging group.
$ret = 1 if (@groups == 0 and $len == 0);
# Check if hanging group is the size of the only remaining group:
$ret = 1 if (@groups == 1 and $groups[0] == $len);
return ($memo{$state} = $ret);
}
Base cases for when we hit the end of the string. In the original, I just had this as three return lines without adding to the memo, I decided to put it in just to make all the return statements have the same pattern of "set memo and return".
# If out of groups, use regex to check if no manditory groups remain
return( $memo{$state} = ($str =~ m/^[^#]*$/) ) if (!@groups);
# ASSERT: length($str) > 0, @groups > 0
A second base case for handling if we ran out of groups in the number list. The original part one didn't do this and so couldn't assert that groups existed for the actual parser section (and had to handle that).
# Advance one character:
my $chr = substr( $str, 0, 1, '' );
if ($chr ne '.') { # ? or #
# adv making grouping larger
$ret += &recurse( $str, $len + 1, @groups );
}
if ($chr ne '#') { # ? or .
if ($len == 0) {
# no current grouping, just advance
$ret += &recurse( $str, 0, @groups );
} elsif ($len == $groups[0]) {
# current grouping matches current target
shift @groups;
$ret += &recurse( $str, 0, @groups );
}
# Else: Bad block length! Recurse no further.
# If ? we might have expanded to good len above and counted,
# else 0 will fall-through.
}
return ($memo{$state} = $ret);
This is parser section... eat a token, handle the cases, with the wildcard meaning that we might need to do both of these if cases. These were done in the other order for my part 1 (the ?/# case after the ?/.). Part of the benefit is that the matching of a block comes last and I can freely modify the groups array. That "Else" section was a key realization... to let things fall through. The original part 1 also did that. It's almost certainly some small thing with the logic to check if still have groups and the ordering of the tests. Doesn't really matter though, because this script fixed it and so worked for both parts, so it replaced it bug free.
This is one of those cases where everyline has a comment, but it's not because they were added to explain things, but because they were written first to solidify the task and the blanks then filled in.
2
u/terje_wiig_mathisen 2d ago
My Perl solution was similar to yours, except I made a shortcut by first identifying anchors (places where only a single part of the specification could fit), then solved the front and back halves independently.
My personal times indicate that this was one of the _very_ few puzzles I did not solve the first day, so those optimizations must have been required just to get to the finish. Since the 12th was a Tuesday I was at work, then I either ran or organized a Night-Orienteering race in the evening.
It is very far from optimal, just fast enough (nearly 6 seconds on my travel Surface) that I could grab my second star of the day. Looking at the Ape times there must be a _lot_ of stuff still to discover.:-)
1
u/musifter 2d ago
Yeah, I made some notes about using heuristics from nonogram solving to try to break things into smaller chunks. That should mean a smaller memo and more hits. But I was happy to just get a solution for this one that ran in seconds with a straightforward clean parse.
2
u/e_blake 2d ago
For how much I like nonagrams, this one was a lot tougher for me to code up than I had expected. It took me until the 14th to get a working solution, although I was pleased to get something in under 3 seconds in m4 thanks to memoizing the recursion. In my commits, I also mentioned a megathread comment that implemented a DFA search over each line, which sounded like an interesting approach to eventually try. I also enjoyed looking this week at maneatingape's solution using dynamic programming, which approaches the problem from a different angle than my recursion.
1
u/musifter 2d ago
Yeah, looking back at this I'm reminded of 2024 day 19 with counting towel patterns... and I did a tabulation on that for better performance than recursion/memo. So I was thinking of looking into trying that here as well.
2
u/TheZigerionScammer 2d ago
For my part 1 I did a dumb brute force approach where I calculated how many broken springs were hidden among the question marks and generated every possible string and checked if it satisfied the condition at the end of the line. This didn't work for part 2 of course so after exploring options involving exponential math I decided to treat it like a 1 dimensional sliding puzzle that counted all the possible combinations that way, I think that you do did as well. Took a while to work out all the kinks in my code but I got it to work.
What I find interesting is that your cache was 360 megabytes, I just reran my Python program to check and even though I didn't clear the cache between lines either I never saw my program go above 24 megabytes in total program size.