diff options
Diffstat (limited to 'core/src/commonMain/kotlin/coffee/liz/rookery')
5 files changed, 405 insertions, 0 deletions
diff --git a/core/src/commonMain/kotlin/coffee/liz/rookery/bld/Bld.kt b/core/src/commonMain/kotlin/coffee/liz/rookery/bld/Bld.kt new file mode 100644 index 0000000..936b103 --- /dev/null +++ b/core/src/commonMain/kotlin/coffee/liz/rookery/bld/Bld.kt @@ -0,0 +1,213 @@ +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]) + } + } + } + + /** 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, seen in the solver's frame. */ + fun stateOf(scramble: String): IntArray = NxnCube(3).apply(scramble).apply(rotation).stickers.copyOf() + + /** 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() } +} + +/** 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 + } + + /** 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 +} diff --git a/core/src/commonMain/kotlin/coffee/liz/rookery/puzzle/CubeMapping.kt b/core/src/commonMain/kotlin/coffee/liz/rookery/puzzle/CubeMapping.kt new file mode 100644 index 0000000..86069c4 --- /dev/null +++ b/core/src/commonMain/kotlin/coffee/liz/rookery/puzzle/CubeMapping.kt @@ -0,0 +1,32 @@ +package coffee.liz.rookery.puzzle + +import kotlin.math.abs +import kotlin.math.roundToInt + +/** + * Bridges [TwistyPuzzle] cubes (what the renderer draws) and [NxnCube] slots (what BLD logic and + * notation-level code use): `slotOf[i]` is the NxnCube slot of generic sticker i. + */ +class CubeMapping(val puzzle: TwistyPuzzle, val n: Int) { + val slotOf: IntArray = IntArray(puzzle.stickers.size) { i -> slotFor(puzzle.stickers[i].centroid) } + private val stickerOf: IntArray = IntArray(6 * n * n).also { inv -> slotOf.forEachIndexed { i, s -> inv[s] = i } } + + fun stickerOfSlot(slot: Int): Int = stickerOf[slot] + + /** Render an NxnCube colour array (indexed by slot) as a generic puzzle state. */ + fun state(slotColors: IntArray): PuzzleState = PuzzleState(puzzle, IntArray(puzzle.stickers.size) { slotColors[slotOf[it]] }) + + // Inverse of NxnCube.slotPosition, on the unit cube ([-1, 1]^3). + private fun slotFor(c: V3): Int { + fun idx(v: Double) = ((v * n + (n - 1)) / 2).roundToInt().coerceIn(0, n - 1) + val (face, row, col) = when { + abs(c.y - 1) < 1e-6 -> Triple(0, idx(c.z), idx(c.x)) // U: a = x, b = z + abs(c.x - 1) < 1e-6 -> Triple(1, idx(-c.y), idx(-c.z)) // R: (n, -b, -a) + abs(c.z - 1) < 1e-6 -> Triple(2, idx(-c.y), idx(c.x)) // F: (a, -b, n) + abs(c.y + 1) < 1e-6 -> Triple(3, idx(-c.z), idx(c.x)) // D: (a, -n, -b) + abs(c.x + 1) < 1e-6 -> Triple(4, idx(-c.y), idx(c.z)) // L: (-n, -b, a) + else -> Triple(5, idx(-c.y), idx(-c.x)) // B: (-a, -b, -n) + } + return face * n * n + row * n + col + } +} diff --git a/core/src/commonMain/kotlin/coffee/liz/rookery/puzzle/NxnCube.kt b/core/src/commonMain/kotlin/coffee/liz/rookery/puzzle/NxnCube.kt index 54b4cda..4d9cd1d 100644 --- a/core/src/commonMain/kotlin/coffee/liz/rookery/puzzle/NxnCube.kt +++ b/core/src/commonMain/kotlin/coffee/liz/rookery/puzzle/NxnCube.kt @@ -73,6 +73,18 @@ class NxnCube(val n: Int) { 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) } diff --git a/core/src/commonMain/kotlin/coffee/liz/rookery/srs/Srs.kt b/core/src/commonMain/kotlin/coffee/liz/rookery/srs/Srs.kt new file mode 100644 index 0000000..a0907da --- /dev/null +++ b/core/src/commonMain/kotlin/coffee/liz/rookery/srs/Srs.kt @@ -0,0 +1,93 @@ +package coffee.liz.rookery.srs + +import kotlin.math.exp +import kotlin.math.max +import kotlin.math.min +import kotlin.math.pow +import kotlin.random.Random + +/** Answer quality, FSRS-style. */ +enum class Grade(val value: Int) { AGAIN(1), HARD(2), GOOD(3), EASY(4) } + +/** One answered prompt. [ms] is how long the answer took (null if not timed). */ +data class Review(val item: String, val at: Long, val grade: Grade, val ms: Long? = null) + +/** + * Memory state of one item: stability (days until recall probability falls to 90%) and + * difficulty (1 easy .. 10 hard), per FSRS-4.5 with its published default weights. + */ +data class Memory(val stability: Double, val difficulty: Double, val lastReview: Long, val reps: Int, val lapses: Int) { + /** Probability of recalling the item at [now]. */ + fun retrievability(now: Long): Double { + val days = max(0.0, (now - lastReview) / DAY_MS) + return (1 + days / (9 * stability)).pow(-1.0) + } + + companion object { const val DAY_MS = 86_400_000.0 } +} + +object Fsrs { + private val w = doubleArrayOf( + 0.4872, 1.4003, 3.7145, 13.8206, 5.1618, 1.2298, 0.8975, 0.031, 1.6474, + 0.1367, 1.0461, 2.1072, 0.0793, 0.3246, 1.587, 0.2272, 2.8755, + ) + + private fun initDifficulty(g: Grade) = (w[4] - (g.value - 3) * w[5]).coerceIn(1.0, 10.0) + + fun first(r: Review) = Memory(w[r.grade.value - 1], initDifficulty(r.grade), r.at, 1, if (r.grade == Grade.AGAIN) 1 else 0) + + fun next(m: Memory, r: Review): Memory { + val ret = m.retrievability(r.at) + val d = m.difficulty - w[6] * (r.grade.value - 3) + val difficulty = (w[7] * initDifficulty(Grade.GOOD) + (1 - w[7]) * d).coerceIn(1.0, 10.0) + val stability = if (r.grade == Grade.AGAIN) { + min(m.stability, w[11] * difficulty.pow(-w[12]) * ((m.stability + 1).pow(w[13]) - 1) * exp(w[14] * (1 - ret))) + } else { + val hard = if (r.grade == Grade.HARD) w[15] else 1.0 + val easy = if (r.grade == Grade.EASY) w[16] else 1.0 + m.stability * (exp(w[8]) * (11 - difficulty) * m.stability.pow(-w[9]) * (exp(w[10] * (1 - ret)) - 1) * hard * easy + 1) + } + return Memory(max(0.01, stability), difficulty, r.at, m.reps + 1, m.lapses + if (r.grade == Grade.AGAIN) 1 else 0) + } + + /** Replay an item's reviews (any order) into its current memory state. */ + fun replay(reviews: List<Review>): Memory? { + var m: Memory? = null + for (r in reviews.sortedBy { it.at }) m = m?.let { next(it, r) } ?: first(r) + return m + } +} + +/** + * Grades a timed answer: wrong → AGAIN, otherwise by speed relative to [goodMs] + * (fast enough to use mid-solve is EASY, a long think is HARD). + */ +fun gradeAnswer(correct: Boolean, ms: Long, goodMs: Long = 2_500): Grade = when { + !correct -> Grade.AGAIN + ms <= goodMs / 2 -> Grade.EASY + ms <= goodMs -> Grade.GOOD + else -> Grade.HARD +} + +/** + * Picks what to drill next. Unlike day-based flashcards, a drill session runs continuously, so items + * are weighted rather than scheduled: forgotten-ish (low retrievability), hard, and recently-missed + * items come up most; never-seen items are mixed in steadily; the last few items are avoided. + */ +class DrillPicker(private val random: Random = Random.Default) { + fun weight(m: Memory?, now: Long, recentMisses: Int): Double { + if (m == null) return 1.5 // new: fairly likely, so the whole set gets introduced + val forget = 1 - m.retrievability(now) + val hard = (m.difficulty - 1) / 9 + return 0.05 + 2.0 * forget + 0.8 * hard + 1.2 * recentMisses + } + + fun <T> pick(items: List<T>, memory: (T) -> Memory?, recentMisses: (T) -> Int, avoid: Collection<T>, now: Long): T? { + val pool = items.filter { it !in avoid }.ifEmpty { items } + if (pool.isEmpty()) return null + val weights = pool.map { weight(memory(it), now, recentMisses(it)) } + var x = random.nextDouble() * weights.sum() + for ((i, wt) in weights.withIndex()) { x -= wt; if (x <= 0) return pool[i] } + return pool.last() + } +} diff --git a/core/src/commonMain/kotlin/coffee/liz/rookery/store/Repo.kt b/core/src/commonMain/kotlin/coffee/liz/rookery/store/Repo.kt index 6c0fafa..3e04f11 100644 --- a/core/src/commonMain/kotlin/coffee/liz/rookery/store/Repo.kt +++ b/core/src/commonMain/kotlin/coffee/liz/rookery/store/Repo.kt @@ -24,6 +24,8 @@ object Coll { const val MEMO = "memo" const val DEVICE = "device" const val PREFS = "prefs" + /** Append-only trainer answers; one entity per answer so concurrent devices never conflict. */ + const val REVIEW = "review" } private fun Map<String, JsonElement>.str(f: String): String? = (this[f] as? JsonPrimitive)?.takeIf { this[f] !is JsonNull }?.contentOrNull @@ -133,6 +135,59 @@ class Repo(val store: Store) { } }.sortedBy { it.at } + // ---- trainer reviews ---- + + fun addReview(id: String, r: coffee.liz.rookery.srs.Review) = store.transact { + set(Coll.REVIEW, id, "v", kotlinx.serialization.json.buildJsonObject { + put("item", JsonPrimitive(r.item)); put("at", JsonPrimitive(r.at)); put("g", JsonPrimitive(r.grade.value)) + r.ms?.let { put("ms", JsonPrimitive(it)) } + }) + } + + fun reviews(): List<coffee.liz.rookery.srs.Review> = store.read { r -> + r.entities(Coll.REVIEW).values.mapNotNull { f -> + val o = f["v"] as? kotlinx.serialization.json.JsonObject ?: return@mapNotNull null + val grade = coffee.liz.rookery.srs.Grade.entries.firstOrNull { it.value.toLong() == o.long("g") } ?: return@mapNotNull null + coffee.liz.rookery.srs.Review(o.str("item") ?: return@mapNotNull null, o.long("at") ?: 0, grade, o.long("ms")) + } + } + + /** Practice history from the Letter Pair Gym prototype: recent results oldest→newest (g/s/m). */ + fun gymHistory(): Map<String, String> = store.read { r -> + r.entities(Coll.PAIR).mapNotNull { (pair, f) -> + val rec = ((f["gymStats"] as? kotlinx.serialization.json.JsonObject)?.get("r") as? JsonPrimitive)?.contentOrNull + rec?.takeIf { it.isNotEmpty() }?.let { pair to it } + }.toMap() + } + + // ---- BLD setup ---- + + fun bldSetup(): coffee.liz.rookery.bld.BldSetup { + val d = coffee.liz.rookery.bld.BldSetup() + val corners = pref("bld.corners")?.takeIf { it.length == 24 } ?: d.scheme.corners + val edges = pref("bld.edges")?.takeIf { it.length == 24 } ?: d.scheme.edges + return coffee.liz.rookery.bld.BldSetup( + rotation = pref("bld.rotation") ?: d.rotation, + scheme = coffee.liz.rookery.bld.LetterScheme(corners, edges), + cornerBuffer = pref("bld.cornerBuffer")?.toIntOrNull() ?: d.cornerBuffer, + edgeBuffer = pref("bld.edgeBuffer")?.toIntOrNull() ?: d.edgeBuffer, + ) + } + + fun setBldSetup(s: coffee.liz.rookery.bld.BldSetup) = store.transact { + set(Coll.PREFS, "global", "bld.rotation", s.rotation) + set(Coll.PREFS, "global", "bld.corners", s.scheme.corners) + set(Coll.PREFS, "global", "bld.edges", s.scheme.edges) + set(Coll.PREFS, "global", "bld.cornerBuffer", s.cornerBuffer.toString()) + set(Coll.PREFS, "global", "bld.edgeBuffer", s.edgeBuffer.toString()) + } + + fun addMemoSession(m: MemoSession, extra: Map<String, String> = emptyMap()) = store.transact { + val id = "memo-" + m.at + set(Coll.MEMO, id, "at", m.at); set(Coll.MEMO, id, "pairs", m.pairs); set(Coll.MEMO, id, "ms", m.memoMs); set(Coll.MEMO, id, "ok", m.recalled) + for ((k, v) in extra) set(Coll.MEMO, id, k, v) + } + // ---- devices & prefs ---- fun devices(): List<CubeDevice> = store.read { r -> |