Le défi

Considérez le diagramme suivant du puzzle de quinze dans son état résolu:

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

À chaque mouvement, un casse-tête excité a la possibilité de déplacer une pièce adjacente à l'espace vide dans l'espace vide. Par exemple, après le 1déménagement, nous avons 2des scénarios possibles ( 0soit un espace vide):

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

Après les 2mouvements, le puzzle a 5des résultats différents (Notez que les deux cas ci-dessus sont exclus, car ils ne peuvent pas être atteints en 2 mouvements). L'une de ces situations est l'état résolu d'origine et peut être atteint de deux manières différentes.

Votre tâche dans ce défi est de produire le nombre de résultats différents qu'un certain nombre de mouvements peuvent entraîner. En entrée, prenez un nombre N >= 0et sortez le nombre de situations uniques qui peuvent apparaître après les Ndéplacements.

Règles

• C'est du code-golf. Le code le plus court gagne!
• Les failles standard ne sont pas autorisées.
• Votre code devrait être capable de calculer le cas pendant N = 10quelques minutes. Je ne testerai probablement pas cette règle à moins qu'il n'y ait un abus de temps évident dans la réponse.

Cas de test

(Résultats générés à partir des sommations d' OEIS A089484 (comme les géobits décrits dans le chat ), automatisés par le script de Martin Büttner . Merci pour toute l'aide!)

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

Pyth, 36 octets

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

Démonstration . Harnais de test.

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.

CJam, 54 52 51 50 49 47 45 octets

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

Essayez-le en ligne dans l' interpréteur CJam (cela devrait prendre moins de 10 secondes).

Comment ça fonctionne

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#

Rétine , 289 276 octets

^
,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

Prend l'entrée et imprime la sortie en unaire.

Vous pouvez mettre chaque ligne dans un seul fichier ou exécuter le code tel quel avec l' -sindicateur. Par exemple:

> echo -n 111|retina -s fifteen_puzzle
111111111111

Le cœur de la méthode est que nous gardons une trace de toutes les positions possibles (sans répétition) qui peuvent se produire après exactement des kétapes. Nous commençons le formulaire k = 0et répétons les étapes de substitution (en utilisant le (` and )` modifiers) jusqu'à ce que nous atteignions le nombre d'étapes entré.

Pendant ce calcul, notre chaîne a toujours la forme de

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

où puzzle_stateest abcd%efgh%ijkl%mnoxavec une permutation des lettres. xreprésente la place vide, le reste des lettres sont les tuiles. %sont des délimiteurs de lignes.

ymarque que l'état est généré dans l'étape actuelle ( k), il ne doit donc pas être utilisé pour générer d'autres états dans cette étape.

1marque le nombre de pas restant.

Le mécanisme de base du code Retina est que chaque correspondance d'une ligne impaire est changée à la ligne suivante (paire).

Le code avec une explication supplémentaire:

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 octets enregistrés grâce à @MartinButtner.

Python, 310 253 243 229 octets

Dernière version avec amélioration suggérée par @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)

Ma propre version, qui était plus longue (243 octets), mais plus facile à lire:

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)

Recherche simple en largeur, encodant les états sous forme de tuples et les stockant dans un ensemble pour les garder uniques.

Prend environ 0,03 seconde sur mon ordinateur portable pour N = 10. Le temps de fonctionnement augmente considérablement pour les grands nombres, par exemple environ 12 secondes pour N = 20.

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

Exemple:

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