En algunos teléfonos Nokia antiguos, había una variación de los quince rompecabezas llamados Rotación. En esta variación, en lugar de deslizar un mosaico a la vez, rotó cuatro mosaicos a la vez en una dirección.

En este juego, comenzarías con un tablero como este:

4 9 2
3 5 7
8 1 6

Y al girar el bloque inferior izquierdo dos veces hacia la derecha y el bloque superior izquierdo una vez hacia la derecha, obtendrás esto:

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

y el 1mosaico estaría en la esquina superior izquierda donde se supone que debe estar. Finalmente, después de algunos movimientos más, terminarías con:

1 2 3
4 5 6
7 8 9

cual es la configuración "original".

Su tarea es crear un programa que tome como entrada una cuadrícula de números 3x3 del 1 al 9 (en cualquier formato que elija) y devolverá como salida una secuencia de movimientos que representan los movimientos que debe realizar para devolver el tablero a su original configuración (nuevamente, en cualquier formato que elija). Los movimientos legales se definen como mover el bloque [arriba / abajo] - [izquierda / derecha] de 4 fichas [en sentido horario / antihorario].

Su programa debe ser capaz de resolver todas las cuadrículas 3x3 posibles (todas las permutaciones son solucionables).

El código más corto para hacer esto gana.

GolfScript, 39/83 bytes

# 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`*

Velocidad vs tamaño

La versión de tamaño optimizado elige aleatoriamente rotaciones en el sentido de las agujas del reloj hasta lograr la permutación deseada. Esto es suficiente, ya que una rotación en sentido antihorario es equivalente a tres rotaciones consecutivas en sentido horario del mismo cuadrado.

La versión con velocidad optimizada hace lo mismo, excepto por lo siguiente:

1. Si el número 1 está en la esquina superior izquierda, ya no gira el cuadrado superior izquierdo.

2. Si el número 9 está en la esquina inferior derecha, ya no gira el cuadrado inferior derecho.

3. Los pasos para intercambiar las posiciones 7 y 8 están codificados, por lo que hay dos posiciones que permiten que el bucle se rompa.

Además de cambiar el algoritmo, la versión con velocidad optimizada logra la rotación de una manera directa, mientras que la versión con tamaño optimizado utiliza el ordenamiento incorporado de GolfScript por mapeo. También codifica el estado final (para comparación) en lugar de ordenar el estado en cada iteración.

La versión con velocidad optimizada requiere menos iteraciones y cada iteración es mucho más rápida por sí misma.

Puntos de referencia

He utilizado el siguiente código para aleatorizar las posiciones de los números y realizar ejecuciones de prueba, descomentando la línea correspondiente a la versión a probar:

[{[
    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 salida muestra el número mínimo y máximo de pasos necesarios para ordenar los números, el promedio y la mediana de todas las ejecuciones, así como el tiempo transcurrido en segundos:

$ 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

En mi máquina (Intel Core i7-3770), el tiempo medio de ejecución de la versión de tamaño optimizado fue de 3.58 minutos. El tiempo medio de ejecución de la versión con velocidad optimizada fue de 0,20 segundos. Por lo tanto, la versión con velocidad optimizada es aproximadamente 1075 veces más rápida.

La versión con velocidad optimizada produce 114 veces menos rotaciones. Realizar cada rotación es 9.4 veces más lento, lo que se debe principalmente a cómo se actualiza el estado.

I / O

La salida consta de números de 3 bits. El MSB está configurado para rotaciones en sentido antihorario, el bit central está configurado para cuadrados más bajos y el LSB está configurado para cuadrados derechos. Por lo tanto, 0 (4) es el cuadrado superior izquierdo, 1 (5) el superior derecho, 2 (6) el inferior izquierdo y 3 (7) el inferior derecho.

La versión con velocidad optimizada imprime todas las rotaciones en una sola línea. La versión de tamaño optimizado imprime una rotación por línea, seguida de la posición final de los números.

Para la versión con velocidad optimizada, la entrada debe producir una matriz que contenga los números del 1 al 9 cuando se evalúa. Para la versión de tamaño optimizado, la entrada debe ser una cadena sin nueva línea final; No se evalúa.

Ejecuciones de ejemplo:

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

Código de tamaño optimizado

{               #
  .             # 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 actualización del estado se logra de la siguiente manera:

La rotación 2 produce el número entero 3 después de sumar 1. Si el estado es "123456789", al dividir el estado se obtiene "456789".

Justo antes de ejecutar "$", los elementos superiores de la pila son:

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

"$" Ejecuta el bloque una vez para cada elemento de la matriz que se ordenará, después de presionar el elemento en sí.

El índice de 1 en “[4 5 6 7 8 9]” es -1 (no presente), por lo que se empuja el último elemento de "1420344440". Esto produce 48, el código ASCII correspondiente al carácter 0. Para 2 y 3, 48 también se empuja.

Los enteros presionados para 4, 5, 6, 7, 8 y 9 son 49, 52, 50, 48, 51 y 52.

Después de ordenar, el primer elemento del estado será uno de los elementos que produzcan 48; el último será uno de los que produzcan 52. El tipo incorporado es inestable en general, pero he comprobado empíricamente que es estable en este caso particular.

El resultado es "[1 2 3 7 4 6 8 5 9]", que corresponde a una rotación en el sentido de las agujas del reloj del cuadrado inferior izquierdo.

Código de velocidad optimizada

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".

Observe que las rotaciones 3, 0, 7, 6 y 4 intercambian los elementos en las posiciones 7 y 8, sin alterar las posiciones de los siete elementos restantes.

Python con 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]

La entrada debe tener el siguiente formato:

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

Cada línea de salida es un movimiento codificado en cadenas como trwo blcy para leerse de la siguiente manera:

• t: parte superior
• b: fondo
• l: izquierda
• r: derecho
• c: agujas del reloj
• w: en sentido antihorario (widdershins)

Este programa realiza movimientos aleatorios hasta que se alcanza la configuración objetivo. ¡Bajo el supuesto aproximado de que cada movimiento tiene una probabilidad independiente de 1/9! para alcanzar la configuración objetivo¹, ¡el número de rotaciones antes de que una solución se distribuya exponencialmente con una media (es decir, el número promedio de movimientos) de 9! ≈ 3.6 · 10⁵. Esto está de acuerdo con un breve experimento (20 carreras).

^{¹ 9! siendo el número total de configuraciones.}

Solución de menos movimientos en C ++: amplitud primero (1847 caracteres)

Después de pensar un poco más, creo que he hecho esto de manera mucho más eficiente y sensata. Esta solución, aunque ciertamente no está ganando este golf, es hasta ahora la única que intentará encontrar el menor número de rotaciones que resolverán el tablero. Hasta ahora, resuelve cada tablero aleatorio que le he lanzado en nueve o menos movimientos. También tiene un rendimiento significativamente mejor que el anterior y, con suerte, aborda los comentarios de Dennis a continuación.

Desde la solución anterior, el cambio más grande fue mover el historial clave del estado del tablero (BS) a una nueva clase que almacena el historial a una profundidad dada (DKH). Cada vez que la aplicación realiza un movimiento, verifica el historial a esa profundidad y todas las profundidades antes de ver si alguna vez se ha evaluado, de ser así, no se agregará nuevamente a la cola. Esto parece reducir significativamente el almacenamiento en la cola (al eliminar todo este historial del estado de la placa) y, por lo tanto, reduce prácticamente toda la estúpida poda que tuve que hacer para evitar que el código se quedara sin memoria. Además, se ejecuta mucho más rápido ya que hay mucho menos para copiar en la cola.

Ahora, es una simple búsqueda de amplitud en los distintos estados del foro. Además, resulta que quiero cambiar el conjunto de claves (actualmente almacenado como un conjunto de números en base-9, cada uno de los cuales es calculado por BS :: key como la representación de base-9 del tablero) a un conjunto de bits teniendo 9! los bits parecen ser innecesarios; aunque descubrí cómo calcular una clave en el "sistema de números factoriales" que podría haberse utilizado para calcular el bit en el conjunto de bits para probar / alternar.

Entonces, la solución más nueva es:

#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;

Otro solucionador aleatorio :)
Toma una cadena como 492357816 y genera una serie (larga) de dígitos del 0 al 3, cada uno de los cuales representa una rotación en sentido horario de un bloque: 0 = arriba a la izquierda, 1 = arriba a la derecha, 2 = abajo -izquierda, 3 = abajo a la derecha.

Breve explicacion:

4mrgenera un número aleatorio de 0 a 3,
_1>+incrementa el número si es mayor que 1 (por lo que terminamos con 0, 1, 3 o 4, los índices iniciales de los 4 bloques)
m<gira la cadena hacia la izquierda (como 492357816 -> 923578164, no la rotación del bloque) para que el bloque gire en la primera posición,
[Z0Y4X]\f=realiza la rotación del bloque que afecta a los primeros 5 caracteres, como 12345 -> 41352;
X = 1, Y = 2, Z = 3, así que [Z0Y4X] es en realidad [3 0 2 4 1] y esos son los índices basados ​​en 0 de las
5>copias de mosaicos rotados, el resto de la cadena
m>gira la cadena (modificada) de nuevo a la derecha
__$>verifica si la cadena está ordenada (es la condición de detención)

Mathematica, 104 caracteres

Podemos interpretar la tarea en el lenguaje de los grupos de permutación. Las cuatro rotaciones son solo cuatro permutaciones que generan el grupo simétrico S ₉ , y la tarea es simplemente escribir una permutación como producto de los generadores. Mathematica tiene una función incorporada para hacer esto.

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

Ejemplo:

Entrada:

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

Salida:

{-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: arriba a la izquierda en sentido horario
• 2: arriba a la derecha en sentido horario
• 3: abajo a la derecha en sentido horario
• 4: abajo a la izquierda en sentido horario
• -1: arriba a la izquierda en sentido antihorario
• -2: arriba a la derecha en sentido antihorario
• -3: abajo a la derecha en sentido antihorario
• -4: abajo a la izquierda en sentido antihorario