I think mine is pretty much the same idea as Raul's for part 1, tough I
used symbols rather than integers for encoding the caves (nodes).
NB. Day 12: Cave mapping paths
sl=: (\: #&>) NB. sort boxes by descending length
NB. remove - and sort boxes by length s.t. start, end are first: unordered
edges, so sorting does not matter.
i12=: (sl {."1)([: sl [: <;._2 ,&'-') ;._2 in 12
NB. find all paths from start to end through caves, visiting each lowercase
cave max once
islc=: (97 ([+i.@>:@-~) 122) *./@e.~ a.&i. NB. is all lower case?
a12=:{{
links=. s: (, |."1) y NB. bidirectional links, so that can look up based
on {."1
lcn =. s: (#~ islc&>) ~. ({."1,{:"1)y NB. lowercase nodes
paths=. ,: s: ' start' NB. list of distinct paths (no box because equal
length)
complete=. 0$a: NB. boxed because ~: lengths
while. *#paths do.
NB. add possible nodes to paths (excluding visited lowercase and the
last)
NB. raze bx path apd lcn in path rem from excllast dest where
source is last
paths =. ;@:(<@(,"1 0 (#~ e.&lcn) -.~ links (]-.~ {:"1@[ #~ {."1@[
= ]) {:)"1) paths
NB. remove complete paths & add to complete
iscomp=. (s:<'end')={:"1 paths
complete=. complete, <iscomp#paths
paths=. paths #~ -.iscomp
end. NB. end if no incomplete paths left
+/#&>complete
}}
For part B, I first made a misinterpretation of the problem: I thought
*any* lowercase node could be visited twice, which lead to a ridiculous
number of solutions, prompting aggressive optimisations (in b12 below),
while the same approach of a12 would have worked as well (see b12a), though
quite a bit slower.
NB. part B: the same, but one lcn can be visited twice; start, end only
once.
b12a=: {{
NB. bidirectional links, so that can look up based on {."1
links=. s: (, |."1) y
NB. remove start as destination
links=. (#~ (s:<'start')~:{:"1) links
lcn =. s: (#~ islc&>) ~. ({."1,{:"1)y NB. lowercase nodes
NB. list of distinct paths (no box because equal length); don't store
start
paths=. ,:s:<'start'
ncomplete=. 0
NB. complete=: 0$a:
NB. *wrong*: only a single lcn can be picked twice
NB. eligible =: (lcn ([#~2<:+/@:="0 1) [) -.~ ]
NB. correct:
eligible =: (lcn ([ (#~ ]>:1+2>>./@]) (+/@:="0 1)) [) -.~ ]
NB. newlinks: make list of connected nodes, removing last (inf loop)
newlinks=: links (]-.~ {:"1@[ #~ {."1@[ = ]) {:
while. *#paths do.
NB. add possible nodes to paths (excluding visited lowercase and the
last)
NB. raze bx apd start rm lcn in path rem from excllast dest
where source is last
paths =. ;@:(<@(,"1 0 ] eligible newlinks)"1) paths
NB. remove complete paths & add to complete
iscomp=. (s:<'end')={:"1 paths
ncomplete=. ncomplete++/iscomp
NB. complete=: complete,<iscomp#paths
paths=. paths #~ -.iscomp
end. NB. end if no incomplete paths left
ncomplete
}}
NB. outcome: a: 10; b: 36
t1=: (sl {."1)([: sl [: <;._2 ,&'-') ;._2{{)n
start-A
start-b
A-c
A-b
b-d
A-end
b-end
}}
NB. outcomes: a: 19; b: 103
t2=: (sl {."1)([: sl [: <;._2 ,&'-') ;._2{{)n
dc-end
HN-start
start-kj
dc-start
dc-HN
LN-dc
HN-end
kj-sa
kj-HN
kj-dc
}}
b12 is my heavily optimised version, based on the consideration that only
the last node and set of visited lower case nodes (not quite a set, since
elements can appear multiple times, but order not important) matter in this
problem, the rest can safely be abstracted away. Doing so would lead to
many duplicate paths that can also be collapsed to a single one if one
keeps counts.
Result: 40x faster, 78x leaner
This would be able to keep track of all paths also if all lcn's would be
allowed to be visited twice, and likely more.
b12=: {{
NB. bidirectional links, so that can look up based on {."1
links=. s: (, |."1) y
NB. remove start as destination; start is not revisited
links=. (#~ (s:<'start')~:{:"1) links
NB. list of distinct paths
paths=. <"0 links ({:"1@[ #~ {."1@[ = ]) (s:<'start')
cts=. #/.~ paths NB. keeps track of duplicity of tracks
NB. remove start as source (already in paths)
links=. (#~ (s:<'start')~:{."1) links
NB. set of lowercase nodes
lcn =. s: (#~ islc&>) ~. ({."1,{:"1)y
NB. set of uppercase nodes
ucn =. s: (#~ -.@:islc&>) ~. ({."1,{:"1)y
ncomplete=. 0 NB. number of complete paths
NB. helper verbs:
NB. filter to remove non-eligible lcn's; x: path; y:reachable links
NB. wrong: only a *single* lcn can be picked twice, while the commented
one allowed *every* lcn to appear twice.
NB. eligible =: (lcn ([#~2<:+/@:="0 1) [) -.~ ]
eligible =. (lcn ([ (#~ ]>:1+2>>./@]) (+/@:="0 1)) [) -.~ ]
NB. newlinks: make list of connected nodes, removing last (inf loop)
newlinks=. links (]-.~ {:"1@[ #~ {."1@[ = ]) {:
NB. Breadth-first search:
while. *#paths do.
NB. add possible nodes to paths (excluding visited lowercase and the
last)
NB. sorted lcn's in path append eligible newlinks
newpaths =. (/:~@(}:^:(ucn e.~ {:)) <@,"1 0 ] eligible newlinks )&.>
paths
NB. ^sort essential to trim possible dupes v
newcts=. cts #~ #&> newpaths NB. duplicate original counts for each
new path
NB. flatten newpaths
newpaths=. ;newpaths
NB. sum counts for equivalent paths
newcts=. newpaths +//. newcts
NB. unique new paths, reduces maintenance cost
newpaths=. ~. newpaths
NB. remove complete new paths & add to ncomplete
NB. complete paths end in 'end'
iscomp=. (s:<'end')={:&> newpaths
NB. add complete counts
ncomplete=. ncomplete++/iscomp#newcts
NB. remove complete paths
paths=. newpaths #~ -.iscomp
NB. remove complete counts
cts=. newcts #~ -.iscomp
end. NB. end if no incomplete paths left
ncomplete
}}
(a12;b12)i12
Jan-Pieter
On Sun, Jan 2, 2022, 05:52 Raul Miller <[email protected]> wrote:
> 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
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
