Ta tâche

.. est de faire ce que Brian Fantana n'a apparemment pas pu faire, et de résoudre le Rubik's Cube 2x2x2.

La disposition

- -   A B   - -   - -
- -   C D   - -   - -

E F   G H   I J   K L
M N   O P   Q R   S T

- -   U V   - -   - -
- -   W X   - -   - -

Et vous sera remis via stdin ou la ligne de commande (votre choix - veuillez préciser dans votre réponse) au format:

ABCDEFGHIJKLMNOPQRSTUVWX

Notez que AD constitue la face U (vers le haut), EFMN constitue la face L (gauche), GHOP constitue la face F (avant), IJQR constitue la face R (droite), KLST constitue la Face B (arrière) et UX composent la face D (bas).

Il y aura six caractères uniques représentant chaque couleur, mais ils peuvent varier, alors préparez-vous à toute combinaison de 6 caractères ascii à utiliser pour chaque couleur.

Caractéristiques

• Votre code doit générer une solution utilisant uniquement les faces droite (R), supérieure (U) et avant (F), et doit utiliser la notation standard: R, R ', R2, U, U', U2, F, F », F2. Vous pouvez trouver plus d'informations ici . La restriction du sous-ensemble RUF est standard pour le cube 2x2 (Astuce: traiter le coin inférieur arrière-gauche comme une base fixe à partir de laquelle travailler).
• Votre code doit être capable de résoudre toutes les permutations possibles du cube de poche.
• Chaque solution devrait prendre moins de 30 secondes.
• Chaque solution doit être inférieure à 30 mouvements.
• Un bonus de -20% sera accordé pour les solutions fournissant toujours des réponses à moins de 20 coups (veuillez en faire la publicité dans votre réponse afin que je puisse en faire une vérification approfondie)
• Un bonus de -50% sera accordé pour le code qui fournit toujours une solution optimale. - Encore une fois, veuillez annoncer dans votre réponse
• Les solutions ne doivent pas contenir deux mouvements consécutifs sur la même face, car ils peuvent être facilement combinés en un seul mouvement.
• Les solutions peuvent éventuellement contenir un seul espace - et seulement un seul espace - entre chaque mouvement.
• La séquence de solution entière, si nécessaire, peut être contenue dans une paire de parenthèses, guillemets, accolades, crochets ou carets, mais aucune autre sortie étrangère n'est autorisée.
• Veuillez fournir une version brièvement commentée de votre code ou une explication approfondie de votre code.
• Pas d'utilisation de fichiers externes. Cela inclut Internet, les tableaux de données et les bibliothèques / packages conçus pour ce type de problème.
• Le code le plus court par nombre d'octets gagne.
• Gagnant choisi mercredi (30 juillet 2014).

Python 2.7: 544 octets -50% = 272 octets **

import sys;o=''.join;r=range;a=sys.argv[1];a=o([(' ',x)[x in a[12]+a[19]+a[22]] for x in a]);v={a:''};w={' '*4+(a[12]*2+' '*4+a[19]*2)*2+a[22]*4:''}
m=lambda a,k:o([a[([0x55a5498531bb9ac58d10a98a4788e0,0xbdab49ca307b9ac2916a4a0e608c02,0xbd9109ca233beac5a92233a842b420][k]>>5*i)%32] for i in r(24)])
def z(d,h):
 t={}
 for s in d[0]:
  if s in d[1]:print d[h][s]+d[1-h][s];exit()
  n=[d[0][s],'']
  for k in r(3):
   for j in r(3):s=m(s,k);t[s]=n[h]+'RUF'[k]+" 2'"[(j,2-j)[h]]+n[1-h]
   s=m(s,k)
 d[0]=t;return d
while 1:v,w=z([v,w],0);w,v=z([w,v],1)

Stackexchange remplace les onglets par plusieurs espaces blancs. Si technique cette version compte 549 octets. Remplacez simplement les deux premiers espaces des lignes 6 à 10 par un tabulateur.

Idée derrière mon programme: Ma première idée a été une première recherche de souffle. Mais cela a pris trop de temps. Environ 2 minutes pour une course difficile (11 mouvements optimaux). J'ai donc décidé d'aborder le problème des deux côtés. J'utilise deux ensembles. Je génère séquentiellement tous les états avec la distance 1,2,3, ... au brouillage et les sauvegarde dans set1, et en même temps tous les états avec la distance 1,2,3, ... à l'état résolu et les sauvegarde dans set2. La première fois qu'un état est dans les deux ensembles, nous avons trouvé la solution.

Pour cela, j'ai besoin des couleurs du cube résolu, qui ne sont pas connues. Les caractères 13, 20 et 23 définissent la couleur gauche, arrière et bas. Mais ces 3 couleurs suffisent pour représenter le cube. Je remplace simplement les 3 autres couleurs par des espaces blancs et je peux représenter mon état résolu comme «____ll____bbll____dddd».

Oh, et pour raccourcir les permutations, j'ai utilisé une idée de /codegolf//a/34651/29577

Version non golfée:

import sys

#define permutations for R,U,F
permutation = [[0,7,2,15,4,5,6,21,16,8,3,11,12,13,14,23,17,9,1,19,20,18,22,10],
            [2,0,3,1,6,7,8,9,10,11,4,5,12,13,14,15,16,17,18,19,20,21,22,23],
            [0,1,13,5,4,20,14,6,2,9,10,11,12,21,15,7,3,17,18,19,16,8,22,23]]

def applyMove(state, move):
    return ''.join([state[i] for i in permutation[move]])

scramble = sys.argv[1]
#remove up,front,rigth colors
scramble = ''.join([(' ', x)[x in scramble[12]+scramble[19]+scramble[22]] for x in scramble])
solved = ' '*4+scramble[12]*2+' '*4+scramble[19]*2+scramble[12]*2+' '*4+scramble[19]*2+scramble[22]*4

dict1 = {scramble: ''} #stores states with dist 0,1,2,... from the scramble
dict2 = {solved: ''} #stores states with dist 0,1,2,... from the solved state

moveName = 'RUF'
turnName = " 2'"

for i in range(6):
    tmp = {}
    for state in dict1:
        if state in dict2:
            #solution found
            print dict1[state] + dict2[state]
            exit()
        moveString = dict1[state]
        #do all 9 moves
        for move in range(3):
            for turn in range(3):
                state = applyMove(state, move)
                tmp[state] = moveString + moveName[move] + turnName[turn]
            state = applyMove(state, move)
    dict1 = tmp
    tmp = {}
    for state in dict2:
        if state in dict1:
            #solution found
            print dict1[state] + dict2[state]
            exit()
        moveString = dict2[state]
        #do all 9 moves
        for move in range(3):
            for turn in range(3):
                state = applyMove(state, move)
                tmp[state] = moveName[move] + turnName[2 - turn] + moveString
            state = applyMove(state, move)
    dict2 = tmp

Je suis assez content du résultat, car je suis assez nouveau sur Python. Ceci est l'un de mes premiers programmes python.

édition: six mois plus tard: 427 - 50% = 213,5

J'ai un peu plus d'expérience en Python et en golf. J'ai donc révisé mon code d'origine et j'ai pu enregistrer plus de 100 caractères.

import sys;o=''.join;a=sys.argv[1];d=[{o((' ',x)[x in a[12]+a[19]+a[22]]for x in a):[]},{' '*4+(a[12]*2+' '*4+a[19]*2)*2+a[22]*4:[]}]
for h in[0,1]*6:
 for s,x in d[h].items():
  for y in range(12):
   d[h][s]=x+[y-[1,-1,1,3][h*y%4]];
   if s in d[1-h]:print o('RUF'[x/4]+" 2'"[x%4]for x in d[0][s]+d[1][s][::-1]);exit()
   s=o(s[ord(c)-97]for c in'acahabcdnpbfegefhugiovjgqkciljdeklflmmmnnvoopxphrqdjrrbsstttuuqsviwwwkxx'[y/4::3])

J'utilise essentiellement la même approche. Le plus grand changement est que je ne définis plus de fonction. Au lieu de

def z(d,h):
 for s in d[0]:
  if s in d[1]:...
while 1:v,w=z([v,w],0);w,v=z([w,v],1)

Je peux faire

for h in[0,1]*6:
 for s in d[h]:
  if s in d[1-h]:...

J'ai aussi changé un peu le mouvement lamda. D'abord raccourci, puis intégré directement le code, car l'appel de fonction n'apparaît qu'une seule fois.

Je garde pour chaque état une liste de nombres entre 0 et 11, pour représenter les coups, au lieu d'une chaîne contenant les coups. Les nombres sont convertis à la toute fin.

J'ai également combiné les deux boucles for 'for k in r(3):for j in r(3):en une seule for y in r(12). Par conséquent, je dois également faire les mouvements U4, R4, F4. Bien sûr, un tel mouvement n'apparaît pas dans la solution la plus courte, donc ça " 2'"[x%4]marche. (Si x % 4 == 3, il y aurait une exception d'index hors plage)

C'est aussi un peu plus rapide, car je cherche l'entrée dans le deuxième set plus tôt. Environ 0,5 seconde pour une solution à 11 mouvements.

C, 366 - Bonus optimal de 50% = 183

char c[99],t[3][26]={"ZGONFZCPTEZBHUMZ","ZIQPHZRUGAZJWOCZ","ZACB@ZJHFDZKIGEZ"};r=20;f(int m,int n){int e,i,j;for(i=4;i--;){for(j=15;j--;)c[t[n][j+1]]=c[t[n][j]];c[m]="FRU"[n],c[m+1]="4'2 "[i],c[m+2]=0;for(e=0,j=68;j<76;j++) e+= (c[j]!=c[j+8]) + (c[j]!=c[j^1]);i&&e&&e<45-m*2&m<r?f(m+2,(n+1)%3),f(m+2,(n+2)%3):e||(puts(c),r=m);}}main(){scanf("%s",c+64);f(0,2),f(0,1),f(0,0);}

En utilisant la récursivité, le programme recherche dans un arbre de jusqu'à 11 mouvements de profondeur (la longueur maximale d'un soluton optimal selon http://en.wikipedia.org/wiki/Pocket_Cube et la page mentionnée ci-dessous) et quand il trouve une solution il l'imprime (jusqu'à 22 caractères de long, suivi par l'argument de la fonction m.) L'ordre utilisé est une sorte d'ordre de dictionnaire, où toutes les routes commençant U, U2, U 'sont recherchées avant toute route commençant R ou F. Ainsi, il ne trouve pas nécessairement la solution optimale en premier.

Lorsqu'une solution est imprimée, rest égal à mce qui garantit que seules des solutions égales ou plus courtes seront imprimées par la suite. La mise r=m-2coûte 2 caractères supplémentaires mais garantit qu'une seule solution de chaque longueur trouvée (jusqu'à optimale) est imprimée. Si vous souhaitez qu'il affiche UNIQUEMENT la solution optimale, la meilleure solution trouvée jusqu'à présent doit être stockée dans une variable et la solution optimale imprimée à la fin du programme (cela coûterait environ 15 caractères supplémentaires.)

l'entrée est lue dans le tableau à c[]partir de l'index 64. Ceci est nécessaire pour utiliser des caractères alphabétiques dans le mobile. Les symboles à @travers Wsont utilisés à la place de A à X par la question, car il est nécessaire de commencer sur un nombre pair pour faire fonctionner le test des solutions. c['Z']est également utilisé pour le stockage temporaire, car pour effectuer une rotation quadruple, un total de 5 affectations est nécessaire. Étant donné que la première partie de c[]n'est pas utilisée, elle est disponible pour stocker la solution (qui se termine par un octet zéro, comme toutes les chaînes C.)

for(i..)passe par une séquence de 4 quarts de tour du visage spécifié par n.

Le premier for(j..)effectue l'échange réel selon le tableau t[].

Pour tester si le cube est résolu, il suffit de vérifier les quatre faces latérales.Les pièces URF et DFR peuvent être distinguées même avec les autocollants U et D retirés, car une pièce lit XRF dans le sens horaire et l'autre XFR. Si les deux pièces sont échangées de sorte que U s'affiche sur la face inférieure et vice versa, la couleur F apparaîtra sur la face droite et vice versa.

Le second for(j..)compte le nombre de décalages sur les quatre faces latérales. Par exemple, pour la face avant, il compare G & O, H & P et G & H (deux fois). Si e== 0, le cube est résolu. Si e<9 ou e<13, il pourrait être possible de résoudre le cube dans le prochain mouvement ou 2 mouvements respectivement. Sinon, il n'est certainement pas possible de résoudre le cube dans ce nombre de mouvements. Afin de gagner du temps, cette heuristique est utilisée pour tailler l'arbre de recherche et éviter de perdre du temps sur plusieurs de ces branches de profondeur 10 ou 11 qui seront infructueuses. Exprimé sous forme de formule, cela devient e<45-m*2.

Code non golfé

char c[99],t[3][26]={"ZGONFZCPTEZBHUMZ","ZIQPHZRUGAZJWOCZ","ZACB@ZJHFDZKIGEZ"};
r=20;                                                       //All moves are output as 2 characters. The index of the last move of the longest solution (11 moves) shall be 20.

f(int m,int n){                                             //perform a cycle through four 1/4 turns of the face specified in n. The index of the move reported in the solution is m.
  int e,i,j;                                                //e is for counting mismatches. i loops through the four 1/4 turns. j performs other functions.
  for(i=4;i--;){

    for(j=15;j--;)c[t[n][j+1]]=c[t[n][j]];                  //A 1/4 turn is performed as three 4-sticker rotations of the type z=a;a=b;b=c;c=d;d=z using the data in the movetable t[][]

    c[m]="FRU"[n],c[m+1]="4'2 "[i],c[m+2]=0;                //Write to the output in c[] the face to be turned and the number of 1/4 turns. Terminate with a zero byte to overwrite any longer solution that may have been found before. 

    for(e=0,j=68;j<76;j++)e+=(c[j]!=c[j+8])+(c[j]!=c[j^1]); //Compare each sticker of the top row of the side faces (64+4 through 64+11) with the stickers below and beside it. Count the number of mismatches.

    i && e && e<45-m*2 & m<r?                               //if the number of 1/4turns is not 4 AND the cube is not solved AND the heuristic (as described in the text) is good AND a shorter solution has not already been found,
      f(m+2,(n+1)%3), f(m+2,(n+2)%3):                       //deepen the search to another faceturn of the other two faces. 
      e||(puts(c),r=m);                                     //otherwise, if a solution has been found, print the solution and reduce the value of r to the new max solution length.
  } 
}

main(){
  scanf("%s",c+64);                                         //scan in the current cube state to c[] at index 64.
  f(0,2),f(0,1),f(0,0);                                     //call f() three times to search for solutions beginning with U R and F.
}

Performance

Le programme a été testé avec les modèles 1 à 13 sur http://www.jaapsch.net/puzzles/cube2.htm

Les résultats suivants donnent le timing sur ma machine pour trouver TOUTES les solutions optimales (pour les curieux.) Aussi pour les positions plus complexes, le timing est donné pour la modification de 2 octets mentionnée ci-dessus qui ne trouve qu'une seule solution optimale. Pour cela, des temporisations sont données à la fois pour trouver la première solution et pour que le programme se termine. Les solutions proposées (qui sont généralement différentes des solutions obtenues en inversant les générateurs sur la page liée) ont été vérifiées avec un simulateur de cube en ligne.

U 4 (1 move) horizontal flags (not mirror symmetric)
1 solution 1 sec

U2 (1 move) 4 horizontal flags (mirror symmetric)
1 solution 1 sec

F2 R2 F2 (3 moves) 4 vertical flags  
UUUULRBFRLFBLRBFRLFBDDDD 2 solutions 1 sec

U2 F2 R2 U2 (4 moves) Supertwist; 6 flags
DDUURRBFRRFBLLBFLLFBUUDD 3 solutions 1 sec

U F2 U2 R2 U (5 moves) 4 vertical flags, 2 checkerboards
UDDULBRFRFLBLBRFRFLBUDDU 2 solutions 1 sec

R2 F2 R2 U2 (4 moves) 4 checkerboards
UUUURLFBLRBFLRBFRLFBDDDD 4 solutions 1 sec

R U2 R' F2 R U' R2 U F2 U' (10 moves) Cube in cube
FFFUDDRFRULLLDRRUULBBBDB 18 solutions 26 sec; 1 solution U F2U'R2U R'F2R U2R' 1,13 sec 

R F U' R2 U F' R U F2 R2 (10 moves) Cube in cube 2
DDDUFFLFRBRRLFLLBBRBUUDU 8 solutions 28 sec; 1 solution R F U'R2U F'R U F2R2 12,21 sec 

U R F2 U R F2 R U F' R (10 moves)3-Cycle
UFFULDRFRULBLLFRURBBDBDD 45 solutions 26 sec; 1 solution U R'F U'F'R'F2U R F2 8,14 sec 

U R U' R2 U' R' F' U F2 R F' (11 moves) Column turn
UUUDLLFRFRBBLLFRFRBBDUDD many solutions 29 sec; 1 solution U R U'F U2R F'R'F'U2F' 3,27 sec 

F' U R' F2 U' R F U R2 U R' (11 moves)Corner swap
UUUURLFBLRBFLLFFRRBBDDDD 29 sec 24 solutions; 1 solution R U'F R U'R2U'F'R'U F2 12,28 sec

U F2 U' (3 moves) Zig-zag 
UDUDLLFRFFLBLBRRFRBBUUDD 1 solution 1 sec 

U' F2 U2 R2 U' F2 U2 R2 U' (9 moves) 2 Checkerboards, 4 L
DUUDLLFBRRBFLRFFRLBBUDDU 8 solutions 13 sec; 1 solution U F2U2R2U R2U2F2U' 1,5 sec