Today's problem was a spin on a pathfinding puzzle. We're given a set of instructions, like:

start-A
start-b
A-c
A-b
b-d
A-end
b-end

That describes a cave system, like:

    start
/ \
c--A-----b--d
\ /
end

There are a mixture of large caves (capital letters) and small caves (lowercase letters).

All paths must start at start and end at end.

The edges aren't weighted, so we don't need a full adjacency matrix, so a Table[Node, seq[Node]] seems like the best fit for storing this structure.

type
Node = string
Graph = Table[Node, seq[Node]]

proc parseGraph(input: string): Graph =
for line in input.splitLines():
let parts = line.split("-")
let (a, b) = (parts[0], parts[1])
discard result.hasKeyOrPut(a, @[])
discard result.hasKeyOrPut(b, @[])
result[a].add(b)
result[b].add(a)
Sidenote: Seq Unpacking

It's a shame that you can't unpack from a seq in Nim. I don't really need the intermediate parts variable here. In many other languages you can unpack/destructure directly from iterable/sequential data structures.

let (a, b) = @[1, 2]

Instead, I need to unpack explicitly.

let a = parts[0]
let b = parts[1]

Or reconstruct the seq as a tuple.

let (a, b) = (parts[0], parts[1])

This could be worked around with macros, but I wish it was a part of the default language.

The first part of this puzzle asks us to find all paths through the cave system, given the restriction that we can only visit small caves once.

Given that we're looking for all paths (rather than the shortest path) a depth-first search should be sufficient.

I ended up using an object type to represent a specific search, to make it easier to track whether a given cave had already been visited.

type
Node = string
Graph = Table[Node, seq[Node]]
Search = object
node: Node
visits: HashSet[Node]

The node property tracks the current node and the visits property tracks all nodes we visited before the current one.

I also created a VisitRule type, as a way to encode the rules about whether a given cave could be visited.

type
VisitRule = proc (search: Search, node: Node): bool

Next I implemented add for the Search type.

proc add(search: Search, node: Node): Search =
result = search
result.node = node
result.visits.incl(node)

Then the depth first search:

proc countPaths(graph: Graph, canVisit: VisitRule): int =
var stack = @[Search(node: "start")]
while stack.len > 0:
let search = stack.pop()
for next in graph[search.node]:
if next == "start": continue
if next == "end": result += 1; continue
if search.canVisit(next): stack.add(search.add(next))

And finally the visit rule.

proc isLargeCave(name: string): bool =
name[0] >= 'A' and name[0] <= 'Z'

proc canVisitSmallCavesOnce(search: Search, node: Node): bool =
node.isLargeCave or node notin search.visits

proc part1(input: string): int =
parseGraph(input).countPaths(canVisitSmallCavesOnce)

The next part wants the same answer, but modifies the rules, allowing us to visit a single small cave twice.

I couldn't think of a efficient way to encode this with a VisitRule without having the details leak into the Search itself.

I ended up just tracking whether we'd visited a duplicate as part of the Search object.

type
Search = object
node: Node
visits: HashSet[Node]
duplicate: bool

This also required a tweak to the add proc.

proc add(search: Search, node: Node): Search =
result = search
result.node = node
result.visits.incl(node)
if result.duplicate: return
result.duplicate = node in search.visits

Then it was possible to write the visit rule and get an answer.

proc canVisitOneSmallCaveTwice(search: Search, node: Node): bool =
if node.isLargeCave: return true
if node notin search.visits: return true
not search.duplicate

proc part2(input: string): int =
parseGraph(input).countPaths(canVisitOneSmallCaveTwice)

Complete solution on GitHub:

GitHub Day 12