https://adventofcode.com/2021/day/12
For day 12, we had a "cave map" which was a list of connections
between named pairs of rooms.
unpack=:-.&;:&'-';._2
sample=: unpack {{)n
start-A
start-b
A-c
A-b
b-d
A-end
b-end
}}
Here, our puzzle task, for part A, was to explore the cave system. We
needed to visit each room at least once. Rooms with lower case names
needed to be visited exactly once. Rooms with ALL CAPS names could be
visited as many times as we wanted. Specifically, we needed to count
how many distinct paths lead from 'start' to 'end'.
I could have solved this more elegantly, but here was my approach for
that part of the puzzle:
a12=:{{
c=. (#~ (<'end')~:{."1) (#~ (<'start')~:{:"1) y,|."1 y
ref=. ~.a:,,c
'from to'=. |:ref i.c
'start end'=. ref i.;:'start end'
r=. i.0 0
paths=. (start = from)#from,.to
reps=. (i. (#~ ] = toupper each)) ref
while.#paths do.
done=. end = {:"1 paths
r=. r, done#paths
paths=. (-.done)#paths
nexts=. (-.to e."1 paths -."1 reps)*({:"1 paths)=/from
paths=. ((+/"1 nexts)#paths),.(,nexts)#(#,nexts)$to
end.
;:inv r { ref
}}
Basically, the connection pairs were two way (except for start and
end), so the first thing I did was convert the bidirectional
connection pairs to unidirectional connection pairs (c).
Then, I assigned integer cave ids and set up my initial state (a list
of incomplete paths from the start location -- technically, I could
have left the start node out of my 'ref' of connection pairs, since I
would never use those connections again).
Once I had that, I started tracing through to all the possible next
available connections for each of my paths (breadth first search), and
moving each complete path to my result variable.
At the end, so I could comprehend the result, I converted the paths
back to a textual form. The actual result I needed was #a12
#a12 sample
10
For part B, the rules changed. Except for start and end, we could also
visit one (and only one) of the rooms with lower case names twice.
Again, there's certainly tidier ways of solving this, but here's how I
approached that:
b12=: {{
c=. (#~ (<'end')~:{."1) (#~ (<'start')~:{:"1) y,|."1 y
ref=. ~.a:,,c
'from to'=. |:ref i.c
'start end'=. ref i.;:'start end'
r=. i.0 0
paths=. (start = from)#from,.to
reps=. (i. (#~ ] = toupper each)) ref
while.#paths do.
done=. end = {:"1 paths
r=. r, done#paths
paths=. (-.done)#paths
any=. 1 = >./"1 }."1 #/.~("1) 0,.paths -."1 reps
nexts=. (any+.-.to e."1 paths -."1 reps)*({:"1 paths)=/from
paths=. ((+/"1 nexts)#paths),.(,nexts)#(#,nexts)$to
end.
;:inv r { ref
}}
The big difference here was that I was tracking whether any
destination room was viable or only unvisited and ALL CAPS rooms were
viable destinations. Other than that, it's the same as the part A
implementation.
And, similar to part A, the actual result I needed was #b12
#b12 sample
36
--
Raul
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
