path: root/core/src/commonMain/kotlin/coffee/liz/rookery/bld/Bld.kt

package coffee.liz.rookery.bld

import coffee.liz.rookery.puzzle.NxnCube

enum class PieceType { CORNER, EDGE }

/**
 * 3x3 blindfolded geometry in the solver's frame (the cube as held while solving, after any
 * rotation away from WCA scrambling orientation).
 *
 * Sticker slots are [NxnCube] slots (faces U R F D L B, 9 stickers each, row-major on a standard net).
 * Each piece type has 24 "positions" in Speffz order: faces U L F R B D, and on each face the
 * corners/edges clockwise from the top-left corner / top edge as seen on the net.
 */
object Cube3 {
    private val geo = NxnCube(3)
    private const val U = 0; private const val R = 1; private const val F = 2; private const val D = 3; private const val L = 4; private const val B = 5

    /** Speffz face order, as NxnCube face indices. */
    private val speffzFaces = intArrayOf(U, L, F, R, B, D)
    private val cornerCells = listOf(0 to 0, 0 to 2, 2 to 2, 2 to 0)
    private val edgeCells = listOf(0 to 1, 1 to 2, 2 to 1, 1 to 0)

    /** Position index (0..23, Speffz order) → sticker slot. */
    val positions: Map<PieceType, IntArray> = mapOf(
        PieceType.CORNER to IntArray(24) { i -> slot(speffzFaces[i / 4], cornerCells[i % 4]) },
        PieceType.EDGE to IntArray(24) { i -> slot(speffzFaces[i / 4], edgeCells[i % 4]) },
    )

    private fun slot(face: Int, cell: Pair<Int, Int>) = face * 9 + cell.first * 3 + cell.second

    fun slotOf(type: PieceType, pos: Int): Int = positions.getValue(type)[pos]
    fun positionOf(type: PieceType, slot: Int): Int? = positions.getValue(type).indexOf(slot).takeIf { it >= 0 }

    /**
     * Positions of the piece holding [pos], starting at [pos] and going clockwise around a corner
     * (seen from outside), or to the other sticker of an edge. Swapping two pieces sticker-by-sticker
     * in these orders is exactly what one Old Pochmann "shot" does.
     */
    fun pieceFrom(type: PieceType, pos: Int): IntArray = pieceCache.getValue(type)[pos]

    private val pieceCache: Map<PieceType, Array<IntArray>> = PieceType.entries.associateWith { type ->
        val slots = positions.getValue(type)
        Array(24) { pos ->
            val cubie = geo.cubieOf(slots[pos])
            val mates = (0 until 24).filter { geo.cubieOf(slots[it]) == cubie }
            if (type == PieceType.EDGE) intArrayOf(pos, mates.first { it != pos })
            else {
                // clockwise from outside: (n_a × n_b) · corner < 0
                val others = mates.filter { it != pos }
                val n0 = geo.normalOf(slots[pos]); val n1 = geo.normalOf(slots[others[0]])
                val cross = Triple(n0.second * n1.third - n0.third * n1.second, n0.third * n1.first - n0.first * n1.third, n0.first * n1.second - n0.second * n1.first)
                val dot = cross.first * cubie.first + cross.second * cubie.second + cross.third * cubie.third
                if (dot < 0) intArrayOf(pos, others[0], others[1]) else intArrayOf(pos, others[1], others[0])
            }
        }
    }

    /**
     * Which corner of the cube to look at (signs along x→R, y→U, z→F) so the whole piece holding
     * [slot] is in view: you need its other stickers to tell which piece it is. Axes the piece
     * doesn't constrain keep [prefer], so the view moves as little as possible.
     */
    fun viewCorner(slot: Int, prefer: Triple<Int, Int, Int> = Triple(1, 1, 1)): Triple<Int, Int, Int> {
        val c = geo.cubieOf(slot)
        fun pick(v: Int, keep: Int) = if (v > 0) 1 else if (v < 0) -1 else keep
        return Triple(pick(c.first, prefer.first), pick(c.second, prefer.second), pick(c.third, prefer.third))
    }

    /** The corner view (signs along x, y, z) from which the most of [slots] can be seen, preferring the usual front-top-right. */
    fun bestView(slots: List<Int>): Triple<Int, Int, Int> {
        val corners = listOf(1, -1).flatMap { x -> listOf(1, -1).flatMap { y -> listOf(1, -1).map { z -> Triple(x, y, z) } } }
        return corners.maxBy { c ->
            slots.count { s -> val n = geo.normalOf(s); n.first * c.first + n.second * c.second + n.third * c.third > 0 } * 8 +
                (if (c.second > 0) 4 else 0) + (if (c.third > 0) 2 else 0) + (if (c.first > 0) 1 else 0)
        }
    }

    /** The piece's lowest position, as a stable id for the piece. */
    fun pieceId(type: PieceType, pos: Int): Int = pieceFrom(type, pos).min()

    /** "UFR", "UF", … in the solver's frame, U/D first, then F/B, then R/L. */
    fun pieceName(type: PieceType, pos: Int): String {
        val names = "URFDLB"
        val order = "UDFBRL"
        return pieceFrom(type, pos).map { names[slotOf(type, it) / 9] }.sortedBy { order.indexOf(it) }.joinToString("")
    }

    /** Name of a single sticker: its face first, then the rest of the piece, e.g. "RDF". */
    fun stickerName(type: PieceType, pos: Int): String {
        val names = "URFDLB"
        val own = names[slotOf(type, pos) / 9]
        return own + pieceName(type, pos).filter { it != own }
    }
}

/**
 * A lettering scheme: one letter per position for each piece type, in Speffz position order.
 * The default is Speffz itself.
 */
data class LetterScheme(val corners: String = SPEFFZ, val edges: String = SPEFFZ) {
    init { require(corners.length == 24 && edges.length == 24) }

    fun letter(type: PieceType, pos: Int): Char = (if (type == PieceType.CORNER) corners else edges)[pos]
    fun position(type: PieceType, letter: Char): Int? =
        (if (type == PieceType.CORNER) corners else edges).indexOf(letter.uppercaseChar()).takeIf { it >= 0 }

    companion object { const val SPEFFZ = "ABCDEFGHIJKLMNOPQRSTUVWX" }
}

/** How the solver holds and solves: orientation, buffers, method. */
data class BldSetup(
    /** Rotation from WCA scrambling orientation (white top, green front) to how you hold the cube. */
    val rotation: String = "x2 y'",
    val scheme: LetterScheme = LetterScheme(),
    /** Buffer positions (Speffz indices). Defaults: UBL corner (A), UR edge (B). */
    val cornerBuffer: Int = 0,
    val edgeBuffer: Int = 1,
) {
    fun buffer(type: PieceType) = if (type == PieceType.CORNER) cornerBuffer else edgeBuffer

    /**
     * Sticker colours (by original face) for a scrambled cube, held the way the solver holds it:
     * picked up by its centres, so scrambles that end in wide moves or rotations (every official BLD
     * scramble does) still come out with your top/front colours on top/front.
     */
    fun stateOf(scramble: String): IntArray {
        val scrambled = NxnCube(3).apply(scramble)
        val wantU = solvedColors[4]
        val wantF = solvedColors[2 * 9 + 4]
        for (r in WHOLE_CUBE_ROTATIONS) {
            val c = scrambled.copy().apply(r)
            if (c.stickers[4] == wantU && c.stickers[2 * 9 + 4] == wantF) return c.stickers.copyOf()
        }
        error("no rotation puts colour $wantU on top and $wantF in front") // impossible for a legal cube
    }

    /** The solved cube as seen in the solver's frame (which colour belongs on each sticker). */
    val solvedColors: IntArray by lazy { NxnCube(3).apply(rotation).stickers.copyOf() }
}

/** All 24 orientations of a cube, as rotation moves: 6 choices of top, then 4 of front. */
internal val WHOLE_CUBE_ROTATIONS: List<String> =
    listOf("", "x", "x2", "x'", "z", "z'").flatMap { up -> listOf("", "y", "y2", "y'").map { "$up $it".trim() } }

/** A memo target: a position of a piece type. */
data class Target(val type: PieceType, val pos: Int)

/** Tracing and checking Old Pochmann style memo on a scrambled cube. */
class Tracer(private val setup: BldSetup) {
    private val solved = setup.solvedColors

    /** home[pos] = the position the sticker currently at pos belongs to. */
    fun homes(state: IntArray, type: PieceType): IntArray = IntArray(24) { pos ->
        val piece = Cube3.pieceFrom(type, pos)
        val colors = piece.map { state[Cube3.slotOf(type, it)] }
        // find the home piece: same colour set in the solved frame
        val home = (0 until 24).first { h ->
            val hp = Cube3.pieceFrom(type, h)
            hp.map { solved[Cube3.slotOf(type, it)] } == colors
        }
        home
    }

    fun isSolved(state: IntArray, type: PieceType): Boolean =
        (0 until 24).all { state[Cube3.slotOf(type, it)] == solved[Cube3.slotOf(type, it)] }

    /**
     * Memo targets in order, the way an OP solver traces: follow from the buffer; when the cycle
     * closes early, break into the unsolved piece with the lowest letter; finish with twisted or
     * flipped pieces (two targets each).
     */
    fun trace(state: IntArray, type: PieceType): List<Target> {
        val home = homes(state, type)
        val buffer = setup.buffer(type)
        val bufferPiece = Cube3.pieceId(type, buffer)
        val done = HashSet<Int>().apply { add(bufferPiece) }
        val out = mutableListOf<Int>()
        fun pieceSolved(pos: Int) = Cube3.pieceFrom(type, pos).all { home[it] == it }
        for (p in 0 until 24) if (pieceSolved(p)) done += Cube3.pieceId(type, p)

        // main cycle from the buffer
        var cur = buffer
        while (true) {
            val next = home[cur]
            if (Cube3.pieceId(type, next) == bufferPiece) break
            out += next; done += Cube3.pieceId(type, next); cur = next
        }
        // cycle breaks (and twists/flips, which are just length-1 cycles)
        while (true) {
            val start = (0 until 24).filter { Cube3.pieceId(type, it) !in done }
                .minByOrNull { setup.scheme.letter(type, it) } ?: break
            val piece = Cube3.pieceId(type, start)
            done += piece
            out += start
            cur = start
            while (true) {
                val next = home[cur]
                out += next
                done += Cube3.pieceId(type, next)
                if (Cube3.pieceId(type, next) == piece) break
                cur = next
            }
        }
        return out.map { Target(type, it) }
    }

    /** Apply OP shots: swap the buffer piece with each target piece, sticker for sticker. */
    fun execute(state: IntArray, targets: List<Target>): IntArray {
        val s = state.copyOf()
        for (t in targets) {
            val a = Cube3.pieceFrom(t.type, setup.buffer(t.type))
            val b = Cube3.pieceFrom(t.type, t.pos)
            for (k in a.indices) {
                val sa = Cube3.slotOf(t.type, a[k]); val sb = Cube3.slotOf(t.type, b[k])
                val tmp = s[sa]; s[sa] = s[sb]; s[sb] = tmp
            }
        }
        return s
    }

    /** Where a memo first stops following the cube. [expected] is the position that should have been typed, if there was exactly one. */
    data class Mistake(val index: Int, val expected: Int?, val brokeIntoSolved: Boolean = false)

    /**
     * Checks a memo target by target against what the cube shows: after each shot, the sticker now in
     * the buffer says where to go next; when the buffer piece comes home, any unsolved piece may be
     * broken into. Returns null for a complete, valid trace; `index == targets.size` means it stopped early.
     */
    fun firstMistake(state: IntArray, targets: List<Target>, type: PieceType): Mistake? {
        var s = state
        val buffer = setup.buffer(type)
        val bufferPiece = Cube3.pieceId(type, buffer)
        for ((i, t) in targets.withIndex()) {
            val home = homes(s, type)
            val next = home[buffer]
            if (Cube3.pieceId(type, next) != bufferPiece) {
                if (t.pos != next) return Mistake(i, next)
            } else if (Cube3.pieceFrom(type, t.pos).all { home[it] == it }) {
                return Mistake(i, null, brokeIntoSolved = true)
            }
            s = execute(s, listOf(t))
        }
        if (isSolved(s, type)) return null
        val next = homes(s, type)[buffer]
        return Mistake(targets.size, next.takeIf { Cube3.pieceId(type, it) != bufferPiece })
    }

    /** Pieces of [type] not solved in [state], by name. */
    fun wrongPieces(state: IntArray, type: PieceType): List<String> =
        (0 until 24).map { Cube3.pieceId(type, it) }.distinct().filter { id ->
            Cube3.pieceFrom(type, id).any { state[Cube3.slotOf(type, it)] != solved[Cube3.slotOf(type, it)] }
        }.map { Cube3.pieceName(type, it) }

    fun letters(targets: List<Target>): String = targets.joinToString("") { setup.scheme.letter(it.type, it.pos).toString() }

    /**
     * Parse typed memo letters (spaces/punctuation ignored). Returns targets, or the offending
     * characters if some letters aren't in the scheme or name the buffer piece.
     */
    fun parse(text: String, type: PieceType): Pair<List<Target>, List<String>> {
        val errors = mutableListOf<String>()
        val bufferPiece = Cube3.pieceId(type, setup.buffer(type))
        val targets = text.filter { it.isLetter() }.mapNotNull { c ->
            val pos = setup.scheme.position(type, c)
            when {
                pos == null -> { errors += "'$c' isn't a ${type.name.lowercase()} letter"; null }
                Cube3.pieceId(type, pos) == bufferPiece -> { errors += "'$c' is on the buffer piece"; null }
                else -> Target(type, pos)
            }
        }
        return targets to errors
    }

    /** Whether corner targets have odd length, i.e. this solve needs the parity algorithm. */
    fun hasParity(cornerTargets: List<Target>): Boolean = cornerTargets.size % 2 == 1
}