Skip to content

Instantly share code, notes, and snippets.

@delphyne

delphyne/Ansi.kt

Created November 22, 2022 20:26
Show Gist options
  • Save delphyne/da176c59b818c8112834c636cd84538e to your computer and use it in GitHub Desktop.
Save delphyne/da176c59b818c8112834c636cd84538e to your computer and use it in GitHub Desktop.
Download ZIP
Hacky path finder for Gold and Goblins
Raw
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)
}
}
Raw
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())
}
}
Raw
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)
@paweltarbaj
Copy link

paweltarbaj commented Nov 24, 2022 •
edited
Loading

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
        }
    }
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment