package dev.bogwalk.batch5

import dev.bogwalk.util.combinatorics.combinations
import dev.bogwalk.util.maths.isPrime
import dev.bogwalk.util.maths.primeNumbers
import dev.bogwalk.util.search.binarySearch
import kotlin.math.pow

/**
 * Problem 51: Prime Digit Replacements
 *
 * https://projecteuler.net/problem=51
 *
 * Goal: Find the smallest N-digit prime which, by replacing K digits of the number with the same
 * digit, is part of an L-prime value family at minimum. K digits are not necessarily adjacent &
 * leading zeroes should not be considered.
 *
 * Constraints: 2 <= N <= 7, 1 <= K <= N, and 1 <= L <= 8
 *
 * Prime value family: A set of prime numbers generated by replacing the same digits with a new
 * digit.
 * e.g. Replacing the 3rd & 4th digits of 56**3 -> {56003, 56113, 56333, 56443, 56663, 56773, 56993}
 *
 * e.g.: N = 2, K = 1, L = 3
 *       replace 1 digit in 1* -> {11, 13, 17, 19}
 *       smallest 3-prime value family = {11, 13, 17}
 */

class PrimeDigitReplacements {
    /**
     * Solution optimised based on the following:
     *
     *  -   Generate all [n]-digit primes first.
     *
     *  -   Only replace digits that are of a value less than the maximum required to generate
     *  [length] primes.
     *
     *  -   Check for primality using a binary search through generated primes.
     *
     *  -   Break loop once a family of primes of desired [length] is found, ensuring the family is
     *  the smallest lexicographically, if multiple exist.
     */
    fun smallestPrimeDigitRepl(n: Int, k: Int, length: Int): List<Int> {
        var smallest = emptyList<Int>()
        val maxDigit = (9 - length + 1).digitToChar()
        val upperBounds = (10.0).pow(n).toInt() - 1
        val lowerBounds = (10.0).pow(n - 1).toInt()
        val primes = primeNumbers(upperBounds)
        for (prime in primes) {
            if (prime < lowerBounds) continue
            val families = getReplacements(prime, maxDigit, k).map { newNums ->
                newNums.filter { num -> binarySearch(num, primes) }
            }.filter { family ->
                family.size >= length - 1
            }
            if (families.isNotEmpty()) {
                smallest = listOf(prime) + (
                        families.minByOrNull { it.first() }?.take(length - 1) ?: emptyList()
                        )
                break
            }
        }
        return smallest
    }

    /**
     * e.g.:
     *      "769" with [k] = 1, [maxDigit] = "6" -> "7*9" -> [[779, 789, 799]]
     *
     *      "797" with [k] = 2, [maxDigit] = "7" -> "*9*" -> [[898, 999]]
     *
     *      "7677" with [k] = 2, [maxDigit] = "7" -> "*6*7", "*67*", "76**" ->
     *      [[8687, 9697], [8678, 9679], [7688, 7699]
     *
     * @param [p] prime to have its digits replaced.
     * @param [maxDigit] max value a digit can be to allow L-primes to be generated.
     * @param [k] number of equal digits to be replaced.
     * @return list of all integer lists generated as a result of replacing k-digits of equal
     * value. The original prime is not included, to avoid it being unnecessarily checked for
     * primality in calling function.
     */
    private fun getReplacements(
        p: Int, maxDigit: Char, k: Int
    ): List<List<Int>> {
        val replaced = mutableListOf<Char>()
        val replacements = mutableListOf<List<Int>>()
        val prime = p.toString()
        for (digit in prime) {
            if (digit <= maxDigit && prime.count { it == digit } >= k && digit !in replaced) {
                replaced.add(digit)
                for (perm in combinations(prime.indices.filter { prime[it] == digit }, k)) {
                    val matches = mutableListOf<Int>()
                    for (d in digit.digitToInt() + 1 until 10) {
                        matches.add(prime.mapIndexed { index, ch ->
                            if (index in perm) d.digitToChar() else ch
                        }.joinToString("").toInt())
                    }
                    replacements.add(matches)
                }
            }
        }
        return replacements
    }

    /**
     * Project Euler specific implementation that requires the smallest prime that is part of an
     * 8-prime value family to be returned. The amount of digits to be replaced is not specified,
     * so all values of K should be attempted for numbers greater than 56009 (the next prime
     * after 56003, which is the smallest prime to be in a 7-prime value family).
     *
     * It is optimised by only replacing digits in {0, 1, 2} as anything greater would not be
     * able to generate 7 more primes of greater value.
     */
    fun smallest8PrimeFamily(): Int {
        var n = 56009
        outer@while (true) {
            if (n.isPrime()) {
                // replace single digits only
                val num = n.toString()
                for ((i, digit) in num.withIndex()) {
                    if (digit <= '2') {
                        val family = (digit.digitToInt() + 1 until 10).map {
                            num.replaceRange(i..i, it.toString()).toInt()
                        }.filter { it.isPrime() }
                        if (family.size == 7) break@outer
                    }
                }
                // replace multiple digits only
                val multiples = mutableListOf<Char>()
                for (digit in num) {
                    if (digit <= '2' && num.count { it == digit } > 1 && digit !in multiples) {
                        multiples.add(digit)
                        val family = (digit.digitToInt() + 1 until 10).map {
                            num.replace(digit, it.digitToChar()).toInt()
                        }.filter { it.isPrime() }
                        if (family.size == 7) break@outer
                    }
                }
            }
            n += 2
        }
        return n
    }
}
package dev.bogwalk.batch5

import dev.bogwalk.util.combinatorics.combinations
import dev.bogwalk.util.maths.isPrime
import dev.bogwalk.util.maths.primeNumbers
import dev.bogwalk.util.search.binarySearch
import kotlin.math.pow

/**
 * Problem 51: Prime Digit Replacements
 *
 * https://projecteuler.net/problem=51
 *
 * Goal: Find the smallest N-digit prime which, by replacing K digits of the number with the same
 * digit, is part of an L-prime value family at minimum. K digits are not necessarily adjacent &
 * leading zeroes should not be considered.
 *
 * Constraints: 2 <= N <= 7, 1 <= K <= N, and 1 <= L <= 8
 *
 * Prime value family: A set of prime numbers generated by replacing the same digits with a new
 * digit.
 * e.g. Replacing the 3rd & 4th digits of 56**3 -> {56003, 56113, 56333, 56443, 56663, 56773, 56993}
 *
 * e.g.: N = 2, K = 1, L = 3
 *       replace 1 digit in 1* -> {11, 13, 17, 19}
 *       smallest 3-prime value family = {11, 13, 17}
 */

class PrimeDigitReplacements {
    /**
     * Solution optimised based on the following:
     *
     *  -   Generate all [n]-digit primes first.
     *
     *  -   Only replace digits that are of a value less than the maximum required to generate
     *  [length] primes.
     *
     *  -   Check for primality using a binary search through generated primes.
     *
     *  -   Break loop once a family of primes of desired [length] is found, ensuring the family is
     *  the smallest lexicographically, if multiple exist.
     */
    fun smallestPrimeDigitRepl(n: Int, k: Int, length: Int): List<Int> {
        var smallest = emptyList<Int>()
        val maxDigit = (9 - length + 1).digitToChar()
        val upperBounds = (10.0).pow(n).toInt() - 1
        val lowerBounds = (10.0).pow(n - 1).toInt()
        val primes = primeNumbers(upperBounds)
        for (prime in primes) {
            if (prime < lowerBounds) continue
            val families = getReplacements(prime, maxDigit, k).map { newNums ->
                newNums.filter { num -> binarySearch(num, primes) }
            }.filter { family ->
                family.size >= length - 1
            }
            if (families.isNotEmpty()) {
                smallest = listOf(prime) + (
                        families.minByOrNull { it.first() }?.take(length - 1) ?: emptyList()
                        )
                break
            }
        }
        return smallest
    }

    /**
     * e.g.:
     *      "769" with [k] = 1, [maxDigit] = "6" -> "7*9" -> [[779, 789, 799]]
     *
     *      "797" with [k] = 2, [maxDigit] = "7" -> "*9*" -> [[898, 999]]
     *
     *      "7677" with [k] = 2, [maxDigit] = "7" -> "*6*7", "*67*", "76**" ->
     *      [[8687, 9697], [8678, 9679], [7688, 7699]
     *
     * @param [p] prime to have its digits replaced.
     * @param [maxDigit] max value a digit can be to allow L-primes to be generated.
     * @param [k] number of equal digits to be replaced.
     * @return list of all integer lists generated as a result of replacing k-digits of equal
     * value. The original prime is not included, to avoid it being unnecessarily checked for
     * primality in calling function.
     */
    private fun getReplacements(
        p: Int, maxDigit: Char, k: Int
    ): List<List<Int>> {
        val replaced = mutableListOf<Char>()
        val replacements = mutableListOf<List<Int>>()
        val prime = p.toString()
        for (digit in prime) {
            if (digit <= maxDigit && prime.count { it == digit } >= k && digit !in replaced) {
                replaced.add(digit)
                for (perm in combinations(prime.indices.filter { prime[it] == digit }, k)) {
                    val matches = mutableListOf<Int>()
                    for (d in digit.digitToInt() + 1 until 10) {
                        matches.add(prime.mapIndexed { index, ch ->
                            if (index in perm) d.digitToChar() else ch
                        }.joinToString("").toInt())
                    }
                    replacements.add(matches)
                }
            }
        }
        return replacements
    }

    /**
     * Project Euler specific implementation that requires the smallest prime that is part of an
     * 8-prime value family to be returned. The amount of digits to be replaced is not specified,
     * so all values of K should be attempted for numbers greater than 56009 (the next prime
     * after 56003, which is the smallest prime to be in a 7-prime value family).
     *
     * It is optimised by only replacing digits in {0, 1, 2} as anything greater would not be
     * able to generate 7 more primes of greater value.
     */
    fun smallest8PrimeFamily(): Int {
        var n = 56009
        outer@while (true) {
            if (n.isPrime()) {
                // replace single digits only
                val num = n.toString()
                for ((i, digit) in num.withIndex()) {
                    if (digit <= '2') {
                        val family = (digit.digitToInt() + 1 until 10).map {
                            num.replaceRange(i..i, it.toString()).toInt()
                        }.filter { it.isPrime() }
                        if (family.size == 7) break@outer
                    }
                }
                // replace multiple digits only
                val multiples = mutableListOf<Char>()
                for (digit in num) {
                    if (digit <= '2' && num.count { it == digit } > 1 && digit !in multiples) {
                        multiples.add(digit)
                        val family = (digit.digitToInt() + 1 until 10).map {
                            num.replace(digit, it.digitToChar()).toInt()
                        }.filter { it.isPrime() }
                        if (family.size == 7) break@outer
                    }
                }
            }
            n += 2
        }
        return n
    }
}