I had a little problem with your code here. You had a lot of long
lines, which got wrapped in email (mostly comment lines). I think I
have those all sorted out now, But, I also got this:
|value error: in
| i12=:(sl{."1)([:sl[:<;._2,&'-');._2 in 12
If I change that line to
i12=:(sl{."1)([:sl[:<;._2,&'-');._2
this seems to work:
(a12,b12) t1
10 36
(a12,b12) t2
19 103
Does that match your expectations?
Thanks,
--
Raul
On Sun, Jan 2, 2022 at 10:21 AM Jan-Pieter Jacobs
<[email protected]> wrote:
>
> 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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
