// Originally generated by the template in CodeDAO
package kotlinadventofcode.`2015`

import com.github.h0tk3y.betterParse.combinators.*
import com.github.h0tk3y.betterParse.grammar.Grammar
import com.github.h0tk3y.betterParse.grammar.parseToEnd
import com.github.h0tk3y.betterParse.lexer.literalToken
import com.github.h0tk3y.betterParse.lexer.regexToken
import kotlinadventofcode.Day
import kotlin.math.max
import kotlin.math.min
import kotlin.random.Random
import kotlin.random.nextInt

const val targetCalories = 500
const val bestScoreExcludingCalories = 21367368
const val totalIngredientAmount = 100
class `2015-15` : Day {

    data class Ingredient(
        val name: String,
        val capacity: Int,
        val durability: Int,
        val flavor: Int,
        val texture: Int,
        val calories: Int
    )

    data class Recipe(val ingredients: Set<Pair<Ingredient, Int>>) {

        val score: Int by lazy {
            max(0, ingredients.sumOf { it.first.capacity * it.second }) *
                max(0, ingredients.sumOf { it.first.durability * it.second }) *
                max(0, ingredients.sumOf { it.first.flavor * it.second }) *
                max(0, ingredients.sumOf { it.first.texture * it.second })
        }

        val tweaks: Collection<Recipe> by lazy {
            val ingredientsList = ingredients.toList()
            var result: MutableSet<Recipe> = mutableSetOf()
            for (indexToGive in ingredientsList.indices) {
                if (ingredientsList[indexToGive].second == 0) continue
                for (indexToTake in ingredientsList.indices.minus(indexToGive)) {
                    result.add(Recipe(
                        ingredientsList.indices
                        .map {
                            when (it) {
                                indexToGive -> ingredientsList[it].first to ingredientsList[it].second - 1
                                indexToTake -> ingredientsList[it].first to ingredientsList[it].second + 1
                                else -> ingredientsList[it]
                            }
                        }
                        .toSet()))
                }
            }

            result
        }
    }

    fun parse(input: String): List<Ingredient> {
        val grammar = object: Grammar<List<Ingredient>>() {

            // match literals first
            val newline by literalToken("\n")
            val capacity by literalToken(": capacity ")
            val durability by literalToken(", durability ")
            val flavor by literalToken(", flavor ")
            val texture by literalToken(", texture ")
            val calories by literalToken(", calories ")

            // then match expressions
            val numberToken by regexToken("""-?\d+""")
            val name by regexToken("""[A-Z][a-z]+""")

            val number by numberToken use { text.toInt() }

            val line by (name use { text }) and
                skip(capacity) and
                number and
                skip(durability) and
                number and
                skip(flavor) and
                number and
                skip(texture) and
                number and
                skip(calories) and
                number

            val ingredient by line.map { Ingredient(it.t1, it.t2, it.t3, it.t4, it.t5, it.t6) }

            override val rootParser by separatedTerms(ingredient, newline)
        }

        return grammar.parseToEnd(input)
    }

    /**
     * After verifying your solution on the AoC site, run `./ka continue` to add a test for it.
     */
    override fun runPartOneNoUI(input: String): String {
        val totalIngredientAmount = 100

        /*
         * Let's see if we can hill climb well enough to not get trapped by local maxes.
         *
         * Edit: the below as implemented works, but may not work if there were local maxes. Instead
         * of sampling up front, this should be changed to take one sample, run the algorithm, then
         * repeat.
         */

        val ingredients = parse(input)

        val numStartingRecipes = 3
        val startingRecipes = (1..numStartingRecipes).map {
            val ingredientAmounts = ingredients.map { 0 }.toMutableList()
            (1..totalIngredientAmount).forEach { ingredientAmounts[Random.nextInt(ingredients.indices)]++ }
            Recipe(ingredients.toList().zip(ingredientAmounts).toSet())
        }

        val queue = ArrayDeque(startingRecipes)
        val recipesPreviouslyAddedToQueue: MutableSet<Recipe> = mutableSetOf()
        recipesPreviouslyAddedToQueue.addAll(startingRecipes)

        var bestRecipe: Recipe? = null
        while (queue.isNotEmpty()) {
            val recipe = queue.removeFirst()
            if (bestRecipe == null || recipe.score > bestRecipe.score) bestRecipe = recipe
            for (tweak in recipe.tweaks) {
                if (tweak !in recipesPreviouslyAddedToQueue && tweak.score >= bestRecipe.score) {
                    queue.addLast(tweak)
                    recipesPreviouslyAddedToQueue.add(tweak)
                }
            }
        }

        return bestRecipe?.score.toString()
    }

    /**
     * This was fun in that the part 1 hill climbing approach doesn't work at all. Instead, I had
     * to use the calorie and teaspoon targets to limit the search space.
     */
    override fun runPartTwoNoUI(input: String): String {

        /**
         * gets all recipes that exactly match the number of teaspoons and number of calories
         */
        fun getAllRecipes(ingredients: Set<Ingredient>, teaspoons: Int, calories: Int): Set<Recipe> {

            // If we need no more ingredients nor calories, there is one valid recipe which matches that.
            if (teaspoons == 0 && calories == 0) return setOf(Recipe(setOf()))

            /**
             * Some conditions that make any valid recipes impossible:
             *  * one of teaspoons or calories is 0 but the other isn't
             *  * teaspoons or calories are negative
             *  * teaspoons and calories are non-zero, but there are no ingredients
             */
            if (teaspoons < 1 || calories < 1 || ingredients.isEmpty()) return setOf()

            val result = mutableSetOf<Recipe>()
            val currentIngredient = ingredients.first()
            val otherIngredients = ingredients.minus(currentIngredient)
            for (currentIngredientAmount in 0..min(teaspoons, calories / currentIngredient.calories)) {
                for (recipe in
                    getAllRecipes(
                        otherIngredients,
                        teaspoons - currentIngredientAmount,
                        calories - (currentIngredient.calories * currentIngredientAmount))) {

                    result.add(Recipe(recipe.ingredients + (currentIngredient to currentIngredientAmount)))
                }
            }

            return result
        }

        return getAllRecipes(parse(input).toSet(), totalIngredientAmount, targetCalories)
            .maxOf { it.score }
            .toString()
    }

    override val defaultInput = """Sprinkles: capacity 2, durability 0, flavor -2, texture 0, calories 3
Butterscotch: capacity 0, durability 5, flavor -3, texture 0, calories 3
Chocolate: capacity 0, durability 0, flavor 5, texture -1, calories 8
Candy: capacity 0, durability -1, flavor 0, texture 5, calories 8"""
}