Hacky path finder for Gold and Goblins

Ansi.kt

package util

/**
 * adapted from https://gist.github.com/dainkaplan/4651352
 */
class Ansi(private vararg val codes: String) {

    fun and(other: Ansi): Ansi {
        return Ansi(*codes, *other.codes)
    }

    fun colorize(original: String): String {
        return codes.joinToString(separator = "") + original + SANE
    }

    fun format(template: String?, vararg args: Any?): String {
        return colorize(String.format(template!!, *args))
    }

    @Suppress("MemberVisibilityCanBePrivate")
    companion object {
        // Color code strings from:
        // http://www.topmudsites.com/forums/mud-coding/413-java-ansi.html
        private const val SANE = "\u001B[0m"
        private const val HIGH_INTENSITY = "\u001B[1m"
        private const val LOW_INTENSITY = "\u001B[2m"
        private const val ITALIC = "\u001B[3m"
        private const val UNDERLINE = "\u001B[4m"
        private const val BLINK = "\u001B[5m"
        private const val RAPID_BLINK = "\u001B[6m"
        private const val REVERSE_VIDEO = "\u001B[7m"
        private const val INVISIBLE_TEXT = "\u001B[8m"
        private const val BLACK = "\u001B[30m"
        private const val RED = "\u001B[31m"
        private const val GREEN = "\u001B[32m"
        private const val YELLOW = "\u001B[33m"
        private const val BLUE = "\u001B[34m"
        private const val MAGENTA = "\u001B[35m"
        private const val CYAN = "\u001B[36m"
        private const val WHITE = "\u001B[37m"
        private const val BACKGROUND_BLACK = "\u001B[40m"
        private const val BACKGROUND_RED = "\u001B[41m"
        private const val BACKGROUND_GREEN = "\u001B[42m"
        private const val BACKGROUND_YELLOW = "\u001B[43m"
        private const val BACKGROUND_BLUE = "\u001B[44m"
        private const val BACKGROUND_MAGENTA = "\u001B[45m"
        private const val BACKGROUND_CYAN = "\u001B[46m"
        private const val BACKGROUND_WHITE = "\u001B[47m"

        val HighIntensity = Ansi(HIGH_INTENSITY)
        val Bold = HighIntensity
        val LowIntensity = Ansi(LOW_INTENSITY)
        val Normal = LowIntensity
        val Italic = Ansi(ITALIC)
        val Underline = Ansi(UNDERLINE)
        val Blink = Ansi(BLINK)
        val RapidBlink = Ansi(RAPID_BLINK)
        val Black = Ansi(BLACK)
        val Red = Ansi(RED)
        val Green = Ansi(GREEN)
        val Yellow = Ansi(YELLOW)
        val Blue = Ansi(BLUE)
        val Magenta = Ansi(MAGENTA)
        val Cyan = Ansi(CYAN)
        val White = Ansi(WHITE)
        val BgBlack = Ansi(BACKGROUND_BLACK)
        val BgRed = Ansi(BACKGROUND_RED)
        val BgGreen = Ansi(BACKGROUND_GREEN)
        val BgYellow = Ansi(BACKGROUND_YELLOW)
        val BgBlue = Ansi(BACKGROUND_BLUE)
        val BgMagenta = Ansi(BACKGROUND_MAGENTA)
        val BgCyan = Ansi(BACKGROUND_CYAN)
        val BgWhite = Ansi(BACKGROUND_WHITE)
    }
}

goldandgoblins.kt

package games.goldandgoblins

import util.Ansi
import util.memoize
import kotlin.math.E
import kotlin.math.abs
import kotlin.math.max
import kotlin.math.min
import kotlin.math.pow

sealed class Square(open val x: Int, open val y: Int, open val value: Int) {

    val coordinate by lazy { x to y }

    abstract fun render(): String

    private fun findAdjacent(board: Board): List<Square> {
        return sequence {
            if (this@Square is Origin) {
                board[0]
                    .filter { it is Mine || it is Empty || it is Breakable }
                    .forEach { yield(it) }
            } else if (this@Square !is Gate) {
                if (!isTopEdge(board)) {
                    yield(board[x,y+1])
                } else if (!isLeftEdge() && !isRightEdge(board)) {
                    yield(Gate)
                }
                if (!isRightEdge(board)) {
                    yield(board[x+1,y])
                }
                if (!isBottomEdge()) {
                    yield(board[x,y-1])
                } else {
                    yield(Origin)
                }
                if (!isLeftEdge()) {
                    yield(board[x-1,y])
                }
            }
        }.toList()
    }

    open fun asDestination(board: Board): Square = this

    fun findOutboundEdges(board: Board): List<Edge> =
        findAdjacent(board)
            .filter { canReach(it, board) }
            .map { square ->
                square.asDestination(board).let {that ->
                    Edge(this, that, cost(that.value))
                }
            }

    private fun isTopEdge(board: Board): Boolean = y == board.height - 1
    private fun isRightEdge(board: Board): Boolean = x == board.width - 1
    private fun isBottomEdge(): Boolean = y == 0
    private fun isLeftEdge(): Boolean = x == 0

    fun isAdjacentTo(that: Square): Boolean =
        this.x == that.x && abs(this.y - that.y) == 1
                || this.y == that.y && abs(this.x - that.x) == 1
                || this is Origin && that.isBottomEdge()
                || that is Origin && this.isBottomEdge()

    open fun canReach(that: Square, board: Board): Boolean {
        return when(that) {
            is Empty, is Breakable, is Mine -> isAdjacentTo(that)
            is Blocked -> false
            is Origin -> this.isBottomEdge()
            is Gate -> isTopEdge(board) && !isLeftEdge() && !isRightEdge(board)
        }
    }

    override fun equals(other: Any?): Boolean {
        return when (other) {
            is Square -> this.x == other.x && this.y == other.y
            else -> false
        }
    }

    override fun hashCode(): Int = (x to y).hashCode()
}

data class Empty(override val x: Int, override val y: Int) : Square(x, y, 0) {
    override fun render() = ""
}

abstract class Blocked(x: Int, y: Int, value: Int) : Square(x, y, value) {
    override fun canReach(that: Square, board: Board) = false
}
data class Boulder(override val x: Int, override val y: Int) : Blocked(x, y , Int.MAX_VALUE) {
    override fun render() = "X"
}
data class Mine(override val x: Int, override val y: Int, override val value: Int) : Blocked(x, y ,value) {

    override fun asDestination(board: Board): Square {
        return findCohort(board)
            .minWith(Comparator.comparing { square: Square -> square.x }.thenComparing { square: Square -> square.y })
    }

    val findCohort: (Board) -> List<Square> = { board: Board ->
            val minx = when (x) {
                0, 1 -> 0
                board.width - 2, board.width - 1 -> board.width - 2
                else -> throw Exception("Mine out of range")
            }
            val maxx = minx + 1
            val miny = max(0, y-2)
            val maxy = min(miny + 4, board.height - 1)

            sequence {
                (minx..maxx).map { itx ->
                    (miny..maxy).map { ity ->
                        board[itx,ity].let { square ->
                            if (square is Mine && square.value == this@Mine.value) {
                                yield(square)
                            }
                        }
                    }
                }
            }.toList()
    }.memoize()

    override fun render() = "M$value"
}

abstract class Breakable(x: Int, y: Int, cost: Int, private val prefix: String) : Square(x, y, cost) {
    override fun render() = "$prefix$value"
}
data class Rock(override val x: Int, override val y: Int, override val value: Int) : Breakable(x, y, value, "")
data class Treasure(override val x: Int, override val y: Int, override val value: Int) : Breakable(x, y, value, "T")
data class Key(override val x: Int, override val y: Int, override val value: Int) : Breakable(x, y, value, "K")
data class Crown(override val x: Int, override val y: Int, override val value: Int): Breakable(x, y, value, "C")

object Origin: Square(x = Int.MIN_VALUE, y = Int.MIN_VALUE, value = 0) {
    override fun render(): String = "O"
    override fun toString(): String = "Origin"
}
object Gate: Square(x = Int.MAX_VALUE, y = Int.MAX_VALUE, value = 0) {
    override fun render() = toString()
    override fun toString(): String = "G"
}

data class Edge(val origin: Square, val destination: Square, val distance: Double)

private fun costImpl(n: Int): Double {
//    val old = (2..n).fold(BigDecimal.ONE) { acc, _ -> acc.times(BigDecimal(1.6))}
    val new = E.pow(0.47*n)
//    println("cost($n)=$old or $new")
    return new
}

val cost = { i: Int -> costImpl(i) }.memoize()


private fun row(y: Int, r: String): List<Square> =
    r
        .split(" ")
        .filter { it.isNotBlank() }
        .mapIndexed { x, it ->
            try {
                when {
                    it.uppercase() == "E" -> Empty(x, y)
                    it.uppercase() == "X" -> Boulder(x, y)
                    it.startsWith("M", true) -> Mine(x, y, it.substring(1).toInt())
                    it.startsWith("T", true) -> Treasure(x, y, it.substring(1).toInt())
                    it.startsWith("K", true) -> Key(x, y, it.substring(1).toInt())
                    it.startsWith("C", true) -> Crown(x, y, it.substring(1).toInt())
                    it.startsWith("R", true) -> Rock(x, y, it.substring(1).toInt())
                    else -> Rock(x, y, it.toInt())
                }
            } catch (t: Throwable) {
                throw Exception("Couldn't parse ($x, $y), '$it'.", t)
            }
        }

class Board private constructor(private val grid: Array<Array<Square>>) {

    val width: Int = grid[0].size
    val height = grid.size

    init {
        grid.forEachIndexed { i, row ->
            check(row.size == width) {
                "Invalid board, all rows must be the same length! y=${height - i - 1} must be $width wide. ${row.joinToString(prefix = "[", postfix = "]") { it.render() }}"
            }
        }
    }


    private val vertices by lazy { grid.flatten() + listOf(Origin, Gate) }
    private val edges by lazy { vertices.flatMap { it.findOutboundEdges(this) } }

    companion object {
        operator fun invoke(board: String): Board {
            return BoardBuilder().apply {
                board
                    .split("\n")
                    .forEach { row(it) }
            }.build()
        }

        operator fun invoke(init: BoardBuilder.() -> Unit): Board {
            return BoardBuilder().apply {
                init(this)
            }.build()
        }

        class BoardBuilder {
            private val rows: MutableList<String> = mutableListOf()
            fun row(r: String) {
                rows.add(r)
            }
            fun build(): Board {
                return Board(
                    rows
                        .asReversed()
                        .mapIndexed { y, row -> row(y, row).toTypedArray() }
                        .toTypedArray()
                )
            }
        }
    }

    operator fun get(x: Int, y: Int): Square {
        return try {
            grid[y][x]
        } catch (ex: Exception) {
            throw Exception("No square at [$x, $y].", ex)
        }
    }

    operator fun get(y: Int): List<Square> {
        return grid[y].asList()
    }

    fun solve(): String {
        val pathData = dijsktra()
        val gatePathNodes = findPathTo(Gate, pathData).toSet()
        val minePathNodes = vertices
            .filterIsInstance<Mine>()
            .map { it.asDestination(this) }
            .distinct()
            .flatMap {
                try {
                    findPathTo(it, pathData)
                } catch (ex: Exception) {
                    throw Exception("No path to $it within $pathData", ex)
                }
            }
            .toSet()
        val keyPathNodes = vertices
            .filterIsInstance<Key>()
            .flatMap { findPathTo(it, pathData) }
            .toSet()
        return toString(gatePathNodes, minePathNodes, keyPathNodes)
    }

    private fun dijsktra(): Map<Square, Square> {
        val distanceFromOrigin = mutableMapOf<Square, Double>().withDefault { cost(100) }.apply { this[Origin] = 0.0 }
        val neighborWithShortestPath = mutableMapOf<Square, Square>()
        val unvisitedSquares = HashSet(vertices)
        while (unvisitedSquares.isNotEmpty()) {
            val square = unvisitedSquares.minBy { distanceFromOrigin.getValue(it) }
            unvisitedSquares.remove(square)
            for (neighbor in edges.filter { it.origin == square }) {
                if (distanceFromOrigin.getValue(neighbor.destination) > distanceFromOrigin.getValue(square).plus(neighbor.distance)) {
                    distanceFromOrigin[neighbor.destination] = distanceFromOrigin.getValue(square).plus(neighbor.distance)
                    neighborWithShortestPath[neighbor.destination] = square
                }
            }
        }
        return neighborWithShortestPath.toMap()
    }

    private fun findPathTo(destination: Square, pathData: Map<Square, Square>): List<Square> {
        val path = mutableListOf<Square>()
        var currentNode = pathData[destination] ?: throw Exception("No path to $destination ${destination.coordinate}")
        path.add(currentNode)
        while (currentNode != Origin) {
            currentNode = pathData[currentNode] ?: throw Exception("No path to ${destination.coordinate}. Stuck at [${currentNode.coordinate}].")
            path.add(0, currentNode)
        }
        if (destination is Mine) {
            path.add(destination.findCohort(this).first { mine -> mine.isAdjacentTo(path.last()) })
        } else {
            path.add(destination)
        }
        return path
    }

    override fun toString(): String = this.toString(setOf(), setOf(), setOf())

    private fun toString(gatePathNodes: Set<Square>, minePathNodes: Set<Square>, keyPathNodes: Set<Square>): String {
        val prefixSize = "${grid.size - 1}: ".length

        return (height-1).downTo(0).joinToString(
            separator = "\n",
            postfix = "\n"
                    + "".padStart(prefixSize + grid[0].size - 1 + grid[0].size * 3, '=')
                    + "\n"
                    + 0.until(grid[0].size)
                .mapIndexed { x, _ ->
                    x.toString().padStart(3)
                }
                .joinToString(prefix = "".padStart(prefixSize, ' '), separator = " ")
        ) { y ->
            (0 until width).joinToString(
                "",
                prefix = "${y.toString().padStart((grid.size - 1).toString().length)}: "
            ) { x ->
                val square = this[x,y]
                when (square) {
                    in gatePathNodes -> Ansi.BgGreen.and(Ansi.Black)
                    in minePathNodes -> Ansi.BgBlue.and(Ansi.Black)
                    in keyPathNodes -> Ansi.BgYellow.and(Ansi.Black)
                    is Mine -> Ansi.BgBlack
                    is Blocked -> Ansi.BgBlack.and(Ansi.Black)
                    else -> Ansi.BgWhite.and(Ansi.Black)
                }.colorize(square.render().padStart(4))
            }
        }
    }
}


fun main() {
    Board("""
        12 t15 13 c20 19 12 k17
        k21 12 19 11 13 t20 13
        x x 11 t18 12 14 x
        x t16 13 10 c17 m15 m15
        x 12 15 11 x m15 m15
        x k14 11 10 11 m15 m15
        x x x t16 12 c15 x
        m14 m14 c12 10 14 11 t13
        m14 m14 9 k11 9 10 11
        m14 m14 8 x x 12 9
        t10 9 e x x e c10
    """.trimIndent()).apply {
        println(solve())
    }

    Board("""
        x t14 c13 14 10 11 t13
        10 9 8 10 k13 9 x
        11 8 t12 9 11 m11 m11
        10 k12 x x c12 m11 m11
        9 8 t11 8 9 m11 m11
        x c10 9 12 8 11 k10
        m9 m9 8 7 t13 9 x
        m9 m9 x 8 7 c8 x
        m9 m9 7 7 9 7 x
        x 6 e e 7 k8 x
    """.trimIndent()).apply {
        println(solve())
    }

    Board("""
        k7 9 c10 7 8 t10 x
        8 6 8 k9 6 c7 x
        x 8 7 6 x m7 m7
        x 5 6 t7 4 m7 m7
        x t6 5 4 5 m7 m7
        x c5 6 k5 4 5 x
        m3 m3 5 4 3 4 x
        m3 m3 4 t3 4 3 x
        m3 m3 3 2 3 k3 x
        x 2 1 e e 3 x    
    """.trimIndent()).apply {
        println(solve())
    }
}

memoize.kt

package util

private class Memoize1<in T, out R>(val f: (T) -> R) : (T) -> R {
    private val values = mutableMapOf<T, R>()
    override fun invoke(x: T): R {
        return values.getOrPut(x) { f(x) }
    }
}

fun <T, R> ((T) -> R).memoize(): (T) -> R = Memoize1(this)

I added some rudimentary IO, but I cant submit it as a pull request here. You can replace the main function with:

fun printMap() {
    var map = ""
    
    do
    {
        val nextLine = try { readln() } catch (e: Exception) { "" }
        if (nextLine.isNullOrEmpty())
        {
            break
        }
        map = map + "\n" + nextLine
    } while (true)

    Board(map.trimIndent()).apply {
        println(solve())
    }
}

fun main()
{
    while (true)
    {
        try
        {
            printMap()
        }
        catch (e: Exception)
        {
            break
        }
    }
}