package Y2023.D23

class TheLongHike(map: List<String>) {
    private val hikingTrails = map.mapIndexed { y, line ->
        line.mapIndexed { x, spot -> (x to y) to spot }
    }.flatten().toMap()
    private val crossRoads = hikingTrails.filter {
        it.value != '#' &&
                it.key.neighbours.filter(this::isValidPath).size != 2
    }
    private val trails = crossRoads.map { crossRoad ->
        crossRoad.key.neighbours.filter(this::isValidPath)
            .map { trail ->
                var count = 0
                var currentStep = trail
                var previousStep = crossRoad.key
                while (currentStep.neighbours.filter(this::isValidPath).size == 2) {
                    val nextStep = currentStep.neighbours.filter(this::isValidPath).filter { it != previousStep }[0]
                    previousStep = currentStep
                    currentStep = nextStep
                    count++
                }
                (crossRoad.key to currentStep) to count + 1
            }
    }.flatten().toMap()

    private fun isValidPath(neighbour: Pair<Int, Int>) =
        hikingTrails[neighbour] != null && hikingTrails[neighbour] != '#'

    val start = map.first().indexOf('.') to 0
    val end = map.last().indexOf('.') to map.lastIndex

    fun takeTheLongPath(): Int {
        return hikingTheLongPath(start, emptyList(), 0)
    }

    private fun hikingTheLongPath(
        position: Pair<Int, Int>,
        visited: List<Pair<Int, Int>>,
        steps: Int
    ): Int {
        if (position == end) return steps
        if (visited.contains(position)) return -1
        val possibleTrails = trails.filter { it.key.first == position }
        return possibleTrails.map { trail ->
            hikingTheLongPath(trail.key.second, visited + trail.key.first, steps + trail.value)
        }.max()!!
    }
}

private val <A, B> Pair<A, B>.reversed: Pair<B, A>
    get() = this.second to this.first

private val Pair<Int, Int>.neighbours: Set<Pair<Int, Int>>
    get() =
        setOf(
            this.first to this.second - 1,
            this.first - 1 to this.second,
            this.first + 1 to this.second,
            this.first to this.second + 1
        )