Advent of Code 2023, December 20

AdventOfCode2023.12.20.fsx

#time "on"

open System
open System.IO

type PulseType = 
    | Low
    | High

type FlipFlopState =
    | On
    | Off

type Outputs = string list

type ConjunctionState = Map<string, PulseType>
    
type ModuleType =
    | Broadcaster of Outputs
    | FlipFlop of FlipFlopState * Outputs
    | Conjunction of ConjunctionState * Outputs
    | Output
    with member this.Outputs =
            match this with
            | Broadcaster x -> x
            | FlipFlop (x,y) -> y
            | Conjunction (x,y) -> y
            | Output -> []

let parseLine (str: string) modules =
    let ndx = str.IndexOf "->"
    let src = str.Substring(0, ndx-1)
    let dest = str.Substring(ndx+3).Split ", " |> Seq.toList
    if src = "broadcaster" then
        modules |> Map.add"broadcaster" (Broadcaster dest)
    else if src[0] = '%' then
        let moduleName = src.Substring 1
        modules |> Map.add moduleName (FlipFlop (Off, dest))
    else if src[0] = '&' then
        let moduleName = src.Substring 1
        modules |> Map.add moduleName (Conjunction (Map.empty, dest))
    else
        raise <| Exception "Unexpected"        

let input =
    File.ReadAllLines(__SOURCE_DIRECTORY__ + "/../data/input20.txt")
    |> Seq.toList
    |> List.fold (fun modules line -> parseLine line modules ) Map.empty

let modules = 
    input
    |> Map.fold (fun acc k v -> 
        match v with
        | Conjunction (state, dest) -> 
            let inputs =
                input
                |> Seq.map (fun kv -> kv.Key, match kv.Value with | FlipFlop (_, dest) -> dest | Conjunction (_, dest) -> dest | _ -> [])
                |> Seq.filter (fun (key, dest) -> dest |> List.contains k)
                |> Seq.map fst
            let state = inputs |> Seq.fold (fun acc input -> acc |> Map.add input Low) Map.empty
            acc |> Map.add k (Conjunction (state, dest))
        | _ -> acc) input


let handlePulse sender receiver pulseType modules =
    let moduleState = if modules |> Map.containsKey receiver then modules[receiver] else Output
    let moduleState, pulses =
        match moduleState with
        | Broadcaster dest -> moduleState, dest |> List.map (fun x -> (receiver, x, pulseType))
        | FlipFlop (state, dest) ->
            match pulseType with
            | High -> moduleState, []
            | Low ->
                match state with
                | On -> FlipFlop (Off, dest), dest |> List.map (fun x -> (receiver, x, Low))
                | Off -> FlipFlop (On, dest), dest |> List.map (fun x -> (receiver, x, High))
        | Conjunction (state, dest) ->
            let oldValue = 
                match state |> Map.tryFind sender with
                | Some value -> value
                | None -> Low
            let state = state |> Map.add sender pulseType
            let pulseType = if state |> Map.forall (fun _ v -> v = High) then Low else High
            Conjunction (state, dest), dest |> List.map (fun x -> (receiver, x, pulseType))
        | Output -> moduleState, []
    let modules = if modules.ContainsKey receiver then modules |> Map.add receiver moduleState else modules
    pulses, modules

// Part One

module One =

    let rec sendPulses pulses modules lowCount highCount =
        let (pulses', modules') = 
            pulses 
            |> List.fold (fun (accPulses, accModules) (sender, receiver, pulseType) -> 
                let ps, ms = handlePulse sender receiver pulseType accModules
                (List.concat [accPulses; ps], ms)) ([], modules)
        let lowCount = lowCount + (pulses |> List.filter (fun (_,_,pt) -> pt = Low) |> List.length)
        let highCount = highCount + (pulses |> List.filter (fun (_,_,pt) -> pt = High) |> List.length)
        match pulses' with
        | [] -> modules', lowCount, highCount
        | _ -> sendPulses pulses' modules' lowCount highCount

    [1..1000]
    |> List.fold (fun (accModules, accLow, accHigh) _ -> 
        let modules, low, high = sendPulses [("none", "broadcaster", Low)] accModules 0 0
        modules, accLow + low, accHigh + high) (modules, 0, 0)
    |> fun (_, low, high) -> int64 low * int64 high

// Part Two

module Two =
            
    let rec gcd x y = if y = 0L then abs x else gcd y (x % y)
    let lcm x y = x * y / (gcd x y)

    let rec sendPulses pulses modules sent =
        let (pulses', modules') = 
            pulses 
            |> List.fold (fun (accPulses, accModules) (sender, receiver, pulseType) -> 
                let ps, ms = handlePulse sender receiver pulseType accModules
                (List.concat [accPulses; ps], ms)) ([], modules)
        let sent = List.concat [sent; pulses]
        match pulses' with
        | [] -> modules', sent
        | _ -> sendPulses pulses' modules' sent

    let rec run modules matchSender matchReceiver count = 
        let modules', sent = sendPulses [("none", "broadcaster", Low)] modules []
        if sent |> List.exists (fun (sender, receiver, pulseType) -> 
            sender = matchSender && receiver = matchReceiver && pulseType = High) then
            count + 1
        else 
            run modules' matchSender matchReceiver (count + 1)

    let senders, receiver =
        let m = modules |> Map.filter (fun k v -> v.Outputs |> List.contains "rx") |> Seq.head
        let senders =
            match m.Value with
            | Conjunction (state, _) -> state |> Map.keys |> Seq.toList
            | _ -> List.empty
        let receiver = m.Key
        senders, receiver

    senders
    |> List.map (fun sender -> run modules sender receiver 0)
    |> List.fold (fun acc elt -> lcm acc elt) 1L