Advent of Code 2023 8

advent2023-8.fs

open System

let input =
    """LLR

AAA = (BBB, BBB)
BBB = (AAA, ZZZ)
ZZZ = (ZZZ, ZZZ)"""
    |> fun x -> x.Split('\n')

type Node =
    { name: string
      left: string
      right: string }

type Game =
    { moves: char[]
      nodes: Map<string, Node>
      startNodes: Node list }

let parseGame (input: string[]) =
    let moves = input.[0].ToCharArray()
    let nodes =
        input
        |> Seq.skip 2
        |> Seq.map (fun x ->
            let name = x.Substring(0, 3)
            let left = x.Substring(7, 3)
            let right = x.Substring(12, 3)
            name, { name = name
                    left = left
                    right = right }
        )
        |> Map.ofSeq
    let startNodes =
        nodes
        |> Seq.map (fun (KeyValue(_, node)) -> node)
        |> Seq.filter (fun node -> node.name.EndsWith 'A')
        |> Seq.toList
    { moves = moves; nodes = nodes; startNodes = startNodes } 

let rec infiniteMoves game = seq {
    yield! game.moves
    yield! infiniteMoves game
}

let playGame game startNode whenToFinish =
    ((infiniteMoves game).GetEnumerator(), startNode)
    |> Seq.unfold (fun (moves, currentNode) ->
        if whenToFinish currentNode then
            None
        else
            moves.MoveNext() |> ignore
            let nextNodeName =
                match moves.Current with
                | 'L' -> currentNode.left
                | 'R' -> currentNode.right
            let nextNode = game.nodes.[nextNodeName]
            Some((), (moves, nextNode))
    )
    |> Seq.fold (fun i _ -> i + 1L) 0L

let part1 game =
    playGame
        game
        game.nodes.["AAA"]
        (fun x -> x.name = "ZZZ")

let part2 game =
    let allFinishes =
        game.startNodes
        |> List.map (fun startNode ->
            playGame
                game
                startNode
                (fun x -> x.name.EndsWith 'Z')
        )
    let rec gcd a b = if b = 0L then a else gcd b (a % b)
    let lcm (a: int64) b = Math.Abs (a * b) / (gcd a b)
    let lcmMany = Seq.reduce lcm
    
    lcmMany allFinishes

let game = parseGame input

part1 game // 6
part2 game // 6