≡ Day 23 of Advent of Code in q

Author - Rory Kemp

--- Day 23: LAN Party ---
As The Historians wander around a secure area at Easter Bunny HQ, you come across posters for a LAN party scheduled for today! Maybe you can find it; you connect to a nearby datalink port and download a map of the local network (your puzzle input).

The network map provides a list of every connection between two computers. For example:
kh-tc
qp-kh
de-cg
ka-co
yn-aq
qp-ub
cg-tb
vc-aq
tb-ka
wh-tc
yn-cg
kh-ub
ta-co
de-co
tc-td
tb-wq
wh-td
ta-ka
td-qp
aq-cg
wq-ub
ub-vc
de-ta
wq-aq
wq-vc
wh-yn
ka-de
kh-ta
co-tc
wh-qp
tb-vc
td-yn
Each line of text in the network map represents a single connection; the line kh-tc represents a connection between the computer named kh and the computer named tc. Connections aren't directional; tc-kh would mean exactly the same thing.

LAN parties typically involve multiplayer games, so maybe you can locate it by finding groups of connected computers. Start by looking for sets of three computers where each computer in the set is connected to the other two computers.

In this example, there are 12 such sets of three inter-connected computers:
aq,cg,yn
aq,vc,wq
co,de,ka
co,de,ta
co,ka,ta
de,ka,ta
kh,qp,ub
qp,td,wh
tb,vc,wq
tc,td,wh
td,wh,yn
ub,vc,wq
If the Chief Historian is here, and he's at the LAN party, it would be best to know that right away. You're pretty sure his computer's name starts with t, so consider only sets of three computers where at least one computer's name starts with t. That narrows the list down to 7 sets of three inter-connected computers:
co,de,ta
co,ka,ta
de,ka,ta
qp,td,wh
tb,vc,wq
tc,td,wh
td,wh,yn
Find all the sets of three inter-connected computers. How many contain at least one computer with a name that starts with t?

We can read the connections using the CSV reader.

show ("SS";"-") 0: `23.txt
kh qp de ka yn qp cg vc tb wh yn kh ta de tc tb wh ta td aq wq ub de wq wq wh..
tc kh cg co aq ub tb aq ka tc cg ub co co td wq td ka qp cg ub vc ta aq vc yn..

As the graph is undirected, we also want to append the other directions. Then, use group to determine the neighbours of each node.

show G: {y group x} . {x,'reverse x} i: ("SS";"-") 0: `23.txt 
kh| tc ub ta qp
qp| kh ub td wh
de| cg co ta ka
ka| co de tb ta
yn| aq cg wh td
cg| tb de yn aq
vc| aq ub wq tb
tb| ka wq vc cg
wh| tc td yn qp
ta| co ka de kh
tc| td kh wh co
td| qp yn tc wh
aq| cg yn vc wq
wq| ub aq vc tb
ub| vc qp kh wq
co| tc ka ta de

To find 3 nodes that are all connected, we start by looking at all pairs. Then, a 3rd node has to be a neighbour of each of them.

{(inter/) G x} each flip i

`symbol$()
,`ub
`symbol$()
`de`ta
,`cg
,`kh
`symbol$()
,`wq
`symbol$()
,`td
,`aq
,`qp
`ka`de
`ta`ka
,`wh
,`vc
`tc`yn`qp
`co`de
,`wh
,`yn
,`vc
,`wq
..

raze {x ,/: (inter/) G x} each flip i
qp kh ub
ka co de
ka co ta
yn aq cg
qp ub kh
vc aq wq
wh tc td
yn cg aq
kh ub qp
ta co ka
ta co de
de co ta
de co ka
tc td wh
tb wq vc
wh td tc
wh td yn
wh td qp
ta ka co
ta ka de
td qp wh
aq cg yn
..

Now, we sort each, and filter the ones where any start with a t.:

{x where "t"in/:first each' string x} distinct asc each raze {x,/:(inter/) G x} each flip i
co ka ta
tc td wh
co de ta
tb vc wq
td wh yn
qp td wh
de ka ta

The result is the count, or the sum of the boolean values.

sum "t"in/:first each' string distinct asc each raze {x,/:(inter/) G x} each flip i
7i

Part 2:

Part 2 Original Description:

--- Part Two ---
There are still way too many results to go through them all. You'll have to find the LAN party another way and go there yourself.

Since it doesn't seem like any employees are around, you figure they must all be at the LAN party. If that's true, the LAN party will be the largest set of computers that are all connected to each other. That is, for each computer at the LAN party, that computer will have a connection to every other computer at the LAN party.

In the above example, the largest set of computers that are all connected to each other is made up of co, de, ka, and ta. Each computer in this set has a connection to every other computer in the set:
ka-co
ta-co
de-co
ta-ka
de-ta
ka-de
The LAN party posters say that the password to get into the LAN party is the name of every computer at the LAN party, sorted alphabetically, then joined together with commas. (The people running the LAN party are clearly a bunch of nerds.) In this example, the password would be co,de,ka,ta.

What is the password to get into the LAN party?

We want to find the largest set that are all connected to each other. This is also known as a maximum clique. There are various algorithms for this, although here brute force is sufficient.

We can reuse the code from before to "expand" each set of nodes, until we've reached the largest set possible.

show cliques:{distinct asc each raze {x,/:(inter/) G x} each x} scan flip i
(`kh`tc;`qp`kh;`de`cg;`ka`co;`yn`aq;`qp`ub;`cg`tb;`vc`aq;`tb`ka;`wh`tc;`yn`cg..
(`s#`kh`qp`ub;`s#`co`de`ka;`s#`co`ka`ta;`s#`aq`cg`yn;`s#`aq`vc`wq;`s#`tc`td`w..
,`s#`co`de`ka`ta
()

Now our answer for part 2 is:

"," sv string first first -2#cliques
co,de,ka,ta

Recap:

The full solution is this. The repeated code has been factored out into a function.

G: {y group x} . {x,'reverse x} i: ("SS";"-") 0: `23.txt
expand:{distinct asc each raze {x,/:(inter/) G x} each x}
sum "t"in/:first each' string expand flip i
","sv string first first -2#expand scan flip i