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
}
vis(solved_cube)
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()
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
}
vis(apply_move(solved_cube, u_move))
create_sticker = (pos, dst) => ({pos: pos, dst : dst || pos})
create_gmove = (name, axis, angle, predicate) => ({ name, axis, angle, predicate } )
create_gmove("U", new Vec(0, 1, 0), 90, (pos) => pos.y > 0)
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
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
}
apply_gmoves= (gcube, moves) =>
moves.trim().split(/ +/).filter(s => s).map(m => gmoves[m]).reduce( apply_gmove, gcube )
draw = (scramble) => vis( gcube_to_fcube( apply_gmoves (solved_gcube, scramble) ) )
draw("M' U M'")
convert_gmove_to_fmove(gmoves["U"]).sort().toString() === u_move.sort().toString()
vis(apply_fmoves(solved_cube, "M' E2 M E2"))
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
}
scramble_dfs = "U R2 B L D"
vis(apply_fmoves(solved_cube, scramble_dfs + " " + solution_dfs))
solve_dfs(fb_simple_solver, apply_fmoves(solved_cube, "L"), [], 3)
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
}
solve_iddfs(fb_simple_solver, apply_fmoves(solved_cube, "L"), 3)
md`### Step 7a: Preparations -- reasoning with a masked cube`
ifcube_idx_to_fcube_face = (idx) => "URFDLB"[Math.floor(idx / 9)]
mask_cube = (ifcube, mask) =>
[...ifcube].map(idx => mask.includes(idx) ? ifcube_idx_to_fcube_face(idx) : "X").join("")
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
}
fb_pruning_table = gen_pruning_table([mask_cube(solved_ifcube, fb_pieces)], fb_pruning_depth, moveset.htmrwm)
create_solver = (is_solved, candidate_moves, pruning_table, pruning_depth) => ({ pruning_table, pruning_depth, is_solved, moves: candidate_moves })
fb_solver = create_solver(fb_is_solved, moveset.htmrwm, fb_pruning_table, fb_pruning_depth)
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
}
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
}
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
}
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("")
}
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("")
}
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}
}
g2_solution = solve_iddfs2(phase2.solver, phase2.mask(create_ifcube(g2_scramble)), phase2.limit)
g3_corner_table = gen_pruning_table( [g3_corner_mask(solved_ifcube)], 10, ["U2", "D2", "F2", "B2", "L2", "R2"])
Object.keys(g3_corner_table).length === 96
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("")
}
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.
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}
}
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
}
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(" ")
}
footnote = (referencingCellName, number, text) => {
return md`<ol start=\"${number}"><li><a href="#${referencingCellName}">^</a> ${text}</li></ol>`;
}
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.