Zagubiony pionek

Po zakończeniu gry w szachy pozostawiono ocalały pionek za liniami wroga. pomóżmy mu znaleźć najkrótszą drogę do domu.

Pierwotny problem opisuje tablicę „szachy” nXn i funkcję f: {1,..,n-1}X{1,..,n}X{-1,0,1} => R+wag. celem jest znalezienie najlepszej ścieżki z jakiegoś kwadratu w linii buttom do innego kwadratu w górnej linii, gdzie możliwe ruchy to: w lewo, w górę, w prawo w górę i nie możesz wyjść z planszy.

Problem jest stosunkowo łatwy do rozwiązania w O (n ^ 2) przy użyciu programowania dynamicznego, ale jest to kodegolf i nie dbamy o bezużyteczne rzeczy, takie jak złożoność czasu pracy ...

Problem

dane wejściowe: tablica 3-wymiarowa (lub inna wybrana przez Ciebie kolekcja, otrzymana przez stdin lub jako argument funkcji), odpowiadająca zwykłej szachownicy, dokładnie w rozmiarze: 7X8X3 (#linePasses X #rowSize X #movesPerPass) zawierająca nieujemne liczby całkowite. koszt przeniesienia z pewnej pozycji, (i,j)gdzie ijest indeks wiersza i jindeks kolumny, to:

• a[i][j][0]na koszt podróży w górę w lewo do kwadratu (i+1,j-1)lub graficznie \.
• a[i][j][1]na koszt podróży do kwadratu (i+1,j)lub graficznie |.
• a[i][j][2]na koszt podróży w górę w prawo do kwadratu (i+1,j+1)lub graficznie /.

możesz założyć, że nie będzie zawierać ścieżki o wartości większej niż MAX_INT.

wyjście: wyjście ascii 8X8 pokazujące najlepszą (najkrótszą, tj. minimalną sumę wag) ścieżkę (jeśli jest więcej niż 1 optymalny wynik, możesz pokazać dowolną wybraną ścieżkę). ścieżka jest rysowana od dołu do góry, gdzie w każdej linii postać odpowiadająca pozycji pionka na ścieżce jest tą, którą zamierza wykonać. np. jeśli pionek ma zamiar przesunąć się w górę w lewo z kolumny 3 (do kolumny 2), powinieneś narysować:

#?######
##\#####

gdzie ?należy zastąpić kolejnym ruchem. ostateczne stanowisko należy ustalić jako X.

Przykłady

Wejście:

[
  [[1,1,1],[1,1,1],[0,1,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1]],
  [[1,1,1],[1,0,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1]],
  [[1,1,1],[1,1,0],[1,1,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1]],
  [[1,1,1],[1,1,1],[1,1,0],[1,1,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1]],
  [[1,1,1],[1,1,1],[1,1,1],[1,0,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1]],
  [[1,1,1],[1,1,1],[1,1,1],[1,0,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1]],
  [[1,1,1],[1,1,1],[1,1,1],[0,1,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1]]
]

wynik:

##X#####
###\####
###|####
###|####
##/#####
#/######
#|######
##\#####

Wejście:

[
  [[41,27,38],[12,83,32],[50,53,35],[46,32,26],[55,89,82],[75,30,87],[2,11,64],[8,55,22]],
  [[56,21,0],[83,25,38],[43,75,63],[56,60,77],[68,55,89],[99,48,67],[94,30,9],[62,62,58]],
  [[23,18,40],[24,47,61],[96,45,72],[71,6,48],[75,63,98],[93,56,51],[23,31,30],[49,34,99]],
  [[20,47,42],[62,79,72],[32,28,44],[68,61,55],[62,39,57],[4,17,49],[97,85,6],[91,18,12]],
  [[51,50,11],[32,39,56],[12,82,23],[33,88,87],[60,55,22],[29,78,14],[70,11,42],[63,94,67]],
  [[75,64,60],[27,79,86],[70,72,56],[55,45,32],[95,67,12],[87,93,98],[81,36,53],[38,22,93]],
  [[31,80,50],[77,71,22],[59,46,86],[64,71,53],[41,19,95],[62,71,22],[92,80,41],[26,74,29]]
]

wynik:

######X#
#####/##
####/###
#####\##
#####|##
######\#
######|#
#######\

to jest kod-golf , więc wygrywa najkrótszy kod.

Graj sprawiedliwie. brak luk ...

EDYTOWAĆ:

Iv'e napisał proste rozwiązanie do gry w golfa w scala, na które można spojrzeć. Istnieje również strona, na której można grać za pomocą kodu Scala on-line: scalakata (wystarczy skopiować i wkleić zawartość do scalakata, a następnie nacisnąć przycisk odtwarzania)

P: 199 bajtów

f:{m::x;n::{@/[+/-1 0 1_\:/:(x;m[y;;|!3]);0 2;(0W,),{x,0W}]};i:*<*|r:{&/n[x;y]}\[8#0;!7];  s:{-1+{*<x}'+n[y;z]}\[();(,8#0),-1_r;!7];j:i,{x+y x}\[i;|s];-1(@[8#"#";;:;]'[j;"X","/|\\"1+s'[|!7;-1_j]]);}

UWAGI

• Q interpreter (kx.com) bezpłatny do użytku niekomercyjnego (wersje dla Windows, Linux, Mac)
• To rozwiązanie wykorzystuje wewnętrzny rdzeń Q (wewnętrznie nazwany k4), więc potrzebujemy pliku skryptowego z rozszerzeniem k lub interaktywnego interpretera w trybie k (\ polecenie przy pierwszym znaku zachęty). Natomiast „pełna” (czytelna) wersja języka wymaga skryptu z rozszerzeniem q i jest trybem domyślnym w interaktywnym tłumaczu.

TEST

f ((1 1 1; 1 1 1; 0 1 1; 1 1 1; 1 1 1; 1 1 1; 1 1 1; 1 1 1)
   (1 1 1; 1 0 1; 1 1 1; 1 1 1; 1 1 1; 1 1 1; 1 1 1; 1 1 1)
   (1 1 1; 1 1 0; 1 1 1; 1 1 1; 1 1 1; 1 1 1; 1 1 1; 1 1 1)
   (1 1 1; 1 1 1; 1 1 0; 1 1 1; 1 1 1; 1 1 1; 1 1 1; 1 1 1)
   (1 1 1; 1 1 1; 1 1 1; 1 0 1; 1 1 1; 1 1 1; 1 1 1; 1 1 1)
   (1 1 1; 1 1 1; 1 1 1; 1 0 1; 1 1 1; 1 1 1; 1 1 1; 1 1 1)
   (1 1 1; 1 1 1; 1 1 1; 0 1 1; 1 1 1; 1 1 1; 1 1 1; 1 1 1))

##X#####
###\####
###|####
###|####
##/#####
#/######
#|######
##\#####

f ((41 27 38; 12 83 32; 50 53 35; 46 32 26; 55 89 82; 75 30 87;  2 11 64;  8 55 22)
   (56 21  0; 83 25 38; 43 75 63; 56 60 77; 68 55 89; 99 48 67; 94 30  9; 62 62 58)
   (23 18 40; 24 47 61; 96 45 72; 71  6 48; 75 63 98; 93 56 51; 23 31 30; 49 34 99)
   (20 47 42; 62 79 72; 32 28 44; 68 61 55; 62 39 57;  4 17 49; 97 85  6; 91 18 12)
   (51 50 11; 32 39 56; 12 82 23; 33 88 87; 60 55 22; 29 78 14; 70 11 42; 63 94 67)
   (75 64 60; 27 79 86; 70 72 56; 55 45 32; 95 67 12; 87 93 98; 81 36 53; 38 22 93)
   (31 80 50; 77 71 22; 59 46 86; 64 71 53; 41 19 95; 62 71 22; 92 80 41; 26 74 29))

######X#
#####/##
####/###
#####\##
######\#
######|#
######|#
#######\

WYJAŚNIENIE

W celu zilustrowania zakładamy drugi test (macierz ((41 27 38; 12 83 32; ....)

Transformujemy macierz oryginalną (m na poziomie kodu): zamiast matrycy pierwotnej z trojaczką dla każdej współrzędnej, definiujemy macierz dla przesunięć w lewo, w górę i w prawo. Lewa macierz zawiera wartości 7x7 (upuszczamy pierwszą kolumnę), górna macierz 7x8, a prawa macierz 7x7 (przestawiamy ostatnią kolumnę).

left                           up                         right
12 50 46 55 75 2  8       27 83 53 32 89 30 11 55     38 32 35 26 82 87 64
83 43 56 68 99 94 62      21 25 75 60 55 48 30 62     0  38 63 77 89 67 9 
24 96 71 75 93 23 49      18 47 45 6  63 56 31 34     40 61 72 48 98 51 30
62 32 68 62 4  97 91      47 79 28 61 39 17 85 18     42 72 44 55 57 49 6 
32 12 33 60 29 70 63      50 39 82 88 55 78 11 94     11 56 23 87 22 14 42
27 70 55 95 87 81 38      64 79 72 45 67 93 36 22     60 86 56 32 12 98 53
77 59 64 41 62 92 26      80 71 46 71 19 71 80 74     50 22 86 53 95 22 41

Aby obliczyć pozycję końcową, musimy ocenić ścieżkę kosztów minimalnych. Zakładamy koszt początkowy 0 0 0 0 0 0 0 0 (koszt dotarcia do każdej kolumny pierwszego rzędu) i iterujemy z każdym kolejnym rzędem. W każdej kolumnie i obliczamy trzy wartości:

• koszt poprzedniej wartości i + 1 plus lewy [i + 1]. Zrzucamy pierwszy składnik kosztu (kolumny przesunięć i wierszy do dodania) i sumujemy składnik do składnika

• koszt poprzedniej wartości i plus [i]. Sumujemy komponent do komponentu

• koszt poprzedniej wartości i-1 plus prawo [i-1]. Opuszczamy ostatni składnik kosztu (kolumny przesunięć i wierszy, aby dodać) i sumujemy składnik do składnika

Aby obliczyć minimum, wykonujemy lewy koszt poprzedzający nieskończoność i prawy koszt dołączający nieskończoność: z 3 wektorami ośmiu składników obliczamy minimalny składnik do komponentu. Wynikowa wartość jest kosztem podstawowym nowej iteracji

Dla pierwszej iteracji otrzymujemy wartości (0 W jest nieskończone w Q)

0W 12 50 46 55 75 2  8
27 83 53 32 89 30 11 55
38 32 35 26 82 87 64 0W

i oblicza minimum każdej kolumny

27 12 35 26 55 30 2 8

Po wszystkich iteracjach mamy minimalny koszt dotarcia do każdego kwadratu (zakładając wiersz 0 u góry, 7 u dołu). Interesuje nas tylko ostatnia kolumna, ale wszystkie wyniki pośrednie rysuję w celach ilustracyjnych

0   0   0   0   0   0   0   0
27  12  35  26  55  30  2   8
27  37  78  82  110 78  11  70
45  61  123 88  173 129 34  104
87  123 151 143 212 133 40  122
98  155 163 176 234 147 51  185
158 182 219 208 246 234 87  207
208 204 265 261 265 256 128 233

Teraz znaleźliśmy minimalną wartość w ostatnim wierszu (128, w kolumnie 6). To koniec ścieżki (znak wyjściowy X).

Ponownie obliczamy koszt, ale teraz adnotujemy kierunek, z którego otrzymujemy każde minimum (która z 3 wartości użytych do obliczenia minimum jest wybraną wartością).

\|/|\///
\\\\\/|/
\\\|//|/
\\|\//|/
\\|//|\/
\\//|\|/
\|/|/|\/

Odwracamy wiersze, umieszczamy „X” w pozycji 6 i zachowujemy tylko ścieżkę, która kończy się w kolumnie 6 (pozostałe są zastąpione przez #)

######X#
#####/##
####/###
#####\##
######\#
######|#
######|#
#######\