Rubik's Revenge

Question

Everyone likes a good puzzle. After all, that's the basis for Code Golf and Code Challenge! What better puzzle exists than the famous Rubik's Cube? Well what else but her slightly larger sister, the Rubik's Revenge!

Rubik's Revenge Background

Released in 1982 following the success of the classic Rubik's Cube invented by Hungarian sculptor and professor of architecture Ernő Rubik, a Rubik's Revenge is a cubic combination puzzle.

Each face contains sixteen stickers (as opposed to the traditional nine), each of which is one of six colours. An internal pivot mechanism enables each face to turn independently, effectively mixing up the colours.

The puzzle is solved when each face contains only one colour.

The biggest difference between the Rubik's Revenge and the Rubik's Cube is that the Revenge contains no fixed facets; the two inner facets are freely movable, allowing for every face to move freely.

Move Notation

A move is defined as a change of state for the Rubik's Revenge. This challenge will stick with the basic 12 moves:

1. F (Outer Front): the outer side currently facing the solver
2. f (Inner Front): the inner side currently facing the solver
3. B (Outer Back): the outer side opposite the front
4. b (Inner Back): the inner side opposite the front
5. U (Outer Up): the outer side above (on top of) the front side
6. u (Inner Up): the inner side above (on top of) the front side
7. D (Outer Down): the outer side opposite the top (underneath the Revenge)
8. d (Inner Down): the inner side opposite the top (underneath the Revenge)
9. L (Outer Left): the outer side directly to the left of the front
10. l (Inner Left): the inner side directly to the left of the front
11. R (Outer Right): the outer side directly to the right of the front
12. r (Inner Right): the inner side directly to the right of the front

All moves are clockwise turns associated with the respective face of the cube. To denote a counter-clockwise turn, a prime symbol (') is used. Example moves and their equivalences follow.

1. Move: b (clockwise inner back)

   1. Rotate the cube clockwise 180° horizontally (such that the back side of the cube now faces the front)
   2. Rotate the inner front face clockwise
   3. Rotate the cube counter-clockwise 180° horizontally (such that the original front side of the cube now faces the front)

2. Move: l' (counter-clockwise inner left)

   1. Rotate the cube counter-clockwise 90° horizontally (such that the left side of the cube now faces the front)
   2. Rotate the inner front face counter-clockwise
   3. Rotate the cube clockwise 90° horizontally (such that the original front side of the cube now faces the front)

3. Move: D (clockwise outer down)

   1. Rotate the cube clockwise 90° vertically (such that the down side of the cube now faces the front)
   2. Rotate the outer front face clockwise
   3. Rotate the cube counter-clockwise 90° vertically (such that the original front side of the cube now faces the front)

More examples will be provided upon request.

Color Scheme

The Rubik's Revenge uses six basic colours for each of the stickers on a face. In this challenge, the colours will be represented as numbers.

• White (W): 0
• Red (R): 1
• Blue (B): 2
• Green (G): 3
• Yellow (Y): 4
• Orange (O): 5

A 2-Dimensional representation of the solved cube is as follows:

        O O O O                        5 5 5 5
        O O O O                        5 5 5 5
        O O O O                        5 5 5 5
        O O O O                        5 5 5 5
G G G G W W W W B B B B        3 3 3 3 0 0 0 0 2 2 2 2
G G G G W W W W B B B B  ===>  3 3 3 3 0 0 0 0 2 2 2 2
G G G G W W W W B B B B  ===>  3 3 3 3 0 0 0 0 2 2 2 2
G G G G W W W W B B B B        3 3 3 3 0 0 0 0 2 2 2 2
        R R R R                        1 1 1 1
        R R R R                        1 1 1 1
        R R R R                        1 1 1 1
        R R R R                        1 1 1 1
        Y Y Y Y                        4 4 4 4
        Y Y Y Y                        4 4 4 4
        Y Y Y Y                        4 4 4 4
        Y Y Y Y                        4 4 4 4

Where the corresponding faces are arranged as follows:

        U U U U
        U U U U
        U U U U
        U U U U
L L L L F F F F R R R R
L L L L F F F F R R R R
L L L L F F F F R R R R
L L L L F F F F R R R R
        D D D D
        D D D D
        D D D D
        D D D D
        B B B B
        B B B B
        B B B B
        B B B B

The Task

In this challenge, the goal will be to write the shortest and most efficient Rubik's Revenge solver. Efficiency in this challenge is defined with respect to the total number of moves to solve a given input. Further, to promote the design of good heuristics, each input should run in less than 5 minutes and take less than 1,000 moves to solve.

Input

The input will be a single value consisting of a sequence of the numbers 0-5. Each input will have exactly 96 digits. The faces of the Revenge will be represented as the following ranges of numbers within the input:

• [0-15] : Front
• [16-31] : Right
• [32-47] : Back
• [48-63] : Left
• [64-79] : Up
• [80-95] : Down

For a single face, the 16 corresponding digits will be represented as follows:

[ 0][ 1][ 2][ 3]
[ 4][ 5][ 6][ 7]
[ 8][ 9][10][11]
[12][13][14][15]

where the upper left digit (i.e. 0) corresponds to the upper left digit in the 2-dimensional representation above. The indices of the input sequence corresponding to the spaces on the Rubik's Revenge are as follows:

                [64][65][66][67]
                [68][69][70][71]
                [72][73][74][75]
                [76][77][78][79]
[48][49][50][51][ 0][ 1][ 2][ 3][16][17][18][19]
[52][53][54][55][ 4][ 5][ 6][ 7][20][21][22][23]
[56][57][58][59][ 8][ 9][10][11][24][25][26][27]
[60][61][62][63][12][13][14][15][28][29][30][31]
                [80][81][82][83]
                [84][85][86][87]
                [88][89][90][91]
                [92][93][94][95]
                [32][33][34][35]
                [36][37][38][39]
                [40][41][42][43]
                [44][45][46][47]

An example solved Revenge can be represented as follows:

000000000000000022222222222222224444444444444444333333333333333355555555555555551111111111111111

Where the front face is white (0), the right face is blue (2), the back face is yellow (4), the left face is green (3), the up face is orange (5), and the down face is red (1).

Note that there are many different possible representations of a solved Revenge, depending on the colour of the front face and the overall orientation of the Revenge.

Assume that a valid solution is reachable from any input.

Output

The output should be the sequence of moves taken to find a solution. The output may or may not have a delimiter between moves; it is up to the coder.

Scoring

Scoring for each test case will be based on the criteria defined in the The Task section.

1. Points for length are calculated as follows (integer division): 100,000 / (characters in code)
2. Points for efficiency are calculated as follows (integer division): 500 / (number of moves)

The total points for a single test is the sum of the above two calculations. The total points for your code will be the sum of the points for all tests. The winner of the challenge will be the highest number of points.

Note that since your score increases with the fewer amount of moves for a solution, it is recommended to find optimal moves for certain patterns.

To preserve readability, white-space and newlines will not count toward code length.

Tests

Tests will be provided (ideally) within a week of posting. Each code must run each of the provided inputs and report total score as well as scores for each test.

---

Since solving the Rubik's Revenge is considerably more difficult than solving the Rubik's Cube and can require many more algorithms to produce optimized solutions, this challenge will be open for an undetermined amount of time.

I project the challenge will remain open for at least three (3) weeks, possibly more. Suggestions on the length of the challenge are encouraged.

Remember to have fun, and happy coding!