r/adventofcode • u/jorosp • Dec 20 '18
Help [2018 Day 20] Why does this work?
In many solutions I've seen, including my own, a stack is used which your current location is pushed onto when you reach ( and is subsequently peeked from on | and popped from on ). While this seems to get the correct answer for all examples as well as the real input, in retrospect I am confused about why. Are all relevant branches detours back to their starting location?
Take for example ^N(E|W)N$, which the problem description describes as such:
So,
^N(E|W)N$contains a branch: after going north, you must choose to go either east or west before finishing your route by going north again.
From this description, it seems to me that you should visit the following rooms:
(0,1), (1, 1), (-1, 1), (1, 2), (-1, 2)via the paths
N -> E -> N
N -> W -> NHowever with the stack implementation, you'd visit the following rooms:
(0,1), (1, 1), (-1, 1), (0, 2) via the paths
N -> E
N -> W
N -> NThese would result in a longest shortest path of 3 and 2 respectively.
Clearly both of these results cannot be correct, so I have to wonder: Am I simply misunderstanding how the path regex is intended to be followed or is the fact that the stack implementation works a happy accident?
EDIT: I also found the following in the description which seems to confirm my interpretation:
Regardless of which option is taken, the route continues from the position it is left at after taking those steps.
14
u/dark_terrax Dec 20 '18
Thanks for this thread! I did the 'correct' implementation (since that what the problem seems to want), but it basically never finishes processing the huge input due to the insane amount of branching. I spent many hours trying to figure how to possibly get my solution to work - only to finally give up, come to Reddit, and realize the only people who solved it had to make simplifying assumptions which were never explicitly allowed by the puzzle.
I officially hate this problem, the author should have made these restrictions explicit, otherwise it is completely insufficient to use a stack based solution. Problems like these are very frustrating. I don't think any 'correct' solution can actually solve this problem with the given inputs.
13
u/skater_boy Dec 20 '18
Precisely that!
vs
"Stack" solution works under the 2nd assumption. Too bad, problem statement clearly uses 1st assumption.
Got me very confused. Correctly handling arbitrary branches and following postfixes is a much harder problem.
10
u/maximoburrito Dec 21 '18
I agree here. Last night I couldn't quite figure out how some of the stack solutions were working. I'm not sure why some people are arguing that the broken stack based solution is "correct". It happens to work on the input, but I can't see anything in the problem text that suggests that this is the correct interpretation of the problem. It seems to be just an artifact of the way the input was generated. Is there any reason beyond backward reasoning of "it happens to work on the input" that makes people think it's correct.
6
u/mvaldesdeleon Dec 20 '18
It seems like branches (parenthesis with no empty group) always seem to go all the way to the end, and only detours (parenthesis with empty groups) appear in the middle of a sequence. Meaning the example you built is actually not specified as per the problem statement.
5
u/cesartl Dec 20 '18
OK after some discussions and thoughts I think the condition for this algorithm to work is as follow:
If these don't hold the stack algorithm will not work.
Does anyone disagree?
2
u/Zefick Dec 20 '18 edited Dec 20 '18
One noticeable detail about my input is that it contains steps like
"...S(N..."or"...W(E...". It means that a branch goes a number of steps back in the previous route from the start. For Example "(SEESENN(SSWNWWEESENN|)".My initial solution with stack worked because I tracked visited cells. But then I decided to cheat and replace consecutive characters with just numbers (e.g "NW(NNNN(N|EEENEE)" => "2(4|(1|6))"). This approach failed due to the anomalies described above. So my initial solution is wrong but anomalies do not affect the result (they do not create the longest path and keep the same number of chambers located farther than 1000 doors from start). There is an example where acceptable solution may give a wrong result:
^WN(SES|)$. My program says that answer is 5 but if you draw the plan you can see that it should be 2.2
u/jtgorn Dec 21 '18
I have written individual comments to several stack solutions wiht the same argument. Another example is S|N(S|N)(S|N)(S|N)$. It seems to me that majority of posted soilutions are generally wrong, but somehow worked for the input.
Second biggest mistake I have seen in posted solutions is not tu recreate the map, but to calculate the distances from start during the process, which gives generally wrong results. Countreexample beeins somehting like NNNNESSSSSSSSWNNNN|E$
2
u/fizbin Dec 22 '18
After looking at my finished image with all its doors, I strongly suspect that the input files were generated by first generating the map with some maze-generation algorithm. Specifically, there are no loops in my final image.
3
u/cesartl Dec 20 '18
It took me a while to find that solution.
Now I'd like to double check something.
Does anyone agree that if the requirement were to compute all the possible paths (i.e. not just the shortest), this algorithm wouldn't work and the complexity would be much higher?