Solve a Rubik's cube: Difference between revisions
Content deleted Content added
Added Kotlin |
Added Go |
||
Line 5: | Line 5: | ||
You may use any sort of input you wish. |
You may use any sort of input you wish. |
||
=={{header|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. |
|||
<lang go>/********************************************************************** |
|||
* |
|||
* 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" |
|||
"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 { |
|||
fmt.Println("The file name should be passed as a command line argument") |
|||
return |
|||
} |
|||
file, err := os.Open(os.Args[1]) |
|||
if err != nil { |
|||
fmt.Println("Unable to open file.") |
|||
return |
|||
} |
|||
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 |
|||
} |
|||
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") |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
Same as Kotlin entry apart, of course, from the timings. |
|||
</pre> |
|||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |