package dev.bogwalk.batch2

import java.math.BigInteger
import kotlin.math.pow

/**
 * Problem 29: Distinct Powers
 *
 * https://projecteuler.net/problem=29
 *
 * Goal: Count the distinct terms in a sequence generated by a^b when 2 <= a <= N and 2 <= b <= N.
 *
 * Constraints: 2 <= N <= 1e5
 *
 * e.g.: N = 4
 *       terms = {4, 8, 16}, {9, 27, 81}, {16, 64, 256}
 *       count = 8
 */

class DistinctPowers {
    /**
     * SPEED (WORSE) 10.10s for N = 1e3
     */
    fun distinctPowersBrute(n: Int): Long {
        val distinct = mutableSetOf<BigInteger>()
        for (a in 2..n) {
            for (b in 2..n) {
                val power = a.toBigInteger().pow(b)
                distinct.add(power)
            }
        }
        return distinct.size.toLong()
    }

    /**
     * Solution finds the amount of duplicate terms produced by a^b and subtracts that from the
     * maximum integer combinations, (n - 1)^2. No need to calculate base 2 exponents larger than
     * 16 since 2^17 > 1e5 (upper constraint).
     *
     * SPEED (BETTER) 8.6e5ns for N = 1e3
     */
    fun distinctPowers(n: Int): Long {
        val maxExp = minOf(16, n - 1)
        val minExponents = IntArray(n * maxExp - 1)
        for (i in 1..maxExp) {
            for (j in 2..n) {
                val index = i * j - 2
                if (minExponents[index] == 0) {
                    minExponents[index] = i
                }
            }
        }
        val bases = IntArray(n - 1)
        var duplicates = 0L
        val exponentDuplicates = LongArray(maxExp - 1)
        for (num in 2..n) {
            val parent = bases[num - 2]
            if (parent == 0) {
                var power: Long = 1L * num * num
                while (power <= n) {
                    bases[power.toInt() - 2] = num
                    power *= num
                }
            } else {
                var exponent = 0
                var reduce = num
                while (reduce > 1) {
                    reduce /= parent
                    exponent++
                }
                if (exponentDuplicates[exponent - 2] != 0L) {
                    duplicates += exponentDuplicates[exponent - 2]
                } else {
                    var dupes = 0L
                    for (y in 2..n) {
                        if (minExponents[y * exponent - 2] < exponent) {
                            dupes++
                        }
                    }
                    exponentDuplicates[exponent - 2] = dupes
                    duplicates += dupes
                }
            }
        }
        return (1.0 * n - 1).pow(2).toLong() - duplicates
    }
}