Public
Edited
Apr 23, 2024
1 fork
16 stars
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
function vis(cube) {
const sc = 15; // scale factor = length of each sticker in pixels.
const canvas = DOM.canvas(13 * sc, 10 * sc);
const ctx = canvas.getContext('2d');
// Retina display hacks
scaleCanvas(canvas, ctx)
ctx.translate(sc / 2, sc / 2)
function draw(idx, r, c) {
for (let i = r; i <= r + 2; i++)
for (let j = c; j <= c + 2; j++) {
ctx.fillStyle = color[cube[idx++]];
ctx.fillRect(sc * j, sc * i, sc, sc);
ctx.lineWidth = 2
ctx.strokeRect(sc * j, sc * i, sc, sc)
}
}
// draw the faces
draw( 0, 0, 3) // U
draw( 9, 3, 6) // R
draw(18, 3, 3) // F
draw(27, 6, 3) // D
draw(36, 3, 0) // L
draw(45, 3, 9) // B
return canvas
}
Insert cell
vis(solved_cube)
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
u_move =
[
perm_from_cycle( [ S("U",1), S("U",3), S("U",9), S("U",7) ] ),
perm_from_cycle( [ S("U",2), S("U",6), S("U",8), S("U",4) ] ),
perm_from_cycle( [ S("F",1), S("L",1), S("B",1), S("R",1) ] ),
perm_from_cycle( [ S("F",2), S("L",2), S("B",2), S("R",2) ] ),
perm_from_cycle( [ S("F",3), S("L",3), S("B",3), S("R",3) ] ),
].flat()
Insert cell
Insert cell
apply_move = function(cube, perm) {
let new_cube = [...cube]
for (let x of perm) {
new_cube[x[1]] = cube[x[0]]
}
//perm.forEach( ([src, dst]) => new_cube[dst] = cube[src] );
return new_cube
}
Insert cell
vis(apply_move(solved_cube, u_move))
Insert cell
Insert cell
Insert cell
Insert cell
create_sticker = (pos, dst) => ({pos: pos, dst : dst || pos})
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
create_gmove = (name, axis, angle, predicate) => ({ name, axis, angle, predicate } )
Insert cell
Insert cell
create_gmove("U", new Vec(0, 1, 0), 90, (pos) => pos.y > 0)
Insert cell
Insert cell
apply_sticker = (move, sticker) => (
(move.predicate(sticker.pos)) ? // does the move involve this position?
{...sticker, pos: new Vec().copy(sticker.pos).applyAxisAngle( move.axis, -move.angle / 180 * Math.PI ).round() } : // if so, rotate around axis with angle
sticker ) // else, do nothing
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
gmoves = {
let create_move_set = (base_name, axis, pred) => {
let move1 = create_gmove(base_name, axis, 90, pred)
let move2 = create_gmove(base_name + "2", axis, 180, pred)
let move3 = create_gmove(base_name + "'", axis, 270, pred)
return [move1, move2, move3]
}
let U = create_move_set("U", new Vec(0, 1, 0), (pos) => pos.y > 0)
let u = create_move_set("u", new Vec(0, 1, 0), (pos) => pos.y >= 0)
let D = create_move_set("D", new Vec(0, -1, 0), (pos) => pos.y < 0)
let d = create_move_set("d", new Vec(0, -1, 0), (pos) => pos.y <= 0)

let E = create_move_set("E", new Vec(0, 1, 0), (pos) => pos.y === 0)
let y = create_move_set("y", new Vec(0, 1, 0), () => true)
let L = create_move_set("L", new Vec(-1, 0, 0), (pos) => pos.x < 0)
let R = create_move_set("R", new Vec(1, 0, 0), (pos) => pos.x > 0)
let l = create_move_set("l", new Vec(-1, 0, 0), (pos) => pos.x <= 0)
let r = create_move_set("r", new Vec(1, 0, 0), (pos) => pos.x >= 0)
let M = create_move_set("M", new Vec(-1,0, 0), (pos) => pos.x === 0)
let x = create_move_set("x", new Vec(1, 0, 0), () => true)
let F = create_move_set("F", new Vec(0, 0, 1), (pos) => pos.z > 0)
let B = create_move_set("B", new Vec(0, 0, -1), (pos) => pos.z < 0)
let S = create_move_set("S", new Vec(0, 0, 1), (pos) => pos.z === 0)
let z = create_move_set("z", new Vec(0, 0, 1), () => true)
let gmoves = {};
[U, D, u, d, E, y, L, R, l, r, M, x, F, B, S, z].flat().map(move => gmoves[move.name] = move)
return gmoves
}
Insert cell
apply_gmoves= (gcube, moves) =>
moves.trim().split(/ +/).filter(s => s).map(m => gmoves[m]).reduce( apply_gmove, gcube )
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
draw = (scramble) => vis( gcube_to_fcube( apply_gmoves (solved_gcube, scramble) ) )
Insert cell
draw("M' U M'")
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
convert_gmove_to_fmove(gmoves["U"]).sort().toString() === u_move.sort().toString()
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
vis(apply_fmoves(solved_cube, "M' E2 M E2"))
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
function solve_dfs(solver, cube, solution, depth_remaining) {
if (solver.is_solved(cube)) return solution.trim()
if (depth_remaining === 0) return null
for (const move of solver.moves) {
let result = solve_dfs(
solver,
apply_move(cube, fmoves[move]),
solution + " " + move,
depth_remaining - 1
)
if (result !== null) return result
}
return null
}
Insert cell
scramble_dfs = "U R2 B L D"
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
vis(apply_fmoves(solved_cube, scramble_dfs + " " + solution_dfs))
Insert cell
Insert cell
Insert cell
solve_dfs(fb_simple_solver, apply_fmoves(solved_cube, "L"), [], 3)
Insert cell
Insert cell
function solve_iddfs(solver, cube, depth_limit) {
for (let depth = 0; depth <= depth_limit; depth++) {
let solution = solve_dfs(solver, cube, [], depth)
if (solution !== null) return solution
}
return null
}
Insert cell
Insert cell
solve_iddfs(fb_simple_solver, apply_fmoves(solved_cube, "L"), 3)
Insert cell
Insert cell
Insert cell
md`### Step 7a: Preparations -- reasoning with a masked cube`
Insert cell
Insert cell
ifcube_idx_to_fcube_face = (idx) => "URFDLB"[Math.floor(idx / 9)]
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
mask_cube = (ifcube, mask) =>
[...ifcube].map(idx => mask.includes(idx) ? ifcube_idx_to_fcube_face(idx) : "X").join("")
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
gen_pruning_table = (solved_states, depth, moveset) => {
let pruning_table = {}
let previous_frontier = solved_states
solved_states.forEach(s => pruning_table[s] = 0)
for (let i = 1; i <= depth; i++) {
const frontier = []
for (let state of previous_frontier) {
for (let move of moveset) {
let new_state = apply_move(state, fmoves[move]).join("")
if (!pruning_table.hasOwnProperty(new_state)) {
pruning_table[new_state] = i
frontier.push(new_state)
}
}
}
previous_frontier = [...frontier]
}
return pruning_table
}
Insert cell
fb_pruning_table = gen_pruning_table([mask_cube(solved_ifcube, fb_pieces)], fb_pruning_depth, moveset.htmrwm)
Insert cell
Insert cell
Insert cell
Insert cell
create_solver = (is_solved, candidate_moves, pruning_table, pruning_depth) => ({ pruning_table, pruning_depth, is_solved, moves: candidate_moves })
Insert cell
fb_solver = create_solver(fb_is_solved, moveset.htmrwm, fb_pruning_table, fb_pruning_depth)
Insert cell
Insert cell
function solve_dfs_with_pruning(solver, cube, solution, depth_remaining) {
const cube_str = Array.isArray(cube) ? cube.join("") : cube
if (solver.is_solved(cube_str)) return solution.join(" ")
// Pruning
let lower_bound = solver.pruning_table[cube_str]
if (lower_bound === undefined) lower_bound = solver.pruning_depth + 1
if (lower_bound > depth_remaining)
return null
for (const move of solver.moves) {
if (solution.length && move[0] === solution[solution.length - 1][0])
continue; // aside: never use the same layer in consecutive moves
solution.push(move)
let result = solve_dfs_with_pruning( solver, apply_move(cube, fmoves[move]), solution, depth_remaining - 1)
if (result !== null) return result
solution.pop()
}
return null
}
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
cross_solver = {
let depth = 4
let table = gen_pruning_table([mask_cube(solved_ifcube, pieces.cross)], depth, moveset.htm)
let solver = create_solver(x => table[x] === 0, moveset.htm, table, depth)
return solver
}
Insert cell
lse_solver = {
let depth = 8
let table = gen_pruning_table([mask_cube(solved_ifcube, pieces.lse)], depth, moveset.mu)
let solver = create_solver(x => table[x] === 0, moveset.mu, table, depth)
return solver
}
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
g1_mask = (ifcube) => {
const eo_facelets = [S("U",2),S("U",4),S("U",6),S("U",8),
S("D",2),S("D",4),S("D",6),S("D",8),
S("F",4),S("F",6),S("B",4),S("B",6)]
return [...ifcube].map(idx => eo_facelets.includes(idx) ? "o" : "X").join("")
}
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
g2_mask = (ifcube) => {
const co_pieces = [S("U",1),S("U",3),S("U",7),S("U",9),
S("D",1),S("D",3),S("D",7),S("D",9)]
const eo_ud_pieces = [S("U",2),S("U",4),S("U",6),S("U",8),
S("D",2),S("D",4),S("D",6),S("D",8)]
const eo_e_pieces = [ S("F",4),S("F",6),S("B",4),S("B",6)]
return [...ifcube].map(idx =>
( (eo_ud_pieces.includes(idx) || co_pieces.includes(idx)) ? "x" :
(eo_e_pieces.includes(idx)) ? "y" : "X")).join("")
}
Insert cell
Insert cell
phase2 = {
let g1_moves = ["U", "U'", "U2", "D", "D'", "D2", "L", "L'", "L2", "R", "R'", "R2", "F2", "B2"]
let depth = 5
let g2_pruning_table = gen_pruning_table([g2_mask(solved_ifcube)], depth, g1_moves)
let g2_solver = create_solver( (x) => x === g2_mask(solved_ifcube), g1_moves, g2_pruning_table, depth)
return { moves: g1_moves, limit: 10, pruning_table: g2_pruning_table, solver: g2_solver, mask: g2_mask}
}
Insert cell
Insert cell
Insert cell
g2_solution = solve_iddfs2(phase2.solver, phase2.mask(create_ifcube(g2_scramble)), phase2.limit)
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
g3_corner_table = gen_pruning_table( [g3_corner_mask(solved_ifcube)], 10, ["U2", "D2", "F2", "B2", "L2", "R2"])
Insert cell
Insert cell
Object.keys(g3_corner_table).length === 96
Insert cell
Insert cell
g3_mask = (ifcube) => {
const cp_pieces = [..."UDFBLR"].map(f => [1,3,7,9].map(x => S(f, x))).flat()
const ep_pieces = [..."FBLR"].map(f => [2,4,6,8].map(x => S(f, x))).flat()
const face = (f) => f === "B" ? "F" : f === "L" ? "R" : f;
return [...ifcube].map(idx =>
( cp_pieces.includes(idx) ) ? "URFDLB"[0 | (idx / 9)]:
( ep_pieces.includes(idx)) ? face("URFDLB"[ 0 | (idx / 9)]) : "X").join("")
}
Insert cell
Insert cell
solved_states_viewed_in_g2 = Object.keys(gen_pruning_table( [g3_mask(solved_ifcube)], 10, ["U2", "D2", "F2", "B2", "L2", "R2"]))
// the solved states viewed in g2 are simply those states whose edges are solved and whose corners in the corner table. We can use the same pruning table generation process to generate these 96 states, the difference being we'll include the edge this time.
Insert cell
phase3 = {
let g2_moves = ["U", "U'", "U2", "D", "D'", "D2", "F2", "B2", "L2", "R2"]
let d = 5
let g3_pruning_table = gen_pruning_table(solved_states_viewed_in_g2, d, g2_moves)
let g3_is_solved = (cube) => g3_pruning_table[cube] === 0
// we could also say (cube) => solved_states_viewed_in_g2.includes(cube) but this is equivalent and faster
let g3_solver = create_solver(g3_is_solved, g2_moves, g3_pruning_table, d)
return {moves: g2_moves, limit: 13, pruning_table: g3_pruning_table, solver: g3_solver, mask: g3_mask}
}
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
solve_thistlethwaite = (cube) => {
let solution = []
let phases = [phase1, phase2, phase3, phase4]
for (const phase of phases) {
let phase_solution = solve_iddfs2(phase.solver, phase.mask(cube), phase.limit)
if (phase_solution === null) return solution
solution.push(phase_solution)
cube = apply_fmoves(cube, phase_solution)
}
return solution
}
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
gen_scramble_from_moves = (moves) => () => {
let pprev = -1, prev = -1
let scramble = []
let axis_of_layer = ({"U":1,"D":1,"F":2,"B":2,"L":3,"R":3,"M":3})
for (let i = 0; i < 30; i++) {
let move;
do {
move = moves[0 | (Math.random() * moves.length)];
} while (move[0] === prev[0] || (axis_of_layer[move[0]] === axis_of_layer[prev[0]] && axis_of_layer[move[0]] === axis_of_layer[pprev[0]] ));
scramble.push(move)
pprev = prev
prev = move
}
return scramble.join(" ")
}

Insert cell
Insert cell
Insert cell
Insert cell
footnote = (referencingCellName, number, text) => {
return md`<ol start=\"${number}"><li><a href="#${referencingCellName}">^</a> ${text}</li></ol>`;
}
Insert cell

One platform to build and deploy the best data apps

Experiment and prototype by building visualizations in live JavaScript notebooks. Collaborate with your team and decide which concepts to build out.
Use Observable Framework to build data apps locally. Use data loaders to build in any language or library, including Python, SQL, and R.
Seamlessly deploy to Observable. Test before you ship, use automatic deploy-on-commit, and ensure your projects are always up-to-date.
Learn more