package dev.bogwalk.batch1

import dev.bogwalk.util.maths.gaussSum
import dev.bogwalk.util.maths.primeFactors
import dev.bogwalk.util.maths.primeNumbers

/**
 * Problem 12: Highly Divisible Triangular Number
 *
 * https://projecteuler.net/problem=12
 *
 * Goal: Find the value of the first triangle number to have more than N divisors.
 *
 * Constraints: 1 <= N <= 1e3
 *
 * Triangle Number: A number generated by adding all natural numbers prior to & including itself.
 *
 * e.g.: N = 5
 *       1st = 1 from [1] -> {1]
 *       2nd = 3 from [1+2] -> {1,3}
 *       3rd = 6 from [1+2+3] -> {1,2,3,6}
 *       4th = 10 from [1+2+3+4] -> {1,2,5,10}
 *       5th = 15 from [1+2+3+4+5] -> {1,3,5,15}
 *       6th = 21 from [1+2+3+4+5+6] -> {1,3,7,21}
 *       7th = 28 from [1+2+3+4+5+6+7] -> {1,2,4,7,14,28}
 *       result = 28
 */

class HighlyDivisibleTriangularNumber {
    /**
     * Returns the found triangle number generated as a Gaussian sum that has had its divisors
     * counted using prime decomposition.
     *
     * Since the components of a Gaussian sum (n & n+1) are co-prime (i.e. they can have neither
     * a common prime factor nor a common divisor), the amount of divisors can be assessed based
     * on the cycling formulae using these smaller values:
     *
     *      t represents Gaussian sum = n(n + 1)/2
     *
     *      (even n) D(t) = D(n/2) * D(n+1)
     *      D(n+1) becomes D(n) for the next number, which will be odd.
     *
     *      (odd n) D(t) = D(n) * D((n+1)/2)
     *
     * SPEED (WORSE) 137.26ms for N = 1e3
     */
    fun firstTriangleBruteA(limit: Int): Int {
        if (limit == 1) return 3
        var n = 2 // D(2) = D(1) * D(3)
        var isEven = true
        var dn1 = 2 // D(3) = 2
        var count = 2
        while (count <= limit) {
            n++
            isEven = !isEven
            val dn2 = if (isEven) countDivisors(n+1) else countDivisors((n+1)/2)
            count = dn1 * dn2
            dn1 = dn2
        }
        return n.gaussSum().toInt()
    }

    /**
     * Identical to the first brute solution except that each triangle number is calculated
     * manually and its own divisors counted.
     *
     * SPEED (WORST) 396.69ms for N = 1e3
     */
    fun firstTriangleBruteB(limit: Int): Int {
        var t = 3
        if (limit == 1) return t
        var n = 2
        var count = 2
        while (count <= limit) {
            n++
            t = n.gaussSum().toInt()
            count = countDivisors(t)
        }
        return t
    }

    /**
     * Identical to the above brute solution except that triangle numbers are generated as a
     * sequence until the first to exceed [limit] is found.
     *
     * SPEED (WORST) 381.42ms for N = 1e3
     */
    fun firstTriangleBruteC(limit: Int): Int {
        return generateSequence(Pair(3, 3)) { Pair(it.first + it.second, it.second + 1) }
            .first { countDivisors(it.first) > limit }
            .first
    }

    /**
     * Counts unique divisors of [n] using prime decomposition, based on the formulae:
     *
     *      n = p_1{e_1} * p_2{e_2} * ... * p_r{e_r}
     *      d(n) = {r}Pi{x=1}(a_x + 1)
     *
     * e.g. 28 = 2^2 * 7^1, therefore
     *
     * number of divisors of 28 = (2 + 1) * (1 + 1) = 6 -> {1, 2, 4, 7, 14, 28}
     */
    fun countDivisors(n: Int): Int {
        return primeFactors(1L * n).values
            .map { it + 1 }
            .reduce { acc, v -> acc * v }
    }

    /**
     * Quick pick solution finds the first triangle number to have over N divisors for every
     * N <= [limit] & stores the results as an IntArray that can be repeatedly accessed afterwards.
     *
     * SPEED (BETTER) 94.44ms for N = 1e3
     */
    fun firstTrianglesCache(limit: Int): IntArray {
        val triangles = IntArray(limit + 1).apply {
            this[0] = 1
            this[1] = 3
            this[2] = 6
        }
        val eMax = 20_000
        val divisorCount = IntArray(eMax) { 2 }.apply { this[1] = 1 }
        for (divisor in 2 until eMax) {
            for (num in divisor * 2 until eMax step divisor) {
                divisorCount[num]++
            }
        }

        var lastN = 3 // D(3) = D(3) * D(2)
        var isEven = false
        var lastDn1 = 2
        var lastTriangle = 6
        var lastCount = 4
        for (i in 3..limit) {
            if (i < lastCount) {
                triangles[i] = lastTriangle
                continue
            }
            var nextN = lastN + 1
            isEven = !isEven
            do {
                val toCount = if (isEven) nextN + 1 else (nextN + 1) / 2
                val dn2 = if (toCount < eMax) divisorCount[toCount] else {
                    countDivisors(toCount)
                }
                val count = lastDn1 * dn2
                lastDn1 = dn2
                if (i < count) {
                    val triangle = nextN.gaussSum().toInt()
                    triangles[i] = triangle
                    lastTriangle = triangle
                    lastN = nextN
                    lastCount = count
                    break
                }
                nextN++
                isEven = !isEven
            } while (true)
        }
        return triangles
    }

    /**
     * Similar to the original single-pick function above that exploits co-prime property of
     * Gaussian sum but stores cumulative divisor counts in an array for quick access instead of
     * calculating the count for every new [n].
     *
     * Dual cyclic formulae use n - 1 instead of n + 1 to match the cached list that is generated
     * with every iteration, so looking forward would produce incorrect counts.
     *
     * N.B. n_max was found by exhausting all solutions for n = [1, 1000] & finding the maximum
     * of the ratios of t:n. At n = 1000, the valid triangle number is the 41041st term.
     *
     * SPEED (BEST) 27.62ms for N = 1e3
     */
    fun firstTriangleOverNOptimised(n: Int): Int {
        val nMax = minOf(n * 53, 41100)
        val divisorCount = IntArray(nMax)
        var num = 0
        var dT = 0
        while (dT <= n) {
            num++
            for (i in num until nMax step num) {
                divisorCount[i]++
            }
            dT = if (num % 2 == 0) {
                divisorCount[num/2] * divisorCount[num-1]
            } else {
                divisorCount[num] * divisorCount[(num-1)/2]
            }
        }
        return num * (num - 1) / 2
    }

    /**
     * Generates primes to count number of divisors based on prime factorisation.
     *
     * SPEED (BETTER): 43.76ms for N = 1e3.
     */
    fun firstTriangleOverNUsingPrimes(n: Int): Int {
        if (n == 1) return 3
        val primes = primeNumbers(n * 2)
        var prime = 3

        var dn = 2 // min num of divisors for any prime
        var count = 0
        while (count <= n) {
            prime++
            var n1 = prime
            if (n1 % 2 == 0) n1 /= 2
            var dn1 = 1
            for (i in primes.indices) {
                // when the prime divisor would be greater than the residual n1
                // that residual n1 is the last prime factor with an exponent == 1.
                // so no need to identify it.
                if (primes[i] * primes[i] > n1) {
                    dn1 *= 2
                    break
                }
                var exponent = 1
                while (n1 % primes[i] == 0) {
                    exponent++
                    n1 /= primes[i]
                }
                if (exponent > 1) dn1 *= exponent
                if (n1 == 1) break
            }
            count = dn * dn1
            dn = dn1
        }
        return prime * (prime - 1) / 2
    }
}