Solve a Rubik's cube
Solve a Rubik's cube is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
- Task
Create a program that is capable of solving a Rubik's Cube as efficiently as possible.
Other names are:
- Magic Cube
- Speed Cube
- Puzzle Cube
- Cube
You may use any sort of input you wish.
Go
As in the case of the Kotlin entry, this is a translation of the C++ competition code by Stefan Pochmann.
On the same machine, typical timings for the 100 line dataset are just over 200 milliseconds which is significantly slower than both the Kotlin and C++ code but still acceptable.
The relative slowness may be partly due to maps in Go not being able to accept reference types (such as slices) as a key because they don't support the '==' operator which tests for structural equality. I've therefore had to copy each slice returned by the 'id' function into a forty element array (a value type in Go) and use that as a key instead.
For the single line example, typical timings are around 240 milliseconds which is much faster than Kotlin due, no doubt, to JVM warm up time.
/**********************************************************************
*
* A cube 'state' is an int array with 40 entries, the first 20
* are a permutation of {0,...,19} and describe which cubie is at
* a certain position (regarding the input ordering). The first
* twelve are for edges, the last eight for corners.
*
* The last 20 entries are for the orientations, each describing
* how often the cubie at a certain position has been turned
* counterclockwise away from the correct orientation. Again the
* first twelve are edges, the last eight are corners. The values
* are 0 or 1 for edges and 0, 1 or 2 for corners.
*
**********************************************************************/
package main
import (
"bufio"
"fmt"
"log"
"os"
"strings"
"time"
)
type ai = [40]int
var applicableMoves = [5]int{0, 262143, 259263, 74943, 74898}
var phase = 0
var affectedCubies = [6][8]int{
{0, 1, 2, 3, 0, 1, 2, 3}, // U
{4, 7, 6, 5, 4, 5, 6, 7}, // D
{0, 9, 4, 8, 0, 3, 5, 4}, // F
{2, 10, 6, 11, 2, 1, 7, 6}, // B
{3, 11, 7, 9, 3, 2, 6, 5}, // L
{1, 8, 5, 10, 1, 0, 4, 7}, // R
}
func btoi(b bool) int {
if b {
return 1
}
return 0
}
func sliceToAi(s []int) ai {
var a ai
copy(a[:], s)
for i := len(s); i < 40; i++ {
a[i] = -1
}
return a
}
func applyMove(move int, state ai) ai {
turns := move%3 + 1
face := move / 3
for turns != 0 {
turns--
oldState := state
for i := 0; i < 8; i++ {
isCorner := btoi(i > 3)
target := affectedCubies[face][i] + isCorner*12
temp := i + 1
if (i & 3) == 3 {
temp = i - 3
}
killer := affectedCubies[face][temp] + isCorner*12
var orientationDelta int
switch {
case i < 4:
orientationDelta = btoi(face > 1 && face < 4)
case face < 2:
orientationDelta = 0
default:
orientationDelta = 2 - (i & 1)
}
state[target] = oldState[killer]
state[target+20] = oldState[killer+20] + orientationDelta
if turns == 0 {
state[target+20] %= 2 + isCorner
}
}
}
return state
}
func inverse(move int) int {
return move + 2 - 2*(move%3)
}
func id(state ai) ai {
//--- Phase 1: Edge orientations.
if phase < 2 {
return sliceToAi(state[20:32])
}
//-- Phase 2: Corner orientations, E slice edges.
if phase < 3 {
result := state[31:40]
for e := uint(0); e < 12; e++ {
result[0] |= (state[e] / 8) << e
}
return sliceToAi(result)
}
//--- Phase 3: Edge slices M and S, corner tetrads, overall parity.
if phase < 4 {
result := []int{0, 0, 0}
for e := uint(0); e < 12; e++ {
temp := 2
if state[e] <= 7 {
temp = state[e] & 1
}
result[0] |= temp << (2 * e)
}
for c := uint(0); c < 8; c++ {
result[1] |= ((state[c+12] - 12) & 5) << (3 * c)
}
for i := 12; i < 19; i++ {
for j := i + 1; j < 20; j++ {
result[2] ^= btoi(state[i] > state[j])
}
}
return sliceToAi(result)
}
//--- Phase 4: The rest.
return state
}
func main() {
startTime := time.Now()
aggregateMoves := 0
//--- Define the goal.
goal := [20]string{
"UF", "UR", "UB", "UL", "DF", "DR", "DB", "DL", "FR", "FL", "BR", "BL",
"UFR", "URB", "UBL", "ULF", "DRF", "DFL", "DLB", "DBR",
}
//--- Load dataset (file name should be passed as a command line argument).
if len(os.Args) != 2 {
log.Fatal("the file name should be passed as a command line argument")
}
file, err := os.Open(os.Args[1])
if err != nil {
log.Fatal(err)
}
defer file.Close()
var lineCount = 0
scanner := bufio.NewScanner(file)
for scanner.Scan() {
line := scanner.Text()
inputs := strings.Fields(line)
lineCount++
phase = 0
totalMoves := 0
//--- Prepare current (start) and goal state.
var currentState ai
var goalState ai
for i := 0; i < 20; i++ {
//--- Goal state.
goalState[i] = i
//--- Current (start) state.
cubie := inputs[i]
for {
idx := -1
for c := 0; c < len(goal); c++ {
if goal[c] == cubie {
idx = c
break
}
}
if idx >= 0 {
currentState[i] = idx
} else {
currentState[i] = 20
}
if currentState[i] != 20 {
break
}
cubie = cubie[1:] + cubie[:1]
currentState[i+20]++
}
}
//--- Dance the funky Thistlethwaite..
nextPhase:
for phase++; phase < 5; phase++ {
//--- Compute ids for current and goal state, skip phase if equal.
currentId := id(currentState)
goalId := id(goalState)
if currentId == goalId {
continue
}
//--- Initialize the BFS queue.
q := []ai{currentState, goalState}
//--- Initialize the BFS tables.
predecessor := make(map[ai]ai)
direction := make(map[ai]int)
lastMove := make(map[ai]int)
direction[currentId] = 1
direction[goalId] = 2
//--- Dance the funky bidirectional BFS...
for {
//--- Get state from queue, compute its ID and get its direction.
oldState := q[0]
q = q[1:]
oldId := id(oldState)
oldDir := direction[oldId]
//--- Apply all applicable moves to it and handle the new state.
for move := 0; move < 18; move++ {
if (applicableMoves[phase] & (1 << uint(move))) != 0 {
//--- Apply the move.
newState := applyMove(move, oldState)
newId := id(newState)
newDir := direction[newId]
//--- Have we seen this state (id) from the other direction already?
//--- I.e. have we found a connection?
if (newDir != 0) && (newDir != oldDir) {
//--- Make oldId represent the forwards
//--- and newId the backwards search state.
if oldDir > 1 {
newId, oldId = oldId, newId
move = inverse(move)
}
//--- Reconstruct the connecting algorithm.
algorithm := []int{move}
for oldId != currentId {
algorithm = append(algorithm, 0)
copy(algorithm[1:], algorithm[0:])
algorithm[0] = lastMove[oldId]
oldId = predecessor[oldId]
}
for newId != goalId {
algorithm = append(algorithm, inverse(lastMove[newId]))
newId = predecessor[newId]
}
//--- Print and apply the algorithm.
for i := 0; i < len(algorithm); i++ {
fmt.Printf("%c", "UDFBLR"[algorithm[i]/3])
fmt.Print(algorithm[i]%3 + 1)
fmt.Print(" ")
totalMoves++
currentState = applyMove(algorithm[i], currentState)
}
//--- Jump to the next phase.
continue nextPhase
}
//--- If we've never seen this state (id) before, visit it.
if newDir == 0 {
q = append(q, newState)
direction[newId] = oldDir
lastMove[newId] = move
predecessor[newId] = oldId
}
}
}
}
}
fmt.Printf(" (moves %d)\n", totalMoves)
aggregateMoves += totalMoves
}
if err := scanner.Err(); err != nil {
log.Fatal(err)
}
endTime := time.Now()
elapsedTime := endTime.Sub(startTime).Nanoseconds() / 1000000
fmt.Println("\nAverage number of moves =", float64(aggregateMoves)/float64(lineCount))
fmt.Println("\nAverage time =", elapsedTime/int64(lineCount), "milliseconds")
}
- Output:
Same as Kotlin entry apart, of course, from the timings.
JavaScript
#!/usr/bin/env node
/**********************************************************************
*
* A cube 'state' is an array <number> with 40 entries, the first 20
* are a permutation of {0,...,19} and describe which cubie is at
* a certain position (regarding the input ordering). The first
* twelve are for edges, the last eight for corners.
*
* The last 20 entries are for the orientations, each describing
* how often the cubie at a certain position has been turned
* counterclockwise away from the correct orientation. Again the
* first twelve are edges, the last eight are corners. The values
* are 0 or 1 for edges and 0, 1 or 2 for corners.
*
**********************************************************************/
const fs = require('fs');
// Helper to serialize array keys for Map usage
const serialize = (arr) => arr.join(',');
// Helper for boolean to int conversion (less verbose)
const boolToInt = (b) => b ? 1 : 0;
// Note: AI (ArrayList<Int>) is just Array<number> in JS
const applicableMoves = [0, 262143, 259263, 74943, 74898];
const affectedCubies = [
[0, 1, 2, 3, 0, 1, 2, 3], // U
[4, 7, 6, 5, 4, 5, 6, 7], // D
[0, 9, 4, 8, 0, 3, 5, 4], // F
[2, 10, 6, 11, 2, 1, 7, 6], // B
[3, 11, 7, 9, 3, 2, 6, 5], // L
[1, 8, 5, 10, 1, 0, 4, 7] // R
];
function applyMove(move, state) {
const state2 = [...state]; // Create a copy to avoid mutating original 'state'.
let turns = move % 3 + 1;
const face = Math.floor(move / 3);
while (turns-- !== 0) {
const oldState2 = [...state2]; // Copy state for this turn application
for (let i = 0; i < 8; i++) {
const isCorner = boolToInt(i > 3);
const target = affectedCubies[face][i] + isCorner * 12;
const temp = (i & 3) === 3 ? i - 3 : i + 1; // Equivalent to Kotlin's logic
const killer = affectedCubies[face][temp] + isCorner * 12;
let orientationDelta = 0;
if (i < 4) { // Edge
orientationDelta = boolToInt(face >= 2 && face <= 3); // F or B face affects edge orientation
} else if (face >= 2) { // Corner on F, B, L, R face
orientationDelta = 2 - (i & 1); // Corners on F/B/L/R need orientation change based on position
} // else: Corner on U/D face -> orientationDelta = 0
state2[target] = oldState2[killer];
state2[target + 20] = oldState2[killer + 20] + orientationDelta;
if (turns === 0) { // Apply modulo only on the final state of the move
state2[target + 20] %= (2 + isCorner); // Mod 2 for edges, Mod 3 for corners
}
}
}
return state2;
}
function inverse(move) {
return move + 2 - 2 * (move % 3);
}
let phase = 0; // Global phase variable
function id(state) {
//--- Phase 1: Edge orientations.
if (phase < 2) {
// Slice creates a new array [20, 32) -> indices 20 to 31
return state.slice(20, 32);
}
//-- Phase 2: Corner orientations, E slice edges.
if (phase < 3) {
// Get corner orientations (indices 32 to 39)
const result = state.slice(32, 40); // Corner orientations [0..7]
// Add space for the E slice edge info
result.unshift(0); // result now has 9 elements, result[0] holds E slice info
for (let e = 0; e < 12; e++) {
// Check if edge 'e' is in the E slice (pieces 8, 9, 10, 11)
// state[e] contains the *piece number* at position 'e'
// Math.floor(state[e] / 8) is 1 if piece is 8,9,10,11, otherwise 0
result[0] |= Math.floor(state[e] / 8) << e;
}
return result; // Array of 9 numbers
}
//--- Phase 3: Edge slices M and S, corner tetrads, overall parity.
if (phase < 4) {
const result = [0, 0, 0]; // Initialize with 3 zeros
// M and S slices edge info
for (let e = 0; e < 12; e++) {
// state[e] > 7 means edge piece is 8,9,10,11 (E slice) -> value 2
// else check if piece is odd (1,3,5,7) -> value 1
// else piece is even (0,2,4,6) -> value 0
// Map {0,2,4,6} -> 0, {1,3,5,7} -> 1, {8,9,10,11} -> 2
const sliceMembership = (state[e] > 7) ? 2 : (state[e] & 1);
result[0] |= sliceMembership << (2 * e); // Store 2 bits per edge
}
// Corner tetrads info
for (let c = 0; c < 8; c++) {
// (state[c + 12] - 12) gives the corner piece number (0-7) relative to goal state
// & 5 (binary 101) extracts bits 0 and 2. This likely encodes tetrad membership.
const cornerInfo = (state[c + 12] - 12) & 5;
result[1] |= cornerInfo << (3 * c); // Store 3 bits per corner
}
// Overall parity (permutation parity of corners + edges)
for (let i = 12; i < 20; i++) { // Check corners first (12-19)
for (let j = i + 1; j < 20; j++) {
result[2] ^= boolToInt(state[i] > state[j]);
}
}
for (let i = 0; i < 12; i++) { // Then check edges (0-11) - Note: Kotlin code only checked corners 12-19? Let's stick to Kotlin version.
// The Kotlin code only iterates i=12..18 and j=i+1..19. This calculates corner permutation parity.
// Let's match Kotlin exactly:
// result[2] = 0; // Re-initialize if we were adding edge parity
// for (let i = 12; i < 20; i++) { // Corrected loop bounds based on Kotlin code
// for (let j = i + 1; j < 20; j++) {
// result[2] ^= boolToInt(state[i] > state[j]);
// }
// }
// Wait, the Kotlin code *did* iterate 12..19. i <= 18 means i goes up to 18. j <= 19 means j goes up to 19.
// The original nested loop `for (i in 12..18) { for (j in (i + 1)..19) {` is correct for checking pairs (12,13)..(12,19), (13,14)..(13,19) ... (18,19)
// So the JS translation above `for (let i = 12; i < 20; i++)` was correct. Let's keep it.
}
// Thistlethwaite doesn't usually calculate full parity until phase 4, maybe this `result[2]` captures something else or just corner parity.
// Based on common Thistlethwaite implementations, this often represents combined M/S slice + corner parity.
return result; // Array of 3 numbers
}
//--- Phase 4: The rest. (ID is the full state)
return state; // Return the full state array (40 numbers)
}
function main() {
const startTime = Date.now();
let aggregateMoves = 0;
let lineCount = 0;
//--- Define the goal cubie names.
const goal = [
"UF", "UR", "UB", "UL", "DF", "DR", "DB", "DL", "FR", "FL", "BR", "BL",
"UFR", "URB", "UBL", "ULF", "DRF", "DFL", "DLB", "DBR"
];
//--- Load dataset (file name should be passed as a command line argument).
const filename = process.argv[2];
if (!filename) {
console.error("Usage: node script.js <filename>");
process.exit(1);
}
let fileContent;
try {
fileContent = fs.readFileSync(filename, 'utf8');
} catch (err) {
console.error(`Error reading file: ${filename}`, err);
process.exit(1);
}
const lines = fileContent.split('\n').filter(line => line.trim() !== ''); // Split lines and remove empty ones
lines.forEach(line => {
const inputs = line.trim().split(/\s+/); // Split by whitespace
if (inputs.length < 20) {
console.warn(`Skipping malformed line: ${line}`);
return; // Skip lines that don't have enough cubies
}
lineCount++;
phase = 0; // Reset phase for each puzzle
let totalMoves = 0;
//--- Prepare current (start) and goal state.
let currentState = Array(40).fill(0);
const goalState = Array(40).fill(0);
for (let i = 0; i < 20; i++) {
//--- Goal state.
goalState[i] = i; // Piece 'i' is at position 'i', orientation 0
//--- Current (start) state.
let cubie = inputs[i];
let orientation = 0;
let positionIndex = -1;
// Find the piece and its orientation by rotating the input string
for (let tries = 0; tries < 3; tries++) { // Max 3 rotations needed
positionIndex = goal.indexOf(cubie);
if (positionIndex !== -1) {
break; // Found the piece
}
// Rotate cubie string (e.g., "ULF" -> "LFU" -> "FUL")
cubie = cubie.substring(1) + cubie[0];
orientation++;
}
if (positionIndex === -1) {
console.error(`Error: Could not find cubie '${inputs[i]}' in goal definition.`);
// Handle error appropriately, maybe skip this line or exit
currentState[i] = 20; // Mark as invalid/unknown?
} else {
currentState[i] = positionIndex; // Set permutation
currentState[i + 20] = orientation; // Set orientation
}
}
//--- Dance the funky Thistlethwaite...
nextPhase: // Label for continuing outer loop
while (++phase < 5) {
//--- Compute ids for current and goal state, skip phase if equal.
const currentIdArr = id(currentState);
const goalIdArr = id(goalState);
// Serialize IDs for comparison and map keys
const currentId = serialize(currentIdArr);
const goalId = serialize(goalIdArr);
if (currentId === goalId) {
// console.log(`Phase ${phase}: Already solved.`); // Optional debug log
continue nextPhase;
}
//--- Initialize the BFS queue.
// Queue stores full states [stateArray]
const q = [currentState, goalState];
//--- Initialize the BFS tables. Keys are *serialized* IDs (strings).
// Map<string, string> : serializedId -> serializedPredecessorId
const predecessor = new Map();
// Map<string, number> : serializedId -> direction (1=forward, 2=backward)
const direction = new Map();
// Map<string, number> : serializedId -> move leading to this state
const lastMove = new Map();
direction.set(currentId, 1);
direction.set(goalId, 2);
// Predecessor and lastMove for starting points are not needed
//--- Dance the funky bidirectional BFS...
searchLoop: // Label for breaking inner search loop
while (q.length > 0) {
//--- Get state from queue, compute its ID and get its direction.
const oldState = q.shift(); // Dequeue
if (!oldState) break; // Should not happen if q.length > 0, but safety check
const oldIdArr = id(oldState);
const oldId = serialize(oldIdArr);
// We know the direction exists because we only add states with directions set
const oldDir = direction.get(oldId);
//--- Apply all applicable moves to it and handle the new state.
for (let move = 0; move < 18; move++) {
// Check if the move is allowed in this phase
if ((applicableMoves[phase] & (1 << move)) !== 0) {
//--- Apply the move.
const newState = applyMove(move, oldState);
const newIdArr = id(newState);
const newId = serialize(newIdArr);
const newDir = direction.get(newId); // Check if seen before
//--- Have we seen this state (id) from the other direction already?
//--- I.e. have we found a connection?
if (newDir !== undefined && newDir !== oldDir) {
let meetingMove = move;
let forwardId = oldId;
let backwardId = newId;
//--- Make oldId represent the forwards (dir=1)
//--- and newId the backwards (dir=2) search state.
if (oldDir === 2) { // oldState came from the goal search
forwardId = newId;
backwardId = oldId;
meetingMove = inverse(move); // The move needs to be inverted
}
//--- Reconstruct the connecting algorithm.
const algorithm = [];
// Trace back from the meeting point on the forward path
let currentTraceId = forwardId;
while (currentTraceId !== currentId) {
const moveApplied = lastMove.get(currentTraceId);
if (moveApplied === undefined) {
console.error("Error reconstructing forward path! Missing move.");
break searchLoop; // Abort search for this puzzle
}
algorithm.unshift(moveApplied); // Add to beginning
const predId = predecessor.get(currentTraceId);
if (predId === undefined) {
console.error("Error reconstructing forward path! Missing predecessor.");
break searchLoop; // Abort search for this puzzle
}
currentTraceId = predId;
}
// Add the meeting move
algorithm.push(meetingMove);
// Trace back from the meeting point on the backward path (inverting moves)
currentTraceId = backwardId;
while (currentTraceId !== goalId) {
const moveApplied = lastMove.get(currentTraceId);
if (moveApplied === undefined) {
console.error("Error reconstructing backward path! Missing move.");
break searchLoop; // Abort search for this puzzle
}
algorithm.push(inverse(moveApplied)); // Add inverted move to end
const predId = predecessor.get(currentTraceId);
if (predId === undefined) {
console.error("Error reconstructing backward path! Missing predecessor.");
break searchLoop; // Abort search for this puzzle
}
currentTraceId = predId;
}
//--- Print and apply the algorithm.
for (let i = 0; i < algorithm.length; i++) {
const currentMove = algorithm[i];
process.stdout.write("UDFBLR"[Math.floor(currentMove / 3)]);
process.stdout.write((currentMove % 3 + 1).toString());
process.stdout.write(" ");
totalMoves++;
currentState = applyMove(currentMove, currentState);
}
//--- Jump to the next phase.
continue nextPhase; // Continue the outer 'phase' loop
}
//--- If we've never seen this state (id) before, visit it.
if (newDir === undefined) {
q.push(newState); // Enqueue the full state
direction.set(newId, oldDir);
lastMove.set(newId, move);
predecessor.set(newId, oldId); // Store the *serialized* predecessor ID
}
} // end if applicable move
} // end for move
} // end while q.length > 0 (BFS loop)
// If the queue becomes empty and we haven't found a solution, something is wrong.
console.error(`Phase ${phase} BFS failed to find a connection for line: ${line}`);
break; // Break out of phase loop for this puzzle
} // end while phase < 5
console.log(` (moves ${totalMoves})`);
aggregateMoves += totalMoves;
}); // end forEach line
const elapsedTime = Date.now() - startTime;
if (lineCount > 0) {
console.log(`\nAverage number of moves = ${aggregateMoves / lineCount}`);
console.log(`Average time = ${elapsedTime / lineCount} milliseconds`);
} else {
console.log("\nNo valid lines processed.");
}
}
// Run the main function
main();
Julia
#=**********************************************************************
*
* A cube 'state' is a vector<int> with 40 entries, the first 20
* are a permutation of {0,...,19} and describe which cubie is at
* a certain position (regarding the input ordering). The first
* twelve are for edges, the last eight for corners.
*
* The last 20 entries are for the orientations, each describing
* how often the cubie at a certain position has been turned
* counterclockwise away from the correct orientation. Again the
* first twelve are edges, the last eight are corners. The values
* are 0 or 1 for edges and 0, 1 or 2 for corners.
*
*********************************************************************=#
const applicablemoves = [0, 262143, 259263, 74943, 74898]
const affectedcubies = [
0 1 2 3 0 1 2 3; # U
4 7 6 5 4 5 6 7; # D
0 9 4 8 0 3 5 4; # F
2 10 6 11 2 1 7 6; # B
3 11 7 9 3 2 6 5; # L
1 8 5 10 1 0 4 7] # R
function applymove(move, state)
state2, oldstate2 = deepcopy(state), zeros(Int, length(state))
face, turns = divrem(move, 3) .+ 1
while turns != 0
turns -= 1
oldstate2 .= state2
for i in 1:8
iscorner = i > 4
target = affectedcubies[face, i] + iscorner * 12 + 1
temp = ((i-1) & 3) == 3 ? i - 3 : i + 1
killer = affectedcubies[face, temp] + iscorner * 12 + 1
orientationdelta = i < 5 ? Int(face in [3, 4]) : face < 3 ? 0 : 2 - ((i-1) & 1)
state2[target] = oldstate2[killer]
state2[target + 20] = oldstate2[killer + 20] + orientationdelta
(turns == 0) && (state2[target + 20] %= 2 + iscorner)
end
end
return state2
end
inverse(move) = move + 2 - 2 * (move % 3)
function id(state::Vector{Int}, phase::Int)
#--- Phase 1: Edge orientations.
if phase < 2
return state[21:32]
elseif phase < 3
#-- Phase 2: Corner orientations, E slice edges.
result = state[32:40]
for e in 0:11
result[1] |= ((state[e + 1] ÷ 8) << e)
end
return result
elseif phase < 4
#--- Phase 3: Edge slices M and S, corner tetrads, overall parity.
result = zeros(Int, 3)
for e in 0:11
result[1] |= state[e + 1] > 7 ? 2 : (state[e + 1] & 1) << (2 * e)
end
for c in 0:7
result[2] |= ((state[c + 12 + 1] - 12) & 5) << (3 * c)
end
for i in 13:19, j in i+1:20
result[3] ⊻= Int(state[i] > state[j])
end
return result
end
#--- Phase 4: The rest.
return state
end
function pochmann(fname)
starttime = time_ns() ÷ 1000000
aggregatemoves = 0
#--- Define the goal.
goal = ["UF", "UR", "UB", "UL", "DF", "DR", "DB", "DL", "FR", "FL", "BR", "BL",
"UFR", "URB", "UBL", "ULF", "DRF", "DFL", "DLB", "DBR"]
#--- Load dataset (file name should be passed as a command line argument).
file = read(fname, String)
linecount = 0
for line in split(strip(file), "\n")
inputs = split(line)
linecount += 1
totalmoves = 0
#--- Prepare current (start) and goal state.
state, goalstate, phase = zeros(Int, 40), zeros(Int, 40), 0
for i in 1:20
#--- Goal state.
goalstate[i] = i - 1
#--- Current (start) state.
cubie = inputs[i]
while true
state[i] = something(findfirst(x -> x .== cubie, goal), 21) - 1
(state[i] != 20) && break
cubie = cubie[2:end] * cubie[1]
state[i + 20] += 1
end
end
#--- Dance the funky Thistlethwaite...
@label nextphase # preserves phase value, but restarts while loop
while (phase += 1) < 5
#--- Compute ids for current and goal state, skip phase if equal.
currentid = id(state, phase)
goalid = id(goalstate, phase)
currentid == goalid && continue
#--- Initialize the BFS queue.
q = [state, goalstate]
#--- Initialize the BFS tables.
predecessor = Dict{Vector{Int}, Vector{Int}}()
direction = Dict{Vector{Int}, Int}()
lastmove = Dict{Vector{Int}, Int}()
direction[currentid] = 1
direction[goalid] = 2
#--- Dance the funky bidirectional BFS...
while true
#--- Get state from queue, compute its ID and get its direction.
oldstate = popfirst!(q)
oldid = id(oldstate, phase)
olddir = get!(direction, oldid, 0)
#--- Apply all applicable moves to it and handle the new state.
for move in 0:17
if applicablemoves[phase + 1] & (1 << UInt(move)) != 0
#--- Apply the move.
newstate = applymove(move, oldstate)
newid = id(newstate, phase)
newdir = get!(direction, newid, 0)
#--- Have we seen this state (id) from the other direction already?
#--- I.e. have we found a connection?
if (newdir != 0) && (newdir != olddir)
#--- Make oldid represent the forwards
#--- and newid the backwards search state.
if olddir > 1
newid, oldid = oldid, newid
move = inverse(move)
end
#--- Reconstruct the connecting algorithm.
algorithm = [move]
while oldid != currentid
pushfirst!(algorithm, get(lastmove, oldid, 0))
oldid = get!(predecessor, oldid, Int[])
end
while newid != goalid
push!(algorithm, inverse(get!(lastmove, newid, 0)))
newid = get!(predecessor, newid, Int[])
end
#--- Print and apply the algorithm.
for i in 1:length(algorithm)
print("UDFBLR"[algorithm[i] ÷ 3 + 1])
print(algorithm[i] % 3 + 1)
print(" ")
totalmoves += 1
state = applymove(algorithm[i], state)
end
#--- Jump to the next phase.
@goto nextphase
end
#--- If we've never seen this state (id) before, visit it.
if newdir == 0
push!(q, newstate)
direction[newid] = olddir
lastmove[newid] = move
predecessor[newid] = oldid
end
end
move += 1
end
end
end
println(" (moves $totalmoves)")
aggregatemoves += totalmoves
end
elapsedtime = time_ns() ÷ 1000000 - starttime
println("\nAverage number of moves = $(aggregatemoves / linecount)")
println("\nAverage time = $(elapsedtime / linecount) milliseconds")
end
pochmann("rubikdata.txt")
- Output:
Using the 100-line database:
(moves 0) U1 U2 (moves 2) U2 (moves 1) U1 (moves 1) F1 F2 (moves 2) F2 (moves 1) F1 (moves 1) R1 R2 (moves 2) R2 (moves 1) R1 (moves 1) D1 D2 (moves 2) D2 (moves 1) D1 (moves 1) B1 B2 (moves 2) B2 (moves 1) B1 (moves 1) L1 L2 (moves 2) L2 (moves 1) L1 (moves 1) U2 B3 B2 (moves 3) L2 U3 (moves 2) R1 U1 (moves 2) D3 L3 (moves 2) D3 L2 (moves 2) D2 F3 F2 (moves 3) R2 F3 (moves 2) R1 F2 F2 R2 F2 (moves 5) D1 D2 U2 (moves 3) L1 B2 F2 L2 R2 B2 F2 (moves 7) L1 L2 D3 (moves 3) D1 F2 (moves 2) U2 R3 (moves 2) L1 L2 U3 (moves 3) U1 R2 (moves 2) U1 R3 (moves 2) F1 U2 (moves 2) U2 R3 R2 (moves 3) F2 D1 F3 (moves 3) F2 D3 D2 U2 (moves 4) L3 D2 R3 (moves 3) D2 R3 R2 D3 (moves 4) F1 R1 B2 B2 R2 B2 (moves 6) L1 B2 F2 (moves 3) U1 R2 B3 B2 (moves 4) R2 F3 R2 (moves 3) L2 D3 R3 R2 (moves 4) L2 F3 L2 L2 F2 L2 (moves 6) F1 R1 B3 D3 B2 D3 L3 U2 L3 U2 L2 U2 L2 U3 R2 U1 F2 L2 U2 B2 L2 F2 U2 L2 U2 F2 D2 F2 U2 (moves 29) L1 L2 U3 R2 (moves 4) L3 B3 B2 R3 R2 (moves 5) B2 U1 R3 R2 (moves 4) L3 B3 L2 (moves 3) D1 B2 L3 L2 (moves 4) B1 B2 R3 F2 F2 R2 F2 (moves 7) D1 F3 D1 D2 (moves 4) R1 B3 D1 R2 F3 L1 U2 F2 D3 B2 D1 L3 U1 F2 R2 U1 L2 U1 F2 U2 R2 U3 F2 U3 F2 D2 F2 L2 F2 L2 F2 U2 F2 D2 L2 (moves 35) F1 R1 U3 D1 B3 U3 D2 L3 B2 R1 F2 D3 L3 U2 R2 D1 R2 B2 U2 L2 U3 U2 F2 U2 L2 B2 R2 D2 R2 D2 B2 L2 F2 U2 (moves 34) U1 R1 F3 L1 R2 U3 L1 D2 F2 U3 L3 L2 U1 F2 D3 F2 F2 U2 D2 L2 U2 F2 R2 F2 D2 R2 U2 (moves 27) R1 D3 R3 F3 R1 D3 F2 U1 R3 D2 U1 R3 F2 U1 L2 U3 F2 U1 B2 D2 L2 D3 F2 F2 U2 F2 D2 L2 U2 L2 F2 L2 U2 R2 (moves 34) D2 R1 B1 L1 F3 U2 D3 L2 R1 D3 B2 U1 F2 L3 F2 U3 B2 U3 B2 L2 U3 B2 U3 F2 U2 F2 U2 L2 F2 R2 B2 D2 L2 D2 F2 (moves 35) B3 U2 L1 F3 F2 U1 R3 D1 F2 R3 D3 B2 R3 B2 U1 F2 U3 R2 U1 R2 U3 R2 L2 F2 U2 R2 F2 D2 R2 B2 U2 R2 B2 (moves 33) L1 F3 L2 D3 U1 F3 L1 B2 R1 U1 D1 B2 R3 U1 L2 U1 B2 U1 F2 U3 L2 D1 F2 U3 F2 U2 D2 R2 U2 L2 F2 R2 U2 F2 R2 (moves 35) F1 R3 U2 F3 B2 U1 L1 U1 R3 B2 U1 R3 R2 U3 L2 U1 B2 U2 R2 U3 L2 U3 F2 L2 U2 F2 U2 B2 L2 D2 L2 F2 L2 F2 U2 (moves 35) U2 D3 B3 U1 L2 D1 R1 U3 L3 D2 U1 R3 U3 B2 D3 R2 F2 U3 F2 U3 U2 B2 D2 B2 L2 F2 R2 D2 R2 (moves 29) D2 L3 U3 F3 B2 U3 L1 U2 R3 D2 L3 U2 L2 U3 R2 B2 D3 F2 R2 U3 U2 L2 U2 F2 U2 D2 R2 F2 U2 B2 D2 (moves 31) F1 L1 U1 L1 B3 U3 L1 F2 L1 B2 F2 U3 L3 F2 D3 B2 D3 R2 U1 F2 U3 L2 U3 U2 F2 D2 B2 U2 F2 R2 F2 L2 (moves 32) B1 L1 U3 F3 B2 U1 L3 B2 R3 L3 U3 L3 D2 B2 D3 F2 L2 U2 R2 U3 F2 U3 F2 L2 U2 B2 L2 U2 B2 F2 R2 U2 F2 (moves 33) F2 L3 F1 D3 B3 B2 U3 R1 D3 U3 L3 L2 R2 U3 B2 D1 B2 U3 R2 U3 F2 L2 F2 L2 U2 F2 B2 R2 B2 L2 (moves 30) D3 F3 U1 B2 U3 L1 D1 R3 U3 F2 L3 U1 F2 U2 L2 U3 L2 B2 R2 L2 D1 F2 F2 L2 U2 F2 L2 U2 R2 D2 B2 R2 L2 (moves 33) F2 R3 U2 F3 U2 L2 B2 D1 F2 R3 B2 D1 L3 D2 R2 B2 D1 R2 B2 U1 L2 B2 R2 B2 R2 D2 L2 D2 F2 L2 B2 L2 F2 (moves 33) U1 R3 F3 D3 R3 B2 L3 D1 F2 U1 R3 L2 U1 B2 D1 L2 U3 R2 U1 L2 U3 F2 U3 F2 U2 B2 L2 D2 L2 U2 R2 F2 (moves 32) F1 R1 F1 D3 B3 F3 U1 R2 F2 U1 L3 U1 F2 U2 R2 U1 R2 U3 L2 U3 D2 L2 F2 L2 F2 U2 B2 U2 L2 F2 (moves 30) F3 R3 L2 B3 U1 B2 U1 F2 U2 B2 R3 D2 L3 B2 U1 F2 U3 L2 U1 B2 D3 L2 U1 L2 U2 L2 D2 R2 F2 D2 F2 U2 R2 U2 (moves 34) D1 B3 D2 L1 F3 U3 F2 D2 L3 F2 L3 D3 L3 D1 L2 B2 U3 R2 U1 R2 U3 L2 U3 L2 D2 R2 D2 F2 R2 F2 L2 D2 U2 F2 U2 (moves 35) U1 B1 D1 R3 F3 U1 B2 R1 U3 L1 D3 B2 U1 R3 U2 F2 L2 U3 R2 U1 B2 D3 B2 U1 L2 F2 U2 D2 L2 U2 B2 R2 B2 L2 D2 L2 (moves 36) U3 F1 L1 F3 B2 U1 B2 R2 D1 R1 U2 L3 U1 F2 R2 U3 L2 U3 B2 F2 R2 F2 B2 U2 R2 F2 L2 U2 L2 (moves 29) U1 B2 L1 B3 F3 U1 F2 B2 R2 D3 R3 U3 L3 B2 U1 F2 U3 F2 U3 L2 U2 F2 R2 B2 R2 U2 F2 U2 F2 U2 F2 (moves 31) U1 B1 U3 D1 F3 U2 D3 R3 D1 U1 L1 F2 L3 D2 L2 U1 F2 B2 R2 U3 F2 U1 L2 U2 R2 F2 D2 F2 U2 L2 B2 U2 F2 (moves 33) D1 F3 U2 R1 B3 L1 B2 R1 U3 L2 D3 F2 R3 L2 D2 L2 D3 L2 F2 U3 F2 B2 D2 L2 B2 L2 B2 D2 L2 F2 U2 F2 U2 (moves 33) R1 B1 D3 F3 D1 R3 D3 B2 L2 B2 U2 L3 L2 U2 B2 L2 U2 F2 U3 U2 F2 L2 D2 L2 B2 U2 R2 F2 L2 B2 (moves 30) U1 D2 F1 L1 B3 D1 B2 D3 L2 R1 D3 L2 U2 R3 D2 F2 U3 F2 R2 U1 B2 U1 F2 U3 B2 R2 U2 L2 U2 B2 D2 F2 L2 B2 F2 U2 (moves 36) U1 L1 D1 L1 F3 L1 U1 L3 U3 L1 D1 R3 F2 U2 R2 U1 F2 U2 F2 L2 D1 F2 U3 F2 U2 R2 D2 F2 R2 B2 L2 B2 D2 B2 (moves 34) L3 D3 U1 F3 U2 F2 D3 R3 B2 D3 U3 L3 R2 U2 L2 D3 R2 U1 L2 U2 F2 U3 F2 U3 U2 L2 U2 R2 B2 R2 B2 U2 F2 U2 (moves 34) L1 B1 U2 D1 F3 B2 U3 R3 D2 U3 L2 U3 L3 F2 U3 R2 U1 F2 R2 L2 D3 F2 F2 B2 L2 D2 F2 R2 D2 B2 R2 F2 L2 (moves 33) L1 B1 U3 F3 U1 L2 D3 L1 B2 R1 L3 U3 L3 U3 L2 D3 L2 U1 L2 B2 F2 U3 L2 D2 L2 U2 R2 F2 D2 B2 U2 R2 U2 (moves 33) F1 U1 B3 F3 B2 U2 D3 L3 U3 L3 U3 R2 D3 B2 D2 L2 U3 R2 U2 F2 U3 F2 L2 D2 L2 R2 F2 L2 U2 L2 D2 U2 F2 U2 (moves 34) D1 L3 R1 F2 U2 F3 U3 F2 D3 L3 D2 L3 U2 L3 D1 L2 U3 R2 D1 B2 U1 L2 R2 U2 L2 D2 B2 R2 F2 L2 D2 U2 F2 U2 (moves 34) L2 R3 D1 F3 D3 L1 U3 L3 D2 L3 B2 L2 U1 R2 U2 F2 U3 F2 L2 F2 L2 B2 U2 R2 U2 R2 B2 U2 B2 (moves 29) L2 U2 R1 B3 F3 U1 L1 D3 F2 U2 R3 U2 L3 L2 U2 L2 D2 L2 F2 U3 F2 U2 L2 U2 B2 U2 R2 D2 R2 B2 (moves 30) L2 F1 U2 F3 D3 R3 U1 D3 L3 D1 U1 L3 R2 D3 R2 F2 D2 B2 U3 F2 U1 F2 D2 L2 B2 U2 L2 U2 R2 B2 F2 U2 (moves 32) F3 D2 F3 L2 B2 D3 L2 U3 B2 L3 L2 F2 L2 D3 L2 B2 U3 L2 L2 U2 F2 D2 L2 D2 L2 B2 L2 F2 L2 U2 (moves 30) F3 R2 U3 F3 U3 R3 D2 R2 D1 F2 U2 L3 D3 L2 D3 R2 U1 F2 U3 L2 U1 F2 L2 B2 D2 B2 L2 F2 U2 L2 F2 D2 (moves 32) B1 R1 U1 D3 F3 R2 U1 L2 R2 D2 B2 U3 L3 R2 F2 U1 L2 B2 U1 F2 U3 L2 U3 R2 U2 F2 D2 F2 L2 B2 L2 U2 F2 (moves 33) L3 D3 U1 B3 L2 F2 D3 L3 R1 U1 R3 L2 D3 F2 R2 U3 F2 R2 U3 L2 D2 R2 U2 B2 U2 B2 L2 U2 R2 F2 U2 (moves 31) L1 F3 L2 R1 B3 L1 U3 L1 R1 D3 F2 D1 R3 B2 R2 U1 F2 L2 D1 R2 F2 D2 L2 R2 B2 R2 B2 U2 L2 U2 (moves 30) U1 F1 U3 L1 B3 D1 L2 B2 R1 D3 R3 F2 L3 U3 F2 B2 L2 U3 B2 D3 L2 U3 L2 D2 R2 F2 D2 L2 F2 D2 F2 (moves 31) D2 L3 U1 F3 U1 D3 L1 F2 D3 R3 F2 U3 R3 L2 U1 L2 U3 L2 U1 F2 L2 U1 R2 U3 F2 U2 L2 D2 B2 U2 L2 F2 U2 F2 U2 (moves 35) F3 L2 F3 U1 L1 U1 D2 L3 U3 L3 B2 U1 F2 U1 F2 D2 R2 U3 L2 U2 F2 U3 R2 F2 D2 L2 D2 R2 F2 U2 F2 U2 F2 U2 (moves 34) U2 L3 B3 U2 R3 U3 L2 B2 U1 R3 R2 D3 R2 U1 R2 U3 F2 U1 F2 U3 F2 U2 L2 F2 R2 F2 D2 L2 D2 L2 B2 (moves 31) F1 B1 R3 F3 U3 F3 B2 D1 B2 R1 U3 L1 U2 L3 F2 U3 F2 R2 U1 R2 U2 B2 D3 F2 U3 F2 B2 L2 U2 F2 L2 D2 B2 F2 L2 B2 (moves 36) Average number of moves = 16.38 Average time = 65.71 milliseconds
Kotlin
This is a translation of Stefan Pochmann's C++ entry in the 2004 competition which was linked to by the author of the Phix entry. This program won the Judge's prize, finished second overall and (as in the case of the winner) is based on Thistlethwaite's algorithm.
I've adjusted the code to accept input from a file whose name is supplied via a command line argument and, as in the case of the original competition, to calculate the average number of moves for each line in the file and the average time to process each one.
To aid readability I've also inserted spaces between each move in the results and added the total moves needed for each line.
// version 1.2.21
/**********************************************************************
*
* A cube 'state' is a vector<int> with 40 entries, the first 20
* are a permutation of {0,...,19} and describe which cubie is at
* a certain position (regarding the input ordering). The first
* twelve are for edges, the last eight for corners.
*
* The last 20 entries are for the orientations, each describing
* how often the cubie at a certain position has been turned
* counterclockwise away from the correct orientation. Again the
* first twelve are edges, the last eight are corners. The values
* are 0 or 1 for edges and 0, 1 or 2 for corners.
*
**********************************************************************/
import java.util.ArrayDeque
import java.io.File
fun Boolean.toInt() = if (this) 1 else 0
typealias AI = ArrayList<Int>
val applicableMoves = intArrayOf(0, 262143, 259263, 74943, 74898)
val affectedCubies = listOf(
intArrayOf(0, 1, 2, 3, 0, 1, 2, 3), // U
intArrayOf(4, 7, 6, 5, 4, 5, 6, 7), // D
intArrayOf(0, 9, 4, 8, 0, 3, 5, 4), // F
intArrayOf(2, 10, 6, 11, 2, 1, 7, 6), // B
intArrayOf(3, 11, 7, 9, 3, 2, 6, 5), // L
intArrayOf(1, 8, 5, 10, 1, 0, 4, 7) // R
)
fun applyMove(move: Int, state: AI): AI {
val state2 = AI(state) // avoids mutating original 'state'.
var turns = move % 3 + 1
val face = move / 3
while (turns-- != 0) {
val oldState2 = AI(state2)
for (i in 0..7) {
val isCorner = (i > 3).toInt()
val target = affectedCubies[face][i] + isCorner * 12
val temp = if ((i and 3) == 3) i - 3 else i + 1
val killer = affectedCubies[face][temp] + isCorner * 12
val orientationDelta =
if (i < 4) (face in 2..3).toInt()
else if (face < 2) 0
else 2 - (i and 1)
state2[target] = oldState2[killer]
state2[target + 20] = oldState2[killer + 20] + orientationDelta
if (turns == 0) state2[target + 20] %= 2 + isCorner
}
}
return state2
}
fun inverse(move: Int) = move + 2 - 2 * (move % 3)
var phase = 0
fun id(state: AI): AI {
//--- Phase 1: Edge orientations.
if (phase < 2) return AI(state.subList(20, 32))
//-- Phase 2: Corner orientations, E slice edges.
if (phase < 3) {
val result = AI(state.subList(31, 40))
for (e in 0..11) result[0] = result[0] or ((state[e] / 8) shl e)
return result
}
//--- Phase 3: Edge slices M and S, corner tetrads, overall parity.
if (phase < 4) {
val result = AI(3)
repeat(3) { result.add(0) }
for (e in 0..11) {
val temp = (if (state[e] > 7) 2 else (state[e] and 1)) shl (2 * e)
result[0] = result[0] or temp
}
for (c in 0..7) {
val temp = ((state[c + 12] - 12) and 5) shl (3 * c)
result[1] = result[1] or temp
}
for (i in 12..18) {
for (j in (i + 1)..19) {
result[2] = result[2] xor (state[i] > state[j]).toInt()
}
}
return result
}
//--- Phase 4: The rest.
return state
}
fun main(args: Array<String>) {
val startTime = System.currentTimeMillis()
var aggregateMoves = 0
//--- Define the goal.
val goal = listOf(
"UF", "UR", "UB", "UL", "DF", "DR", "DB", "DL", "FR", "FL", "BR", "BL",
"UFR", "URB", "UBL", "ULF", "DRF", "DFL", "DLB", "DBR"
)
//--- Load dataset (file name should be passed as a command line argument).
val file = File(args[0])
var lineCount = 0
file.forEachLine { line ->
val inputs = line.split(' ')
lineCount++
phase = 0
var totalMoves = 0
//--- Prepare current (start) and goal state.
var currentState = AI(40)
repeat(40) { currentState.add(0) }
val goalState = AI(40)
repeat(40) { goalState.add(0) }
for (i in 0..19) {
//--- Goal state.
goalState[i] = i
//--- Current (start) state.
var cubie = inputs[i]
while (true) {
val idx = goal.indexOf(cubie)
currentState[i] = if (idx >= 0) idx else 20
if (currentState[i] != 20) break
cubie = cubie.substring(1) + cubie[0]
currentState[i + 20]++
}
}
//--- Dance the funky Thistlethwaite...
nextPhase@ while (++phase < 5) {
//--- Compute ids for current and goal state, skip phase if equal.
val currentId = id(currentState)
val goalId = id(goalState)
if (currentId == goalId) continue
//--- Initialize the BFS queue.
val q = ArrayDeque<AI>()
q.addLast(currentState)
q.addLast(goalState)
//--- Initialize the BFS tables.
val predecessor = mutableMapOf<AI, AI>()
val direction = mutableMapOf<AI, Int>()
val lastMove = mutableMapOf<AI, Int>()
direction[currentId] = 1
direction[goalId] = 2
//--- Dance the funky bidirectional BFS...
while (true) {
//--- Get state from queue, compute its ID and get its direction.
val oldState = q.peek()
q.pop()
var oldId = id(oldState)
val oldDir = direction.getOrPut(oldId) { 0 }
//--- Apply all applicable moves to it and handle the new state.
var move = 0
while (move < 18) {
if ((applicableMoves[phase] and (1 shl move)) != 0) {
//--- Apply the move.
val newState = applyMove(move, oldState)
var newId = id(newState)
var newDir = direction.getOrPut(newId) { 0 }
//--- Have we seen this state (id) from the other direction already?
//--- I.e. have we found a connection?
if ((newDir != 0) && (newDir != oldDir)) {
//--- Make oldId represent the forwards
//--- and newId the backwards search state.
if (oldDir > 1) {
val temp = newId
newId = oldId
oldId = temp
move = inverse(move)
}
//--- Reconstruct the connecting algorithm.
val algorithm = AI()
algorithm.add(move)
while (oldId != currentId) {
val tempI = lastMove.getOrPut(oldId) { 0 }
algorithm.add(0, tempI)
val tempAI = predecessor.getOrPut(oldId) { AI() }
oldId = tempAI
}
while (newId != goalId) {
val tempI = lastMove.getOrPut(newId) { 0 }
algorithm.add(inverse(tempI))
val tempAI = predecessor.getOrPut(newId) { AI() }
newId = tempAI
}
//--- Print and apply the algorithm.
for (i in 0 until algorithm.size) {
print("UDFBLR"[algorithm[i] / 3])
print(algorithm[i] % 3 + 1)
print(" ")
totalMoves++
currentState = applyMove(algorithm[i], currentState)
}
//--- Jump to the next phase.
continue@nextPhase
}
//--- If we've never seen this state (id) before, visit it.
if (newDir == 0) {
q.addLast(newState)
direction[newId] = oldDir
lastMove[newId] = move
predecessor[newId] = oldId
}
}
move++
}
}
}
println(" (moves $totalMoves)")
aggregateMoves += totalMoves
}
val elapsedTime = System.currentTimeMillis() - startTime
println("\nAverage number of moves = ${aggregateMoves.toDouble() / lineCount}")
println("\nAverage time = ${elapsedTime / lineCount} milliseconds")
}
- Output:
Using the original dataset of 100 lines, the results were as follows (time doesn't mean much but is typical for my modest machine):
U1 U2 (moves 2) U2 (moves 1) U1 (moves 1) F1 F2 (moves 2) F2 (moves 1) F1 (moves 1) R1 R2 (moves 2) R2 (moves 1) R1 (moves 1) D1 D2 (moves 2) D2 (moves 1) D1 (moves 1) B1 B2 (moves 2) B2 (moves 1) B1 (moves 1) L1 L2 (moves 2) L2 (moves 1) L1 (moves 1) U2 B3 B2 (moves 3) L2 U3 (moves 2) R1 U1 (moves 2) D3 L3 (moves 2) D3 L2 (moves 2) D2 F3 F2 (moves 3) R2 F3 (moves 2) R1 F2 F2 R2 F2 (moves 5) D1 D2 U2 (moves 3) L1 B2 F2 L2 R2 B2 F2 (moves 7) L1 L2 D3 (moves 3) D1 F2 (moves 2) U2 R3 (moves 2) L1 L2 U3 (moves 3) U1 R2 (moves 2) U1 R3 (moves 2) F1 U2 (moves 2) U2 R3 R2 (moves 3) F2 D1 F3 (moves 3) F2 D3 D2 U2 (moves 4) L3 D2 R3 (moves 3) D2 R3 R2 D3 (moves 4) F1 R1 B2 B2 R2 B2 (moves 6) L1 B2 F2 (moves 3) U1 R2 B3 B2 (moves 4) R2 F3 R2 (moves 3) L2 D3 R3 R2 (moves 4) L2 F3 L2 L2 F2 L2 (moves 6) F1 R1 B3 D3 B2 D3 L3 U2 L3 U2 L2 U2 L2 U3 R2 U1 F2 L2 U2 B2 L2 F2 U2 L2 U2 F2 D2 F2 U2 (moves 29) L1 L2 U3 R2 (moves 4) L3 B3 B2 R3 R2 (moves 5) B2 U1 R3 R2 (moves 4) L3 B3 L2 (moves 3) D1 B2 L3 L2 (moves 4) B1 B2 R3 F2 F2 R2 F2 (moves 7) D1 F3 D1 D2 (moves 4) R1 B3 D1 R2 F3 L1 U2 F2 D3 B2 D1 L3 U1 F2 R2 U1 L2 U1 F2 U2 R2 U3 F2 U3 F2 D2 F2 L2 F2 L2 F2 U2 F2 D2 L2 (moves 35) F1 R1 U3 D1 B3 U3 D2 L3 B2 R1 F2 D3 L3 U2 R2 D1 R2 B2 U2 L2 U3 U2 F2 U2 L2 B2 R2 D2 R2 D2 B2 L2 F2 U2 (moves 34) U1 R1 F3 L1 R2 U3 L1 D2 F2 U3 L3 L2 U1 F2 D3 F2 F2 U2 D2 L2 U2 F2 R2 F2 D2 R2 U2 (moves 27) R1 D3 R3 F3 R1 D3 F2 U1 R3 D2 U1 R3 F2 U1 L2 U3 F2 U1 B2 D2 L2 D3 F2 F2 U2 F2 D2 L2 U2 L2 F2 L2 U2 R2 (moves 34) D2 R1 B1 L1 F3 U2 D3 L2 R1 D3 B2 U1 F2 L3 F2 U3 B2 U3 B2 L2 U3 B2 U3 F2 U2 F2 U2 L2 F2 R2 B2 D2 L2 D2 F2 (moves 35) B3 U2 L1 F3 F2 U1 R3 D1 F2 R3 D3 B2 R3 B2 U1 F2 U3 R2 U1 R2 U3 R2 L2 F2 U2 R2 F2 D2 R2 B2 U2 R2 B2 (moves 33) L1 F3 L2 D3 U1 F3 L1 B2 R1 U1 D1 B2 R3 U1 L2 U1 B2 U1 F2 U3 L2 D1 F2 U3 F2 U2 D2 R2 U2 L2 F2 R2 U2 F2 R2 (moves 35) F1 R3 U2 F3 B2 U1 L1 U1 R3 B2 U1 R3 R2 U3 L2 U1 B2 U2 R2 U3 L2 U3 F2 L2 U2 F2 U2 B2 L2 D2 L2 F2 L2 F2 U2 (moves 35) U2 D3 B3 U1 L2 D1 R1 U3 L3 D2 U1 R3 U3 B2 D3 R2 F2 U3 F2 U3 U2 B2 D2 B2 L2 F2 R2 D2 R2 (moves 29) D2 L3 U3 F3 B2 U3 L1 U2 R3 D2 L3 U2 L2 U3 R2 B2 D3 F2 R2 U3 U2 L2 U2 F2 U2 D2 R2 F2 U2 B2 D2 (moves 31) F1 L1 U1 L1 B3 U3 L1 F2 L1 B2 F2 U3 L3 F2 D3 B2 D3 R2 U1 F2 U3 L2 U3 U2 F2 D2 B2 U2 F2 R2 F2 L2 (moves 32) B1 L1 U3 F3 B2 U1 L3 B2 R3 L3 U3 L3 D2 B2 D3 F2 L2 U2 R2 U3 F2 U3 F2 L2 U2 B2 L2 U2 B2 F2 R2 U2 F2 (moves 33) F2 L3 F1 D3 B3 B2 U3 R1 D3 U3 L3 L2 R2 U3 B2 D1 B2 U3 R2 U3 F2 L2 F2 L2 U2 F2 B2 R2 B2 L2 (moves 30) D3 F3 U1 B2 U3 L1 D1 R3 U3 F2 L3 U1 F2 U2 L2 U3 L2 B2 R2 L2 D1 F2 F2 L2 U2 F2 L2 U2 R2 D2 B2 R2 L2 (moves 33) F2 R3 U2 F3 U2 L2 B2 D1 F2 R3 B2 D1 L3 D2 R2 B2 D1 R2 B2 U1 L2 B2 R2 B2 R2 D2 L2 D2 F2 L2 B2 L2 F2 (moves 33) U1 R3 F3 D3 R3 B2 L3 D1 F2 U1 R3 L2 U1 B2 D1 L2 U3 R2 U1 L2 U3 F2 U3 F2 U2 B2 L2 D2 L2 U2 R2 F2 (moves 32) F1 R1 F1 D3 B3 F3 U1 R2 F2 U1 L3 U1 F2 U2 R2 U1 R2 U3 L2 U3 D2 L2 F2 L2 F2 U2 B2 U2 L2 F2 (moves 30) F3 R3 L2 B3 U1 B2 U1 F2 U2 B2 R3 D2 L3 B2 U1 F2 U3 L2 U1 B2 D3 L2 U1 L2 U2 L2 D2 R2 F2 D2 F2 U2 R2 U2 (moves 34) D1 B3 D2 L1 F3 U3 F2 D2 L3 F2 L3 D3 L3 D1 L2 B2 U3 R2 U1 R2 U3 L2 U3 L2 D2 R2 D2 F2 R2 F2 L2 D2 U2 F2 U2 (moves 35) U1 B1 D1 R3 F3 U1 B2 R1 U3 L1 D3 B2 U1 R3 U2 F2 L2 U3 R2 U1 B2 D3 B2 U1 L2 F2 U2 D2 L2 U2 B2 R2 B2 L2 D2 L2 (moves 36) U3 F1 L1 F3 B2 U1 B2 R2 D1 R1 U2 L3 U1 F2 R2 U3 L2 U3 B2 F2 R2 F2 B2 U2 R2 F2 L2 U2 L2 (moves 29) U1 B2 L1 B3 F3 U1 F2 B2 R2 D3 R3 U3 L3 B2 U1 F2 U3 F2 U3 L2 U2 F2 R2 B2 R2 U2 F2 U2 F2 U2 F2 (moves 31) U1 B1 U3 D1 F3 U2 D3 R3 D1 U1 L1 F2 L3 D2 L2 U1 F2 B2 R2 U3 F2 U1 L2 U2 R2 F2 D2 F2 U2 L2 B2 U2 F2 (moves 33) D1 F3 U2 R1 B3 L1 B2 R1 U3 L2 D3 F2 R3 L2 D2 L2 D3 L2 F2 U3 F2 B2 D2 L2 B2 L2 B2 D2 L2 F2 U2 F2 U2 (moves 33) R1 B1 D3 F3 D1 R3 D3 B2 L2 B2 U2 L3 L2 U2 B2 L2 U2 F2 U3 U2 F2 L2 D2 L2 B2 U2 R2 F2 L2 B2 (moves 30) U1 D2 F1 L1 B3 D1 B2 D3 L2 R1 D3 L2 U2 R3 D2 F2 U3 F2 R2 U1 B2 U1 F2 U3 B2 R2 U2 L2 U2 B2 D2 F2 L2 B2 F2 U2 (moves 36) U1 L1 D1 L1 F3 L1 U1 L3 U3 L1 D1 R3 F2 U2 R2 U1 F2 U2 F2 L2 D1 F2 U3 F2 U2 R2 D2 F2 R2 B2 L2 B2 D2 B2 (moves 34) L3 D3 U1 F3 U2 F2 D3 R3 B2 D3 U3 L3 R2 U2 L2 D3 R2 U1 L2 U2 F2 U3 F2 U3 U2 L2 U2 R2 B2 R2 B2 U2 F2 U2 (moves 34) L1 B1 U2 D1 F3 B2 U3 R3 D2 U3 L2 U3 L3 F2 U3 R2 U1 F2 R2 L2 D3 F2 F2 B2 L2 D2 F2 R2 D2 B2 R2 F2 L2 (moves 33) L1 B1 U3 F3 U1 L2 D3 L1 B2 R1 L3 U3 L3 U3 L2 D3 L2 U1 L2 B2 F2 U3 L2 D2 L2 U2 R2 F2 D2 B2 U2 R2 U2 (moves 33) F1 U1 B3 F3 B2 U2 D3 L3 U3 L3 U3 R2 D3 B2 D2 L2 U3 R2 U2 F2 U3 F2 L2 D2 L2 R2 F2 L2 U2 L2 D2 U2 F2 U2 (moves 34) D1 L3 R1 F2 U2 F3 U3 F2 D3 L3 D2 L3 U2 L3 D1 L2 U3 R2 D1 B2 U1 L2 R2 U2 L2 D2 B2 R2 F2 L2 D2 U2 F2 U2 (moves 34) L2 R3 D1 F3 D3 L1 U3 L3 D2 L3 B2 L2 U1 R2 U2 F2 U3 F2 L2 F2 L2 B2 U2 R2 U2 R2 B2 U2 B2 (moves 29) L2 U2 R1 B3 F3 U1 L1 D3 F2 U2 R3 U2 L3 L2 U2 L2 D2 L2 F2 U3 F2 U2 L2 U2 B2 U2 R2 D2 R2 B2 (moves 30) L2 F1 U2 F3 D3 R3 U1 D3 L3 D1 U1 L3 R2 D3 R2 F2 D2 B2 U3 F2 U1 F2 D2 L2 B2 U2 L2 U2 R2 B2 F2 U2 (moves 32) F3 D2 F3 L2 B2 D3 L2 U3 B2 L3 L2 F2 L2 D3 L2 B2 U3 L2 L2 U2 F2 D2 L2 D2 L2 B2 L2 F2 L2 U2 (moves 30) F3 R2 U3 F3 U3 R3 D2 R2 D1 F2 U2 L3 D3 L2 D3 R2 U1 F2 U3 L2 U1 F2 L2 B2 D2 B2 L2 F2 U2 L2 F2 D2 (moves 32) B1 R1 U1 D3 F3 R2 U1 L2 R2 D2 B2 U3 L3 R2 F2 U1 L2 B2 U1 F2 U3 L2 U3 R2 U2 F2 D2 F2 L2 B2 L2 U2 F2 (moves 33) L3 D3 U1 B3 L2 F2 D3 L3 R1 U1 R3 L2 D3 F2 R2 U3 F2 R2 U3 L2 D2 R2 U2 B2 U2 B2 L2 U2 R2 F2 U2 (moves 31) L1 F3 L2 R1 B3 L1 U3 L1 R1 D3 F2 D1 R3 B2 R2 U1 F2 L2 D1 R2 F2 D2 L2 R2 B2 R2 B2 U2 L2 U2 (moves 30) U1 F1 U3 L1 B3 D1 L2 B2 R1 D3 R3 F2 L3 U3 F2 B2 L2 U3 B2 D3 L2 U3 L2 D2 R2 F2 D2 L2 F2 D2 F2 (moves 31) D2 L3 U1 F3 U1 D3 L1 F2 D3 R3 F2 U3 R3 L2 U1 L2 U3 L2 U1 F2 L2 U1 R2 U3 F2 U2 L2 D2 B2 U2 L2 F2 U2 F2 U2 (moves 35) F3 L2 F3 U1 L1 U1 D2 L3 U3 L3 B2 U1 F2 U1 F2 D2 R2 U3 L2 U2 F2 U3 R2 F2 D2 L2 D2 R2 F2 U2 F2 U2 F2 U2 (moves 34) U2 L3 B3 U2 R3 U3 L2 B2 U1 R3 R2 D3 R2 U1 R2 U3 F2 U1 F2 U3 F2 U2 L2 F2 R2 F2 D2 L2 D2 L2 B2 (moves 31) F1 B1 R3 F3 U3 F3 B2 D1 B2 R1 U3 L1 U2 L3 F2 U3 F2 R2 U1 R2 U2 B2 D3 F2 U3 F2 B2 L2 U2 F2 L2 D2 B2 F2 L2 B2 (moves 36) B2 D3 B3 U2 B2 D3 L3 D1 R1 U2 L3 L2 U3 B2 U1 B2 D2 R2 U3 F2 U3 U2 L2 U2 F2 D2 F2 U2 B2 L2 D2 F2 R2 F2 (moves 34)
Average number of moves = 16.72 Average time = 127 milliseconds
When run with a file containing the single line:
UL DL RF UB FD BR DB UF DR UR BL FL FDR BLU DLB URB RUF FLD BRD FUL
a typical result was:
U3 F1 L1 F3 B2 U1 B2 R2 D1 R1 U2 L3 U1 F2 R2 U3 L2 U3 B2 F2 R2 F2 B2 U2 R2 F2 L2 U2 L2 (moves 29) Average number of moves = 29.0 Average time = 522 milliseconds
Nim
#[
**********************************************************************
*
* A cube 'state' is a sequence of ints with 40 entries, the first
* 20 are a permutation of {0,...,19} and describe which cubie is
* at a certain position (regarding the input ordering). The first
* twelve are for edges, the last eight for corners.
*
* The last 20 entries are for the orientations, each describing
* how often the cubie at a certain position has been turned
* counterclockwise away from the correct orientation. Again the
* first twelve are edges, the last eight are corners. The values
* are 0 or 1 for edges and 0, 1 or 2 for corners.
*
**********************************************************************
]#
import deques, os, strformat, strutils, tables, times
const
ApplicableMoves = [0, 262143, 259263, 74943, 74898]
AffectedCubies = [[0, 1, 2, 3, 0, 1, 2, 3], # U
[4, 7, 6, 5, 4, 5, 6, 7], # D
[0, 9, 4, 8, 0, 3, 5, 4], # F
[2, 10, 6, 11, 2, 1, 7, 6], # B
[3, 11, 7, 9, 3, 2, 6, 5], # L
[1, 8, 5, 10, 1, 0, 4, 7]] # R
type State = seq[int]
func initState(n: Natural = 0): State = newSeq[int](n)
var phase: Natural
proc slicetoState(s: openArray[int]): State =
result.setLen(40)
for i, val in s: result[i] = val
for i in s.len..39: result[i] = -1
proc id(state: State): State =
case phase
of 1: # Phase 1: Edge orientations.
result = sliceToState(state[20..31])
of 2: # Phase 2: Corner orientations, E slice edges.
var res = state[31..39]
for e in 0..11:
res[0] = res[0] or state[e] shr 3 shl e
result = sliceToState(res)
of 3: # Phase 3: Edge slices M and S, corner tetrads, overall parity.
var res = @[0, 0, 0]
for e in 0..11:
let temp = if state[e] > 7: 2 else: (state[e] and 1) shl (2 * e)
res[0] = res[0] or temp
for c in 0..7:
res[1] = res[1] or ((state[c + 12] - 12) and 5) shl (3 * c)
for i in 12..18:
for j in (i + 1)..19:
res[2] = res[2] xor ord(state[i] > state[j])
result = sliceToState(res)
else: # Phase 4: The rest.
result = state
proc applyMove(move: int; state: State): State =
result = state
var turns = move mod 3 + 1
let face = move div 3
while turns != 0:
dec turns
var oldState = result
for i in 0..7:
let isCorner = ord(i > 3)
let target = AffectedCubies[face][i] + isCorner * 12
let temp = if (i and 3) == 3: i - 3 else: i + 1
let killer = AffectedCubies[face][temp] + isCorner * 12
let orientationDelta =
if i < 4: ord(face in 2..3)
elif face < 2: 0
else: 2 - (i and 1)
result[target] = oldState[killer]
result[target + 20] = oldState[killer + 20] + orientationDelta
if turns == 0:
result[target + 20] = result[target + 20] mod (2 + isCorner)
func inverse(move: int): int = move + 2 - 2 * (move mod 3)
let startTime = cpuTime()
var aggregateMoves = 0
# Define the goal.
const Goal = ["UF", "UR", "UB", "UL", "DF", "DR", "DB", "DL", "FR", "FL", "BR", "BL",
"UFR", "URB", "UBL", "ULF", "DRF", "DFL", "DLB", "DBR"]
# Load dataset (file name should be passed as a command line argument).
if paramCount() == 0: quit "Missing file name", QuitFailure
var lineCount = 0
for line in paramStr(1).lines():
let inputs = line.splitWhitespace()
inc lineCount
var totalMoves = 0
# Prepare current (start) and goal state.
var currentState, goalState = initState(40)
for i in 0..19:
# Goal state.
goalState[i] = i
# Current (start) state.
var cubie = inputs[i]
while true:
let idx = Goal.find(cubie)
currentState[i] = if idx >= 0: idx else: 20
if currentState[i] != 20: break
cubie = cubie[1..^1] & cubie[0]
inc currentState[i + 20]
# Dance the funky Thistlethwaite...
phase = 1
while phase < 5:
block doPhase:
# Compute ids for current and goal state, skip phase if equal.
let currentId = id(currentState)
let goalId = id(goalState)
if currentId == goalId: break doPhase
# Initialize the BFS queue.
var q = [currentState, goalState].toDeque
# Initialize the BFS tables.
var predecessor: Table[State, State]
var direction, lastMove: Table[State, int]
direction[currentId] = 1
direction[goalId] = 2
# Dance the funky bidirectional BFS.
while true:
# Get state from queue, compute its ID and get its direction.
let oldState = q.popFirst()
var oldId = id(oldState)
let oldDir = direction[oldId]
# Apply all applicable moves to it and handle the new state.
var move = 0
while move < 18:
if (ApplicableMoves[phase] and (1 shl move)) != 0:
# Apply the move.
let newState = applyMove(move, oldState)
var newId = id(newState)
let newDir = direction.getOrDefault(newId, 0)
# Have we seen this state (id) from the other direction already?
# I.e. have we found a connection?
if newDir != 0 and newDir != oldDir:
# Make oldId represent the forwards and newId the backwards search state.
if oldDir > 1:
swap newId, oldId
move = inverse(move)
# Reconstruct the connecting algorithm.
var algorithm: State = @[move]
while oldId != currentId:
algorithm.insert(lastMove.mgetOrPut(oldId, 0), 0)
oldId = predecessor.mgetOrPut(oldId, initState())
while newId != goalId:
algorithm.add inverse(lastMove.mgetOrPut(newId, 0))
newId = predecessor.mgetOrPut(newId, initState())
# Print and apply the algorithm.
for step in algorithm:
stdout.write "UDFBLR"[step div 3], step mod 3 + 1, ' '
inc totalMoves
currentState = applyMove(step, currentState)
# Jump to the next phase.
break doPhase
# If we've never seen this state (id) before, visit it.
if newdir == 0:
q.addLast(newState)
direction[newId] = oldDir
lastMove[newId] = move
predecessor[newId] = oldId
inc move
inc phase
echo &" (moves {totalMoves})"
inc aggregateMoves, totalMoves
let elapsedTime = cpuTime() - startTime
echo &"\nAverage number of moves = {aggregateMoves / lineCount}"
echo &"\nAverage time = {elapsedTime * 1000 / lineCount.toFloat:.2f} milliseconds"
- Output:
We compiled the program with command nim c -d:danger --gc:arc -d:lto, which means no runtime checks, ARC memory management and link time optimization.
When run with the original dataset of 100 lines, we got:
U1 U2 (moves 2) U2 (moves 1) U1 (moves 1) F1 F2 (moves 2) F2 (moves 1) F1 (moves 1) R1 R2 (moves 2) R2 (moves 1) R1 (moves 1) D1 D2 (moves 2) D2 (moves 1) D1 (moves 1) B1 B2 (moves 2) B2 (moves 1) B1 (moves 1) L1 L2 (moves 2) L2 (moves 1) L1 (moves 1) U2 B3 B2 (moves 3) L2 U3 (moves 2) R1 U1 (moves 2) D3 L3 (moves 2) D3 L2 (moves 2) D2 F3 F2 (moves 3) R2 F3 (moves 2) R1 F2 F2 R2 F2 (moves 5) D1 D2 U2 (moves 3) L1 B2 F2 L2 R2 B2 F2 (moves 7) L1 L2 D3 (moves 3) D1 F2 (moves 2) U2 R3 (moves 2) L1 L2 U3 (moves 3) U1 R2 (moves 2) U1 R3 (moves 2) F1 U2 (moves 2) U2 R3 R2 (moves 3) F2 D1 F3 (moves 3) F2 D3 D2 U2 (moves 4) L3 D2 R3 (moves 3) D2 R3 R2 D3 (moves 4) F1 R1 B2 B2 R2 B2 (moves 6) L1 B2 F2 (moves 3) U1 R2 B3 B2 (moves 4) R2 F3 R2 (moves 3) L2 D3 R3 R2 (moves 4) L2 F3 L2 L2 F2 L2 (moves 6) F1 R1 B3 D3 B2 D3 L3 U2 L3 U2 L2 U2 L2 U3 R2 U1 F2 L2 U2 B2 L2 F2 U2 L2 U2 F2 D2 F2 U2 (moves 29) L1 L2 U3 R2 (moves 4) L3 B3 B2 R3 R2 (moves 5) B2 U1 R3 R2 (moves 4) L3 B3 L2 (moves 3) D1 B2 L3 L2 (moves 4) B1 B2 R3 F2 F2 R2 F2 (moves 7) D1 F3 D1 D2 (moves 4) R1 B3 D1 R2 F3 L1 U2 F2 D3 B2 D1 L3 U1 F2 R2 U1 L2 U1 F2 U2 R2 U3 F2 U3 F2 D2 F2 L2 F2 L2 F2 U2 F2 D2 L2 (moves 35) F1 R1 U3 D1 B3 U3 D2 L3 B2 R1 F2 D3 L3 U2 R2 D1 R2 B2 U2 L2 U3 U2 F2 U2 L2 B2 R2 D2 R2 D2 B2 L2 F2 U2 (moves 34) U1 R1 F3 L1 R2 U3 L1 D2 F2 U3 L3 L2 U1 F2 D3 F2 F2 U2 D2 L2 U2 F2 R2 F2 D2 R2 U2 (moves 27) R1 D3 R3 F3 R1 D3 F2 U1 R3 D2 U1 R3 F2 U1 L2 U3 F2 U1 B2 D2 L2 D3 F2 F2 U2 F2 D2 L2 U2 L2 F2 L2 U2 R2 (moves 34) D2 R1 B1 L1 F3 U2 D3 L2 R1 D3 B2 U1 F2 L3 F2 U3 B2 U3 B2 L2 U3 B2 U3 F2 U2 F2 U2 L2 F2 R2 B2 D2 L2 D2 F2 (moves 35) B3 U2 L1 F3 F2 U1 R3 D1 F2 R3 D3 B2 R3 B2 U1 F2 U3 R2 U1 R2 U3 R2 L2 F2 U2 R2 F2 D2 R2 B2 U2 R2 B2 (moves 33) L1 F3 L2 D3 U1 F3 L1 B2 R1 U1 D1 B2 R3 U1 L2 U1 B2 U1 F2 U3 L2 D1 F2 U3 F2 U2 D2 R2 U2 L2 F2 R2 U2 F2 R2 (moves 35) F1 R3 U2 F3 B2 U1 L1 U1 R3 B2 U1 R3 R2 U3 L2 U1 B2 U2 R2 U3 L2 U3 F2 L2 U2 F2 U2 B2 L2 D2 L2 F2 L2 F2 U2 (moves 35) U2 D3 B3 U1 L2 D1 R1 U3 L3 D2 U1 R3 U3 B2 D3 R2 F2 U3 F2 U3 U2 B2 D2 B2 L2 F2 R2 D2 R2 (moves 29) D2 L3 U3 F3 B2 U3 L1 U2 R3 D2 L3 U2 L2 U3 R2 B2 D3 F2 R2 U3 U2 L2 U2 F2 U2 D2 R2 F2 U2 B2 D2 (moves 31) F1 L1 U1 L1 B3 U3 L1 F2 L1 B2 F2 U3 L3 F2 D3 B2 D3 R2 U1 F2 U3 L2 U3 U2 F2 D2 B2 U2 F2 R2 F2 L2 (moves 32) B1 L1 U3 F3 B2 U1 L3 B2 R3 L3 U3 L3 D2 B2 D3 F2 L2 U2 R2 U3 F2 U3 F2 L2 U2 B2 L2 U2 B2 F2 R2 U2 F2 (moves 33) F2 L3 F1 D3 B3 B2 U3 R1 D3 U3 L3 L2 R2 U3 B2 D1 B2 U3 R2 U3 F2 L2 F2 L2 U2 F2 B2 R2 B2 L2 (moves 30) D3 F3 U1 B2 U3 L1 D1 R3 U3 F2 L3 U1 F2 U2 L2 U3 L2 B2 R2 L2 D1 F2 F2 L2 U2 F2 L2 U2 R2 D2 B2 R2 L2 (moves 33) F2 R3 U2 F3 U2 L2 B2 D1 F2 R3 B2 D1 L3 D2 R2 B2 D1 R2 B2 U1 L2 B2 R2 B2 R2 D2 L2 D2 F2 L2 B2 L2 F2 (moves 33) U1 R3 F3 D3 R3 B2 L3 D1 F2 U1 R3 L2 U1 B2 D1 L2 U3 R2 U1 L2 U3 F2 U3 F2 U2 B2 L2 D2 L2 U2 R2 F2 (moves 32) F1 R1 F1 D3 B3 F3 U1 R2 F2 U1 L3 U1 F2 U2 R2 U1 R2 U3 L2 U3 D2 L2 F2 L2 F2 U2 B2 U2 L2 F2 (moves 30) F3 R3 L2 B3 U1 B2 U1 F2 U2 B2 R3 D2 L3 B2 U1 F2 U3 L2 U1 B2 D3 L2 U1 L2 U2 L2 D2 R2 F2 D2 F2 U2 R2 U2 (moves 34) D1 B3 D2 L1 F3 U3 F2 D2 L3 F2 L3 D3 L3 D1 L2 B2 U3 R2 U1 R2 U3 L2 U3 L2 D2 R2 D2 F2 R2 F2 L2 D2 U2 F2 U2 (moves 35) U1 B1 D1 R3 F3 U1 B2 R1 U3 L1 D3 B2 U1 R3 U2 F2 L2 U3 R2 U1 B2 D3 B2 U1 L2 F2 U2 D2 L2 U2 B2 R2 B2 L2 D2 L2 (moves 36) U3 F1 L1 F3 B2 U1 B2 R2 D1 R1 U2 L3 U1 F2 R2 U3 L2 U3 B2 F2 R2 F2 B2 U2 R2 F2 L2 U2 L2 (moves 29) U1 B2 L1 B3 F3 U1 F2 B2 R2 D3 R3 U3 L3 B2 U1 F2 U3 F2 U3 L2 U2 F2 R2 B2 R2 U2 F2 U2 F2 U2 F2 (moves 31) U1 B1 U3 D1 F3 U2 D3 R3 D1 U1 L1 F2 L3 D2 L2 U1 F2 B2 R2 U3 F2 U1 L2 U2 R2 F2 D2 F2 U2 L2 B2 U2 F2 (moves 33) D1 F3 U2 R1 B3 L1 B2 R1 U3 L2 D3 F2 R3 L2 D2 L2 D3 L2 F2 U3 F2 B2 D2 L2 B2 L2 B2 D2 L2 F2 U2 F2 U2 (moves 33) R1 B1 D3 F3 D1 R3 D3 B2 L2 B2 U2 L3 L2 U2 B2 L2 U2 F2 U3 U2 F2 L2 D2 L2 B2 U2 R2 F2 L2 B2 (moves 30) U1 D2 F1 L1 B3 D1 B2 D3 L2 R1 D3 L2 U2 R3 D2 F2 U3 F2 R2 U1 B2 U1 F2 U3 B2 R2 U2 L2 U2 B2 D2 F2 L2 B2 F2 U2 (moves 36) U1 L1 D1 L1 F3 L1 U1 L3 U3 L1 D1 R3 F2 U2 R2 U1 F2 U2 F2 L2 D1 F2 U3 F2 U2 R2 D2 F2 R2 B2 L2 B2 D2 B2 (moves 34) L3 D3 U1 F3 U2 F2 D3 R3 B2 D3 U3 L3 R2 U2 L2 D3 R2 U1 L2 U2 F2 U3 F2 U3 U2 L2 U2 R2 B2 R2 B2 U2 F2 U2 (moves 34) L1 B1 U2 D1 F3 B2 U3 R3 D2 U3 L2 U3 L3 F2 U3 R2 U1 F2 R2 L2 D3 F2 F2 B2 L2 D2 F2 R2 D2 B2 R2 F2 L2 (moves 33) L1 B1 U3 F3 U1 L2 D3 L1 B2 R1 L3 U3 L3 U3 L2 D3 L2 U1 L2 B2 F2 U3 L2 D2 L2 U2 R2 F2 D2 B2 U2 R2 U2 (moves 33) F1 U1 B3 F3 B2 U2 D3 L3 U3 L3 U3 R2 D3 B2 D2 L2 U3 R2 U2 F2 U3 F2 L2 D2 L2 R2 F2 L2 U2 L2 D2 U2 F2 U2 (moves 34) D1 L3 R1 F2 U2 F3 U3 F2 D3 L3 D2 L3 U2 L3 D1 L2 U3 R2 D1 B2 U1 L2 R2 U2 L2 D2 B2 R2 F2 L2 D2 U2 F2 U2 (moves 34) L2 R3 D1 F3 D3 L1 U3 L3 D2 L3 B2 L2 U1 R2 U2 F2 U3 F2 L2 F2 L2 B2 U2 R2 U2 R2 B2 U2 B2 (moves 29) L2 U2 R1 B3 F3 U1 L1 D3 F2 U2 R3 U2 L3 L2 U2 L2 D2 L2 F2 U3 F2 U2 L2 U2 B2 U2 R2 D2 R2 B2 (moves 30) L2 F1 U2 F3 D3 R3 U1 D3 L3 D1 U1 L3 R2 D3 R2 F2 D2 B2 U3 F2 U1 F2 D2 L2 B2 U2 L2 U2 R2 B2 F2 U2 (moves 32) F3 D2 F3 L2 B2 D3 L2 U3 B2 L3 L2 F2 L2 D3 L2 B2 U3 L2 L2 U2 F2 D2 L2 D2 L2 B2 L2 F2 L2 U2 (moves 30) F3 R2 U3 F3 U3 R3 D2 R2 D1 F2 U2 L3 D3 L2 D3 R2 U1 F2 U3 L2 U1 F2 L2 B2 D2 B2 L2 F2 U2 L2 F2 D2 (moves 32) B1 R1 U1 D3 F3 R2 U1 L2 R2 D2 B2 U3 L3 R2 F2 U1 L2 B2 U1 F2 U3 L2 U3 R2 U2 F2 D2 F2 L2 B2 L2 U2 F2 (moves 33) L3 D3 U1 B3 L2 F2 D3 L3 R1 U1 R3 L2 D3 F2 R2 U3 F2 R2 U3 L2 D2 R2 U2 B2 U2 B2 L2 U2 R2 F2 U2 (moves 31) L1 F3 L2 R1 B3 L1 U3 L1 R1 D3 F2 D1 R3 B2 R2 U1 F2 L2 D1 R2 F2 D2 L2 R2 B2 R2 B2 U2 L2 U2 (moves 30) U1 F1 U3 L1 B3 D1 L2 B2 R1 D3 R3 F2 L3 U3 F2 B2 L2 U3 B2 D3 L2 U3 L2 D2 R2 F2 D2 L2 F2 D2 F2 (moves 31) D2 L3 U1 F3 U1 D3 L1 F2 D3 R3 F2 U3 R3 L2 U1 L2 U3 L2 U1 F2 L2 U1 R2 U3 F2 U2 L2 D2 B2 U2 L2 F2 U2 F2 U2 (moves 35) F3 L2 F3 U1 L1 U1 D2 L3 U3 L3 B2 U1 F2 U1 F2 D2 R2 U3 L2 U2 F2 U3 R2 F2 D2 L2 D2 R2 F2 U2 F2 U2 F2 U2 (moves 34) U2 L3 B3 U2 R3 U3 L2 B2 U1 R3 R2 D3 R2 U1 R2 U3 F2 U1 F2 U3 F2 U2 L2 F2 R2 F2 D2 L2 D2 L2 B2 (moves 31) F1 B1 R3 F3 U3 F3 B2 D1 B2 R1 U3 L1 U2 L3 F2 U3 F2 R2 U1 R2 U2 B2 D3 F2 U3 F2 B2 L2 U2 F2 L2 D2 B2 F2 L2 B2 (moves 36) B2 D3 B3 U2 B2 D3 L3 D1 R1 U2 L3 L2 U3 B2 U1 B2 D2 R2 U3 F2 U3 U2 L2 U2 F2 D2 F2 U2 B2 L2 D2 F2 R2 F2 (moves 34)
Average number of moves = 16.72 Average time = 52.03 milliseconds
When run with a file containing the single line:
UL DL RF UB FD BR DB UF DR UR BL FL FDR BLU DLB URB RUF FLD BRD FUL
a typical result was:
U3 F1 L1 F3 B2 U1 B2 R2 D1 R1 U2 L3 U1 F2 R2 U3 L2 U3 B2 F2 R2 F2 B2 U2 R2 F2 L2 U2 L2 (moves 29) Average number of moves = 29.0 Average time = 69.01 milliseconds
Phix
cfop
Uses brute-force (width/highscore-first) Fridrich-steps (ie cross,f2l,oll,pll).
Not the fastest (see THRESHOLD) or shortest results (see thistlethwaite) but the code is pretty easy to follow.
The final stage (pll) would probably benefit the most from being replaced with standard algorithms.
While technically this works under pwa/p2js, you should expect a blank screen for nearly 3 minutes.
-- -- demo\rosetta\rubik_cfop.exw -- -- Each stage uses a workspace of moves tried so far, ranked by score. -- We repeatedly take the best scoring so far and try more moves, storing -- those results in a second/new workspace. The THRESHOLD value below -- determines the minimum number we should examine before discarding a -- workspace and switching to the new (one move longer) one. We only ever -- switch on change of score, and obviously the first workspace is empty, -- and the next new workspace has a maximum of 12 entries (+/-90 by 6), -- both of which will force earlier switches. -- with javascript_semantics constant THRESHOLD = 100000 -- 100000 -- very slow (100s), best results -- 10000 -- 10000 -- slow (10s), reasonable results -- 1000 -- fast (1s), fairly poor results -- 100 -- (counter-productive/slower) string init =""" ---YYY-------- ---YYY-------- ---YYY-------- BBBRRRGGGOOO-- BBBRRRGGGOOO-- BBBRRRGGGOOO-- ------WWW----- ------WWW----- ------WWW----- """ -- numbering: -- 1..15: ---456--------\n -- 16..30: ---901--------\n -- U -- 31..45: ---456--------\n -- 46..60: 678901234567--\n -- 61..75: 123456789012--\n -- LFRB -- 76..90: 678901234567--\n -- 91..105: ------789-----\n -- 106..120:------234-----\n -- D -- 121..136:------789-----\n\n if length(init)!=136 then ?9/0 end if -- -- TIP: Wrap a cube with blank paper, and write -- the numbers on it, to derive these sets. -- constant centres = {20,62,65,68,71,113} constant edges = {{ 4, 5, 6,57,56,55}, -- ie YYY/OOO { 6, 21, 36,54,53,52}, -- YYY/GGG { 34, 35, 36,49,50,51}, -- YYY/RRR { 4, 19, 34,46,47,48}, -- YYY/BBB { 51, 66, 81,52,67,82}, -- RRR/GGG { 54, 69, 84,55,70,85}, -- GGG/OOO { 57, 72, 87,46,61,76}, -- OOO/BBB { 48, 63, 78,49,64,79}, -- BBB/RRR { 97, 98, 99,82,83,84}, -- WWW/GGG { 99,114,129,85,86,87}, -- WWW/OOO {127,128,129,78,77,76}, -- WWW/BBB { 97,112,127,81,80,79}} -- WWW/RRR constant corners = {{ 4, 57,46},{34,48, 49},{36,51,52},{ 6,54,55}, -- YOB/UBL YBR/UFL YRG/UFR YGO/UBL {76,129,87},{78,79,127},{81,82,97},{84,85,99}} -- BWO/DBL BRW/DFL RGW/DFR GOW/DFL constant facing_corners = {-16,-14,16,14}, -- (nb not 14,16) facing_edges = {-15, 1,15,-1}, fce = facing_corners&facing_edges, rotations = { -- up (clockwise): {{57,54,51,48}, -- clockwise corners {46,55,52,49}, -- anticlockwise corners {47,56,53,50}}, -- middle edges -- left {{ 4,49,127, 87}, {57,34, 79,129}, {19,64,128, 72}}, -- front {{34,52, 97, 78}, {48,36, 82,127}, {35,67,112, 63}}, -- right {{36,55,99,81}, {51, 6,85,97}, {21,70,98,66}}, -- back {{ 6,46,129,84}, {54, 4, 76,99}, { 5,61,114,69}}, -- down {{82,85,76,79}, {81,84,87,78}, {83,86,77,80}}} --Up/Left/Front/Right/Back/Down enum U=1,L=2,F=3,R=4,B=5,D=6,Dbl=#08,Shift=#10 constant U2 = U+Dbl, F2 = F+Dbl, /*R2 = R+Dbl, B2 = B+Dbl,*/ D2 = D+Dbl, Us = U+Shift, Fs = F+Shift, Bs = B+Shift, Rs = R+Shift, Ds = D+Shift enum CROSS,F2L,OLL,PLL integer f2l = 0 -- (28==done) integer edge_score = 0 -- (0..12 for f2l [as U cleared], -- 0..24 for oll and pll stages) function score(string cube, integer stage) integer res = 0, c, cc, k f2l = 0 for i=1 to length(centres) do c = centres[i] cc = cube[c] for j=1 to length(fce) do -- (the 8 next to c) k = c+fce[j] if cube[k]=cc then res += 1 f2l += (stage>CROSS and k>=61) end if end for end for -- give extra credit for edges paired with corners edge_score = 0 -- += (0|1|2) for the 12 edges: if stage>CROSS then for i=1 to length(edges) do sequence ei = edges[i] -- as 123 -- -- 456 -- then if {1,4}=={2,5} then edge_score += 1, -- plus if {2,5}=={3,6} then edge_score += 1. edge_score += (cube[ei[1]]=cube[ei[2]] and cube[ei[4]]=cube[ei[5]]) + (cube[ei[2]]=cube[ei[3]] and cube[ei[5]]=cube[ei[6]]) end for end if return res end function function oll_score(string cube) -- (should only be invoked if f2l==28) integer res = 0 -- (true if res=8) integer cu = centres[U] if cube[cu]!='Y' then ?9/0 end if for i=1 to length(fce) do integer fcei = fce[i] res += (cube[cu+fcei]='Y') end for return res end function function rotate_face(string cube, integer face) -- -- face is 1..6 for clockwise (ULFRBD), -- plus #08(Dbl) for a 180 (clockwise), -- plus #10(Shift) for anti-clockwise. -- integer dbl = 1+(and_bits(face,Dbl)=Dbl) bool cw = 1-floor(face/Shift) face = remainder(face,Dbl) integer cf = centres[face] sequence rf = {sq_add(facing_corners,cf), sq_add(facing_edges,cf)} &rotations[face] for d=1 to dbl do for i=1 to length(rf) do sequence rfi = rf[i] if cw then rfi = reverse(rfi) end if integer rfi1 = cube[rfi[1]] for j=1 to 3 do cube[rfi[j]] = cube[rfi[j+1]] end for cube[rfi[4]] = rfi1 end for end for return cube end function function apply_moves(string cube, sequence moves) for i=1 to length(moves) do cube = rotate_face(cube,moves[i]) end for return cube end function constant ULFRBD = "ULFRBD" function moves_to_string(sequence moves) -- convert eg {1,20,11} to "UR'F2" string res = "" integer l = length(moves) for i=1 to l do integer face = moves[i] integer dbl = and_bits(face,Dbl)=Dbl bool anticw = floor(face/Shift) face = remainder(face,Dbl) res &= ULFRBD[face] if dbl then res &= '2' elsif anticw then res &= '\'' end if end for res &=sprintf(" (%d move%s) ",{l,iff(l=1?"":"s")}) return res end function -- -- The seen dictionary. -- Without this, since it uses a breadth/highscore-first -- algorithm, after f2l (for instance) it would probably -- just do U and U' as the new high scores, forever. -- (The THRESHOLD constant mitigates that to some extent) -- integer seen = new_dict() function solve_stage(string cube, integer stage) atom t1 = time()+1 string moves = "", moves2 sequence workspace, w2, init integer wslen, high = 1, s, c2c = 0, o = 0 bool done if stage=CROSS then -- -- first, blank out all corners, and -- all edges without a white on them. -- for i=1 to length(rotations) do for j=1 to 2 do -- (just corners) for k=1 to 4 do cube[rotations[i][j][k]]='-' end for end for end for for i=1 to length(edges) do integer {?,m1,?,?,m2,?} = edges[i] if cube[m1]!='W' and cube[m2]!='W' then cube[m1] = '-' cube[m2] = '-' end if end for wslen = 8 s = score(cube,CROSS) done = (s=8) elsif stage=F2L then -- -- first, blank out all pieces with a yellow -- for i=1 to length(corners) do integer {c1,c2,c3} = corners[i] if cube[c1]='Y' or cube[c2]='Y' or cube[c3]='Y' then cube[c1] = '-' cube[c2] = '-' cube[c3] = '-' end if end for for i=1 to length(edges) do integer {?,m1,?,?,m2,?} = edges[i] if cube[m1]='Y' and cube[m2]='Y' then cube[m1] = '-' cube[m2] = '-' end if end for wslen = 57+12 s = score(cube,F2L) done = (f2l=28) else wslen = 77+24 s = score(cube,stage) if f2l!=28 then ?9/0 end if if stage=OLL then done = (oll_score(cube)=8) else -- (stage=PLL) done = (s=48) end if end if if not done then workspace = repeat({},wslen) w2 = deep_copy(workspace) init = cube workspace[high] = {""} destroy_dict(seen,justclear:=1) integer move_count = 1 while 1 do if workspace[high]={} then while high and workspace[high]={} do high -= 1 end while if high=0 or (stage!=CROSS and c2c>THRESHOLD) then move_count += 1 workspace = w2 w2 = repeat({},wslen) c2c = 0 high = wslen while workspace[high]={} do high -= 1 end while end if end if moves = workspace[high][1] workspace[high] = workspace[high][2..$] cube = apply_moves(init,moves) for face=U to D do -- (originally this loop did 180s as well, but that -- gave them far too much dominance, esp during pll. -- instead we now coalese those that survive a 90.) for m=0 to Shift by Shift do integer mi = face+m sequence cube2 = rotate_face(cube,mi) if getd_index(cube2,seen)=0 then putd(cube2,0,seen) s = score(cube2,stage) if stage=CROSS then done = (s=8) elsif stage=F2L then done = (f2l=28) else if f2l=28 then o = oll_score(cube2) else o = 0 end if if stage=OLL then done = (o=8) else done = (s=48) end if end if moves2 = moves if length(moves2) and moves2[$]=mi then moves2[$] = face+Dbl else moves2 &= mi end if if done then destroy_dict(seen,justclear:=1) return moves2 end if s += 1+edge_score*2+o w2[s] = append(w2[s],moves2) c2c += 1 end if end for end for if time()>t1 and platform()!=JS then printf(1,"working... %d moves, %d positions\r",{move_count,dict_size(seen)}) t1 = time()+1 if get_key()=#1B then exit end if end if end while end if return "" -- (already solved case) end function constant stage_desc = { "make cross", "solve first two layers", "orientate last layer", "permute last layer" } procedure main() string cube sequence moves integer total_moves = 0 atom t0 = time() -- "hardest case" from http://www.cube20.org moves = {F, Us, F2, Ds, B, U, Rs, Fs, L, Ds, Rs, Us, L, U, Bs, D2, Rs, F, U2, D2} cube = apply_moves(init,moves) if length(moves)<=20 then printf(1,"scramble: %s\n",{moves_to_string(moves)}) end if puts(1,substitute(cube,"-"," ")) for stage=CROSS to PLL do moves = solve_stage(cube, stage) total_moves += length(moves) cube = apply_moves(cube,moves) printf(1,"%s: %s\n",{stage_desc[stage],moves_to_string(moves)}) if length(moves) then puts(1,substitute(cube,"-"," ")) end if end for printf(1,"\nsolution of %d total moves found in %3.2fs\n",{total_moves,time()-t0}) end procedure main()
- Output:
The "hardest case" from http://www.cube20.org with a high threshold. You can try this manually. Disclaimer: the results are not always quite as good as this!
scramble: FU'F2D'BUR'F'LD'R'U'LUB'D2R'FU2D2 (20 moves)
ROB
BYG
GRO
YYOYYBYYRYYG
RBOBRGOGRGOB
WWOWWBWWRWWG
OGB
RWO
GBR
make cross: DLBRFL (6 moves)
BRB
YYG
YYY
ROBRBRGOYOGW
OBRBRYRGYGOB
RBYORGOGOBOW
WWW
WWW
GWG
solve first two layers: FUL'R'FLRF'LRB'R'U'BU'B'U'B (18 moves)
RYG
OYR
YYY
BYRGGOBYOYBY
BBBRRRGGGOOO
BBBRRRGGGOOO
WWW
WWW
WWW
orientate last layer: R'F'U'FUR (6 moves)
YYY
YYY
YYY
GGBRRGOOOBBR
BBBRRRGGGOOO
BBBRRRGGGOOO
WWW
WWW
WWW
permute last layer: RU'L'UR'U2LU'L'U2LU' (12 moves)
YYY
YYY
YYY
BBBRRRGGGOOO
BBBRRRGGGOOO
BBBRRRGGGOOO
WWW
WWW
WWW
solution of 42 total moves found in 81.33s
thistlethwaite
Translation/de-golf(hrumph) of Tomas Sirgedas' winning entry from http://tomas.rokicki.com/cubecontest as held in 2004.
Faster and shorter solutions (in most cases) than cfop, however probably nigh on impossible to debug/enhance...
-- -- demo\rosetta\rubik_tomas.exw -- with javascript_semantics function xor_string(string s) return xor_bits(s[1],xor_bits(s[2],iff(length(s)=3?s[3]:'!'))) end function function xor_all(sequence s) for i=1 to length(s) do s[i] = xor_string(s[i]) end for return s end function constant d1 = xor_all(split("UF DF UB DB UR DR UL DL FR FL BR BL UFR DBR UBL DFL DLB ULF DRF URB")) -- This is Mike Reid's notation, 12 sides then 8 corners, which may be rotated - hence we xor the -- characters for fast lookup. The above string represents a cube in the solved state. constant d2 = {18,12,17,15,0, 9,1,8,16,14,19,13,2,10,3,11,12,18,13,19,4,8,5,10, 14,16,15,17,6,11,7,9,17,12,19,14,6, 0,4, 2,18,15,16,13,1,7,3, 5} --?sort(d2): (0..11 appear twice, 12..19 appear thrice - edges/corners is pretty much all I can say) constant d3 = {13,16,15,1,3, 19,18,17,4,6} -- these apppear to be swapped during initialisation, dunno why... integer cur_phase, search_mode, history_idx sequence history_mov = repeat(0,48), history_rpt = repeat(0,48), depth_to_go, hash_table = repeat(repeat(6,6912),48) -- (hash_table can/should be preserved for different problems) sequence cubelet_pos = repeat(0,48), cubelet_twi = repeat(0,48) procedure rot(integer cur_phase) if cur_phase<4 then for i=0 to 3 do integer di = cur_phase*8+i+1, j = d2[di]+1, k = d2[di+4]+1 cubelet_twi[j] = mod(cubelet_twi[j]+2-mod(i,2),3) cubelet_twi[k] = xor_bits(cubelet_twi[k],cur_phase<2) end for end if for i=0 to 6 do integer di = cur_phase*8+i+1, j = d2[di+(i!=3)]+1, k = d2[di]+1 -- swap(cubelet[j]], cubelet[k]); {cubelet_pos[j],cubelet_pos[k]} = {cubelet_pos[k],cubelet_pos[j]} {cubelet_twi[j],cubelet_twi[k]} = {cubelet_twi[k],cubelet_twi[j]} end for end procedure function hashf() int ret = 0; switch cur_phase do case 0: for i=0 to 10 do ret += ret + cubelet_twi[i+1] end for return ret; case 1: for i=0 to 6 do ret = ret*3 + cubelet_twi[i+12+1] end for for i=0 to 10 do ret += ret + (cubelet_pos[i+1]>7) end for return ret-7; case 2: sequence inva = repeat(0,48), b = repeat(0,48) for i=0 to 7 do integer ci12p = cubelet_pos[i+12+1], ci12p3 = and_bits(ci12p,3) if ci12p<16 then inva[ci12p3+1] = ret ret += 1 else b[i-ret+1] = ci12p3 end if end for for i=0 to 6 do ret += ret + (cubelet_pos[i+1]>3); end for for i=0 to 6 do ret += ret + (cubelet_pos[i+12+1]>15); end for integer ib2 = xor_bits(inva[b[1]+1],inva[b[2]+1])*2, ib3 = xor_bits(inva[b[1]+1],inva[b[3]+1]), ib4 = xor_bits(inva[b[1]+1],inva[b[4]+1]) return ret*54 + ib2 + (ib3 > ib4) - 3587708 end switch for i=0 to 4 do ret *= 24; for cp=0 to 3 do for k=0 to cp-1 do if cubelet_pos[i*4+cp+1] < cubelet_pos[i*4+k+1] then ret += cp + iff(cp=3?cp:0) end if end for end for end for return floor(ret/2) end function function do_search(integer dpt) integer h = hashf(), q = (floor(cur_phase/2)*19+8)*power(2,7), hmq = mod(h,q)+1, hfq = floor(h/q)+1, d = (dpt < hash_table[cur_phase+1][hmq] or dpt < hash_table[cur_phase+4+1][hfq]) if d xor search_mode then if search_mode then if dpt <= depth_to_go[h+1] then return not h; else depth_to_go[h+1] = dpt; end if end if hash_table[cur_phase+1][hmq] = min(hash_table[cur_phase+1][hmq],dpt); hash_table[cur_phase+5][hfq] = min(hash_table[cur_phase+5][hfq],dpt); for k=0 to 5 do for i=0 to 3 do rot(k) if (k>=cur_phase*2 or i=1) and i<=2 then history_idx += 1 history_mov[history_idx] = k history_rpt[history_idx] = i if do_search(dpt-search_mode*2+1) then return 1 end if history_idx -= 1 end if end for end for end if return 0 end function function pack_moves() string moves = "" integer n = 0, curr, last, last_rpt if history_idx!=0 then -- add a dummy move to trigger the last move print: last = xor_bits(history_mov[history_idx],1) -- F<->B, etc history_idx += 1 history_mov[history_idx] = last history_rpt[history_idx] = 0 last = history_mov[1] last_rpt = 0 for i=1 to history_idx do curr = history_mov[i] if curr!=last then -- coalesce eg F1F2 to F' (unless you wanna fix do_search()!) if last_rpt then moves &= "FBRLUD"[last+1] & {"","2","'"}[last_rpt] n += 1 end if last = curr last_rpt = history_rpt[i]+1 else last_rpt = mod(last_rpt+history_rpt[i]+1,4) end if end for end if return {moves,n,iff(n=1?"":"s")} end function function tomas(sequence args) search_mode = 0 history_idx = 0 depth_to_go = repeat(0,5*power(2,20)) for i=0 to 19 do cubelet_pos[i+1] = i end for for i=0 to 3 do cur_phase = i {} = do_search(0) end for args = split(args) for i=0 to 19 do string s = args[i+1] -- (may be rotated, eg RU or UR) integer p = find(xor_string(s),d1) if p=0 then ?9/0 end if -- sensible message(bad args)? cubelet_pos[i+1] = p-1 int x = max(find('U',s), find('D',s)); cubelet_twi[i+1] = iff(x!=0 ? x-1 : s[1]>'F') end for for i=0 to 4 do integer j = d3[i+1]+1, k = d3[i+6]+1 -- swap(cubelet[j], cubelet[k]); {cubelet_pos[j],cubelet_pos[k]} = {cubelet_pos[k],cubelet_pos[j]} {cubelet_twi[j],cubelet_twi[k]} = {cubelet_twi[k],cubelet_twi[j]} end for search_mode = 1; for cp=0 to 3 do cur_phase = cp for i=0 to 19 do if do_search(i) then exit end if end for end for return pack_moves() end function printf(1,"%s (%d move%s)\n",tomas("UL DL RF UB FD BR DB UF DR UR BL FL FDR BLU DLB URB RUF FLD BRD FUL"))
- Output:
UF'R'FB2R2B2LD2L2DLR2U'F2UF2U2F2L2UF2DF2U2R2U2R2B2D2R2F2L2B2D2 (35 moves)
The distributed copy of demo\rosetta\rubik_cfop.exw also contains routines to convert between my 136-character cube and reid notation, and demo\rosetta\rubik_tomas.exw also contains the full 100-long test set from the original competition.
Python
import time
import sys
ai = list[int]
applicable_moves = [0, 262143, 259263, 74943, 74898]
phase = 0
affected_cubies = [
[0, 1, 2, 3, 0, 1, 2, 3], # U
[4, 7, 6, 5, 4, 5, 6, 7], # D
[0, 9, 4, 8, 0, 3, 5, 4], # F
[2, 10, 6, 11, 2, 1, 7, 6], # B
[3, 11, 7, 9, 3, 2, 6, 5], # L
[1, 8, 5, 10, 1, 0, 4, 7], # R
]
def btoi(b: bool) -> int:
"""Converts a boolean to an integer (1 for True, 0 for False)."""
return 1 if b else 0
def slice_to_ai(s: list[int]) -> ai:
"""Converts a slice to an ai (list of 40 ints)."""
a: ai = [0] * 40
a[:len(s)] = s
for i in range(len(s), 40):
a[i] = -1
return a
def apply_move(move: int, state: ai) -> ai:
"""Applies a given move to the given state."""
turns = move % 3 + 1
face = move // 3
new_state = state[:] # Create a copy of the state
for _ in range(turns):
old_state = new_state[:]
for i in range(8):
is_corner = btoi(i > 3)
target = affected_cubies[face][i] + is_corner * 12
temp = i + 1
if (i & 3) == 3:
temp = i - 3
killer = affected_cubies[face][temp] + is_corner * 12
orientation_delta = 0
if i < 4:
orientation_delta = btoi(face > 1 and face < 4)
elif face < 2:
orientation_delta = 0
else:
orientation_delta = 2 - (i & 1)
new_state[target] = old_state[killer]
new_state[target + 20] = (old_state[killer + 20] + orientation_delta) % (2 + is_corner)
return new_state
def inverse(move: int) -> int:
"""Calculates the inverse of a given move."""
return move + 2 - 2 * (move % 3)
def id(state: ai) -> ai:
"""Calculates the ID of a given state based on the current phase."""
global phase
#--- Phase 1: Edge orientations.
if phase < 2:
return slice_to_ai(state[20:32])
#-- Phase 2: Corner orientations, E slice edges.
if phase < 3:
result = state[31:40][:] # Copy the relevant slice
for e in range(12):
result[0] |= (state[e] // 8) << e
return slice_to_ai(result)
#--- Phase 3: Edge slices M and S, corner tetrads, overall parity.
if phase < 4:
result = [0, 0, 0]
for e in range(12):
temp = 2
if state[e] <= 7:
temp = state[e] & 1
result[0] |= temp << (2 * e)
for c in range(8):
result[1] |= ((state[c + 12] - 12) & 5) << (3 * c)
for i in range(12, 19):
for j in range(i + 1, 20):
result[2] ^= btoi(state[i] > state[j])
return slice_to_ai(result)
#--- Phase 4: The rest.
return state
def main():
"""Main function to solve the cube."""
global phase
start_time = time.time()
aggregate_moves = 0
#--- Define the goal.
goal = [
"UF", "UR", "UB", "UL", "DF", "DR", "DB", "DL", "FR", "FL", "BR", "BL",
"UFR", "URB", "UBL", "ULF", "DRF", "DFL", "DLB", "DBR",
]
#--- Load dataset (file name should be passed as a command line argument).
if len(sys.argv) != 2:
print("the file name should be passed as a command line argument")
sys.exit(1)
try:
with open(sys.argv[1], 'r') as file:
lines = file.readlines()
except FileNotFoundError:
print(f"Error: File '{sys.argv[1]}' not found.")
sys.exit(1)
except Exception as e:
print(f"Error: An error occurred while reading the file: {e}")
sys.exit(1)
line_count = 0
for line in lines:
inputs = line.strip().split()
line_count += 1
phase = 0
total_moves = 0
#--- Prepare current (start) and goal state.
current_state: ai = [0] * 40
goal_state: ai = [0] * 40
for i in range(20):
#--- Goal state.
goal_state[i] = i
#--- Current (start) state.
cubie = inputs[i]
current_state[i+20] = 0
while True:
idx = -1
for c in range(len(goal)):
if goal[c] == cubie:
idx = c
break
if idx >= 0:
current_state[i] = idx
else:
current_state[i] = 20
if current_state[i] != 20:
break
cubie = cubie[1:] + cubie[:1]
current_state[i+20] += 1
current_state[i+20] %= (2 + (i > 11))
#--- Dance the funky Thistlethwaite..
phase = 0
while phase < 4:
phase += 1
#--- Compute ids for current and goal state, skip phase if equal.
current_id = id(current_state)
goal_id = id(goal_state)
if current_id == goal_id:
continue
#--- Initialize the BFS queue.
q = [current_state[:], goal_state[:]]
#--- Initialize the BFS tables.
predecessor: dict[tuple[int], tuple[int]] = {}
direction: dict[tuple[int], int] = {}
last_move: dict[tuple[int], int] = {}
direction[tuple(id(current_state))] = 1
direction[tuple(id(goal_state))] = 2
#--- Dance the funky bidirectional BFS...
while q:
#--- Get state from queue, compute its ID and get its direction.
old_state = q.pop(0)
old_id = tuple(id(old_state)) # needs to be hashable
old_dir = direction[old_id]
#--- Apply all applicable moves to it and handle the new state.
for move in range(18):
if (applicable_moves[phase] & (1 << move)) != 0:
#--- Apply the move.
new_state = apply_move(move, old_state)
new_id = tuple(id(new_state))
new_dir = direction.get(new_id, 0)
#--- Have we seen this state (id) from the other direction already?
#--- I.e. have we found a connection?
if (new_dir != 0) and (new_dir != old_dir):
#--- Make oldId represent the forwards
#--- and newId the backwards search state.
if old_dir > 1:
new_id, old_id = old_id, new_id
move = inverse(move)
#--- Reconstruct the connecting algorithm.
algorithm = [move]
while old_id != tuple(id(current_state)):
algorithm.insert(0, last_move[old_id])
old_id = predecessor[old_id]
while new_id != tuple(id(goal_state)):
algorithm.append(inverse(last_move[new_id]))
new_id = predecessor[new_id]
#--- Print and apply the algorithm.
for i in range(len(algorithm)):
print("UDFBLR"[algorithm[i] // 3], algorithm[i] % 3 + 1, end=" ")
total_moves += 1
current_state = apply_move(algorithm[i], current_state)
#--- Jump to the next phase.
goto_next_phase = True
break
else:
continue
break # inner loop break, goto the next phase.
print(f" (moves {total_moves})")
aggregate_moves += total_moves
end_time = time.time()
elapsed_time = (end_time - start_time) * 1000
print("\nAverage number of moves =", aggregate_moves / line_count)
print("\nAverage time =", elapsed_time / line_count, "milliseconds")
if __name__ == "__main__":
main()
Raku
This is a translation of the Perl competition code, by Stefan Pochmann.
# 20230401 Raku programming solution
my @data=<UL DL RF UB FD BR DB UF DR UR BL FL FDR BLU DLB URB RUF FLD BRD FUL>;
my @goal=<UF UR UB UL DF DR DB DL FR FL BR BL UFR URB UBL ULF DRF DFL DLB DBR>;
sub printAlg ($x) { #--- Algorithms.
my $algo = 'x0F0DN0EB0H00N0B0R0KB0L0QB0G1A1M11C1I1E1OFI2'~
'DN2IEOB2H22N2B2GRM2MKGB2GLM2QBK23D3EN3E3B3N33H3';
$algo ~~ s:g
!(\D*)(\d)!{
$0 ~ <ILOFCLKHRNQCL OBIRALOBIRAL CEJHPEIMIG DFNRHRDKMQ>[$1]
# ~ [~] reverse map { TR/G..R/M..X/ }, " $0".comb }!;
~ " $0".trans( ['G'..'R'] => ['M'..'X'] ).flip }!;
my @algo = $algo.split: ' ';
#`[[[ or use the following to save some CPU power and time # my @algo = <
xILOFCLKHRNQCLx FILOFCLKHRNQCLF DNILOFCLKHRNQCLTD EBILOFCLKHRNQCLBE
HILOFCLKHRNQCLN ILOFCLKHRNQCL NILOFCLKHRNQCLT BILOFCLKHRNQCLB
RILOFCLKHRNQCLX KBILOFCLKHRNQCLBQ LILOFCLKHRNQCLR QBILOFCLKHRNQCLBW
GOBIRALOBIRALM AOBIRALOBIRALA MOBIRALOBIRALS OBIRALOBIRAL
COBIRALOBIRALC IOBIRALOBIRALO EOBIRALOBIRALE OFICEJHPEIMIGOFU
DNCEJHPEIMIGTD IEOBCEJHPEIMIGBUEO HCEJHPEIMIGN CEJHPEIMIG
NCEJHPEIMIGT BCEJHPEIMIGB GRMCEJHPEIMIGSXM MKGBCEJHPEIMIGBMQS
GLMCEJHPEIMIGSRM QBKCEJHPEIMIGQBW DFNRHRDKMQ DDFNRHRDKMQD
ENDFNRHRDKMQTE EDFNRHRDKMQE BDFNRHRDKMQB NDFNRHRDKMQT
DFNRHRDKMQ HDFNRHRDKMQN >; #]]]
say [~] my @moves = map {
substr('UDFBLR', (my $ord=.ord-65) % 6, 1) ~ substr("2 '", $ord div 6, 1)
}, @algo[$x].comb;
return @moves.elems
}
my $total = 0;
for 1..18 -> $x { #--- Orient.
until @data[$x] ∈ @goal {
$total += printAlg $x;
@data[$x] ~~ s/(.)(.+)/$1$0/;
@data[$x < 12 ?? 0 !! 19] ~~ s/(.+)(.)/$1$0/;
}
}
for ^41 { #--- Permute.
for ^20 -> $w {
next if @data[$w] eq @goal[$w];
my $x = 0;
until @data[$w] eq @goal[$x] { $x++ };
$x < 12 ?? ( @data[0,$x,12,15] = @data[$x,0,15,12] )
!! ( @data[12,$x] = @data[$x,12] );
$total += printAlg $x+=18 and last
}
}
say "\nTotal number of moves : $total";
- Output:
B2D'F R F'R2F2R L D R'D'L'F2R DB2 D F R F'R2F2R L D R'D'L'F2R D' U F'D2F R'U2R F'D2F R'U2R U' U2F'D2F R'U2R F'D2F R'U2R U2 U2F'D2F R'U2R F'D2F R'U2R U2 F2F'D2F R'U2R F'D2F R'U2R F2 F F'D2F R'U2R F'D2F R'U2R F' F F'D2F R'U2R F'D2F R'U2R F' L2F'D2F R'U2R F'D2F R'U2R L2 L2F'D2F R'U2R F'D2F R'U2R L2 F L2F'D2F2L2B D B'L2F U'F U D2FL2F' B2D'F2L2B D B'L2F U'F U DB2 U R'U'F2L2B D B'L2F U'F U URU' F2L2B D B'L2F U'F U U R U'F2L2B D B'L2F U'F U UR'U' L'D2L F2L2B D B'L2F U'F U L'D2L U'L U D2F2L2B D B'L2F U'F U D2U'L'U F'R2F F2L2B D B'L2F U'F U F'R2F D2F2L2B D B'L2F U'F U D2 B2B2R2D'R'D R'B2L U'L'B2 L2D'B2R2D'R'D R'B2L U'L'DL2 B2R2D'R'D R'B2L U'L' D B2R2D'R'D R'B2L U'L'D' L2B2R2D'R'D R'B2L U'L'L2 D2B2R2D'R'D R'B2L U'L'D2 Total number of moves : 352
Rust
/**********************************************************************
*
* A cube 'state' is an int array with 40 entries, the first 20
* are a permutation of {0,...,19} and describe which cubie is at
* a certain position (regarding the input ordering). The first
* twelve are for edges, the last eight for corners.
*
* The last 20 entries are for the orientations, each describing
* how often the cubie at a certain position has been turned
* counterclockwise away from the correct orientation. Again the
* first twelve are edges, the last eight are corners. The values
* are 0 or 1 for edges and 0, 1 or 2 for corners.
*
**********************************************************************/
use std::collections::{HashMap, VecDeque};
use std::env;
use std::fs::File;
use std::io::{self, BufRead, BufReader};
use std::time::Instant;
// Type alias for the cube state array. Using i32 for general integers.
// Note: Arrays of size > 32 are not `Copy` by default in Rust.
// This impacts how they are passed and stored (moves instead of copies).
type Ai = [i32; 40];
// Constants corresponding to Go's global variables.
// Using `static` for arrays initialized at runtime (though these are effectively const).
static APPLICABLE_MOVES: [u32; 5] = [0, 262143, 259263, 74943, 74898];
// Note: `phase` is handled locally in `main` as it changes per puzzle.
static AFFECTED_CUBIES: [[usize; 8]; 6] = [
[0, 1, 2, 3, 0, 1, 2, 3], // U
[4, 7, 6, 5, 4, 5, 6, 7], // D
[0, 9, 4, 8, 0, 3, 5, 4], // F
[2, 10, 6, 11, 2, 1, 7, 6], // B
[3, 11, 7, 9, 3, 2, 6, 5], // L
[1, 8, 5, 10, 1, 0, 4, 7], // R
];
// Equivalent to Go's btoi. Rust can cast bool to integer.
#[inline(always)]
fn btoi(b: bool) -> i32 {
b as i32
}
// Helper function to create an Ai from a slice, padding with -1.
// Similar purpose to Go's sliceToAi, but needed within the `id` function logic.
fn slice_to_ai(s: &[i32]) -> Ai {
let mut a: Ai = [-1; 40]; // Initialize with sentinel value
let len = std::cmp::min(s.len(), 40);
a[..len].copy_from_slice(&s[..len]);
a
}
// Helper function to create an Ai from a Vec<i32>
fn vec_to_ai(v: Vec<i32>) -> Ai {
slice_to_ai(&v)
}
// Applies a move to the state. Takes ownership of `state` and returns a new `Ai`.
fn apply_move(move_code: i32, state: Ai) -> Ai {
let mut turns = move_code % 3 + 1;
let face = (move_code / 3) as usize;
let mut current_state = state; // Take ownership
while turns != 0 {
turns -= 1;
let old_state = current_state; // Copy happens here if needed (Ai is not Copy)
// If Ai were Copy, this would be a cheap copy.
// Since it's not, this is a move/clone, which is fine.
for i in 0..8 {
let is_corner = btoi(i > 3);
let target = AFFECTED_CUBIES[face][i] + (is_corner * 12) as usize;
// Calculate index 'killer' (source cubie)
let temp_idx = i + 1;
let killer_idx = if (i & 3) == 3 { i - 3 } else { temp_idx };
let killer = AFFECTED_CUBIES[face][killer_idx] + (is_corner * 12) as usize;
let orientation_delta = match i {
// Edges
0..=3 => {
// U/D face affects edge orientation (0), others (1)
btoi(face > 1 && face < 4) // F=2, B=3, L=4, R=5 in Go; F=2, B=3, L=4, R=5 here
}
// Corners
_ => {
if face < 2 { // U/D
0
} else { // F/B/L/R
2 - (i & 1) as i32 // 1 for i=4,6; 2 for i=5,7 in Go -> 2 - (i&1) -> 1 for i=5,7; 2 for i=4,6. Needs check.
// Go: i=4 -> 2, i=5 -> 1, i=6 -> 2, i=7 -> 1
// Rust: i=4 -> 2-(4&1)=2-0=2. i=5 -> 2-(5&1)=2-1=1. i=6 -> 2-(6&1)=2-0=2. i=7 -> 2-(7&1)=2-1=1. OK.
}
}
};
current_state[target] = old_state[killer];
// Orientation update needs modulo only on the *last* turn
current_state[target + 20] = old_state[killer + 20] + orientation_delta;
if turns == 0 {
current_state[target + 20] %= 2 + is_corner;
}
}
}
current_state
}
// Calculates the inverse move.
fn inverse(move_code: i32) -> i32 {
move_code + 2 - 2 * (move_code % 3)
}
// Computes the phase-specific ID for a state.
// Takes a reference to avoid moving the state.
fn id(state: &Ai, phase: usize) -> Ai {
match phase {
// Phase 1: Edge orientations.
1 => {
// Get slice of edge orientations
slice_to_ai(&state[20..32])
}
// Phase 2: Corner orientations, E slice edges (edges 8,9,10,11).
2 => {
// Corner orientations (8) + 1 int for E slice edges
let mut result = Vec::with_capacity(9);
// E slice edges (represented by a single integer)
let mut e_slice_val = 0;
for e in 0..12 {
// Check if edge e (state[e]) is in the E slice (original positions 8, 9, 10, 11)
if state[e] >= 8 && state[e] <= 11 {
e_slice_val |= 1 << e; // Set bit if edge e is in E slice
}
}
result.push(e_slice_val);
// Corner orientations
result.extend_from_slice(&state[32..40]); // Add corner orientations
vec_to_ai(result) // Pad with -1
}
// Phase 3: M and S slice edges, corner tetrads, overall parity.
3 => {
let mut result = vec![0; 3]; // [M/S slice, tetrads, parity]
// M slice edges (4,5,6,7) and S slice edges (0,2,8,10 -> F/B layer edges not L/R)
// Represented as 0, 1, or 2 based on slice membership.
for e in 0..12 {
// Edge cubie `state[e]` original position
let original_pos = state[e];
let slice_val = if original_pos >= 4 && original_pos <= 7 { // M slice
1
} else if original_pos >= 8 && original_pos <= 11 { // E slice (already handled in phase 2) -> value 2?
2 // Use 2 for E slice? No, Go code uses 0/1/2 based on *position* e
// Go code: `state[e] <= 7 ? state[e] & 1 : 2` ???
// Let's re-read Go: `result[0] |= ((state[e] > 7) ? 2 : state[e] & 1) << (2*e)`
// It seems to encode the *slice* the cubie at *position* e belongs to.
// If original position state[e] is 0..7 (U/D layer), store low bit (0 or 1).
// If original position state[e] is 8..11 (E layer), store 2.
// This seems wrong based on descriptions. Let's trust the linked C++ code's comment if available, or typical Thistlethwaite.
// Typical Phase 3: E slice edges solved, M slice edges (4,5,6,7) correct positions, S slice edges (F/B edges 0,2,8,10) correct positions.
// Let's assume the Go code intends to check *if the cubie currently at position e* belongs to the M slice (value 1) or E slice (value 2).
// M slice original positions: FR(8), FL(9), BR(10), BL(11) ?? No, that's E slice.
// M slice original positions: UR(1), UB(2), DR(5), DB(6) ?? No... URF(12)..?
// Let's stick to the common definition: Edges 4,5,6,7 must be in the M slice positions (4,5,6,7).
// And parity check. And corner orbits.
// Let's re-implement based on common Phase 3 goals.
// Let's retry the Go code logic interpretation:
// For each edge position `e` (0..11):
// `cubie = state[e]` (the original cubie at this position)
// If `cubie <= 7` (it's a U or D layer edge originally): encode `cubie & 1` (0 for UF/UB/DF/DB, 1 for UR/UL/DR/DL)
// If `cubie > 7` (it's an E layer edge originally): encode `2`
// Store this 2-bit value for each position `e`.
let cubie_original_pos = state[e];
let val = if cubie_original_pos <= 7 { cubie_original_pos & 1 } else { 2 };
result[0] |= val << (2 * e);
} else { // cubie_original_pos >= 8 && cubie_original_pos <= 11 (E slice edge)
2
};
result[0] |= slice_val << (2 * e as u32);
}
// Corner orbits/tetrads: Check if corner `c` (state[c+12]) is in its orbit.
// Orbit 0: UFR(12), UBL(14), DRF(16), DLB(18) (even permutation indices)
// Orbit 1: URB(13), ULF(15), DFL(17), DBR(19) (odd permutation indices)
// Check parity of the corner's original position index.
for c in 0..8 {
let corner_original_pos = state[c + 12]; // Original position of corner at c+12
// Original index 12..19 -> check (corner_original_pos - 12) % 2
result[1] |= ((corner_original_pos - 12) & 1) << c; // Store 0 or 1 based on orbit
// Go code: `result[1] |= ((state[c+12]-12)&5) << (3*c)` -> This is different, uses 3 bits? And `& 5` (101b)? Maybe tetrad identity? Let's use the Go code's way.
//result[1] |= ((state[c + 12] - 12) & 5) << (3 * c as u32); // Go code version
}
// Re-checking Go code: `result[1] |= ((state[c+12]-12)&5) << (3*c)` is likely a typo or misunderstanding.
// A common Phase 3 goal is corner permutation parity within orbits (tetrads). Let's stick to the orbit parity bit.
//result[1] |= ((state[c + 12] - 12) & 1) << c;
// Re-re-checking Go code: result[1] |= ((state[c+12] - 12) & 5) << (3 * c). The & 5 (101 binary) doesn't make sense for simple orbit parity.
// Let's assume the Go code is doing something specific, maybe related to corner pairs. Let's implement it directly for now.
for c in 0..8 {
result[1] |= ((state[c+12] - 12) & 5) << (3 * c as u32);
}
// Overall permutation parity (corners + edges)
// Calculate inversions for corners (12..19) and edges (0..11) separately.
let mut parity = 0;
for i in 0..19 { // Check both edges and corners
for j in (i + 1)..20 {
if state[i] > state[j] {
parity ^= 1;
}
}
}
result[2] = parity;
// Go code only checks 12..19 vs 12..19? `for i:=12; i<19; i++ { for j:=i+1; j<20; j++ { ... } }`
// This calculates only the corner permutation parity. Standard Thistlethwaite usually needs total parity or edge parity.
// Let's implement the Go version exactly.
result[2] = 0; // Reset parity calculation
for i in 12..19 {
for j in (i + 1)..20 {
if state[i] > state[j] {
result[2] ^= 1;
}
}
}
vec_to_ai(result) // Pad with -1
}
// Phase 4: The rest (full state).
4 => {
// Return the full state as the ID (already unique)
state.clone() // Clone since Ai is not Copy
}
_ => panic!("Invalid phase"),
}
}
fn main() -> io::Result<()> {
let start_time = Instant::now();
let mut aggregate_moves = 0;
let mut line_count = 0;
// Define the goal state configuration names.
const GOAL_STR: [&str; 20] = [
"UF", "UR", "UB", "UL", "DF", "DR", "DB", "DL", "FR", "FL", "BR", "BL", // Edges 0-11
"UFR", "URB", "UBL", "ULF", "DRF", "DFL", "DLB", "DBR", // Corners 12-19
];
// --- Load dataset (file name should be passed as a command line argument). ---
let args: Vec<String> = env::args().collect();
if args.len() != 2 {
eprintln!("Usage: {} <filename>", args.get(0).map_or("program", |s| s.as_str()));
// Use a more specific error type if desired, but exiting works.
std::process::exit(1);
}
let filename = &args[1];
let file = File::open(filename)?;
let reader = BufReader::new(file);
// --- Process each line (puzzle) ---
for line_result in reader.lines() {
let line = line_result?;
let inputs: Vec<&str> = line.split_whitespace().collect();
if inputs.len() < 20 {
eprintln!("Skipping invalid line: {}", line);
continue;
}
line_count += 1;
let mut phase = 0; // Reset phase for each puzzle
let mut total_moves = 0;
// --- Prepare current (start) and goal state. ---
let mut current_state: Ai = [0; 40];
let mut goal_state: Ai = [0; 40]; // Goal state permutation and orientation
for i in 0..20 {
// Goal state: identity permutation, zero orientation
goal_state[i] = i as i32;
goal_state[i + 20] = 0; // Orientation is 0
// Current (start) state: parse from input
let mut cubie = inputs[i].to_string(); // Mutable string for rotation
let mut orientation = 0;
loop {
// Find the index of the cubie in the goal state configuration
if let Some(idx) = GOAL_STR.iter().position(|&s| s == cubie) {
current_state[i] = idx as i32;
current_state[i + 20] = orientation;
break;
} else {
// If not found, rotate the cubie string and increment orientation
// Edge rotation (2 chars): "UR" -> "RU"
// Corner rotation (3 chars): "UFR" -> "FRU" -> "RUF"
if cubie.len() > 1 {
let first_char = cubie.remove(0);
cubie.push(first_char);
orientation += 1;
// Check for infinite loops (shouldn't happen with valid input)
let max_rots = if cubie.len() == 2 { 2 } else { 3 };
if orientation >= max_rots{
eprintln!("Error: Could not identify cubie '{}' from input '{}' at pos {}", inputs[i], line, i);
// Consider how to handle this error - skip line or panic?
// Let's default to an invalid state marker like -1, though the original Go might implicitly fail later.
current_state[i] = -1; // Mark as invalid
current_state[i+20] = -1;
break; // Break the inner loop
}
} else {
eprintln!("Error: Invalid cubie format '{}' from input '{}'", cubie, line);
current_state[i] = -1; // Mark as invalid
current_state[i+20] = -1;
break; // Break the inner loop
}
}
}
// If any cubie failed parsing, skip the line maybe?
if current_state[i] == -1 {
eprintln!("Skipping line due to parsing error: {}", line);
// Need a way to break the outer loop or skip processing this line
// Using continue 'outer? No, let's just check after the loop.
}
}
// Check if any cubie failed parsing before proceeding
if current_state[0..20].iter().any(|&x| x == -1) {
continue; // Skip to next line
}
// --- Dance the funky Thistlethwaite.. ---
'next_phase: loop {
phase += 1;
if phase >= 5 {
break; // Finished all phases
}
// Compute ids for current and goal state, skip phase if equal.
// Clone is necessary because `id` returns Ai which is not Copy.
let current_id = id(¤t_state, phase);
let goal_id = id(&goal_state, phase);
if current_id == goal_id {
// println!("Phase {} skipped", phase); // Debug print
continue 'next_phase;
}
// println!("Phase {} starting", phase); // Debug print
// --- Initialize the BFS queue. ---
let mut q: VecDeque<Ai> = VecDeque::new();
q.push_back(current_state); // Move ownership to queue
q.push_back(goal_state); // Move ownership to queue
// --- Initialize the BFS tables. ---
// Key: Phase ID (Ai), Value: Predecessor ID (Ai) / Direction (i32) / Last Move (i32)
let mut predecessor: HashMap<Ai, Ai> = HashMap::new();
let mut direction: HashMap<Ai, i32> = HashMap::new();
let mut last_move: HashMap<Ai, i32> = HashMap::new();
// Mark starting points
direction.insert(current_id, 1); // Forward direction = 1
direction.insert(goal_id, 2); // Backward direction = 2
// --- Dance the funky bidirectional BFS... ---
while let Some(old_state) = q.pop_front() { // Takes ownership from queue
// Compute its ID and get its direction.
let old_id = id(&old_state, phase); // Pass by reference
// We need old_id owned for map lookups/insertions if it wasn't already there.
// `direction.get` borrows, which is fine.
let old_dir = *direction.get(&old_id).unwrap_or(&0); // Should always exist if state is in queue
if old_dir == 0 {
eprintln!("State found in queue but not in direction map - logic error?");
continue; // Should not happen
}
// Apply all applicable moves to it and handle the new state.
for move_code in 0..18 {
// Check if move is applicable in this phase
if (APPLICABLE_MOVES[phase] & (1 << move_code)) != 0 {
// Apply the move. apply_move consumes old_state if not Copy.
// Since Ai is not Copy, we need to clone old_state if we need it again.
// We *do* need old_id later, but id(&old_state) was already called.
// apply_move takes Ai by value, consumes it, returns new Ai.
let new_state = apply_move(move_code, old_state); // old_state moved here
let new_id = id(&new_state, phase); // Pass ref to new_state
// Look up direction of the new state's ID
let new_dir_entry = direction.entry(new_id.clone()); // Use entry API
// new_id cloned here for potential insertion
match new_dir_entry {
std::collections::hash_map::Entry::Occupied(entry) => {
// Seen this ID before. Check if it's from the other direction.
let new_dir = *entry.get();
if new_dir != 0 && new_dir != old_dir {
// --- Connection found! ---
let mut path1_id;
let mut path2_id;
let mut meeting_move;
// Make old_id the forward state, new_id the backward state
if old_dir == 1 {
path1_id = old_id.clone(); // start from old_id (forward)
path2_id = new_id.clone(); // start from new_id (backward)
meeting_move = move_code;
} else { // old_dir == 2
path1_id = new_id.clone(); // start from new_id (forward)
path2_id = old_id.clone(); // start from old_id (backward)
meeting_move = inverse(move_code);
}
// Reconstruct the path from forward start (current_id) to path1_id
let mut algorithm: Vec<i32> = Vec::new();
let mut current_trace_id = path1_id; // Clone needed
while current_trace_id != current_id {
// Need to clone the ID found in the map if Ai is not Copy
let pred_id = predecessor.get(¤t_trace_id).expect("Predecessor path broken").clone();
let move_taken = *last_move.get(¤t_trace_id).expect("Last move path broken");
algorithm.insert(0, move_taken); // Prepend move
current_trace_id = pred_id; // Move to predecessor
}
// Add the meeting move
algorithm.push(meeting_move);
// Reconstruct the path from backward start (goal_id) to path2_id
current_trace_id = path2_id; // Clone needed
while current_trace_id != goal_id {
// Need to clone the ID found in the map if Ai is not Copy
let pred_id = predecessor.get(¤t_trace_id).expect("Predecessor path broken").clone();
let move_taken = *last_move.get(¤t_trace_id).expect("Last move path broken");
algorithm.push(inverse(move_taken)); // Append inverse move
current_trace_id = pred_id; // Move to predecessor
}
// Apply and print the algorithm moves
for &alg_move in &algorithm {
print!(
"{}{}",
"UDFBLR".chars().nth((alg_move / 3) as usize).unwrap(),
alg_move % 3 + 1
);
print!(" ");
total_moves += 1;
// Apply move to the actual current_state (the one outside BFS)
current_state = apply_move(alg_move, current_state);
}
// Jump to the next phase
continue 'next_phase;
}
// Else: Seen this ID from the same direction, ignore.
}
std::collections::hash_map::Entry::Vacant(entry) => {
// --- Never seen this state (id) before, visit it. ---
entry.insert(old_dir); // Set direction for new_id
q.push_back(new_state); // Add state to queue (new_state moved here)
// Store predecessor and last move (need owned IDs)
// old_id was calculated from old_state before it was moved/consumed by apply_move.
predecessor.insert(new_id.clone(), old_id.clone()); // Clone IDs for map ownership
last_move.insert(new_id, move_code); // new_id moved here
}
}
// If we reach here, new_state was either processed or queued.
// Need to restore old_state for the next iteration of the move loop if Ai is not Copy.
// But apply_move consumed it. We need to clone *before* calling apply_move.
// Let's refactor the loop slightly.
// Refactored approach:
/*
let old_state_ref = &old_state; // Keep borrowing old_state
let old_id = id(old_state_ref, phase); // Use reference
let old_dir = *direction.get(&old_id).unwrap();
for move_code in 0..18 {
if (APPLICABLE_MOVES[phase] & (1 << move_code)) != 0 {
let new_state = apply_move(move_code, old_state.clone()); // Clone old_state here
let new_id = id(&new_state, phase);
// ... rest of logic using new_state, new_id, old_id (cloned if needed for map keys) ...
// If new_id is added to maps/queue, new_state is moved.
}
}
*/
// The original structure where apply_move takes ownership and old_state is implicitly
// regenerated by getting the next item from the queue is more complex with non-Copy types.
// Let's stick to the clone-before-apply approach. Redoing the loop structure.
// ****** Reverting to the original loop structure for now, assuming the logic handles ownership implicitly ******
// The tricky part is `old_id` must remain valid after `old_state` is moved into `apply_move`.
// Since `old_id` is an `Ai` itself (not Copy), we must clone it *before* `old_state` is moved.
// Let's adjust where cloning happens.
// Re-entry point after potential continue 'next_phase or map insertion.
// Need the *original* `old_state` for the next iteration of the `move_code` loop.
// This means `apply_move` *must not* consume `old_state`, or we need to clone it inside the loop.
// Let's modify `apply_move` to take a reference or ensure cloning happens.
// Easiest is to clone inside the loop: `apply_move(move_code, old_state.clone())`
// Corrected loop structure:
/*
while let Some(old_state) = q.pop_front() {
let old_id = id(&old_state, phase); // Calculate ID once
let old_dir = *direction.get(&old_id).expect("Should be in map");
for move_code in 0..18 {
if (APPLICABLE_MOVES[phase] & (1 << move_code)) != 0 {
let new_state = apply_move(move_code, old_state.clone()); // CLONE HERE
let new_id = id(&new_state, phase);
// ... rest of map lookup, insertion, path reconstruction logic ...
// Use new_id.clone() and old_id.clone() when inserting into maps.
// Move `new_state` into queue if needed.
} // end move loop
} // end state processing
} // end while let Some
*/
// Sticking with the already written logic flow, adjusting clones as needed.
// Need `old_state` back for the next move_code iteration.
// The `apply_move` consumed it. This loop structure is flawed for non-Copy Ai.
// Must clone `old_state` before passing to `apply_move`.
// Let's restructure the loop logic again.
} // end if applicable move
} // end for move_code loop
// We need `old_state` again here if the loop continues? No, loop ends when queue empty or solution found.
// *** Correction Point ***
// The loop needs `old_state` available for *every* `move_code`.
// `apply_move` consuming it is the issue.
// Solution: Clone `old_state` inside the `move_code` loop *before* calling `apply_move`.
} // end while let Some(old_state) = q.pop_front()
// If the queue becomes empty and we haven't found a connection, something is wrong (unsolvable?)
// This algorithm assumes the input state is solvable.
eprintln!("Warning: BFS queue emptied in phase {} without finding solution path.", phase);
} // end 'next_phase loop
println!(" (moves {})", total_moves);
aggregate_moves += total_moves;
} // end loop over lines
// --- Print final statistics ---
let end_time = Instant::now();
let elapsed_ms = end_time.duration_since(start_time).as_millis();
if line_count > 0 {
println!(
"\nAverage number of moves = {:.2}",
aggregate_moves as f64 / line_count as f64
);
println!(
"\nAverage time = {} milliseconds",
elapsed_ms / (line_count as u128)
);
println!("Total time = {} ms", elapsed_ms);
println!("Total puzzles = {}", line_count);
} else {
println!("\nNo puzzles processed.");
}
Ok(())
}
// ****** Final Structural Correction for the BFS Loop ******
// The BFS loop needs to be structured like this to handle non-Copy Ai state:
/*
while let Some(old_state) = q.pop_front() { // `old_state` is owned here
let old_id = id(&old_state, phase); // `old_id` is calculated and owned
// Check if `old_id` is already visited from the other direction (collision at dequeue?)
// This check isn't strictly necessary if the main collision check works, but can be an optimization.
let old_dir = match direction.get(&old_id) {
Some(dir) => *dir,
None => {
eprintln!("Dequeued state ID not found in direction map - error!");
continue; // Skip this state
}
};
// Apply all applicable moves
for move_code in 0..18 {
if (APPLICABLE_MOVES[phase] & (1 << move_code)) == 0 {
continue;
}
// Clone `old_state` *before* it's potentially moved into `apply_move`
let new_state = apply_move(move_code, old_state.clone()); // Clone here!
let new_id = id(&new_state, phase); // Calculate new ID
match direction.entry(new_id.clone()) { // Use Entry API, clone new_id for potential insert
std::collections::hash_map::Entry::Occupied(entry) => {
// Seen before
let found_dir = *entry.get();
if found_dir != old_dir {
// Collision detected!
// ... reconstruct path using old_id.clone(), new_id.clone(), meeting_move ...
// ... print moves, update global current_state ...
// ... continue 'next_phase ...
}
// else: Seen from same direction, do nothing. `new_state` is dropped.
}
std::collections::hash_map::Entry::Vacant(entry) => {
// First time seeing this ID
entry.insert(old_dir); // Mark direction
predecessor.insert(new_id.clone(), old_id.clone()); // Store predecessor (clone IDs)
last_move.insert(new_id.clone(), move_code); // Store move (clone new_id)
q.push_back(new_state); // Add state to queue (moves ownership)
}
}
} // end move loop
} // end while loop
*/
// The implemented code *should* follow this corrected logic now regarding cloning. Double-check map insertions and path reconstruction cloning.
Wren
Wren has a similar problem to Go in that Lists cannot be used as Map keys. Worse still Wren doesn't support fixed size arrays so I've had to convert the Lists to space delimited Strings which is an expensive operation.
Despite this, the script is taking an average of just over a second to calculate the number of moves for each line which is probably not too bad for an interpreted language.
/**********************************************************************
*
* A cube 'state' is an int array with 40 entries, the first 20
* are a permutation of {0,...,19} and describe which cubie is at
* a certain position (regarding the input ordering). The first
* twelve are for edges, the last eight for corners.
*
* The last 20 entries are for the orientations, each describing
* how often the cubie at a certain position has been turned
* counterclockwise away from the correct orientation. Again the
* first twelve are edges, the last eight are corners. The values
* are 0 or 1 for edges and 0, 1 or 2 for corners.
*
**********************************************************************/
import "os" for Process
import "io" for File
var applicableMoves= [0, 262143, 259263, 74943, 74898]
var phase = 0
var affectedCubies = [
[0, 1, 2, 3, 0, 1, 2, 3], // U
[4, 7, 6, 5, 4, 5, 6, 7], // D
[0, 9, 4, 8, 0, 3, 5, 4], // F
[2, 10, 6, 11, 2, 1, 7, 6], // B
[3, 11, 7, 9, 3, 2, 6, 5], // L
[1, 8, 5, 10, 1, 0, 4, 7] // R
]
var btoi = Fn.new { |b| (b) ? 1 : 0 }
var applyMove = Fn.new { |move, origState|
var state = origState[0..-1] // make copy so don't mutate original
var turns = move%3 + 1
var face = (move/3).floor
while (turns != 0) {
turns = turns - 1
var oldState = state[0..-1] // make a copy prior to mutation
for (i in 0..7) {
var isCorner = btoi.call(i > 3)
var target = affectedCubies[face][i] + isCorner*12
var temp = (i&3 == 3) ? i - 3 : i + 1
var killer = affectedCubies[face][temp] + isCorner*12
var orientationDelta
if (i < 4) {
orientationDelta = btoi.call(face > 1 && face < 4)
} else if (face < 2) {
orientationDelta = 0
} else {
orientationDelta = 2 - (i&1)
}
state[target] = oldState[killer]
state[target+20] = oldState[killer+20] + orientationDelta
if (turns == 0) state[target+20] = state[target+20] % (2 + isCorner)
}
}
return state
}
var inverse = Fn.new { |move| move + 2 - 2*(move%3) }
var id = Fn.new { |state|
//--- Phase 1: Edge orientations.
if (phase < 2) return state[20...32]
//--- Phase 2: Corner orientations, E slice edges.
if (phase < 3) {
var result = state[31...40]
for (e in 0..11) result[0] = result[0] | ((state[e]/8).floor << e)
return result
}
//--- Phase 3: Edge slices M and S, corner tetrads, overall parity.
if (phase < 4) {
var result = [0, 0, 0]
for (e in 0..11) {
var temp = ((state[e] > 7) ? 2 : state[e] & 1) << (2 * e)
result[0] = result[0] | temp
}
for (c in 0..7) {
var temp = ((state[c + 12] - 12) & 5) << (3 * c)
result[1] = result[1] | temp
}
for (i in 12..18) {
for (j in i+1..19) result[2] = result[2] ^ btoi.call(state[i] > state[j])
}
return result
}
//--- Phase 4: The rest.
return state
}
var startTime = System.clock
var aggregateMoves = 0
//--- Define the goal.
var goal = ["UF", "UR", "UB", "UL", "DF", "DR", "DB", "DL", "FR", "FL", "BR", "BL",
"UFR", "URB", "UBL", "ULF", "DRF", "DFL", "DLB", "DBR"]
//--- Load dataset (file name should be passed as a command line argument).
if (Process.arguments.count != 1) {
Fiber.abort("The file name should be passed as a command line argument.")
}
var lines = File.read(Process.arguments[0]).split("\n")
if (lines[-1] == "") lines.removeAt(-1) // if there's a final blank line remove it
var lineCount = lines.count
for (line in lines) {
var inputs = line.split(" ")
phase = 0
var totalMoves = 0
//--- Prepare current (start) and goal state.
var currentState = List.filled(40, 0)
var goalState = List.filled(40, 0)
for (i in 0..19) {
//--- Goal state.
goalState[i] = i
//--- Current (start) state.
var cubie = inputs[i]
while (true) {
var idx = -1
for (c in 0...goal.count) {
if (goal[c] == cubie) {
idx = c
break
}
}
currentState[i] = (idx >= 0) ? idx : 20
if (currentState[i] != 20) break
cubie = cubie[1..-1] + cubie[0]
currentState[i+20] = currentState[i+20] + 1
}
}
//--- Dance the funky Thistlethwaite..
phase = phase + 1
while (phase < 5) {
var nextPhase = false
//--- Compute ids for current and goal state, skip phase if equal.
var currentId = id.call(currentState).join(" ")
var goalId = id.call(goalState).join(" ")
if (currentId != goalId) {
//--- Initialize the BFS queue.
var q = [currentState, goalState]
//--- Initialize the BFS tables.
var predecessor = {}
var direction = {}
var lastMove = {}
direction[currentId] = 1
direction[goalId] = 2
//--- Dance the funky bidirectional BFS...
while (true) {
//--- Get state from queue, compute its ID and get its direction.
var oldState = q[0]
q = q[1..-1]
var oldId = id.call(oldState).join(" ")
var oldDir = direction[oldId]
if (oldDir == null) {
oldDir = 0
direction[oldId] = 0
}
//--- Apply all applicable moves to it and handle the new state.
var move = 0
while (move < 18) {
if ((applicableMoves[phase] & (1 << move)) != 0) {
//--- Apply the move.
var newState = applyMove.call(move, oldState)
var newId = id.call(newState).join(" ")
var newDir = direction[newId]
if (newDir == null) {
newDir = 0
direction[newId] = 0
}
//--- Have we seen this state (id) from the other direction already?
//--- I.e. have we found a connection?
if (newDir != 0 && newDir != oldDir) {
//--- Make oldId represent the forwards
//--- and newId the backwards search state.
if (oldDir > 1) {
var t = newId
newId = oldId
oldId = t
move = inverse.call(move)
}
//--- Reconstruct the connecting algorithm.
var algorithm = [move]
while (oldId != currentId) {
var t = lastMove[oldId]
if (t == null) {
t = 0
lastMove[oldId] = 0
}
algorithm.insert(0, t)
oldId = predecessor[oldId]
if (oldId == null) {
oldId = ""
predecessor[oldId] = ""
}
}
while (newId != goalId) {
var t = lastMove[newId]
if (t == null) {
t = 0
lastMove[newId] = 0
}
algorithm.add(inverse.call(t))
newId = predecessor[newId]
if (newId == null) {
newId = ""
predecessor[newId] = ""
}
}
//--- Print and apply the algorithm.
for (i in 0...algorithm.count) {
System.write("UDFBLR"[(algorithm[i]/3).floor])
System.write(algorithm[i]%3 + 1)
System.write(" ")
totalMoves = totalMoves + 1
currentState = applyMove.call(algorithm[i], currentState)
}
nextPhase = true
break
}
//--- If we've never seen this state (id) before, visit it.
if (newDir == 0) {
q.add(newState)
direction[newId] = oldDir
lastMove[newId] = move
predecessor[newId] = oldId
}
}
move = move + 1
}
if (nextPhase) break
}
}
phase = phase + 1
}
System.print(" (moves %(totalMoves))")
aggregateMoves = aggregateMoves + totalMoves
}
var endTime = System.clock
var elapsedTime = ((endTime - startTime) * 1000).round
System.print("\nAverage number of moves = %(aggregateMoves/lineCount)")
System.print("\nAverage time = %(elapsedTime/lineCount) milliseconds")
- Output:
Using the original dataset of 100 lines, the results were as follows:
U1 U2 (moves 2) U2 (moves 1) U1 (moves 1) F1 F2 (moves 2) F2 (moves 1) F1 (moves 1) R1 R2 (moves 2) R2 (moves 1) R1 (moves 1) D1 D2 (moves 2) D2 (moves 1) D1 (moves 1) B1 B2 (moves 2) B2 (moves 1) B1 (moves 1) L1 L2 (moves 2) L2 (moves 1) L1 (moves 1) U2 B3 B2 (moves 3) L2 U3 (moves 2) R1 U1 (moves 2) D3 L3 (moves 2) D3 L2 (moves 2) D2 F3 F2 (moves 3) R2 F3 (moves 2) R1 F2 F2 R2 F2 (moves 5) D1 D2 U2 (moves 3) L1 B2 F2 L2 R2 B2 F2 (moves 7) L1 L2 D3 (moves 3) D1 F2 (moves 2) U2 R3 (moves 2) L1 L2 U3 (moves 3) U1 R2 (moves 2) U1 R3 (moves 2) F1 U2 (moves 2) U2 R3 R2 (moves 3) F2 D1 F3 (moves 3) F2 D3 D2 U2 (moves 4) L3 D2 R3 (moves 3) D2 R3 R2 D3 (moves 4) F1 R1 B2 B2 R2 B2 (moves 6) L1 B2 F2 (moves 3) U1 R2 B3 B2 (moves 4) R2 F3 R2 (moves 3) L2 D3 R3 R2 (moves 4) L2 F3 L2 L2 F2 L2 (moves 6) F1 R1 B3 D3 B2 D3 L3 U2 L3 U2 L2 U2 L2 U3 R2 U1 F2 L2 U2 B2 L2 F2 U2 L2 U2 F2 D2 F2 U2 (moves 29) L1 L2 U3 R2 (moves 4) L3 B3 B2 R3 R2 (moves 5) B2 U1 R3 R2 (moves 4) L3 B3 L2 (moves 3) D1 B2 L3 L2 (moves 4) B1 B2 R3 F2 F2 R2 F2 (moves 7) D1 F3 D1 D2 (moves 4) R1 B3 D1 R2 F3 L1 U2 F2 D3 B2 D1 L3 U1 F2 R2 U1 L2 U1 F2 U2 R2 U3 F2 U3 F2 D2 F2 L2 F2 L2 F2 U2 F2 D2 L2 (moves 35) F1 R1 U3 D1 B3 U3 D2 L3 B2 R1 F2 D3 L3 U2 R2 D1 R2 B2 U2 L2 U3 U2 F2 U2 L2 B2 R2 D2 R2 D2 B2 L2 F2 U2 (moves 34) U1 R1 F3 L1 R2 U3 L1 D2 F2 U3 L3 L2 U1 F2 D3 F2 F2 U2 D2 L2 U2 F2 R2 F2 D2 R2 U2 (moves 27) R1 D3 R3 F3 R1 D3 F2 U1 R3 D2 U1 R3 F2 U1 L2 U3 F2 U1 B2 D2 L2 D3 F2 F2 U2 F2 D2 L2 U2 L2 F2 L2 U2 R2 (moves 34) D2 R1 B1 L1 F3 U2 D3 L2 R1 D3 B2 U1 F2 L3 F2 U3 B2 U3 B2 L2 U3 B2 U3 F2 U2 F2 U2 L2 F2 R2 B2 D2 L2 D2 F2 (moves 35) B3 U2 L1 F3 F2 U1 R3 D1 F2 R3 D3 B2 R3 B2 U1 F2 U3 R2 U1 R2 U3 R2 L2 F2 U2 R2 F2 D2 R2 B2 U2 R2 B2 (moves 33) L1 F3 L2 D3 U1 F3 L1 B2 R1 U1 D1 B2 R3 U1 L2 U1 B2 U1 F2 U3 L2 D1 F2 U3 F2 U2 D2 R2 U2 L2 F2 R2 U2 F2 R2 (moves 35) F1 R3 U2 F3 B2 U1 L1 U1 R3 B2 U1 R3 R2 U3 L2 U1 B2 U2 R2 U3 L2 U3 F2 L2 U2 F2 U2 B2 L2 D2 L2 F2 L2 F2 U2 (moves 35) U2 D3 B3 U1 L2 D1 R1 U3 L3 D2 U1 R3 U3 B2 D3 R2 F2 U3 F2 U3 U2 B2 D2 B2 L2 F2 R2 D2 R2 (moves 29) D2 L3 U3 F3 B2 U3 L1 U2 R3 D2 L3 U2 L2 U3 R2 B2 D3 F2 R2 U3 U2 L2 U2 F2 U2 D2 R2 F2 U2 B2 D2 (moves 31) F1 L1 U1 L1 B3 U3 L1 F2 L1 B2 F2 U3 L3 F2 D3 B2 D3 R2 U1 F2 U3 L2 U3 U2 F2 D2 B2 U2 F2 R2 F2 L2 (moves 32) B1 L1 U3 F3 B2 U1 L3 B2 R3 L3 U3 L3 D2 B2 D3 F2 L2 U2 R2 U3 F2 U3 F2 L2 U2 B2 L2 U2 B2 F2 R2 U2 F2 (moves 33) F2 L3 F1 D3 B3 B2 U3 R1 D3 U3 L3 L2 R2 U3 B2 D1 B2 U3 R2 U3 F2 L2 F2 L2 U2 F2 B2 R2 B2 L2 (moves 30) D3 F3 U1 B2 U3 L1 D1 R3 U3 F2 L3 U1 F2 U2 L2 U3 L2 B2 R2 L2 D1 F2 F2 L2 U2 F2 L2 U2 R2 D2 B2 R2 L2 (moves 33) F2 R3 U2 F3 U2 L2 B2 D1 F2 R3 B2 D1 L3 D2 R2 B2 D1 R2 B2 U1 L2 B2 R2 B2 R2 D2 L2 D2 F2 L2 B2 L2 F2 (moves 33) U1 R3 F3 D3 R3 B2 L3 D1 F2 U1 R3 L2 U1 B2 D1 L2 U3 R2 U1 L2 U3 F2 U3 F2 U2 B2 L2 D2 L2 U2 R2 F2 (moves 32) F1 R1 F1 D3 B3 F3 U1 R2 F2 U1 L3 U1 F2 U2 R2 U1 R2 U3 L2 U3 D2 L2 F2 L2 F2 U2 B2 U2 L2 F2 (moves 30) F3 R3 L2 B3 U1 B2 U1 F2 U2 B2 R3 D2 L3 B2 U1 F2 U3 L2 U1 B2 D3 L2 U1 L2 U2 L2 D2 R2 F2 D2 F2 U2 R2 U2 (moves 34) D1 B3 D2 L1 F3 U3 F2 D2 L3 F2 L3 D3 L3 D1 L2 B2 U3 R2 U1 R2 U3 L2 U3 L2 D2 R2 D2 F2 R2 F2 L2 D2 U2 F2 U2 (moves 35) U1 B1 D1 R3 F3 U1 B2 R1 U3 L1 D3 B2 U1 R3 U2 F2 L2 U3 R2 U1 B2 D3 B2 U1 L2 F2 U2 D2 L2 U2 B2 R2 B2 L2 D2 L2 (moves 36) U3 F1 L1 F3 B2 U1 B2 R2 D1 R1 U2 L3 U1 F2 R2 U3 L2 U3 B2 F2 R2 F2 B2 U2 R2 F2 L2 U2 L2 (moves 29) U1 B2 L1 B3 F3 U1 F2 B2 R2 D3 R3 U3 L3 B2 U1 F2 U3 F2 U3 L2 U2 F2 R2 B2 R2 U2 F2 U2 F2 U2 F2 (moves 31) U1 B1 U3 D1 F3 U2 D3 R3 D1 U1 L1 F2 L3 D2 L2 U1 F2 B2 R2 U3 F2 U1 L2 U2 R2 F2 D2 F2 U2 L2 B2 U2 F2 (moves 33) D1 F3 U2 R1 B3 L1 B2 R1 U3 L2 D3 F2 R3 L2 D2 L2 D3 L2 F2 U3 F2 B2 D2 L2 B2 L2 B2 D2 L2 F2 U2 F2 U2 (moves 33) R1 B1 D3 F3 D1 R3 D3 B2 L2 B2 U2 L3 L2 U2 B2 L2 U2 F2 U3 U2 F2 L2 D2 L2 B2 U2 R2 F2 L2 B2 (moves 30) U1 D2 F1 L1 B3 D1 B2 D3 L2 R1 D3 L2 U2 R3 D2 F2 U3 F2 R2 U1 B2 U1 F2 U3 B2 R2 U2 L2 U2 B2 D2 F2 L2 B2 F2 U2 (moves 36) U1 L1 D1 L1 F3 L1 U1 L3 U3 L1 D1 R3 F2 U2 R2 U1 F2 U2 F2 L2 D1 F2 U3 F2 U2 R2 D2 F2 R2 B2 L2 B2 D2 B2 (moves 34) L3 D3 U1 F3 U2 F2 D3 R3 B2 D3 U3 L3 R2 U2 L2 D3 R2 U1 L2 U2 F2 U3 F2 U3 U2 L2 U2 R2 B2 R2 B2 U2 F2 U2 (moves 34) L1 B1 U2 D1 F3 B2 U3 R3 D2 U3 L2 U3 L3 F2 U3 R2 U1 F2 R2 L2 D3 F2 F2 B2 L2 D2 F2 R2 D2 B2 R2 F2 L2 (moves 33) L1 B1 U3 F3 U1 L2 D3 L1 B2 R1 L3 U3 L3 U3 L2 D3 L2 U1 L2 B2 F2 U3 L2 D2 L2 U2 R2 F2 D2 B2 U2 R2 U2 (moves 33) F1 U1 B3 F3 B2 U2 D3 L3 U3 L3 U3 R2 D3 B2 D2 L2 U3 R2 U2 F2 U3 F2 L2 D2 L2 R2 F2 L2 U2 L2 D2 U2 F2 U2 (moves 34) D1 L3 R1 F2 U2 F3 U3 F2 D3 L3 D2 L3 U2 L3 D1 L2 U3 R2 D1 B2 U1 L2 R2 U2 L2 D2 B2 R2 F2 L2 D2 U2 F2 U2 (moves 34) L2 R3 D1 F3 D3 L1 U3 L3 D2 L3 B2 L2 U1 R2 U2 F2 U3 F2 L2 F2 L2 B2 U2 R2 U2 R2 B2 U2 B2 (moves 29) L2 U2 R1 B3 F3 U1 L1 D3 F2 U2 R3 U2 L3 L2 U2 L2 D2 L2 F2 U3 F2 U2 L2 U2 B2 U2 R2 D2 R2 B2 (moves 30) L2 F1 U2 F3 D3 R3 U1 D3 L3 D1 U1 L3 R2 D3 R2 F2 D2 B2 U3 F2 U1 F2 D2 L2 B2 U2 L2 U2 R2 B2 F2 U2 (moves 32) F3 D2 F3 L2 B2 D3 L2 U3 B2 L3 L2 F2 L2 D3 L2 B2 U3 L2 L2 U2 F2 D2 L2 D2 L2 B2 L2 F2 L2 U2 (moves 30) F3 R2 U3 F3 U3 R3 D2 R2 D1 F2 U2 L3 D3 L2 D3 R2 U1 F2 U3 L2 U1 F2 L2 B2 D2 B2 L2 F2 U2 L2 F2 D2 (moves 32) B1 R1 U1 D3 F3 R2 U1 L2 R2 D2 B2 U3 L3 R2 F2 U1 L2 B2 U1 F2 U3 L2 U3 R2 U2 F2 D2 F2 L2 B2 L2 U2 F2 (moves 33) L3 D3 U1 B3 L2 F2 D3 L3 R1 U1 R3 L2 D3 F2 R2 U3 F2 R2 U3 L2 D2 R2 U2 B2 U2 B2 L2 U2 R2 F2 U2 (moves 31) L1 F3 L2 R1 B3 L1 U3 L1 R1 D3 F2 D1 R3 B2 R2 U1 F2 L2 D1 R2 F2 D2 L2 R2 B2 R2 B2 U2 L2 U2 (moves 30) U1 F1 U3 L1 B3 D1 L2 B2 R1 D3 R3 F2 L3 U3 F2 B2 L2 U3 B2 D3 L2 U3 L2 D2 R2 F2 D2 L2 F2 D2 F2 (moves 31) D2 L3 U1 F3 U1 D3 L1 F2 D3 R3 F2 U3 R3 L2 U1 L2 U3 L2 U1 F2 L2 U1 R2 U3 F2 U2 L2 D2 B2 U2 L2 F2 U2 F2 U2 (moves 35) F3 L2 F3 U1 L1 U1 D2 L3 U3 L3 B2 U1 F2 U1 F2 D2 R2 U3 L2 U2 F2 U3 R2 F2 D2 L2 D2 R2 F2 U2 F2 U2 F2 U2 (moves 34) U2 L3 B3 U2 R3 U3 L2 B2 U1 R3 R2 D3 R2 U1 R2 U3 F2 U1 F2 U3 F2 U2 L2 F2 R2 F2 D2 L2 D2 L2 B2 (moves 31) F1 B1 R3 F3 U3 F3 B2 D1 B2 R1 U3 L1 U2 L3 F2 U3 F2 R2 U1 R2 U2 B2 D3 F2 U3 F2 B2 L2 U2 F2 L2 D2 B2 F2 L2 B2 (moves 36) B2 D3 B3 U2 B2 D3 L3 D1 R1 U2 L3 L2 U3 B2 U1 B2 D2 R2 U3 F2 U3 U2 L2 U2 F2 D2 F2 U2 B2 L2 D2 F2 R2 F2 (moves 34) Average number of moves = 16.72 Average time = 1005.78 milliseconds
When run with a file containing the single line:
UL DL RF UB FD BR DB UF DR UR BL FL FDR BLU DLB URB RUF FLD BRD FUL
a typical result was:
U3 F1 L1 F3 B2 U1 B2 R2 D1 R1 U2 L3 U1 F2 R2 U3 L2 U3 B2 F2 R2 F2 B2 U2 R2 F2 L2 U2 L2 (moves 29) Average number of moves = 29 Average time = 665 milliseconds