Skip to content

Instantly share code, notes, and snippets.

@ygrenzinger

ygrenzinger/MineSweeper.kt

Created May 8, 2020 06:09
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save ygrenzinger/c560b32b9ebf2ac3d169a3a18f2e9bb1 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save ygrenzinger/c560b32b9ebf2ac3d169a3a18f2e9bb1 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. ygrenzinger created this gist May 8, 2020.
    250 changes: 250 additions & 0 deletions MineSweeper.kt
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,250 @@
    package minesweeper

    import java.util.*
    import kotlin.random.Random

    enum class Command {
    MARK, EXPLORE
    }

    enum class State {
    PLAYING, LOST, WON
    }

    enum class CellState {
    MARKED, UNEXPLORED, EXPLORED
    }

    sealed class Cell() {
    abstract val pos: Position

    var state: CellState = CellState.UNEXPLORED
    private set

    fun explored() {
    state = CellState.EXPLORED
    }

    fun switchMark() {
    state = when (state) {
    CellState.UNEXPLORED -> CellState.MARKED
    CellState.MARKED -> CellState.UNEXPLORED
    else -> CellState.EXPLORED
    }
    }
    }

    data class Mine(override val pos: Position) : Cell()
    data class SafeCell(override val pos: Position, val nbOfNearMines: Int) : Cell()

    typealias Position = Pair<Int, Int>
    typealias Field = List<List<Cell>>

    class Minesweeper(private val numberOfMines: Int) {
    private val size = 9
    private var state = State.PLAYING
    private var firstExploration = true

    private val minePositions: MutableSet<Position>
    private var field: Field = listOf()

    init {
    this.minePositions = randomMinePositions(numberOfMines)
    initField()
    }

    private fun randomMinePositions(numberOfMines: Int): MutableSet<Position> {
    return (1..numberOfMines).fold(setOf<Position>()) { acc, _ ->
    var newPos = randomMinePosition()
    while (newPos in acc) newPos = randomMinePosition()
    acc + newPos
    }.toMutableSet()
    }

    private fun nbOfNearMines(pos: Position): Int {
    return neighbours(pos).count { it in minePositions }
    }

    private fun neighbours(pos: Position) = (-1..1).flatMap { i ->
    (-1..1).map { j ->
    Position(pos.first + i, pos.second + j)
    }
    }

    // private fun euclidianDistance(a: Position, b: Position): Int {
    // return sqrt((a.first - b.first).toDouble().pow(2) + (a.second - b.second).toDouble().pow(2)).roundToInt()
    // }

    private fun randomMinePosition() = Pair(Random.nextInt(size), Random.nextInt(size))

    private fun initField() {
    val markedCells = markedCells()
    field = (0 until size).map { row ->
    (0 until size).map { column ->
    val pos = Pair(row, column)
    val cell = if (minePositions.contains(pos)) {
    Mine(pos)
    } else {
    SafeCell(pos, nbOfNearMines(pos))
    }
    if (pos in markedCells) {
    cell.switchMark()
    }
    cell
    }
    }
    }

    private fun symbolOf(cell: Cell): String {
    return when {
    state == State.LOST && cell is Mine -> "X"
    cell.state == CellState.EXPLORED && cell is SafeCell -> if (cell.nbOfNearMines == 0) {
    "/"
    } else {
    cell.nbOfNearMines.toString()
    }
    cell.state == CellState.MARKED -> "*"
    else -> "."
    }
    }

    fun display() {
    val separator = "—|" + (1..size).joinToString("") { "—" } + "|"
    println(" |" + (1..size).joinToString("") { it.toString() } + "|")
    println(separator)
    field.forEachIndexed { i, row ->
    println((i + 1).toString() + "|" + row.joinToString("") { symbolOf(it) } + "|")
    }
    println(separator)
    }

    private fun mark(pos: Position) {
    cellAt(pos)?.also {
    it.switchMark()
    val markedPositions = markedCells()
    state = if (minePositions == markedPositions) {
    State.WON
    } else {
    State.PLAYING
    }
    }
    }

    private fun explore(pos: Position) {
    manageFirstExploration(pos)
    cellAt(pos)?.also {
    state = if (it is Mine) {
    it.explored()
    State.LOST
    } else {
    exploreFill(pos, setOf())
    State.PLAYING
    }
    }
    }

    private fun manageFirstExploration(pos: Position) {
    if (firstExploration) {
    if (pos in minePositions) {
    var newPos = randomMinePosition()
    while (newPos in minePositions) newPos = randomMinePosition()
    minePositions.remove(pos)
    minePositions.add(newPos)
    initField()
    }
    firstExploration = false
    }
    }

    private fun exploreFill(pos: Position, alreadyExplored: Set<Position>): Set<Position> {
    if (alreadyExplored.contains(pos)) return alreadyExplored
    return cellAt(pos)?.let {
    it.explored()
    var newlyExplored = alreadyExplored + pos
    if (it is SafeCell && it.nbOfNearMines == 0) {
    newlyExplored = newlyExplored + exploreFill(Position(pos.first + 1, pos.second + 1), newlyExplored)
    newlyExplored = newlyExplored + exploreFill(Position(pos.first + 1, pos.second), newlyExplored)
    newlyExplored = newlyExplored + exploreFill(Position(pos.first + 1, pos.second - 1), newlyExplored)
    newlyExplored = newlyExplored + exploreFill(Position(pos.first - 1, pos.second + 1), newlyExplored)
    newlyExplored = newlyExplored + exploreFill(Position(pos.first - 1, pos.second), newlyExplored)
    newlyExplored = newlyExplored + exploreFill(Position(pos.first - 1, pos.second - 1), newlyExplored)
    newlyExplored = newlyExplored + exploreFill(Position(pos.first, pos.second + 1), newlyExplored)
    newlyExplored = newlyExplored + exploreFill(Position(pos.first, pos.second - 1), newlyExplored)
    newlyExplored = newlyExplored + exploreFill(Position(pos.first, pos.second - 1), newlyExplored)
    }
    newlyExplored
    } ?: alreadyExplored
    }

    /*
    Flood-fill (node, target-color, replacement-color):
    1. If target-color is equal to replacement-color, return.
    2. ElseIf the color of node is not equal to target-color, return.
    3. Else Set the color of node to replacement-color.
    4. Perform Flood-fill (one step to the south of node, target-color, replacement-color).
    Perform Flood-fill (one step to the north of node, target-color, replacement-color).
    Perform Flood-fill (one step to the west of node, target-color, replacement-color).
    Perform Flood-fill (one step to the east of node, target-color, replacement-color).
    5. Return.
    */

    private fun cellAt(pos: Position): Cell? {
    if (isOutOfIndex(pos)) return null
    return field[pos.first][pos.second]
    }


    private fun isOutOfIndex(pos: Position): Boolean {
    return isOutOfIndex(pos.first) || isOutOfIndex(pos.second)
    }

    private fun isOutOfIndex(index: Int): Boolean {
    return index < 0 || index >= size
    }

    private fun markedCells() =
    field.mapIndexed { i, row ->
    row.mapIndexed { j, cell -> if (cell.state == CellState.MARKED) Pair(i, j) else null }.filterNotNull()
    }.flatten().toSet()

    companion object {
    private fun from(input: String): Pair<Command, Pair<Int, Int>> {
    val splited = input.split(" ")
    val command = when (splited[2]) {
    "free" -> Command.EXPLORE
    else -> Command.MARK
    }
    return Pair(command, Pair(splited[1].toInt() - 1, splited[0].toInt() - 1))
    }

    fun play(scanner: Scanner) {
    print("How many mines do you want on the field? ")
    val nbOfMines = scanner.nextLine().toInt()
    val minesweeper = Minesweeper(nbOfMines)
    minesweeper.display()
    while (minesweeper.state == State.PLAYING) {
    print("Set/unset mines marks or claim a cell as free: ")
    val input = scanner.nextLine()
    if (input.isBlank()) continue
    val command = from(input)
    if (command.first == Command.EXPLORE) {
    minesweeper.explore(command.second)
    } else {
    minesweeper.mark(command.second)
    }
    minesweeper.display()
    }
    if (minesweeper.state == State.WON) {
    println("Congratulations! You found all mines!")
    } else {
    println("You stepped on a mine and failed!")
    }
    }
    }
    }

    fun main() {
    val scanner = Scanner(System.`in`)
    Minesweeper.play(scanner)
    }