// Before: writing it from scratch every year
fun gcd(a: Long, b: Long): Long = if (b == 0L) a else gcd(b, a % b)
fun lcm(a: Long, b: Long): Long = a / gcd(a, b) * b
val answer = cycleLengths.reduce(::lcm)

// After: just import and solve
import kodvent.math.*
val answer = cycleLengths.reduce(::lcm)

kotlin {
    sourceSets {
        commonMain {
            dependencies {
                implementation("io.github.dmitrynekrasov:kodvent:0.3.1")
            }
        }
    }
}

dependencies {
    implementation("io.github.dmitrynekrasov:kodvent:0.3.1")
}

val frequencies = mutableMapOf<Char, Int>()

// Count character occurrences
"hello world".forEach { char ->
    frequencies.increment(char)
}

// frequencies now contains: {h=1, e=1, l=3, o=2, w=1, r=1, d=1}

// Greatest common divisor and the least common multiple
val g = gcd(48, 18)   // 6
val l = lcm(12, 18)   // 36

// Simplify a fraction
val divisor = gcd(48, 180)
val simplified = "${48 / divisor}/${180 / divisor}"  // "4/15"

// Binary exponentiation with infix syntax
val result = 2L pow 10L  // 1024

// Modular exponentiation — useful for number theory problems
val modulo = 1000000007L
val big = 2L.pow(100L, modulo)  // 976371285

// Squared distance without temporary variables
val distanceSquared = dx.sqr() + dy.sqr()

// Detect cycles in a graph
val dsu = DisjointSetUnion(4)

dsu.union(0, 1)
dsu.union(1, 2)
dsu.union(2, 3)

val hasCycle = !dsu.union(0, 3)  // true - cycle detected!

// Kruskal's algorithm for Minimum Spanning Tree
data class Edge(val from: Int, val to: Int, val weight: Int)

val edges = listOf(
    Edge(0, 1, 4),
    Edge(0, 2, 2),
    Edge(1, 2, 1),
    Edge(1, 3, 5)
)

val dsuMst = DisjointSetUnion(4)
val mst = edges.sortedBy { it.weight }.filter { dsuMst.union(it.from, it.to) }

// Range sum queries with bracket syntax
val numbers = listOf(1, 3, 5, 7, 9, 11)
val sumTree = SegmentTree(numbers, Int::plus)

sumTree[1, 4]           // 24 (sum of 3 + 5 + 7 + 9)
sumTree[2] = 15         // point update
sumTree[2] += 10        // compound assignment

// Works with any associative operation
val minTree = SegmentTree(data, ::minOf)
val maxTree = SegmentTree(data, ::maxOf)
val gcdTree = SegmentTree(values, ::gcd)

// Safe queries for bounds you can't guarantee
sumTree.getOrNull(0, 100)         // null (out of bounds)
sumTree.getOrDefault(0, 100, 0)   // 0

// Find all occurrences of a pattern in text
val indices = "ababcababa".allIndicesOf("aba")  // [0, 5, 7]

// Finds overlapping patterns
"aaaa".allIndicesOf("aa")  // [0, 1, 2]

// Period detection via prefix function
val pi = "abababab".prefixFunction()
val period = "abababab".length - pi.last()  // 2

// Generic prefix function works with any sequence
val numPi = prefixFunction(numbers.size, numbers::get)

// Binary search on answer: maximize minimum distance
// LeetCode 1552: Magnetic Force Between Two Balls
fun canPlaceBalls(positions: IntArray, m: Int, minDistance: Int): Boolean {
    var ballsPlaced = 1
    var lastPosition = positions[0]
    for (i in 1..positions.lastIndex) {
        if (positions[i] - lastPosition >= minDistance) {
            ballsPlaced++
            lastPosition = positions[i]
        }
    }
    return ballsPlaced >= m
}

val positions = intArrayOf(1, 2, 3, 4, 7)
val m = 3
positions.sort()

val partitionPoint = partitionPoint(0, positions.last() + 1) { distance ->
    canPlaceBalls(positions, m, distance)
}
val maxMinDistance = partitionPoint - 1  // 3

val list = listOf(1, 3, 3, 3, 5, 5, 7, 9, 9, 9, 9, 11)

val lower = list.lowerBound(9)  // 7 - index of first 9
val upper = list.upperBound(9)  // 11 - index after last 9
val count = upper - lower       // 4

// For elements that don't exist, lower == upper
list.upperBound(8) - list.lowerBound(8)  // 0

// A rectangle has a fixed perimeter P = 40.
// Side lengths: x and (P/2 - x). Area = x * (20 - x).
// Find x that maximizes area, with x in [0, 20].
val halfP = 40.0 / 2

val x = ternarySearch(0.0, halfP) { x -> x * (halfP - x) }
// x = 10.0 (maximum area when the rectangle is a square)