@LeviKornelsen I think the heavily constrained mechanical arc of My Life With Master doesn't quite sit in category 3.
Games like Montsigeur, Rosenstrasse are also, I think, a bit outside your categories: the "plot" is defined but the "story" comes from choices within it.
What if proving sentience to the other inhabitants of the universe was just like Eurovision?
This is the first goofy scifi I've read that actually comes close to living up to Adams' Hitchhikers without overdoing it the whole way through. Parts are wryly cutting, lambasting those who deserve it, like officious governmental cogs too full of...
I decided to use a probabilistic approach. I pick 200 random pairs of nodes and find the paths between them. About half those paths use the cut-set edges, so those three edges will be used more than the others. That's enough to identity the cut-set.
A geometric approach to finding the solution, involving slicing up the map for part 2 into regions that would repeat, then finding how many of each I'd need for the final solution.
A day of two parts: variations on parsing the input, and some fiddling around with finding the area (which I admit, I just looked up after a bit of a struggle).
Things became much more simple when I stopped trying to be clever and instead represented the moves as actual Move records. I also used phantom types to handle the two types of move generation while keeping all the rest of the code the same.
Nothing much clever here. Depth first search to find the loop, breadth-first search to flood-fill the regions. The only clever bit is doubling the scale of the map to make it easy to "squeeze between pipes."
A suggestion on Reddit prompted me to revisit an earlier #AdventOfCode solution (day 2) to use the Applicative typeclass, and more use of built-in monoids.