astar.kt

package day12.astar

import java.io.FileInputStream
import java.util.*
import kotlin.math.abs

const val startSymbol = 'a' - 1
const val endSymbol = 'z' + 1
const val symbols = "${startSymbol}abcdefghijklmnopqrstuvwxyz${endSymbol}"
var mapWidth = 0
var mapHeight = 0
val map = mutableListOf<List<Char>>()
var startPosition = Position(0, 0)
var endPosition = Position(0, 0)

data class Position(val x: Int, val y:Int) {
    fun isValid(closedList: List<Position>, actualSymbol: Char) : Boolean {
        return x in 0 until mapWidth
                && y in 0 until mapHeight
                && this !in closedList
                && symbols.indexOf(map[y][x]) <= symbols.indexOf(actualSymbol) + 1
    }
}

data class AStarNode(val route: List<Position>) {

    fun distanceFromStart() : Int = route.size - 1

    fun distanceFromEnd() : Int {
        return 0 +
                abs(route.last().x - endPosition.x) + // x axis
                abs(route.last().y - endPosition.y) + // y axis
                symbols.indexOf(map[route.last().y][route.last().x]) - symbols.length + 1
    }

    fun cost() : Int {
        return distanceFromStart() + distanceFromEnd()
    }
}

fun astar(map: List<List<Char>>, position: Position): AStarNode? {
    val openList = mutableListOf(AStarNode(listOf(position)))
    val closedList = mutableListOf<Position>()

    while (openList.isNotEmpty()) {

        // zoradenie podla min(vzdialenost_S + vzdialenost_E)
        openList.sortBy { it.cost() }

        // vyber vrcholu a jeho charakteristik
        val node = openList[0]
        val route = node.route
        val actualPosition = route.last()
        val actualSymbol = map[actualPosition.y][actualPosition.x]

        // pridanie pozicie do zatvoreneho zoznamu
        closedList.add(actualPosition)
        
        // dosiahli sme koniec
        if (map[actualPosition.y][actualPosition.x] == endSymbol) {
            return node
        }

        for (newPosition in listOf(
            Position(actualPosition.x - 1, actualPosition.y),
            Position(actualPosition.x, actualPosition.y - 1),
            Position(actualPosition.x + 1, actualPosition.y),
            Position(actualPosition.x, actualPosition.y + 1)
        )) {
            // ignoruj nevalidne cesty alebo cesty v uzatvorenom zozname
            if (!newPosition.isValid(closedList, actualSymbol)) continue

            // zisti, ci aktualna cesta nie je v otvorenom zozname
            val openListRoute = openList.firstOrNull { it.route.last() == newPosition }
            if (openListRoute == null) {
                // cesta este nie je v otvorenom zozname vytvor novu cestu
                openList.add(AStarNode(route + newPosition))
            } else {
                // cesta uz je v otvorenom zozname, ak to ma zmysel, treba ju aktualizovat
                if (openListRoute.route.size > route.size) {
                    openList.remove(openListRoute)
                    openList.add(AStarNode(route + newPosition))
                }
            }
        }
    }

    return null
}

fun main() {
    val s = Scanner(FileInputStream("src/main/kotlin/day12/day12.txt"))

    while (s.hasNext()) {
        map.add(s.nextLine().mapIndexed { x, c ->
            when (c) {
                'S' -> 'a'.also { startPosition = Position(x, mapHeight) }
                'E' -> endSymbol.also { endPosition = Position(x, mapHeight) }
                else -> c
            }
        })
        mapHeight++
    }

    mapWidth = map[0].size
    readln()
    val bestRoute = astar(map, startPosition)!!
    println(bestRoute.route.size - 1)
}