Advent of Code 2023 - Day 25

using System.Text;

var input = File.ReadAllLines("input.txt");

// We will generate a GraphViz file (*.dot) to visualize the graph and identify the edges that have to be removed.
var dotFile = new StringBuilder();
dotFile.AppendLine("graph {");

var wires = new Dictionary<string, HashSet<string>>();
foreach (var line in input)
{
    var parts = line.Split(": ");
    var wire = parts[0].Trim();
    var connections = parts[1].Trim().Split(" ").ToList();

    if (!wires.ContainsKey(wire))
    {
        wires[wire] = [];
    }

    foreach (var connection in connections)
    {
        // Generate content for a GraphViz graph.
        dotFile.AppendLine($"    {wire} -- {connection}");

        if (!wires.ContainsKey(connection))
        {
            wires[connection] = [];
        }

        wires[wire].Add(connection);
        wires[connection].Add(wire);
    }
}

dotFile.AppendLine("}");
File.WriteAllText("graph.dot", dotFile.ToString());

// I used Gephi (https://gephi.org/) to visualize the graph and identify the edges that have to be removed.
// I used the "Force Atlas" layout algorithm to get a nice layout of the graph.
// Here are the edges that had to be removed for my input:

const string a1 = "cbl";
const string b1 = "vmq";

const string a2 = "bvz";
const string b2 = "nvf";

const string a3 = "klk";
const string b3 = "xgz";

wires[a1].Remove(b1);
wires[b1].Remove(a1);

wires[a2].Remove(b2);
wires[b2].Remove(a2);

wires[a3].Remove(b3);
wires[b3].Remove(a3);

// Now we just need to use BFS to count the number of reachable nodes from a random single node of the removed pairs

var visited = new HashSet<string>();
var queue = new Queue<string>();
queue.Enqueue(a1);

while (queue.Count > 0)
{
    var current = queue.Dequeue();

    if (!visited.Add(current))
    {
        continue;
    }

    foreach (var connection in wires[current])
    {
        queue.Enqueue(connection);
    }
}

// We have the size of one of the two subsets, so we can calculate the size other subset by subtracting the first's
// size from the total number of nodes.

Console.Write($"Part 1: {visited.Count * (wires.Count - visited.Count)}");