Permutacje Piętnastki


13

Wyzwanie

Rozważ następujący schemat Piętnastki w stanie ułożonym:

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

Podekscytowany łamigłówka przy każdym ruchu ma możliwość przesunięcia jednego elementu sąsiadującego z pustym polem do pustego pola. Na przykład po 1przeniesieniu mamy 2możliwe scenariusze (niech 0będzie spacją):

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

Po 2ruchach łamigłówka ma 5różne wyniki (pamiętaj, że dwa powyższe przypadki są wykluczone, ponieważ nie można ich osiągnąć w 2 ruchach). Jedną z takich sytuacji jest pierwotnie rozwiązany stan, który można osiągnąć na dwa różne sposoby.

Twoim zadaniem w tym wyzwaniu jest uzyskanie szeregu różnych wyników, do których może doprowadzić określona liczba ruchów. Jako dane wejściowe weź liczbę N >= 0i wypisz liczbę unikalnych sytuacji, które mogą pojawić się po Nruchach.

Zasady

  • To jest golf golfowy. Najkrótszy kod wygrywa!
  • Standardowe luki są niedozwolone.
  • Twój kod powinien być w stanie obliczyć sprawę w N = 10ciągu kilku minut. Prawdopodobnie nie przetestuję tej zasady, chyba że w odpowiedzi znajdzie się oczywiste nadużycie czasu.

Przypadki testowe

(Wyniki wygenerowane na podstawie podsumowań OEIS A089484 (Jak opisano na czacie Geobits ), zautomatyzowane przez skrypt Martina Büttnera . Dziękujemy za całą pomoc!)

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

Odpowiedzi:


5

Pyth, 36 bajtów

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

Demonstracja . Uprząż testowa.

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.

3

CJam, 54 52 51 50 49 47 45 bajtów

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

Wypróbuj online w interpretatorze CJam (powinno to zająć mniej niż 10 sekund).

Jak to działa

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#

3

Retina , 289 276 bajtów

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

Pobiera dane wejściowe i drukuje dane wyjściowe jako jednoargumentowy.

Możesz umieścić każdą linię w jednym pliku lub uruchomić kod tak jak w przypadku -sflagi. Na przykład:

> echo -n 111|retina -s fifteen_puzzle
111111111111

Istotą tej metody jest śledzenie wszystkich możliwych pozycji (bez powtórzeń), które mogą wystąpić po dokładnych kkrokach. Zaczynamy formularz k = 0i powtarzamy kroki podstawiania (używając (` and )` modifiers), aż osiągniemy wejściową liczbę kroków.

Podczas tego obliczenia nasz ciąg zawsze ma postać

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

gdzie puzzle_statejest abcd%efgh%ijkl%mnoxpewna permutacja liter. xoznacza puste miejsce, pozostałe litery to kafelki. %są ogranicznikami wierszy.

yoznacza, że ​​stan jest generowany w bieżącym kroku ( k), więc nie należy go używać do generowania innych stanów w tym kroku.

1zaznacz liczbę pozostałych kroków.

Podstawową mechaniką kodu Retina jest to, że każde dopasowanie nieparzystej linii jest zmieniane na następną (parzystą) linię.

Kod z dodanym wyjaśnieniem:

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 bajtów zapisanych dzięki @MartinButtner.


2

Python, 310 253 243 229 bajtów

Najnowsza wersja z ulepszeniami sugerowanymi przez @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)

Moja własna wersja, która była dłuższa (243 bajty), ale łatwiejsza do odczytania:

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)

Proste wyszukiwanie w pierwszej kolejności, kodowanie stanów jako krotki i przechowywanie ich w zestawie, aby były wyjątkowe.

Zajmuje około 0,03 sekundy na moim laptopie dla N = 10. Czas pracy znacznie wzrasta w przypadku większych liczb, na przykład około 12 sekund dla N = 20.


Aliasing s.addprawdopodobnie uratuje niektóre postacie.
isaacg

@isaacg Zapisałem sporo, przenosząc podobny kod do funkcji. Patrząc na to teraz, prawdopodobnie nie muszę podawać się tza argument. Poza tym, myślę, że prawdopodobnie byłoby więcej miejsca na ulepszenia, gdybym miał lepsze umiejętności w Pythonie.
Reto Koradi

3
Można przekonwertować ifoświadczenia do wyrażenia Zwarcie z efektem ubocznym jak j%4and e(j-1,j)tak można umieścić je w jednej linii jako logiczną krotki: 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

@randomra Brzmi dobrze, spróbuję tego jutro. Pomyślałem, że istnieje pewnie sprytny sposób użycia wyrażeń warunkowych zamiast serii ifinstrukcji. Zastanawiam się także, czy istnieje krótszy sposób na zbudowanie krotki z zamianą dwóch elementów.
Reto Koradi

1
Konwersja do listy, zamiana i Nawrócenie krotki jest trochę krótsza: def e(a,b):*l,=t;l[a],l[b]=l[b],l[a];s.add(tuple(l)).
randomra

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

Przykład:

$ time perl 15.pl <<<20
2244884
real    0m39.660s
user    0m38.822s
sys 0m0.336s
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.