1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
|
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'"
}
}
}
|
