package coffee.liz.rookery.puzzle

/**
 * Sticker-level model of an NxN cube, enough to draw scramble previews and replay notation.
 *
 * Faces are stored U R F D L B (Kociemba order), each n*n stickers row-major as you look at the
 * face on a standard net. Geometry uses doubled integer coordinates: cubie centres sit on odd/even
 * steps in [-(n-1), n-1] and stickers poke out to ±n, so quarter turns stay exact integers.
 * Axes: x→R, y→U, z→F.
 */
class NxnCube(val n: Int) {
    init { require(n in 1..12) }

    enum class Face { U, R, F, D, L, B }

    /** Colour index per sticker slot; the colour index is the face it started on. */
    val stickers = IntArray(6 * n * n) { it / (n * n) }

    val isSolved: Boolean get() = (0 until 6).all { f -> (0 until n * n).all { stickers[f * n * n + it] == f } }

    fun copy(): NxnCube = NxnCube(n).also { stickers.copyInto(it.stickers) }

    fun apply(alg: String): NxnCube { for (m in Notation.parse(alg, n)) turn(m); return this }

    fun turn(m: Move) {
        val perm = permutation(m.axis, m.layers, m.quarter)
        val old = stickers.copyOf()
        for (i in perm.indices) stickers[perm[i]] = old[i]
    }

    // ---- geometry ----

    private class P(val x: Int, val y: Int, val z: Int)

    private val positions: Array<P> = Array(6 * n * n) { slotPosition(it) }
    private val index: Map<Triple<Int, Int, Int>, Int> = positions.withIndex().associate { (i, p) -> Triple(p.x, p.y, p.z) to i }

    private fun slotPosition(slot: Int): P {
        val face = Face.entries[slot / (n * n)]
        val r = (slot % (n * n)) / n
        val c = slot % n
        val a = 2 * c - (n - 1) // left→right
        val b = 2 * r - (n - 1) // top→bottom
        return when (face) {
            Face.U -> P(a, n, b)
            Face.D -> P(a, -n, -b)
            Face.F -> P(a, -b, n)
            Face.B -> P(-a, -b, -n)
            Face.R -> P(n, -b, -a)
            Face.L -> P(-n, -b, a)
        }
    }

    private val cache = HashMap<Triple<Int, Set<Int>, Int>, IntArray>()

    /**
     * Where each slot goes for a turn of [layers] (0 = the +axis face layer, n-1 = the -axis face
     * layer) about [axis] (0=x,1=y,2=z), clockwise looking from +axis, [quarter] times (1..3).
     */
    private fun permutation(axis: Int, layers: Set<Int>, quarter: Int): IntArray = cache.getOrPut(Triple(axis, layers, quarter)) {
        IntArray(positions.size) { i ->
            var p = positions[i]
            val coord = when (axis) { 0 -> p.x; 1 -> p.y; else -> p.z }.coerceIn(-(n - 1), n - 1)
            val layer = ((n - 1) - coord) / 2
            if (layer in layers) repeat(quarter) { p = rotate(p, axis) }
            index.getValue(Triple(p.x, p.y, p.z))
        }
    }

    private fun rotate(p: P, axis: Int): P = when (axis) {
        0 -> P(p.x, p.z, -p.y)
        1 -> P(-p.z, p.y, p.x)
        else -> P(p.y, -p.x, p.z)
    }

    /** Cubie position of a sticker slot, in doubled coordinates (each axis in -(n-1)..n-1). */
    fun cubieOf(slot: Int): Triple<Int, Int, Int> {
        val p = positions[slot]
        return Triple(p.x.coerceIn(-(n - 1), n - 1), p.y.coerceIn(-(n - 1), n - 1), p.z.coerceIn(-(n - 1), n - 1))
    }

    /** Outward normal of a sticker slot as an axis-aligned unit vector. */
    fun normalOf(slot: Int): Triple<Int, Int, Int> {
        val p = positions[slot]
        return Triple(if (kotlin.math.abs(p.x) == n) p.x / n else 0, if (kotlin.math.abs(p.y) == n) p.y / n else 0, if (kotlin.math.abs(p.z) == n) p.z / n else 0)
    }

    fun face(f: Face): IntArray = stickers.copyOfRange(f.ordinal * n * n, (f.ordinal + 1) * n * n)
}

/** A turn of a set of layers about an axis, clockwise from the +axis side. */
data class Move(val axis: Int, val layers: Set<Int>, val quarter: Int)

object Notation {
    private val token = Regex("""^(\d*)([URFDLBurfdlbxyzMES])(w?)(\d*)('?)$""")

    /** Parse WCA/SiGN notation (R, U2', Rw, 3Rw, r, 2R, x, M…) into layer turns for an n-cube. */
    fun parse(alg: String, n: Int): List<Move> = alg
        .replace("(", " ").replace(")", " ")
        .split(Regex("\\s+")).filter { it.isNotEmpty() }
        .map { parseMove(it, n) ?: throw IllegalArgumentException("bad move '$it' for ${n}x$n") }

    fun parseMove(t: String, n: Int): Move? {
        val m = token.matchEntire(t) ?: return null
        val (prefix, letter, w, amountStr, prime) = m.destructured
        var amount = if (amountStr.isEmpty()) 1 else amountStr.toInt()
        if (prime.isNotEmpty()) amount = -amount
        val all = (0 until n).toSet()
        val lower = letter[0].isLowerCase() && letter[0] !in "xyz"
        val face = letter.uppercase()[0]
        val depth: IntRange = when {
            face in "XYZ" -> 0 until n
            face in "MES" -> if (n % 2 == 1 && n > 1) (n / 2)..(n / 2) else return null
            w.isNotEmpty() || lower -> 0 until (if (prefix.isEmpty()) 2 else prefix.toInt())
            prefix.isNotEmpty() -> (prefix.toInt() - 1)..(prefix.toInt() - 1)
            else -> 0..0
        }
        if (depth.last >= n) return null
        // axis, and whether this face sits on the -axis side (so layers count from the other end and direction flips)
        val (axis, negative) = when (face) {
            'R', 'X' -> 0 to false; 'L', 'M' -> 0 to true
            'U', 'Y' -> 1 to false; 'D', 'E' -> 1 to true
            'F', 'Z', 'S' -> 2 to false; 'B' -> 2 to true
            else -> return null
        }
        val layers = if (face in "XYZ") all else depth.map { if (negative) n - 1 - it else it }.toSet()
        val q = ((if (negative) -amount else amount) % 4 + 4) % 4
        return Move(axis, layers, if (q == 0) 4 else q)
    }

    /** Inverse of a move sequence, as text. */
    fun invert(alg: String): String = alg.trim().split(Regex("\\s+")).filter { it.isNotEmpty() }.reversed().joinToString(" ") { t ->
        when {
            t.endsWith("2'") -> t.dropLast(1)
            t.endsWith("2") -> t
            t.endsWith("'") -> t.dropLast(1)
            else -> "$t'"
        }
    }
}