This seems like an interesting type of graph problem... though it's pretty simple. Build a dictionary of which systems each computer is connected to; from there just look at all potential pairs for each system I'm interested in.
public object PartOne()
{
return CountTrios((a, b, c) => a[0] == 't' || b[0] == 't' || c[0] == 't');
}
public int CountTrios(Func<string, string, string, bool> validFunc)
{
var count = 0;
var systems = links.Keys.ToList();
for (int i = 0; i < systems.Count; i++)
for (int j = i + 1; j < systems.Count; j++)
for (int k = j + 1; k < systems.Count; k++)
{
if (i == j || i == k || j == k) continue;
string a = systems[i];
string b = systems[j];
string c = systems[k];
if (validFunc(a, b, c) && links[a].Contains(b) && links[a].Contains(c) && links[b].Contains(c)) count++;
}
return count;
}
Okay, at first glance I'm at a loss.
After a bit of googling, it seems that the name for "All nodes mutually connected to each other in a graph" is called a clique. The wikipedia page even has a (basic) description of how to find the maximal clique! I just decided to enumerate every clique, and do a few things on the results to get the max with the password
public List<ImmutableList<string>> GetCliques(ImmutableList<string> otherSystems)
{
var cliques = new List<ImmutableList<string>>();
foreach (var system in systems)
{
if (otherSystems.Contains(system)) continue;
if (!otherSystems.All(o => links[system].Contains(o))) continue;
var newClique = otherSystems.Add(system);
cliques.Add(newClique);
cliques.AddRange(GetCliques(newClique));
}
return cliques;
}
public object PartTwo()
{
return GetCliques(ImmutableList<string>.Empty)
.Select(c => c.Sort())
.Select(c => string.Join(',', c))
.Distinct()
.ToList()
.MaxBy(c => c.Length) ?? "???";
}
This works, but seems to be running incredibly slow... Oh! I shouldn't be looking at all existing systems, just systems connected to at least one of the systems I'm checking. Except that still runs too long. Bleh.
Rather than trying to logic this out myself, after a while I started to look up if this sort of thing was solved. Looking past that basic description on Wikipedia before, I found the Bron-Kerbosch algorithm which, when implemented, runs pretty quick; only about 1000ms!
public IEnumerable<ImmutableList<string>> BronKerbosch(ImmutableList<string> r, ImmutableList<string> p, ImmutableList<string> x)
{
if (r.Count == 0 && x.Count == 0) yield return p;
foreach (var n in r)
{
var np = p.Add(n);
var nr = r.Where(n => links[n].Contains(n)).ToImmutableList();
var nx = x.Where(n => links[n].Contains(n)).ToImmutableList();
foreach (var clique in BronKerbosch(np, nr, nx)) yield return clique;
r = r.Remove(n);
x = x.Remove(n);
}
}
I suppose it's the time of the year where I just find the right esoteric algorithm to sovle the problems. Surprised it took until day 23 for me to find it necessary. I built a few other more brute-force algorithms, and I'll leave them in my code I guess, but they aren't exactly fast enough to be reasonable.