34
\$\begingroup\$

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!

Solved 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!

\$\endgroup\$

closed as unclear what you're asking by Downgoat, Liam, wizzwizz4, Martin Ender Feb 6 '16 at 11:28

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    \$\begingroup\$ As currently specified, this is asking for a Dijkstra's implementation, which is a) not very interesting, because previous questions have covered that ground; b) unlikely to run to completion in a reasonable time. \$\endgroup\$ – Peter Taylor Jul 13 '13 at 6:31
  • \$\begingroup\$ @PeterTaylor This is in no way requiring an implementation using Djikstra's Algorithm. If you feel it is, please let me know how I can reword the post to better promote any type of solution. \$\endgroup\$ – Alex Brooks Jul 13 '13 at 23:33
  • \$\begingroup\$ It favours optimal solutions and has no time constraints. Ok, there is an even simpler brute-force approach than Dijkstra, but that hardly improves the situation. The most similar existing question has a tough time limit which forces optimal solutions to be very well designed, and pushes people instead to good heuristics. \$\endgroup\$ – Peter Taylor Jul 14 '13 at 7:30
  • 2
    \$\begingroup\$ @PeterTaylor Thank you for the suggestion. I updated the The Task section to include some limitations on the speed and efficiency of the code. \$\endgroup\$ – Alex Brooks Jul 14 '13 at 16:33
  • 2
    \$\begingroup\$ just a btw whitespace should either count or only text-based programs should be accepted because of this \$\endgroup\$ – FantaC Dec 1 '17 at 16:11