Permutações do Quinze Quebra-Cabeças

13

O desafio

Considere o seguinte diagrama do Quinze quebra-cabeças em seu estado resolvido:

_____________________
|    |    |    |    |
| 1  | 2  | 3  | 4  |
|____|____|____|____|
|    |    |    |    |
| 5  | 6  | 7  | 8  |
|____|____|____|____|
|    |    |    |    |
| 9  | 10 | 11 | 12 |
|____|____|____|____|
|    |    |    |    |
| 13 | 14 | 15 |    |
|____|____|____|____|

A cada movimento, um quebra-cabeças animado tem a oportunidade de mover uma peça adjacente ao espaço em branco para o espaço em branco. Por exemplo, após a 1mudança, temos 2cenários possíveis (deixe 0um espaço em branco):

1   2   3   4          1   2   3   4
5   6   7   8          5   6   7   8
9   10  11  12   and   9   10  11  0
13  14  0   15         13  14  15  12

Após os 2movimentos, o quebra-cabeça tem 5resultados diferentes (observe que os dois casos acima são excluídos, pois não podem ser alcançados em 2 movimentos). Uma dessas situações é o estado resolvido original e pode ser alcançado de duas maneiras diferentes.

Sua tarefa neste desafio é produzir o número de resultados diferentes aos quais um certo número de movimentos pode levar. Como entrada, pegue um número N >= 0e produza o número de situações únicas que podem aparecer após os Nmovimentos.

Regras

  • Isso é código-golfe. O código mais curto vence!
  • As brechas padrão não são permitidas.
  • Seu código deve poder calcular o caso N = 10em alguns minutos. Provavelmente não testarei essa regra, a menos que exista um abuso óbvio de tempo em uma resposta.

Casos de teste

(Resultados gerados a partir dos somatórios de OEIS A089484 (conforme Geobits descrito no bate-papo ), automatizados pelo script de Martin Büttner . Obrigado por toda a ajuda!)

0 moves: 1
1 moves: 2
2 moves: 5
3 moves: 12
4 moves: 29
5 moves: 66
6 moves: 136
7 moves: 278
8 moves: 582
9 moves: 1224
10 moves: 2530
11 moves: 5162
12 moves: 10338
13 moves: 20706
14 moves: 41159
15 moves: 81548
16 moves: 160159
17 moves: 313392
18 moves: 607501
19 moves: 1173136
20 moves: 2244884
21 moves: 4271406
22 moves: 8047295
23 moves: 15055186
24 moves: 27873613
25 moves: 51197332
26 moves: 93009236
27 moves: 167435388
28 moves: 297909255
29 moves: 524507316
30 moves: 911835416
31 moves: 1566529356
BrainSteel
fonte

Respostas:

5

Pitão, 36 bytes

lu{smmXd,0@dk)fq1.a.DR4,Txd0UdGQ]U16

Demonstração . Equipamento de teste.

lu{smmXd,0@dk)fq1.a.DR4,Txd0UdGQ]U16

                 .a.DR4,Txd0            Find the Euclidean distance between the
                                        present location of 0 and a given location.
              fq1           Ud          Filter over all locations on that distance
                                        equaling 1.
     mXd,0@dk)                          Map each such location to the grid with 0
                                        and the value at that location swapped.
  {sm                         G         Map all unique grids possible after n-1
                                        steps to all unique grids after n steps.
 u                             Q]U16    Repeat <input> times, starting with the
                                        initial grid.
l                                       Print the length of the resulting set.
isaacg
fonte
3

CJam, 54 52 51 50 49 47 45 bytes

G,ari{{:S0#S{4md2$4md@-@@-mh1=},f{Se\}}%:|}*,

Experimente online no intérprete CJam (deve levar menos de 10 segundos).

Como funciona

G,a       e# Push R := [[0 1 ... 15]].
ri{       e# Do int(input()) times:
  {:S     e#   For each S in R:
    0#    e#     Push the index of 0 in S (I).
    S{    e#     Filter S; for each J in in S:
      4md e#       Push J/4 and J%4.
      2$  e#       Copy I.
      4md e#       Push I/4 and I%4.
      @-  e#       Compute (I%4)-(J%4).
      @@- e#       Compute (J%4)-(I%4).
      mh  e#       2-norm distance: a b -> sqrt(aa + bb)
      1=  e#       Check if the distance is 1.
    },    e#     Keep all values of J with distance 1 from I.
    f{    e#     For each J:
      S   e#       Push S. 
      e\  e#       Swap S at indexes I and J.
    }     e#     This pushes an array of all valid modifications of S.
  }%      e#   Collect the results for all S in R in an array.
  :|      e#   Reduce the outmost array using set union (removes duplicates).
}*        e#
Dennis
fonte
3

Retina , 289 276 bytes

^
,abcd%efgh%ijkl%mnox,
(`(,[^,]*)x([^,%])([^,y]*),
$0$1$2x$3y,
(,[^,]*)([^,%])x([^,y]*),
$0$1x$2$3y,
(,[^,]*)x([^,]{4})([^,])([^,y]*),
$0$1$3$2x$4y,
(,[^,]*)([^,])([^,]{4})x([^,y]*),
$0$1x$3$2$4y,
,.{19},(?=.*1)|,[^,]{20},(?=[^1]*$)|y|1$

+)`([^,]{19})(.*),\1,
$1$2
[^a]

a
1

Recebe entrada e imprime a saída em unário.

Você pode colocar cada linha em um único arquivo ou executar o código como está com o -ssinalizador. Por exemplo:

> echo -n 111|retina -s fifteen_puzzle
111111111111

O núcleo do método é que controlamos todas as posições possíveis (sem repetição) que podem ocorrer após exatamente as ketapas. Começamos a formar k = 0e repetimos as etapas de substituição (usando o (` and )` modifiers) até atingirmos o número de etapas de entrada.

Durante esse cálculo, nossa string sempre tem a forma de

(,[puzzle_state]y?,)+1*

onde puzzle_stateestá abcd%efgh%ijkl%mnoxcom alguma permutação das letras. xrepresenta o lugar vazio, o resto das letras são os azulejos. %são delimitadores de linha.

ymarca que o estado é gerado na etapa atual ( k), portanto, não deve ser usado para gerar outros estados nesta etapa.

1marca o número de etapas restantes.

O mecanismo básico do código Retina é que todas as correspondências de uma linha ímpar são alteradas para a próxima linha (par).

O código com explicação adicional:

initialize string
^
,abcd%efgh%ijkl%mnox,

while string changes
(`

for every old (y-less) state concatenate a new state with moving the empty tile to r/l/d/u if possible
right
(,[^,]*)x([^,%])([^,y]*),
$0$1$2x$3y,
left
(,[^,]*)([^,%])x([^,y]*),
$0$1x$2$3y,
down
(,[^,]*)x([^,]{4})([^,])([^,y]*),
$0$1$3$2x$4y,
up
(,[^,]*)([^,])([^,]{4})x([^,y]*),
$0$1x$3$2$4y,

if we should have made this step (there are 1's left) remove old states
,.{19},(?=.*1)

if we should not have made this step (no more 1's left) remove new states
,[^,]{20},(?=[^1]*$)

remove y markers
y

remove one 1 (decrease remaining step count)
1$


remove duplicates until string changes (with + modifier)
+`([^,]{19})(.*),\1,
$1$2    

end while
)`

remove non-a's, 1 a stays from each state
[^a]

change a's to 1's
a
1

10 bytes salvos graças a @MartinButtner.

randomra
fonte
2

Python, 310 253 243 229 bytes

Versão mais recente com melhoria sugerida por @randomra:

s=set()
s.add(tuple(range(16)))
def e(a,b):s.add(t[:a]+(t[b],)+t[a+1:b]+(t[a],)+t[b+1:])
for k in range(input()):
 p,s=s,set()
 for t in p:j=t.index(0);j%4and e(j-1,j);j%4>2or e(j,j+1);j<4or e(j-4,j);j>11or e(j,j+4)
print len(s)

Minha própria versão, que era mais longa (243 bytes), mas mais fácil de ler:

s=set()
s.add(tuple(range(16)))
def e(a,b):s.add(t[:a]+(t[b],)+t[a+1:b]+(t[a],)+t[b+1:])
for k in range(input()):
 p,s=s,set()
 for t in p:
  j=t.index(0)
  if j%4:e(j-1,j)
  if j%4<3:e(j,j+1)
  if j>3:e(j-4,j)
  if j<12:e(j,j+4)
print len(s)

Primeira pesquisa de largura simples, codificando os estados como tuplas e armazenando-os em um conjunto para mantê-los exclusivos.

Leva cerca de 0,03 segundos no meu laptop para N = 10. O tempo de execução aumenta substancialmente para números maiores, por exemplo, cerca de 12 segundos para N = 20.

Reto Koradi
fonte
O aliasing s.addprovavelmente salvaria alguns caracteres.
Isaacg
@isaacg Eu economizei bastante movendo o código semelhante para uma função. Olhando para isso agora, provavelmente não tenho que passar tcomo argumento. Fora isso, acho que provavelmente há mais espaço para melhorias se eu tivesse melhores habilidades em Python.
Reto Koradi 27/05
3
Você pode converter as ifdeclarações em expressões-circuito curto, com efeitos a lado como j%4and e(j-1,j)para que você possa colocá-los em uma linha como uma tupla boolean: j%4and e(j-1,j),j%4>2or e(j,j+1),j<4or e(j-4,j),j>11or e(j,j+4).
randomra 27/05
@ randomra Parece bom, vou tentar isso amanhã. Pensei que houvesse provavelmente uma maneira inteligente de usar expressões condicionais em vez da série de ifdeclarações. Também me pergunto se existe uma maneira mais curta de construir uma tupla com dois elementos trocados.
Reto Koradi 27/05
1
Convertendo a lista, trocando e converter de volta para tupla é um pouco menor: def e(a,b):*l,=t;l[a],l[b]=l[b],l[a];s.add(tuple(l)).
randomra 27/05
1

Perl, 148

#!perl -p
$s{"abcd.efgh.ijkl.mno#"}=1;for(1..$_){$x=$_,map{$r{$_}=1if
s/($x)/$3$2$1/}keys%s for
qw!\w)(# #)(\w \w)(.{4})(# #)(.{4})(\w!;%s=%r;%r=()}$_=keys%s

Exemplo:

$ time perl 15.pl <<<20
2244884
real    0m39.660s
user    0m38.822s
sys 0m0.336s
nutki
fonte