package dev.bogwalk.batch9

import dev.bogwalk.util.maths.sumProperDivisors

/**
 * Problem 95: Amicable Chains
 *
 * https://projecteuler.net/problem=95
 *
 * Goal: Find the smallest member of the longest amicable chain possible without any member
 * exceeding N.
 *
 * Constraints: 6 <= N <= 1e6
 *
 * Perfect Number: A chain of only 1 member denotes a perfect number; i.e. the sum of this
 * number's proper divisors is the number itself. e.g. [6], [28], [496].
 * Amicable Pair: A chain of only 2 members. e.g. [220, 284], [1184, 1210], [2620, 2924].
 * Amicable Chain: A chain of numbers generated by calculating the sum of each number's proper
 * divisors. e.g. 12496 → 14288 → 15472 → 14536 → 14264 (→ 12496 → ...).
 *
 * e.g.: N = 10
 *       6 -> {1, 2, 3} = [6]
 *       output = 6
 */

class AmicableChains {
    /**
     * Solution optimised by storing the results of previous chain members in a cache to avoid
     * redundant invocation of the helper function.
     *
     * Potential chains are also terminated early if any member is smaller than the starter
     * number (as the former would have already been assessed and deemed valid, invalid, or a
     * prime). This is supported by the observation that the few chains (with >2 members) follow a
     * normal distribution curve, with the smallest element being the first starter.
     *
     * Iteration through starters is also reduced by only considering even numbers, based on the
     * observation that amicable chains only consist of even numbers.
     */
    fun longestAmicableChain(limit: Int): List<Int> {
        // null signifies that the starter has yet to be assessed
        // emptyList() means no valid chain from starter at that index (most likely ends in a prime)
        // list() means a valid chain was found by a smaller starter
        val cache = MutableList(limit + 1) {
            if (it == 6) listOf(6)
            else if (it < 10) emptyList()
            else null
        }
        var longest = listOf(6)
        for (n in 10..limit step 2) {
            if (cache[n] == null) {
                val chain = mutableListOf(n)
                var prev = n
                while (true) {
                    prev = sumProperDivisors(prev)
                    // either a perfect number or a closed chain
                    if (prev == n) {
                        for (num in chain) {
                            cache[num] = chain
                        }
                        if (chain.size > longest.size) longest = chain
                        break
                    }
                    // either determined invalid by a smaller starter, is amicable pair/perfect,
                    // or is already part of an amicable chain
                    // e.g. 25 -> {1, 5} -> [6]
                    // e.g. 1692 leads to pair [2924, 2620] that first appears in 1188 chain
                    if (prev !in (n + 1)..limit || cache[prev] != null) {
                        for (num in chain) {
                            cache[num] = emptyList()
                        }
                        break
                    }
                    // found smaller sub-chain (could be longer than a pair)
                    if (prev in chain) {
                        val index = chain.indexOf(prev)
                        val subChain = chain.slice(index..chain.lastIndex)
                        if (subChain.size > longest.size) longest = subChain
                        for ((i, num) in chain.withIndex()) {
                            cache[num] = if (i < index) emptyList() else subChain
                        }
                        break
                    }
                    chain.add(prev)
                }
            }
        }
        return longest
    }
}