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

import com.github.h0tk3y.betterParse.combinators.*
import com.github.h0tk3y.betterParse.grammar.*
import com.github.h0tk3y.betterParse.lexer.*
import kotlinadventofcode.Day
import kotlin.math.max
import kotlin.math.min

class `2015-09` : Day {

    data class City(val name: String, val distances: Map<City, Int>) {
        override fun equals(other: Any?): Boolean = other is City && name == other.name
        override fun hashCode(): Int = name.hashCode()
    }

    fun parse(input: String): Set<City> {
        val distancesByCityName: MutableMap<String, MutableMap<City, Int>> = mutableMapOf()
        val cities: MutableSet<City> = mutableSetOf()

        val grammar = object: Grammar<List<Unit>>() {
            val newLine by literalToken("\n")
            val to by literalToken(" to ")
            val equals by literalToken(" = ")
            val digits by regexToken("\\d+")
            val name by regexToken("[a-zA-Z]+")

            val city by name use {

                val city = City(text, distancesByCityName.getOrPut(text) { mutableMapOf() })
                cities += city
                city
            }

            val distance by digits use { text.toInt() }

            val line by city and -to and city and -equals and distance map { (leftCity, rightCity, distance) ->
                fun saveCityMappings(city1: City, city2: City) {
                    distancesByCityName.getOrPut(city1.name) { mutableMapOf() } += city2 to distance
                }

                saveCityMappings(leftCity, rightCity)
                saveCityMappings(rightCity, leftCity)
            }

            override val rootParser by separatedTerms(line, newLine)
        }

        grammar.parseToEnd(input)
        return cities
    }

    override fun runPartOneNoUI(input: String): String {
        return run(input, ::min)
    }

    fun run(input: String, bestChooser: (Int, Int) -> Int): String {
        val cities = parse(input)
        val paths: ArrayDeque<List<City>> = ArrayDeque(cities.map { listOf(it) })
        var best: Int? = null
        while (!paths.isEmpty()) {
            val path = paths.removeLast()

            if (path.size == cities.size) {
                var distance = 0
                for (i in 0..path.size - 2) {
                    distance += path[i].distances[path[i + 1]] ?: throw Exception("City distance missing.")
                }

                best = best?.let { bestChooser(it, distance) } ?: distance
            } else {
                path.last().distances
                    .filterKeys { it !in path }
                    .forEach { (city, _) -> paths.addLast(path + city) }
            }
        }

        return best.toString()
    }

    /**
     * After verifying your solution on the AoC site, run `./ka continue` to add a test for it.
     */
    override fun runPartTwoNoUI(input: String): String {
        return run(input, ::max)
    }

    override val defaultInput = """Tristram to AlphaCentauri = 34
Tristram to Snowdin = 100
Tristram to Tambi = 63
Tristram to Faerun = 108
Tristram to Norrath = 111
Tristram to Straylight = 89
Tristram to Arbre = 132
AlphaCentauri to Snowdin = 4
AlphaCentauri to Tambi = 79
AlphaCentauri to Faerun = 44
AlphaCentauri to Norrath = 147
AlphaCentauri to Straylight = 133
AlphaCentauri to Arbre = 74
Snowdin to Tambi = 105
Snowdin to Faerun = 95
Snowdin to Norrath = 48
Snowdin to Straylight = 88
Snowdin to Arbre = 7
Tambi to Faerun = 68
Tambi to Norrath = 134
Tambi to Straylight = 107
Tambi to Arbre = 40
Faerun to Norrath = 11
Faerun to Straylight = 66
Faerun to Arbre = 144
Norrath to Straylight = 115
Norrath to Arbre = 135
Straylight to Arbre = 127"""
}