All submissions must be uploaded here by midnight US Pacific Time, 29 February 2004.
You may use any of the following languages:
The sequence returned must be shorter than 1,000 moves.
Only the standard libraries provided with a language may be used. That is, you can't simply say
use Cube::Solver ; print solve @ARGV ;and say that Cube::Solver is on CPAN.
The input format will be the same as that of Mike Reid's cube solver. A solved cube is represented by the input
UF UR UB UL DF DR DB DL FR FL BR BL UFR URB UBL ULF DRF DFL DLB DBRThis input is given on the command line. The first 12 values are the edge cubies, and the next eight are the corners. The faces are called U(p), D(own), R(ight), L(eft), F(ront), and B(ack). First the cubie that's in the UF position is given, by the color (in UFRDBL notation) that's on top first, and then the other color next. And so on. For instance, starting with a solved cube, the move U+ results in
UR UB UL UF DF DR DB DL FR FL BR BL URB UBL ULF UFR DRF DFL DLB DBRStarting with a solved cube, the move F+ results in
LF UR UB UL RF DR DB DL FU FD BR BL LFU URB UBL LDF RUF RFD DLB DBRStarting with a solved cube, the moves F- U+ F- D- L- D- F- U- L2 D- results in
RU LF UB DR DL BL UL FU BD RF BR FD LDF LBD FUL RFD UFR RDB UBL RBUFor this input, a valid solution would be the inverse of the above sequence, or
D+ L2 U+ F+ D+ L+ D+ F+ U- F+Of course there are many other valid output sequences.
The program need not detect malformed input, nor terminate or give any particular response if the input is malformed in any way, including bad characters, bad length, or bad cube parity. All input sequences the programs are tested on will be valid.
The output sequence should be in the face turn metric, and should include only the characters ufrdblUFRDBL123+-', space, and newline. 1 and + (and no suffix) mean a clockwise turn, 2 means a half turn, and 3, ', and - mean a counterclockwise turn. Spaces may be provided for clarity or omitted. The length of a sequence is the number of moves in the half-turn metric, not the number of characters in the output description. The output sequence should be written to stdout, and it should be the only output of the program to stdout (any output to stderr is acceptable and will be ignored).
To test your cube solver, click here to access a script that generates a random cube position, and takes a solution you generate and says whether it is correct or not.
The size of the program will be determined by counting the number of non-whitespace, non-comment characters, except that identifiers and keywords only count as a single character. Whitespace in strings will count as characters, as will literal data in strings and literal numbers. For some languages (Perl) this determination will probably have to be largely a manual process. Note that the Perl phrase $foo will count as two characters (the $ will be considered syntax); the C++ phrase cube::rotate will be considered four characters (that's two identifiers separated by the double-colon syntax). The purpose of this rule is to prevent programs from being overly obfuscated. When you submit a program, I will reply with an email containing the character count and which characters counted. I reserve the right to refine these rules as necessary, if people come up with particularly crazy ways to reduce the character count. For instance, having thousands of blank lines just to be able to use __LINE__ as a one-character integer literal is unacceptable.
The score will be the product of:
1314 * (0.5 + 0.103) * 53
or 41,994. Lower scores are better. The 0.5 addend for time is due to a couple of reasons; first, it's hard to measure execution time from the command line very accurately because it's somewhat nondeterministic, and this also somewhat negates the speed advantage some languages may have. I will do nothing else to compensate for language choice; it should be straightforward to solve this problem in under a tenth of a second for any of the above languages, including Java with its large JVM.
Prizes are as follows:
If I do not receive at valid solutions from at least four different people, some lower prizes may not be awarded.
All programs submitted must be submitted with the understanding that they will be published on my web site and made freely available by anyone for any use whatsoever.
Every entry should include a README with the programmer's name and an email address I can use to contact the winners, the city and country the programmmer lives in, the source code, compilation instructions if any, how to run the program, and any additional information about the program. The program should be packaged up in a gzip'ed tar archive, or a ZIP archive. Note that I will be testing the program on an x86 linux machine running RedHat 9. If you request, I will obliterate the email address in your README before publishing your solution. The solution should be uploaded here by midnight US Pacific Time, 29 February 2004.
Questions and answers will be posted in the yahoo group
email@example.com. If desired, private
mail can be sent to
All judge's decisions are final. This contest is an entirely private affair run by me and only by me and has no relation to any other organization.
Generate Example Cases -