[cubing.js issue] Detect partial solve

[Wyverex42]

[cubing.js issue] Detect partial solve

[lgarron]

• I'm wondering why the transformation in cubeOrientation is called inverseTransformation. algToTransformation creates a transformation from a given alg, i.e. the tranformation describes how to transform a KPattern to another after applying that alg, right? So isn't this the actual transformation and not the inverse?

We're using it as a lookup table for how to undo a transformation. I admit I haven't 100% thought this through, but this is the direction that gives the correct result.

• At first I didn't quite understand the need for finding the DRF and looking up the corresponding solved patterns yet, since conceptually there's only one single solved pattern for Roux SB with a given "color orientation". IIUC, this is because the pattern might be solved but the cube might be oriented differently, e.g. both blocks being in the top layer now, that's why we have to find the DRF given the current orientation and then check the pattern, right? So I could potentially simplify here as well if I can guarantee that the cube is in a certain orientation

Yeah, if you want to enforce a certain orientation for blocks you can remove some of the orientations.

In any case, this code motivated me to finally put together the missing pieces for https://experiments.cubing.net/cubing.js/live-reconstruction/ — it has some way to go, but turns out it's quite practical to implement pattern detection across multiple solving methods for us now!

[lgarron]

My issue might actually be a non-issue and purely due to lack of understanding on the internals of cubing.js. More documentation around KPattern and KTransformation would help immensely for first timers! (or maybe I just didn't find it?)

You're not missing anything. KPattern and KTransformation are still more on the experimental side of things, because we don't know exactly what features and assumptions we should bake into the core implementation for the long term. Feature requests like yours can helps us figure that out.

There are two challenges here:

• We don't have a way for one pattern to match another pattern unless they're identical. (KPattern is specifically designed to make this practical in the future, but we haven't implemented it yet.)
• Roux second block can't be normalized using centers.
• Not only do you have the orientation of the blocks to take into account, but also the "color orientation".

The naïve implementation of this might take 24 × 24 = 576 comparisons, which isn't great. So what I would do is build a table or all solved "color orientations" normalized to standard orientation, and use any piece to normalize the candidates for
a comparison that masks out just the relevant pieces. The following code does this:

import { Alg, AlgBuilder, Move } from "cubing/alg";
import {
  KPattern,
  type KPatternData,
  type KPatternOrbitData,
  KTransformation,
} from "cubing/kpuzzle";
import { cube3x3x3 } from "cubing/puzzles";

enum PieceMask {
  Regular,
  Ignore,
}
const R = PieceMask.Regular;
const I = PieceMask.Ignore;
type PatternMask = Record<string /* orbit name */, PieceMask[]>;

const rouxSecondBlockPatternMask: PatternMask = {
  EDGES: [I, I, I, I, I, R, I, R, R, R, R, R],
  CORNERS: [I, I, I, I, R, R, R, R],
  CENTERS: [I, R, I, R, I, I],
};

const IGNORED_PIECE_VALUE = 99; // TODO: This should really be set to the lowest otherwise unused piece number in the orbit.

function applyPatternMask(pattern: KPattern, mask: PatternMask): KPattern {
  const newPatternData: KPatternData = {};
  for (const orbitDefinition of kpuzzle.definition.orbits) {
    const patternOrbit = pattern.patternData[orbitDefinition.orbitName];
    const maskOrbit = mask[orbitDefinition.orbitName];
    const newOrbitData: KPatternOrbitData & { orientationMod: number[] } = {
      pieces: [],
      orientation: [],
      orientationMod: [],
    };

    for (let i = 0; i < orbitDefinition.numPieces; i++) {
      switch (maskOrbit[i]) {
        case PieceMask.Regular: {
          newOrbitData.pieces.push(patternOrbit.pieces[i]);
          newOrbitData.orientation.push(patternOrbit.orientation[i]);
          newOrbitData.orientationMod.push(
            patternOrbit.orientationMod?.[i] ?? 0,
          );
          break;
        }
        case PieceMask.Ignore: {
          newOrbitData.pieces.push(IGNORED_PIECE_VALUE);
          newOrbitData.orientation.push(0);
          newOrbitData.orientationMod.push(1);
          break;
        }
        default: {
          throw new Error("Unrecognized `PieceMaskAction` value.");
        }
      }
    }
    newPatternData[orbitDefinition.orbitName] = newOrbitData;
  }
  return new KPattern(pattern.kpuzzle, newPatternData);
}

const kpuzzle = await cube3x3x3.kpuzzle();

const cubeOrientations: {
  inverseTransformation: KTransformation;
  algToNormalize: Alg;
}[] = [];
for (const moveToSetU of [
  null,
  new Move("x"),
  new Move("x2"),
  new Move("x'"),
  new Move("z"),
  new Move("z'"),
]) {
  for (const moveToSetF of [
    null,
    new Move("y"),
    new Move("y2"),
    new Move("y'"),
  ]) {
    const algBuilder: AlgBuilder = new AlgBuilder();
    if (moveToSetU) {
      algBuilder.push(moveToSetU);
    }
    if (moveToSetF) {
      algBuilder.push(moveToSetF);
    }
    const algToNormalize = algBuilder.toAlg();
    const inverseTransformation = kpuzzle.algToTransformation(algToNormalize);
    cubeOrientations.push({
      inverseTransformation,
      algToNormalize,
    });
  }
}

const orientedSolvedPattern: KPattern = kpuzzle.defaultPattern();

const solvedPatternsByDRF: Record<
  number /* DRF piece */,
  Record<number /* DRF orientation */, KPattern>
> = {};
const DRF_ORBIT = "CORNERS";
const DRF_INDEX = 4;
// Assumes DRF is a piece with known piece number and orientation.
function extractDRFCoordinates(pattern: KPattern): {
  pieceDRF: number;
  orientationDRF: number;
} {
  const orbitData = pattern.patternData[DRF_ORBIT];
  if ((orbitData.orientationMod?.[DRF_INDEX] ?? 0) !== 0) {
    throw new Error("Unexpected partially known orientation");
  }
  return {
    pieceDRF: orbitData.pieces[DRF_INDEX],
    orientationDRF: orbitData.orientation[DRF_INDEX],
  };
}
for (const cubeOrientation of cubeOrientations) {
  const orientedPattern = orientedSolvedPattern.applyTransformation(
    cubeOrientation.inverseTransformation,
  );
  const maskedPattern = applyPatternMask(
    orientedPattern,
    rouxSecondBlockPatternMask,
  );
  const { pieceDRF, orientationDRF } = extractDRFCoordinates(orientedPattern);
  const byOrientation = (solvedPatternsByDRF[pieceDRF] ??= {});
  byOrientation[orientationDRF] = maskedPattern;
}

function isRouxSecondBlockSolved(
  candidateFull3x3x3Pattern: KPattern,
): { isSolved: false } | { isSolved: true; algToNormalize: Alg } {
  for (const cubeOrientation of cubeOrientations) {
    const reorientedCandidate = candidateFull3x3x3Pattern.applyTransformation(
      cubeOrientation.inverseTransformation,
    );
    const candidateMasked = applyPatternMask(
      reorientedCandidate,
      rouxSecondBlockPatternMask,
    );
    const { pieceDRF, orientationDRF } =
      extractDRFCoordinates(reorientedCandidate);
    const solvedPatternByDRF = solvedPatternsByDRF[pieceDRF][orientationDRF];
    if (candidateMasked.isIdentical(solvedPatternByDRF)) {
      const { algToNormalize } = cubeOrientation;
      return { isSolved: true, algToNormalize };
    }
  }
  return { isSolved: false };
}

function test(candidate: KPattern) {
  const isSolvedInfo = isRouxSecondBlockSolved(candidate);
  if (isSolvedInfo.isSolved) {
    console.log(
      `Solved, orient using: ${
        isSolvedInfo.algToNormalize.experimentalIsEmpty()
          ? "(empty alg)"
          : isSolvedInfo.algToNormalize
      }`,
    );
  } else {
    console.log("Unsolved");
  }
}

test(orientedSolvedPattern.applyAlg("U L F R B D")); // Prints: "Unsolved"
test(orientedSolvedPattern.applyAlg("y b U B' U F R2 F' y'")); // Prints: "Solved, orient using: (empty alg)"
test(orientedSolvedPattern.applyAlg("M' U'")); // Prints: "Solved, orient using: (empty alg)"
test(orientedSolvedPattern.applyAlg("F")); // Prints: "Solved, orient using: x"
test(orientedSolvedPattern.applyAlg("b U B' U F R2 F'")); // Prints: "Solved, orient using: y"
test(orientedSolvedPattern.applyAlg("[S', L]")); // Prints: "Solved, orient using: z y"

This obviously is a lot of work, but it has most of the ideas I expect to use to implement this in cubing.js for most puzzles.

[Wyverex42]

Oh wow, I didn't expect a full-blown solution as an answer! You're a star, thanks!

I think this all makes sense to me, except for the questions below. I can also simplify this a bit for my use case as I know the cube orientation beforehand, so I don't need to iterate over all orientations to check the solution. But this is great to understand better how everything fits together!

• I'm wondering why the transformation in cubeOrientation is called inverseTransformation. algToTransformation creates a transformation from a given alg, i.e. the tranformation describes how to transform a KPattern to another after applying that alg, right? So isn't this the actual transformation and not the inverse?
• At first I didn't quite understand the need for finding the DRF and looking up the corresponding solved patterns yet, since conceptually there's only one single solved pattern for Roux SB with a given "color orientation". IIUC, this is because the pattern might be solved but the cube might be oriented differently, e.g. both blocks being in the top layer now, that's why we have to find the DRF given the current orientation and then check the pattern, right? So I could potentially simplify here as well if I can guarantee that the cube is in a certain orientation

[Wyverex42]

I've been struggling with this code for the last few days as I couldn't quite make it do what I wanted. And I now know why. Let's say you are in "x2 y" orientation, so yellow top, red front, on a solved cube. If you now apply an R move, it's immediately apparent that second block isn't solved anymore. However, the test function still claims it is. Because it realizes that there is another second block pattern on the cube which is still solved, in fact there are several, one of which can be obtained by applying a z' rotation.

Now this is correct, however, it's not useful for a trainer. When solving Roux, you decide on an orientation during inspection and then never rotate. So what I really want is to limit the solved patterns to those that correspond to the chosen cube orientation. And that's exactly one pattern.

However, since slice moves can make the virtual cube think it was rotated (e.g. M or M' can apply a virtual x or x' rotation), I also need to consider the same pattern mask rotated by x, x' and x2 (in case of Roux specifically where M slices are prevalent). So I ended up writing a function that can permute the pattern mask (and the stickering mask) by a given KTransformation.

The end result is much simpler for my use so I'm sharing it here in case someone else can make use of it too. Note that since parsing a stickering mask isn't exposed, I had to write that code again (which isn't included here).

export interface IPuzzle {
    setup(
        cubeOrientation: CubeOrientation,
        stickeringMask: StickeringMaskData,
        patternMask: PatternMask,
        additionalSolveOrientations?: Alg[]): void;
    setAlg(alg: Alg): void;

    isCaseSolved(pattern: KPattern): boolean;
}

export class Puzzle implements IPuzzle {
    readonly player: TwistyPlayer;
    readonly kpuzzle: KPuzzle;
    cubeOrientation: CubeOrientation;
    patternMasks: PatternMask[] = [];
    solvedPatterns: KPattern[] = [];

    constructor(player: TwistyPlayer, kpuzzle: KPuzzle) {
        this.player = player;
        this.kpuzzle = kpuzzle;
        this.cubeOrientation = new CubeOrientation(new Alg(), this.kpuzzle);
    }

    setup(cubeOrientation: CubeOrientation, stickeringMask: StickeringMaskData, patternMask: PatternMask, additionalSolveOrientations?: Alg[]) {
        this.cubeOrientation = cubeOrientation;
        this.patternMasks = [];
        this.solvedPatterns = [];

        var newMask = permuteOrbitArrays(this.kpuzzle, stickeringMask, cubeOrientation.inverseTransformation);
        this.player.experimentalModel.twistySceneModel.stickeringMaskRequest.set(serializeStickeringMask(newMask));

        // Default pattern + cube orientation
        const reorientedDefaultPattern = this.kpuzzle.defaultPattern().applyTransformation(cubeOrientation.inverseTransformation);

        this.patternMasks.push(patternMask);
        this.solvedPatterns.push(applyPatternMask(this.kpuzzle, reorientedDefaultPattern, patternMask));

        // Slice moves can reorient the virtual cube, e.g. M & M' can make it look like we applied additional x rotations.
        // Calculate the solved pattern for each of these additional rotations here
        if (additionalSolveOrientations) {
            for (const overlay of additionalSolveOrientations) {
                const transform = this.kpuzzle.algToTransformation(overlay);
                const pattern = reorientedDefaultPattern.applyTransformation(transform);
                const orientedMask = permuteOrbitArrays(this.kpuzzle, patternMask, transform);
                this.patternMasks.push(orientedMask);
                this.solvedPatterns.push(applyPatternMask(this.kpuzzle, pattern, orientedMask));
            }
        }
    }

    setAlg(alg: Alg): void {
        this.player.alg = "";
        const fullAlg = this.cubeOrientation.algToNormalize.concat(alg);
        this.player.alg = fullAlg;
    }

    isCaseSolved(pattern: KPattern): boolean {
        for (var i = 0; i < this.patternMasks.length; ++i) {
            const maskedPattern = applyPatternMask(this.kpuzzle, pattern, this.patternMasks[i]);
            if (maskedPattern.isIdentical(this.solvedPatterns[i])) {
                return true;
            }
        }
        return false;
    }
}

Permutation is done with this:

function permuteArray<T>(array: T[], permutations: number[]): T[] {
    const newArray = [...array];
    for (let i = 0; i < permutations.length; ++i) {
      newArray[i] = array[permutations[i]];
    }
    return newArray;
}

export function forAllOrbits(kpuzzle: KPuzzle, callback: (name: string) => void) {
	for (const orbit of kpuzzle.definition.orbits) {
		callback(orbit.orbitName);
	}
}

type ArrayByOrbit<T> = Record<string, T[]>;
export function permuteOrbitArrays<T>(kpuzzle: KPuzzle, data: ArrayByOrbit<T>, transformation: KTransformation): ArrayByOrbit<T> {
        const inverseTransformation = transformation.invert();
	var outData = Object.assign({}, data);
	forAllOrbits(kpuzzle, (name: string) => {
		const entry = data[name];
		const permutation = inverseTransformation.transformationData[name].permutation;
		outData[name] = permuteArray(entry, permutation);
	});
	return outData;
}