Em alguns telefones antigos da Nokia, havia uma variação dos quinze quebra-cabeças chamados Rotação. Nesta variação, em vez de deslizar um bloco de cada vez, você girou quatro blocos de cada vez em uma direção.

Neste jogo, você começaria com um quadro como este:

4 9 2
3 5 7
8 1 6

E girando o bloco inferior esquerdo duas vezes no sentido horário e o bloco superior esquerdo uma vez no sentido horário, você obtém o seguinte:

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

e o 1ladrilho estaria no canto superior esquerdo, onde deveria estar. Eventualmente, depois de mais alguns movimentos, você acabaria com:

1 2 3
4 5 6
7 8 9

qual é a configuração "original".

Sua tarefa é criar um programa que terá como entrada uma grade de números 3x3 de 1 a 9 (em qualquer formato que você escolher) e retorne como saída uma sequência de movimentos que representam os movimentos que você deve executar para retornar o quadro ao seu original. configuração (novamente, em qualquer formato que você escolher). Os movimentos legais são definidos como mover o bloco [superior / inferior] - [esquerdo / direito] de 4 peças [no sentido horário / anti-horário].

Seu programa deve ser capaz de resolver todas as grades 3x3 possíveis (todas as permutações são solucionáveis).

O código mais curto para fazer isso vence.

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

Velocidade vs tamanho

A versão com tamanho otimizado escolhe aleatoriamente as rotações no sentido horário até que a permutação desejada seja alcançada. Isso é suficiente, uma vez que uma rotação no sentido anti-horário é equivalente a três rotações consecutivas no sentido horário do mesmo quadrado.

A versão com velocidade otimizada faz o mesmo, exceto pelo seguinte:

1. Se o número 1 estiver no canto superior esquerdo, ele não girará mais o quadrado superior esquerdo.

2. Se o número 9 estiver no canto inferior direito, ele não girará mais o quadrado inferior direito.

3. As etapas para trocar as posições 7 e 8 são codificadas permanentemente, portanto, existem duas posições que permitem a quebra do loop.

Além de alterar o algoritmo, a versão com velocidade otimizada consegue a rotação de maneira direta, enquanto a versão com tamanho otimizado usa a classificação incorporada do GolfScript por mapeamento. Ele também codifica o estado final (para comparação) em vez de classificar o estado em todas as iterações.

A versão otimizada para velocidade requer menos iterações e cada iteração é muito mais rápida por si só.

Benchmarks

Eu usei o seguinte código para randomizar as posições dos números e executar testes, descomentando a linha correspondente à versão a ser testada:

[{[
    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: '\+

A saída mostra o número mínimo e máximo de etapas necessárias para ordenar os números, a média e a mediana de todas as execuções, bem como o tempo decorrido em 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

Na minha máquina (Intel Core i7-3770), o tempo médio de execução da versão com tamanho otimizado foi de 3,58 minutos. O tempo médio de execução da versão com velocidade otimizada foi de 0,20 segundos. Assim, a versão com velocidade otimizada é aproximadamente 1075 vezes mais rápida.

A versão com velocidade otimizada produz 114 vezes menos rotações. A execução de cada rotação é 9,4 vezes mais lenta, principalmente devido à atualização do estado.

I / O

A saída consiste em números de 3 bits. O MSB é definido para rotações no sentido anti-horário, o bit do meio é definido para os quadrados inferiores e o LSB é definido para os quadrados direitos. Assim, 0 (4) é o quadrado superior esquerdo, 1 (5) o superior direito, 2 (6) o inferior esquerdo e 3 (7) o inferior direito.

A versão com velocidade otimizada imprime todas as rotações em uma única linha. A versão com tamanho otimizado imprime uma rotação por linha, seguida pela posição final dos números.

Para a versão com velocidade otimizada, a entrada deve gerar uma matriz contendo os números de 1 a 9 quando avaliados. Para a versão com tamanho otimizado, a entrada deve ser uma sequência sem nova linha final; não é avaliado.

Exemplo é executado:

$ 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 com tamanho otimizado

{               #
  .             # 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.

A atualização do estado é alcançada da seguinte maneira:

A rotação 2 produz o número inteiro 3 após adicionar 1. Se o estado for "123456789", o fatiamento do estado produzirá "456789".

Logo antes de executar "$", os elementos mais altos da pilha são:

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

"$" Executa o bloco uma vez para cada elemento da matriz a ser classificado, depois de pressionar o próprio elemento.

O índice de 1 em “[4 5 6 7 8 9]” é -1 (não está presente); portanto, o último elemento de "1420344440" é pressionado. Isso gera 48, o código ASCII correspondente ao caractere 0. Para 2 e 3, 48 também é pressionado.

Os números inteiros pressionados para 4, 5, 6, 7, 8 e 9 são 49, 52, 50, 48, 51 e 52.

Após a classificação, o primeiro elemento do estado será um dos elementos com 48; o último será um daqueles com 52 anos. A classificação interna é instável em geral, mas verifiquei empiricamente que é estável nesse caso específico.

O resultado é "[1 2 3 7 4 6 8 5 9]", que corresponde a uma rotação no sentido horário do quadrado inferior esquerdo.

Código otimizado para velocidade

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 as rotações 3, 0, 7, 6 e 4 trocam os elementos nas posições 7 e 8, sem alterar as posições dos sete elementos restantes.

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

A entrada deve ter o seguinte formato:

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

Cada linha de saída é um movimento codificado em strings como trwou blce deve ser lido da seguinte maneira:

• t: topo
• b: inferior
• l: esquerda
• r: certo
• c: sentido horário
• w: anti-horário (widdershins)

Este programa executa movimentos aleatórios até que a configuração de destino seja atingida. Sob o pressuposto aproximado de que todo movimento tem uma probabilidade independente de 1/9! para atingir a configuração de destino¹, o número de rotações antes que uma solução seja exponencialmente distribuída com uma média (ou seja, o número médio de movimentos) de 9! ≈ 3,6 · 10⁵. Isso está de acordo com um pequeno experimento (20 execuções).

^{9! sendo o número total de configurações.}

Solução com menos movimentos de C ++ - largura em primeiro lugar (caracteres de 1847)

Depois de pensar um pouco mais, acho que fiz isso de maneira muito mais eficiente e sensata. Essa solução, embora certamente não esteja ganhando esse golfe, é a única que tenta encontrar o menor número de rotações que resolverá o quadro. Até agora, ele resolve todos os tabuleiros aleatórios que joguei em nove ou menos movimentos. Ele também tem um desempenho significativamente melhor que o meu último e, espero, aborda os comentários de Dennis abaixo.

A partir da solução anterior, a maior mudança foi mover o histórico principal do estado da placa (BS) para uma nova classe que armazena o histórico em uma determinada profundidade (DKH). Sempre que o aplicativo faz uma mudança, ele verifica o histórico nessa profundidade e em todas as profundidades anteriores para ver se alguma vez foi avaliado; nesse caso, não será adicionado à fila novamente. Isso parece reduzir significativamente o armazenamento na fila (removendo todo esse histórico do próprio estado da placa) e, portanto, reduz praticamente todas as podas estúpidas que eu tive que fazer para impedir que o código fique sem memória. Além disso, ele roda muito mais rápido, pois há muito menos para copiar na fila.

Agora, é uma primeira pesquisa simples e abrangente nos vários estados do fórum. Além disso, como quero dizer, eu quero alterar o conjunto de teclas (atualmente armazenado como conjunto de números na base-9, cada um dos quais é calculado pela BS :: key como a representação da placa-base-9) para um bitset tendo 9! bits parece desnecessário; embora eu tenha descoberto como calcular uma chave no "sistema de números fatoriais" que poderia ter sido usada para calcular o bit no bitset para testar / alternar.

Portanto, a solução mais nova é:

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

Outro solucionador aleatório :)
Ele pega uma sequência como 492357816 e gera uma série (longa) de dígitos de 0 a 3, cada um representando uma rotação no sentido horário de um bloco: 0 = superior esquerdo, 1 = superior direito, 2 = inferior esquerda, 3 = canto inferior direito.

Breve explicação:

4mrgera um número aleatório de 0 a 3
_1>+incrementa o número se for maior que 1 (então terminamos com 0, 1, 3 ou 4 - os índices iniciais dos 4 blocos)
m<gira a string para a esquerda (como 492357816 -> 923578164, não a rotação do bloco) para fazer com que o bloco gire na primeira posição,
[Z0Y4X]\f=faz a rotação do bloco que afeta os 5 primeiros caracteres, como 12345 -> 41352;
X = 1, Y = 2, Z = 3, de modo que [Z0Y4X] é realmente [3 0 2 4 1] e esses são os índices baseados em 0 dos blocos girados copiam
5>o restante da sequência
m>gira a sequência (modificada) de volta para o direito
__$>verifica se a sequência está classificada (é a condição de parada)

Mathematica, 104 caracteres

Podemos interpretar a tarefa na linguagem dos grupos de permutação. As quatro rotações são apenas quatro permutações que geram o grupo simétrico S ₉ , e a tarefa é apenas escrever uma permutação como um produto dos geradores. O Mathematica possui uma função interna para fazer isso.

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

Exemplo:

Entrada:

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

Resultado:

{-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: canto superior esquerdo no sentido horário
• 2: canto superior direito no sentido horário
• 3: canto inferior direito no sentido horário
• 4: canto inferior esquerdo no sentido horário
• -1: superior esquerdo no sentido anti-horário
• -2: canto superior direito no sentido anti-horário
• -3: canto inferior direito no sentido anti-horário
• -4: canto inferior esquerdo no sentido anti-horário