Sur certains vieux téléphones Nokia, il y avait une variation du puzzle de quinze appelé Rotation. Dans cette variante, au lieu de glisser une tuile à la fois, vous avez fait pivoter quatre tuiles à la fois dans une direction.

Dans ce jeu, vous commenceriez avec un tableau comme celui-ci:

4 9 2
3 5 7
8 1 6

Et en faisant tourner le bloc inférieur gauche deux fois dans le sens horaire et le bloc supérieur gauche une fois dans le sens horaire, vous obtenez ceci:

4 9 2
8 3 7
1 5 6

4 9 2
1 8 7
3 5 6

1 4 2
8 9 7
3 5 6

et la 1tuile serait dans le coin supérieur gauche où elle est censée être. Finalement, après quelques mouvements de plus, vous vous retrouvez avec:

1 2 3
4 5 6
7 8 9

qui est la configuration "originale".

Votre tâche consiste à créer un programme qui prendra en entrée une grille 3x3 de nombres de 1 à 9 (dans n'importe quel format que vous choisirez) et retournera en sortie une séquence de mouvements représentant les mouvements que vous devez effectuer pour ramener le tableau à son état d'origine. configuration (encore une fois, dans n'importe quel format que vous choisissez). Les déplacements légaux sont définis comme le déplacement du bloc [haut / bas] - [gauche / droite] de 4 tuiles [sens horaire / antihoraire].

Votre programme doit être capable de résoudre toutes les grilles 3x3 possibles (toutes les permutations sont résolubles).

Le code le plus court pour ce faire gagne.

GolfScript, 39/83 octets

# Optimized for size:

{.4rand.p.2/+>`{?1420344440`=}+$..$>}do

# Optimized for speed:

6,(7++:t;~{.(1=.@7=9=+4\-rand+..2/+@.@>:s^[3s=0s=2s=4s=1s=]+s|.)9<\t>|}do.$>30764`*

Vitesse vs taille

La version à taille optimisée choisit au hasard des rotations dans le sens horaire jusqu'à ce que la permutation souhaitée soit atteinte. Cela suffit, car une rotation dans le sens antihoraire équivaut à trois rotations consécutives dans le sens horaire du même carré.

La version à vitesse optimisée fait de même, à l'exception des éléments suivants:

1. Si le chiffre 1 est dans le coin supérieur gauche, il ne fait plus tourner le carré supérieur gauche.

2. Si le chiffre 9 est dans le coin inférieur droit, il ne fait plus tourner le carré inférieur droit.

3. Les étapes de permutation des positions 7 et 8 sont codées en dur, il y a donc deux positions qui permettent à la boucle de se rompre.

Outre la modification de l'algorithme, la version à vitesse optimisée réalise la rotation d'une manière simple, tandis que la version à taille optimisée utilise le tri intégré de GolfScript par mappage. Il code également en dur l'état final (à titre de comparaison) au lieu de trier l'état à chaque itération.

La version à vitesse optimisée nécessite moins d'itérations et chaque itération est beaucoup plus rapide en elle-même.

Repères

J'ai utilisé le code suivant pour randomiser les positions des nombres et effectuer des tests, sans commenter la ligne correspondant à la version à tester:

[{[
    0:c;10,1>{;2 32?rand}$
    #{c):c;.4rand.2/+>`{?1420344440`=}+$..$>}do
    #6,(7++:t;{.(1=.@7=9=+4\-rand+..2/+@.@>:s^[3s=0s=2s=4s=1s=]+s|.)9<\t>|}do.$>30764`*
],c+}\~*]

$.0='Min: '\+puts .-1='Max: '\+puts ..{+}*\,/'Avg: '\+puts .,2/='Med: '\+

La sortie indique le nombre minimum et maximum d'étapes nécessaires pour ordonner les nombres, la moyenne et la médiane de tous les cycles, ainsi que le temps écoulé en secondes:

$ TIME='\n%e s' time golfscript rotation-test-size.gs <<< 100
Min: 4652
Max: 2187030
Avg: 346668
Med: 216888

21500.10 s
$
$ TIME='\n%e s' time golfscript rotation-test-speed.gs <<< 1000
Min: 26
Max: 23963
Avg: 3036
Med: 2150

202.62 s

Sur ma machine (Intel Core i7-3770), le temps d'exécution moyen de la version à taille optimisée était de 3,58 minutes. Le temps d'exécution moyen de la version à vitesse optimisée était de 0,20 seconde. Ainsi, la version à vitesse optimisée est environ 1075 fois plus rapide.

La version à vitesse optimisée produit 114 fois moins de rotations. L'exécution de chaque rotation est 9,4 fois plus lente, principalement en raison de la mise à jour de l'état.

E / S

La sortie se compose de nombres à 3 bits. Le MSB est réglé pour les rotations dans le sens antihoraire, le bit du milieu est réglé pour les carrés inférieurs et le LSB est réglé pour les carrés droits. Ainsi, 0 (4) est le carré supérieur gauche, 1 (5) le coin supérieur droit, 2 (6) le coin inférieur gauche et 3 (7) le coin inférieur droit.

La version à vitesse optimisée imprime toutes les rotations sur une seule ligne. La version à taille optimisée imprime une rotation par ligne, suivie de la position finale des chiffres.

Pour la version à vitesse optimisée, l'entrée doit produire un tableau contenant les nombres de 1 à 9 lors de l'évaluation. Pour la version à taille optimisée, l'entrée doit être une chaîne sans retour à la ligne final; il n'est pas évalué.

L'exemple s'exécute:

$ echo -n '253169748' | golfscript rotation-size.gs
3
0
123456789
$ golfscript rotation-speed.gs <<< '[5 4 7 1 2 9 3 8 6]'
2210300121312212222212211121122211122221211111122211211222112230764

Code optimisé pour la taille

{               #
  .             # Duplicate the state.
  4rand         # Push a randomly chosen integers between 0 and 3.
  .p            # Print that integer.
  .2/+          # Add 1 to it if it is grater than one. Possible results: 0, 1, 3, 4
  >`            # Slice the state at the above index.
  {             # Push a code block doing the following:
    ?           # Get the index of the element of the iteration in the sliced state.
    1420344440` # Push the string "14020344440".
    =           # Retrieve the element at the position of the computed index.
  }+            # Concatenate the code block with the sliced state.
  $             # Sort the state according to the above code block. See below.
  ..$>          # Push two copies of the state, sort the second and compare the arrays.
}do             # If the state is not sorted, repeat the loop.

La mise à jour de l'état est réalisée de la manière suivante:

La rotation 2 donne l'entier 3 après avoir ajouté 1. Si l'état est «123456789», le découpage de l'état donne «456789».

Juste avant d'exécuter «$», les éléments supérieurs de la pile sont:

[ 1 2 3 4 5 6 7 8 9 ] { [ 4 5 6 7 8 9 ] ? "1420344440" = }

«$» Exécute le bloc une fois pour chaque élément du tableau à trier, après avoir poussé l'élément lui-même.

L'index de 1 dans «[4 5 6 7 8 9]» est -1 (non présent), donc le dernier élément de «1420344440» est poussé. Cela donne 48, le code ASCII correspondant au caractère 0. Pour 2 et 3, 48 est également poussé.

Les entiers poussés pour 4, 5, 6, 7, 8 et 9 sont 49, 52, 50, 48, 51 et 52.

Après le tri, le premier élément de l'état sera l'un des éléments donnant 48; le dernier sera l'un de ceux qui donneront 52. Le tri intégré est instable en général, mais j'ai vérifié empiriquement qu'il est stable dans ce cas particulier.

Le résultat est «[1 2 3 7 4 6 8 5 9]», ce qui correspond à une rotation dans le sens horaire du carré inférieur gauche.

Code optimisé pour la vitesse

6,(7++:t;       # Save [ 1 2 3 4 5 7 ] in variable “t” and discard it.
~               # Interpret the input string.
{               #
  :s            # Duplicate the current state.
  (1=           # Unshift the first element and push 1 if it is equal to 1 and 0 otherwise.
  .@            # Duplicate the boolean and rotate the unshifted array on top of it.
  7=9=          # Push 1 if the eighth element of “s” is equal to 9 and 0 otherwise.
  +4\-          # Add the booleans and subtract their sum from 4.
  rand          # Push a randomly chosen integers between 0 and the result from above.
  +.            # Add this integer to the first boolean and duplicate it for the output.
  .2/+          # Add 1 to the result if it is grater than one. Possible results: 0, 1, 3, 4
  @.            # Rotate the state on top of the stack and duplicate it.
  @>:s          # Slice the state at the integer from above and save the result in “s”.
  ^             # Compute the symmetric difference of state and sliced state.
  [             # Apply a clockwise rotation to the sliced array:
    3s=         # The fourth element becomes the first.
    0s=         # The first element becomes the second.
    2s=         # The third element remains the same.
    4s=         # The fifth element becomes the fourth.
    1s=         # The second element becomes the fifth.
  ]             # Collect the results into an array.
  +             # Concatenate with array of elements preceding the slice.
  s|            # Perform set union to add the remaining elements of “s”.
  .             # Duplicate the updated state.
  )9<           # Pop the last element; push 0 if it is equal to 9 and 1 otherwise.
  \t            # Swap the popped state on top and push [ 1 2 3 4 5 7 ].
  >             # Push 0 if the state begins with [ 1 2 3 4 5 6 ] and 1 otherwise.
  |             # Take the logical OR of the booleans.
}do             # If the resulting boolean is 1, repeat the loop.
.$              # Duplicate the state and sort it.
>30764`*        # If the state was not sorted, 7 and 8 are swapped, so push "30764".

Observez que les rotations 3, 0, 7, 6 et 4 permutent les éléments dans les positions 7 et 8, sans modifier les positions des sept éléments restants.

Python avec Numpy - 158

from numpy import*
A=input()
while any(A.flat>range(1,10)):i,j,k=random.randint(0,2,3);A[i:i+2,j:j+2]=rot90(A[i:i+2,j:j+2],1+2*k);print"tb"[i]+"lr"[j]+"wc"[k]

L'entrée doit être au format suivant:

array([[1,2,5],[4,3,6],[7,8,9]])

Chaque ligne de sortie est un mouvement codé en chaînes comme trwou blcet à lire comme suit:

• t: Haut
• b: bas
• l: la gauche
• r: droite
• c: dans le sens horaire
• w: anti-horaire (widdershins)

Ce programme effectue des déplacements aléatoires jusqu'à ce que la configuration cible soit atteinte. Dans l'hypothèse approximative que chaque mouvement a une probabilité indépendante de 1/9! pour atteindre la configuration cible¹, le nombre de rotations avant qu'une solution soit exponentiellement distribuée avec une moyenne (c'est-à-dire le nombre moyen de mouvements) de 9! ≈ 3,6 · 10⁵. Ceci est conforme à une courte expérience (20 essais).

^{¹ 9! étant le nombre total de configurations.}

Solution C ++ avec le moins de coups - largeur d'abord (1847 car.)

Après un peu plus de réflexion, je pense que cela a été fait de manière beaucoup plus efficace et plus sensible. Cette solution, même si elle ne remporte certainement pas ce golf, est jusqu'à présent la seule qui tentera de trouver le plus petit nombre de rotations qui résoudra la planche. Jusqu'à présent, il résout chaque plateau aléatoire que je lui ai lancé en neuf mouvements ou moins. Il fonctionne également beaucoup mieux que le dernier et, espérons-le, répond aux commentaires de Dennis ci-dessous.

Par rapport à la solution précédente, le plus grand changement consistait à déplacer l'historique des clés de l'état de la carte (BS) dans une nouvelle classe qui stocke l'historique à une profondeur donnée (DKH). Chaque fois que l'application effectue un mouvement, elle vérifie l'historique à cette profondeur et à toutes les profondeurs avant de voir si elle a déjà été évaluée, si c'est le cas, elle ne sera pas ajoutée à la file d'attente. Cela semble réduire considérablement le stockage dans la file d'attente (en supprimant tout cet historique de l'état de la carte lui-même) et réduit donc à peu près tous les élagages stupides que j'ai dû faire pour empêcher le code de manquer de mémoire. De plus, il s'exécute beaucoup plus rapidement car il y a beaucoup moins à copier dans la file d'attente.

Maintenant, c'est une première recherche simple sur les différents états du forum. De plus, il s'avère que je veux changer le jeu de clés (actuellement stocké sous la forme d'un ensemble de nombres en base 9, chacun étant calculé par BS :: key comme représentation en base 9 de la carte) sur un jeu de bits avoir 9! les bits semblent inutiles; bien que j'aie découvert comment calculer une clé dans le "système de nombres factoriels" qui aurait pu être utilisé pour calculer le bit dans le jeu de bits à tester / basculer.

Ainsi, la nouvelle solution est:

#include <iostream>
#include <list>
#include <set>
#include <vector>
using namespace std;
struct BS{
#define LPB(i) for(int*i=b;i-b<9;i++)
struct ROP{int t, d;};
typedef vector<ROP> SV;
typedef unsigned int KEY;
typedef set<KEY> KH;
BS(const int*d){const int*x=d;int*y=b;for(;x-d<9;x++,y++)*y=*x;}
BS(){LPB(i)*i=i-b+1;}
bool solved(){LPB(i)if(i-b+1!=*i)return 0;return 1;}
void rot(int t, int d){return rot((ROP){t,d});}
void rot(ROP r){rotb(r);s.push_back(r);}
bool undo(){if (s.empty())return false;ROP &u=s.back();u.d*=-1;rotb(u);s.pop_back();return true;}
SV &sol(){return s;}
KEY key(){KEY rv=0;LPB(i){rv*=9;rv+=*i-1;}return rv;}
int b[9];
SV s;
void rotb(ROP r){int c=r.t<2?r.t:r.t+1;int bi=(r.d>0?3:4)+c;const int*ri=r.d>0?(const int[]){0,1,4}:(const int[]){1,0,3};for(int i=0;i<3;i++)swap(b[bi],b[c+ri[i]]);}
};
ostream &operator<<(ostream &o, BS::ROP r){static const char *s[]={"tl","tr","bl","br"};o<<s[r.t]<<(r.d<0?"w":"c");return o;}
struct DKH{
~DKH(){for(HV::iterator i=h.begin();i<h.end();++i)if(*i!=NULL)delete *i;}
void add(int d,BS b){h.resize(d+1);if(h[d]==NULL)h[d]=new BS::KH();h[d]->insert(b.key());}
bool exists(BS &b){BS::KEY k=b.key();size_t d=min(b.sol().size(),h.size()-1);do if (h[d]->find(k)!=h[d]->end())return true;while(d--!=0);return false;}
typedef vector<BS::KH *> HV;HV h;
};
static bool solve(BS &b)
{
const BS::ROP v[8]={{0,-1},{0,1},{1,-1},{1,1},{2,-1},{2,1},{3,-1},{3,1}};
DKH h;h.add(0,b);
list<BS> q;q.push_back(b);
while (!q.empty())
{
BS qb=q.front();q.pop_front();
if (qb.solved()){b=qb;return true;}
int d=qb.sol().size()+1;
for (int m=0;m<8;++m){qb.rot(v[m]);if (!h.exists(qb)){h.add(d,qb);q.push_back(qb);}qb.undo();}
}
return false;
}
int main()
{
BS b((const int[]){4,9,2,3,5,7,8,1,6});
if (solve(b)){BS::SV s=b.sol();for(BS::SV::iterator i=s.begin();i!=s.end();++i)cout<<*i<<" ";cout<<endl;}
}

CJam - 39

l{4mr_o_1>+_@m<_[Z0Y4X]\f=\5>+m>__$>}g;

Un autre solveur aléatoire :)
Il prend une chaîne telle que 492357816 et génère une (longue) série de chiffres de 0 à 3, chacun représentant une rotation dans le sens horaire d'un bloc: 0 = en haut à gauche, 1 = en haut à droite, 2 = en bas -gauche, 3 = en bas à droite.

Brève explication:

4mrgénère un nombre aléatoire de 0 à 3
_1>+incrémente le nombre s'il est supérieur à 1 (nous nous retrouvons donc avec 0, 1, 3 ou 4 - les index de départ des 4 blocs)
m<fait tourner la chaîne vers la gauche (comme 492357816 -> 923578164, pas la rotation du bloc) afin d'amener le bloc à tourner dans la première position,
[Z0Y4X]\f=la rotation du bloc affecte les 5 premiers caractères, comme 12345 -> 41352;
X = 1, Y = 2, Z = 3 donc [Z0Y4X] est en fait [3 0 2 4 1] et ce sont les index basés sur 0 des tuiles pivotées
5>copie le reste de la chaîne
m>fait pivoter la chaîne (modifiée) vers la bonne
__$>vérifie si la chaîne est triée (c'est la condition d'arrêt)

Mathematica, 104 caractères

Nous pouvons interpréter la tâche dans le langage des groupes de permutation. Les quatre rotations ne sont que quatre permutations qui génèrent le groupe symétrique S ₉ , et la tâche consiste simplement à écrire une permutation en tant que produit des générateurs. Mathematica a une fonction intégrée pour ce faire.

i={1,2,5,4};GroupElementToWord[PermutationGroup[Cycles/@({i}+#&/@i-1)],Input[]~FindPermutation~Range@9]

Exemple:

Contribution:

{4, 9, 2, 8, 3, 7, 1, 5, 6}

Production:

{-2, -3, -4, 2, 4, 1, 4, -1, -2, 3, 2, -4, 3, 4, -3, -3, -4, -4, -2, -2, -3, -2, 3, -1}

• 1: en haut à gauche dans le sens horaire
• 2: en haut à droite dans le sens horaire
• 3: en bas à droite dans le sens horaire
• 4: en bas à gauche dans le sens horaire
• -1: en haut à gauche dans le sens antihoraire
• -2: en haut à droite dans le sens antihoraire
• -3: en bas à droite dans le sens antihoraire
• -4: en bas à gauche dans le sens antihoraire