package dev.bogwalk.batch4

import dev.bogwalk.util.maths.isPentagonalNumber

/**
 * Problem 44: Pentagon Numbers
 *
 * https://projecteuler.net/problem=44
 *
 * Goal: For a given K, find all P_n, where n < N, such that P_n - P_(n-K) || P_n + P_(n-K) is
 * also pentagonal.
 *
 * Constraints: 1 <= K <= 9999, K+1 <= N <= 1e6
 *
 * Pentagonal Number: The sequence is generated by -> pN = n(3n - 1) / 2 ->
 * 1, 5, 12, 22, 35, 51, 70, 92, 117, 145,...
 *
 * e.g. P_7 = 70 is special in that, if K = 2:
 *      P_7 - P_5 = 35 = P_5; and, if K = 3:
 *      P_7 + P_4 = 92 = P_8
 *
 * e.g.: N = 10, K = 2
 *       output = {70}
 */

class PentagonNumbers {
    fun pentagonNumbersHR(n: Int, k: Int): Set<Long> {
        val pNs = List(n) { 1L * it * (3 * it - 1) / 2 }
        val results = mutableSetOf<Long>()
        for (i in k + 1 until n - 1) {
            val pN = pNs[i]
            val pNMinusK = pNs[i - k]
            if (
                (pN - pNMinusK).isPentagonalNumber() != null ||
                (pN + pNMinusK).isPentagonalNumber() != null
            ) {
                results.add(pN)
            }
        }
        return results
    }

    /**
     * Project Euler specific implementation that returns the smallest difference, |P_x - P_y|,
     * for a pair of pentagonal numbers whose sum and difference are both pentagonal.
     *
     * Surprisingly, the first eligible pair found has the smallest difference:
     * P_x = 7_042_750, where x = 2167, and
     * P_y = 1_560_090, where y = 1020.
     */
    fun pentagonNumbersPE(): Int {
        val pentagonals = List(10_001) { it * (3 * it - 1) / 2 }
        var delta = Int.MAX_VALUE
        for (x in 3..10_000) {
            val pX = pentagonals[x]
            for (y in x - 1 downTo 2) {
                val pY = pentagonals[y]
                val minus = pX - pY
                if (
                    (pX + pY).toLong().isPentagonalNumber() == null ||
                    (minus).toLong().isPentagonalNumber() == null
                ) continue
                delta = minOf(delta, minus)
            }
        }
        return delta
    }
}