Advent of Code 2023 - Day 20

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

var modules = new Dictionary<string, IModule>();

foreach (var line in input)
{
    var split = line.Split(" -> ");
    var name = split[0];
    var targets = split[1].Split(',', StringSplitOptions.RemoveEmptyEntries | StringSplitOptions.TrimEntries).ToList();

    if (name == "broadcaster")
    {
        modules[name] = new Broadcaster(name, targets);
    }
    else if (name.StartsWith('%'))
    {
        modules[name[1..]] = new FlipFlop(name[1..], targets);
    }
    else if (name.StartsWith('&'))
    {
        modules[name[1..]] = new Conjunction(name[1..], targets);
    }
}

foreach (var module in modules.Values)
{
    if (module is not Conjunction conjunction) continue;

    var inputs = modules.Values.Where(m => m.Targets.ContainsKey(module.Name)).ToList();
    foreach (var inputModule in inputs)
    {
        conjunction.Inputs[inputModule.Name] = PulseType.Low;
    }
}

var lowPulses = 0;
var highPulses = 0;
var queue = new Queue<(IModule Module, PulseType PulseType)>();
var currentPulse = PulseType.Low;
var count = 0;

// The module that sends pulses to rx - it's a conjunction.
// In order to send a low pulse to rx, all of its inputs must be sending a high pulse.
var rxSource = modules.Values.First(m => m.Targets.ContainsKey("rx"));

// The modules that send pulses to the conjunction that sends pulses to rx.
var rxSourceInputs = modules.Values.Where(m => m.Targets.ContainsKey(rxSource.Name)).ToList();

// We will count how many pushes are needed for each module to send out a high pulse.
var rxSourceInputCounts = new Dictionary<string, (int Count, bool Done)>();
foreach (var rxSourceModule in rxSourceInputs)
{
    rxSourceInputCounts[rxSourceModule.Name] = (0, false);
}

while (true)
{
    if (count == 1000)
    {
        Console.WriteLine($"Part 1: {lowPulses * highPulses}");
    }

    count++;

    queue.Enqueue((modules["broadcaster"], currentPulse));

    if (currentPulse == PulseType.Low)
    {
        lowPulses++;
    }
    else
    {
        highPulses++;
    }

    if (rxSourceInputCounts.All(rxs => rxs.Value.Done))
    {
        // We know that all of the inputs to the conjunction that sends pulses to rx have sent out a high pulse.
        // Now we just find the LCM of the counts for each input in order to find the first time that all of the inputs
        // have sent out a high pulse, which in turn would cause rx to receive a low pulse.
        Console.WriteLine($"Part 2: {Lcm(rxSourceInputCounts.Select(rxs => rxs.Value.Count).ToArray())}");
        break;
    }

    while (queue.TryDequeue(out var current))
    {
        current.Module.Process(current.PulseType);

        foreach (var target in current.Module.Targets.Keys)
        {
            var targetPulse = current.Module.Targets[target];

            if (target == "rx")
            {
                if (current.Module is not Conjunction conjunction) continue;

                var highInputs = conjunction.Inputs.Where(conjunctionInput => conjunctionInput.Value == PulseType.High);
                foreach (var conjunctionInput in highInputs)
                {
                    // The module is sending a high pulse to rx, so store its count.
                    rxSourceInputCounts[conjunctionInput.Key] = (count, true);
                }
            }

            switch (targetPulse)
            {
                case PulseType.Low:
                    lowPulses++;
                    break;
                case PulseType.High:
                    highPulses++;
                    break;
                case PulseType.None:
                default:
                    break;
            }

            if (targetPulse != PulseType.None)
            {
                if (!modules.ContainsKey(target))
                {
                    continue;
                }

                if (modules[target] is Conjunction conjunction)
                {
                    conjunction.Inputs[current.Module.Name] = targetPulse;
                }

                queue.Enqueue((modules[target], targetPulse));
            }

            if (queue.Count == 0)
            {
                currentPulse = current.PulseType == PulseType.Low ? PulseType.High : PulseType.Low;
            }
        }
    }
}

return;

static long Lcm(IEnumerable<int> numbers) => numbers.Select(Convert.ToInt64).Aggregate((a, b) => a * b / Gcd(a, b));

static long Gcd(long a, long b) => b == 0 ? a : Gcd(b, a % b);

internal interface IModule
{
    string Name { get; set; }
    Dictionary<string, PulseType> Targets { get; set; }
    void Process(PulseType pulse);
}

internal class Broadcaster : IModule
{
    public Broadcaster(string name, List<string> targets)
    {
        Name = name;

        foreach (var target in targets)
        {
            Targets[target] = PulseType.Low;
        }
    }

    public string Name { get; set; }
    public Dictionary<string, PulseType> Targets { get; set; } = new();

    public virtual void Process(PulseType pulse)
    {
        foreach (var name in Targets.Keys)
        {
            Targets[name] = pulse;
        }
    }
}

internal class FlipFlop(string name, List<string> targets) : Broadcaster(name, targets)
{
    public bool PoweredOn { get; set; }

    public override void Process(PulseType pulse)
    {
        var output = PulseType.None;

        if (pulse == PulseType.Low)
        {
            output = PoweredOn ? PulseType.Low : PulseType.High;
            PoweredOn = !PoweredOn;
        }

        foreach (var targetName in Targets.Keys)
        {
            Targets[targetName] = output;
        }
    }
}

internal class Conjunction(string name, List<string> targets) : Broadcaster(name, targets)
{
    public Dictionary<string, PulseType> Inputs { get; set; } = new();

    public override void Process(PulseType pulse)
    {
        foreach (var name in Targets.Keys)
        {
            Targets[name] = Inputs.Values.All(x => x == PulseType.High) ? PulseType.Low : PulseType.High;
        }
    }
}

internal enum PulseType
{
    None,
    Low,
    High
}