module EveryBodyCodes2025.QuestOne_ai

open System
open System.Collections.Generic
open System.IO
open System.Numerics
open System.Threading.Tasks

let eni (n:int64) (exp:int64) (m:int64) =
    // Compute n^k mod m for k = 1..exp
    // The sequence will cycle, so we detect the cycle and use it
    // Track pairs of consecutive remainders to detect cycles
    let mutable remainders = []
    let mutable score : int64 = 1
    let mutable seenPairs = Map.empty<int64 * int64, int> // Map from (prev, curr) pair to position
    let mutable prevScore = 0L
    let mutable cycleLength = -1
    let mutable doneWithCycle = false
    
    // Build sequence until we detect a cycle
    let mutable k = 1
    while k <= int exp && not doneWithCycle do
        prevScore <- score
        score <- (score * n) % m
        remainders <- score::remainders
        
        // Check if we've seen this (prev, curr) pair before
        if k > 1 && seenPairs.ContainsKey (prevScore, score) && cycleLength = -1 then
            let prevPos = seenPairs[(prevScore, score)]
            let candidateLength = (remainders.Length - 1) - prevPos
            
            // Verify it's a cycle by checking one more value
            if candidateLength > 0 then
                let nextScore = (score * n) % m
                let nextPos = if prevPos + 1 < remainders.Length then 
                                  (remainders.Length - 1) - (prevPos + 1)
                              else -1
                if nextPos >= 0 && nextPos < remainders.Length && remainders[nextPos] = nextScore then
                    // Found a cycle!
                    cycleLength <- candidateLength
                    
                    // Use cycle to compute remaining values
                    let remaining = int exp - k
                    if remaining > 0 then
                        // Extract the cycle (in correct order)
                        let cycleList = remainders.[0..cycleLength - 1] |> List.rev
                        let fullCycles = remaining / cycleLength
                        let extra = remaining % cycleLength
                        
                        for _ in 1..fullCycles do
                            remainders <- cycleList @ remainders
                        
                        for i in 0..extra - 1 do
                            remainders <- cycleList.[i]::remainders
                        
                        doneWithCycle <- true
        else
            if cycleLength = -1 && k > 1 then
                seenPairs <- seenPairs.Add((prevScore, score), remainders.Length - 1)
        
        k <- k + 1
    
    List.rev remainders
        
// let test1 = eni 2 4 5 |> fun l -> String.Join("", l) |> int64
// let test2 = eni 3 5 16 |> fun l -> String.Join("", l) |> int64

let part1Lines (input:String array) =
    input |> Array.map (fun line ->
        line.Split(" ") |> Array.map(fun segment ->
            let parts = segment.Split("=")
            let alias = parts[0]
            let num = parts[1] |> int64
            (alias, num)
            )
        |> dict
    )
    
let toBigInt (list:int64 list) = String.Join("", list) |> BigInteger.Parse
    
let part1 (input: IDictionary<string, int64> array)=
    input
    |> Seq.map (fun line ->
        let a = eni line["A"] line["X"] line["M"] |> toBigInt
        let b = eni line["B"] line["Y"] line["M"] |> toBigInt
        let c = eni line["C"] line["Z"] line["M"] |> toBigInt
        a + b + c
    ) |> Seq.max
    
let part1Answer =
    File.ReadAllLines "Inputs/Q01_P01.txt"
    |> part1Lines
    |> part1
    

let eni2 (n:int64) (exp:int64) (m:int64) =
    // For part 2, we only need the last 5 remainders
    // Use the same cycle detection as eni, then take last 5
    let allRemainders = eni n exp m
    let len = List.length allRemainders
    if len <= 5 then
        allRemainders
    else
        allRemainders |> List.skip (len - 5)

let part2 (input: IDictionary<string, int64> array)=
    input
    |> Array.Parallel.map (fun line ->
        let a = eni2 line["A"] line["X"] line["M"] |> toBigInt
        let b = eni2 line["B"] line["Y"] line["M"] |> toBigInt
        let c = eni2 line["C"] line["Z"] line["M"] |> toBigInt
        a + b + c
    ) |> Seq.max
    
let test2 =
    toBigInt(eni2 5 6 15) + toBigInt(eni2 9 16 15) + toBigInt(eni2 7 18 15)
    

let part2Answer = 
    File.ReadAllLines "Inputs/Q01_P02.txt"
    |> part1Lines
    |> part2