123 lines
4.4 KiB
Forth
123 lines
4.4 KiB
Forth
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
|
|
|