Zainspirowany przez We hopping tower i związany z 2D Maze Minus 1D

Wprowadzenie

Twoim zadaniem jest znalezienie najkrótszej ścieżki, aby wydostać się z labiryntu tablicowego zgodnie z określonymi regułami.

Wyzwanie

Macierz 1D a z n elementów można uznać za labirynt złożony z n punktów, przy czym punkt o indeksie k jest połączony z punktami za pomocą k + a [ k ] i k - a [ k ] w sposób jednokierunkowy. Innymi słowy, można przeskoczyć do przodu lub wstecz dokładnie [ k ] kroki od punktu o indeksie k . Punkty z indeksem poza granicami tablicy są traktowane poza labiryntem.

Aby to zilustrować, rozważ następującą tablicę:

[0,8,5,9,4,1,1,1,2,1,2]

Jeśli znajdujemy się teraz w piątym elemencie, ponieważ element ma 4, możemy przeskoczyć 4 kroki do przodu do 9 elementu lub 4 kroki do tyłu do pierwszego elementu. Jeśli zrobimy to drugie, otrzymamy element 0, co oznacza, że ​​dalsze ruchy nie są możliwe. Jeśli zrobimy to pierwsze, ponieważ dziewiąty element to 2, możemy przeskoczyć do 11. elementu, który jest znowu 2, a następnie możemy ponownie wskoczyć do „13. elementu”, który jest poza granicami i rozważał wyjście do labiryntu.

Więc jeśli zaczniemy od elementu pośrodku, jednym ze sposobów na wydostanie się z labiryntu jest przeskoczenie 1 krok do tyłu, 4 kroki do przodu, 2 kroki do przodu i ponownie 2 kroki do przodu, które można wyrazić jako tablicę [-1,4,2,2]. Alternatywnie można wyrazić z układem [4,8,10,12], który jest zapisywany indeksem zero na bazie wszystkich pośrednich i końcowych punktów (1 oparte wskaźnik jest dobry) lub tylko oznaczeń [-1,1,1,1].

Ucieczka z labiryntu od końca niskiego indeksu również jest OK.

Zastosowanie pierwszej notacji i rozpoczęcie od tego samego elementu [1,1,1,2,2]jest również rozwiązaniem, ale nie jest optymalne, ponieważ jest 5 kroków zamiast 4.

Zadanie polega na znalezieniu najkrótszej ścieżki, aby wydostać się z labiryntu macierzy i wyprowadzić ścieżkę. Jeśli istnieje więcej niż jedna optymalna ścieżka, możesz wyprowadzić jedną lub wszystkie z nich. Jeśli nie ma rozwiązania, powinieneś wypisać wybraną przez siebie wartość fałszowania, która jest dostrzegalna z prawidłowej ścieżki (nie generowanie żadnego wyniku również jest OK).

Dla uproszczenia liczba elementów w tablicy jest zawsze liczbą nieparzystą i zawsze zaczynamy od elementu pośrodku.

Przypadki testowe

Przypadki testowe ilustrują różne formy wyników, ale nie są do nich ograniczone.

Input
Output

[0,8,5,9,4,1,1,1,2,1,2]
[-1,4,2,2]

[2,3,7,1,2,0,2,8,9]
[2,9] (or [2,-5] or [[2,9],[2,-5]])

[0,1,2,2,3,4,4,4,3,2,2,3,0]
[1,-1,1,1]

[0,1,2,2,4,4,6,6,6,6,6,4,2,1,2,2,0]
[]

Okular

• Możesz napisać funkcję lub pełny program.

• Tablica zawiera tylko nieujemne liczby całkowite.

• Możesz pobierać dane wejściowe i wyjściowe za pomocą dowolnego standardowego formularza , ale w odpowiedzi określ, którego formularza używasz.

• To jest golf golfowy , najniższa liczba bajtów wygrywa.

• Jak zwykle obowiązują tutaj domyślne luki .

JavaScript (ES6), 117 bajtów

Zwraca tablicę pośrednich i końcowych punktów o indeksie 0 lub pustą tablicę, jeśli nie ma rozwiązania.

a=>(g=(x,p,d=a[x])=>1/d?[d,-d].map(d=>p.includes(X=x+d)||g(X,[...p,X])):o=o==''|o[p.length]?p:o)(a.length>>1,o=[])&&o

Wypróbuj online!

Skomentował

a =>                              // given the maze a[]
  (g = (                          // g = recursive function taking:
    x,                            //   x = current position
    p,                            //   p[] = list of visited cells
    d = a[x]                      //   d = value of current cell
  ) =>                            //
    1 / d ?                       // if d is defined:
      [d, -d].map(d =>            //   for d and -d:
        p.includes(X = x + d) ||  //     if the cell at X = x + d was not yet visited,
        g(X, [...p, X])           //     do a recursive call to g() at this position
      )                           //   end of map()
    :                             // else:
      o =                         //   update o:
        o == '' |                 //     if o was empty
        o[p.length] ?             //     or p is shorter than o:
          p                       //       set o to p
        :                         //     else:
          o                       //       let o unchanged
  )(a.length >> 1, o = [])        // initial call to g(), starting in the middle
  && o                            // return o

Łuska , 22 bajty

ḟȯ¬€ŀ¹FS+o*!¹⌈½L¹ṁπṡ1ŀ

Zwraca listę znaków lub pustą listę, jeśli rozwiązanie nie istnieje. Wypróbuj online!

Wyjaśnienie

Jest to rozwiązanie typu brute force, które sprawdza listy -1,0,1o coraz większej długości i zwraca pierwsze, które powoduje wyskakiwanie z tablicy. Ponieważ ma minimalną długość, nie będzie zawierać zer.

ḟȯ¬€ŀ¹FS+o*!¹⌈½L¹ṁπṡ1ŀ  Implicit input, say A = [0,1,1]
                     ŀ  Indices of A: [1,2,3]
                 ṁ      Map over them and concatenate:
                  π      Cartesian power
                   ṡ1    of the symmetric range [-1,0,1].
                        Result is B = [[-1],[0],[1],[-1,-1],...,[1,1,1]]
ḟ                       Find the first element of B that satisfies this:
                         Argument is a list, say C = [1,-1].
      F                  Reduce C from the left
             ⌈½L¹        using ceil(length(A)/2) as the initial value
       S+o*!¹            with this function:
                          Arguments are an index of A, say I = 2, and a sign, say S = 1.
           !¹             The element of A at I: 1
         o*               Multiply by S: 1
       S+                 Add to I: 2
                         At the end of the reduction, we have a number I, here 2.
   €ŀ¹                   Is it an element of the indices of A: Yes.
 ȯ¬                      Negate: No.
                        The result is the shortest list C for which I is outside of A.

Python 3 , 195 188 179 bajtów

def f(a):
 v=len(a);x,*s={v//2},[v//2]
 while all(v>b>-1for*c,b in s)*s:s=[x.add(u)or c+[b,u]for*c,b in s for u in[b+a[b],b-a[b]]if{u}-x]
 return[b[1:]for b in s if not-1<b[-1]<v]

Wypróbuj online!

Edytować:

• Zapisane 9 bajtów przez all(..)and s => all(..)*s, if u not in x => if{u}-x
  Pierwsze wykorzystuje boolean * list == int * list, drugie wykorzystują różnicę zestawu (pusty zestaw jest również fałszem).

Format wyjściowy: Zagnieżdżona tablica wszystkich optymalnych odpowiedzi, podana w postaci zerowych wskaźników punktów pośrednich i końcowych.

Na przykład: f([0,8,5,9,4,1,1,1,2,1,2]) == [[4, 8, 10, 12]].

Algorytm jest prosty BFS. srejestruje wszystkie możliwe iścieżki długości podczas iiteracji, z wyłączeniem indeksów już odwiedzonych. Zauważ, że rozszerzona notacja gwiazdowa jest używana (ab), ponieważ wielokrotny dostęp do tablicy jest kosztowny. Stwierdziłem, że taki zapis może również zmniejszyć niektóre białe spacje, jeśli jest stosowany poprawnie.

Z powyższego rozwiązania wykonałem również wersję rekurencyjną (ale dłuższą). Zarówno s andi or ssą potrzebne, w przeciwnym razie nie działa.

Python 3 , 210 bajtów

lambda a:[b[1:]for b in g(a,[[len(a)//2]],{len(a)//2})if not-1<b[-1]<len(a)]
g=lambda a,s,x:s and all(-1<b<len(a)for*c,b in s)and g(a,[x.add(u)or c+[b,u]for*c,b in s for u in[b+a[b],b-a[b]]if u not in x],x)or s

Wypróbuj online!

Haskell , 207 202 bajtów

^{5 bajtów zaoszczędzonych dzięki BMO .}

l=length
x!p|i<-h p,d<-x!!i=[p++[x]|x<-[(-d,i-d),(d,i+d)],x`notElem`p]
x?p|i<-h p=i<0||i>=l x
h=snd.last
x#[]=[]
x#p|l(x%p)<1=x#(p>>=(x!))|1>0=x%p
(%)=filter.(?)
f x=(tail.map fst)<$>x#[[(0,l x`div`2)]]

Wypróbuj online!

Jest to funkcja, która przyjmuje listę Intjako parametr i zwraca listę ścieżek, gdzie każda ścieżka jest listą względnych skoków wykonanych w celu wydostania się z tablicy.

Wersja bez golfa:

move :: [Int] -> [(Int, Int)] -> [Path]
move xs path = map(\x->path++[x]) $ filter (\s -> s`notElem`path) $ [(-delta, i-delta), (delta, i+delta)]
  where (_,i) = last path
        delta = xs!!i :: Int

outside :: [Int] -> Path -> Bool
outside xs paths = i < 0 || i >= length xs
  where (_,i) = last paths

shortest' :: [Path] -> [Int] -> [Path]
shortest' paths xs | null paths       = []
                   | not (null ready) = ready
                   | otherwise        = shortest' paths' xs
                   where ready  = filter (outside xs) paths
                         paths' = concatMap (move xs) paths

shortest xs = map tail $ map (map fst) $ shortest' [[(0,length xs`div`2)]] xs

C (gcc) , 269 bajtów

#define A n){for(printf("%d,",n);i^l[i];i=l[i])printf("%d,",x[i]);break;}if(!u[n]){u[n]=x[m]=n;l[m++]=i;
#define M calloc(r,sizeof(s))
*x,*u,*l,s,m=1,i,j,n,w;main(r,v)char**v;{s=r-1;x=M;u=M;l=M;for(*x=1+s/2;i<m;i++){j=x[i];if(w=atoi(v[j])){n=j+w;if(s<A}n=j-w;if(1>A}}}}

Wypróbuj online!

Początkowo próbowałem rekurencyjnego wyszukiwania wstecznego, ponieważ korzystanie mainz rekurencji jest zawsze zabawne. Ostatecznie jednak proste, nierekurencyjne wyszukiwanie po raz pierwszy zostało zmniejszone, czyli taka jest ta wersja. Ten program przyjmuje tablicę wejściową jako argumenty wiersza poleceń, bez nawiasów klamrowych, np. 0 8 5 9 4 1 1 1 2 1 2W pierwszym podanym przykładzie. Program wyświetla na wyjściu listę indeksów tablic 1-indeksowanych , rozdzielanych przecinkami, w odwrotnej kolejności, zaczynając od ostatecznego indeksu poza zakresem / „ucieczki” i przechodząc ponownie przez osiągnięte indeksy pośrednie (nie wyświetla środek, indeks początkowy). Program nie wyświetla nawiasów klamrowych wokół tablicy i pozostawia przecinek końcowy, ponieważ jest osobnyprintfinstrukcje mają wiele znaków. Dane wyjściowe odpowiadające pierwszemu przykładowi testu powyżej są 13,11,9,5,na przykład.

Jeśli nie ma drogi ucieczki z labiryntu macierzowego, program nic nie wypisuje.

Odtłuszczono i wyjaśniłem, że jest poniżej (mocno odśluzowany z pewnymi zmianami dla czytelności):

int *x, *u, *l, s, m = 1, i, j, n, w;                        //Declare all the state we'll need
int main(r, v) char** v;{                            
    s = r - 1;                                               //s is our actual array size, since v[0] is the program name.
    x = calloc(r, sizeof(int));                              //x is an array that will form our BFS queue. Since it is a BFS we've no need to visit any elements more than once (first visit will have been on a shortest route to it), so the amount of space we have here should suffice.
    u = calloc(r, sizeof(int));                              //u is an array that will be used to flag when an array index has been visited; only reason it's int* is for ease of declaration
    l = calloc(r, sizeof(int));                              //l is an array that will be used parallel to x and stores backpointers in the form of indexes into x, which will be used to construct the actual path once it is found.
    x[0] = 1 + (s/2);                                        //Init the first element in the queue to our center index of the array, adding one because of the program name in v/argv.
    for(; i < m; i++) {                                      //m is the number of elements in our BFS queue. It starts at 1 and grows during iteration; if this loop terminates before finding a path there is none.
        j = x[i];                                            //Current index in the array we are examining
        if (w = atoi(v[j])) {                                //Set w to be the actual array value at the current index (and check that it's nonzero since if it isn't we can't get anywhere from here)
            n = j + w;                                       //Try a move in the positive direction
            if (n > s) {                                     //If the move escapes the array
                for(printf("%d,", n); i ^ l[i]; i = l[i]) {  //Print the location escaped to and then loop back through the backpointers to reconstruct the path. The only backpointer that will point to its own queue index is the starting one, so terminate there.
                    printf("%d,", x[i]);                     //Print each intermediate array index
                }
                break;                                       //Then break the outer for loop and exit.
            }
            if(!u[n]) {                                      //If the jump didn't take us out of the array and we haven't visited where it goes to, add it to the queue.
                u[n] = x[m] = n;                             //m is the current tail of the queue, so put this new location there. Since we're 1-indexed and if n was zero we'd have escaped, we know it isn't so can use it to mark this index as visited also.
                l[m++] = i;                                  //Also set the backpointer for this new queue element to point back to the current index, then increment the tail of the queue.
            }
            n = j - w;                                       //Now the backwards move
            if (n < 1) {                                     //Repeat analogous to the forward case.
                for(printf("%d,", n); i ^ l[i]; i = l[i]) {
                    printf("%d,", x[i]);
                }
                break;
            }
            if (!u[n]) {
                u[n] = x[m] = n;
                l[m++] = i;
            }
        }
    }
}

Jak zwykle w golfowym kodzie C, wyniki kompilacji będą oczywiście zawierać przyjazną ścianę ostrzeżeń i notatek.

Perl 5 , -a: 73 bajty

(liczenie w starym stylu: 75 bajtów, +1dla ai +1zastępowanie -//przez -/$/i używanie $`dla $')

#!/usr/bin/perl -a
use 5.10.0;
@;=$#F/2;$v{$^H=$_}//=push@;,map$'+$_*($F[$^H]//1/!say$').$".$',-//,1for@

Podaj tablicę wejściową jako jedną linię na STDIN, np 0 8 5 9 4 1 1 1 2 1 2

drukuje odwiedzane pozycje w odwrotnej kolejności, łącznie z punktem początkowym, a następnie ulega awarii

Nic nie drukuje, jeśli nie ma rozwiązania

Wypróbuj online!

Rubin , 102 bajty

->a{b=[[a.size>>1]];b.map{|x|(v=a[w=x[0]])&&w>=0?[w-v,w+v].map{|j|x.index(j)?0:b<<[j]+x}:(break p x)}}

Wypróbuj online!

Bierze labirynt wejściowy jako tablicę, wypisuje drukując ścieżkę ucieczki w odwrotnej kolejności, od wyjścia do punktu początkowego (włącznie). Nie drukuje nic, jeśli nie ma ucieczki.

Takie podejście niewłaściwie wykorzystuje metodę mapy do iteracji przez tymczasową tablicę przechowującą historię ścieżek, która jest stale rozszerzana w locie, ilekroć istnieje kolejny możliwy krok do zrobienia.

Zasadniczo mógłbym zaoszczędzić kolejny bajt, używając return xzamiast niego break p x, ale oznaczałoby to twierdzenie, że moja wartość fałszowania jest równa wszystkim potwornym śmieciom w nim przechowywanym b. Prawdopodobnie byłoby to zbyt wiele, nawet biorąc pod uwagę dopuszczalną elastyczność wyjścia ...

Przewodnik

->a{
  b=[[a.size>>1]] #Initialize an array of paths with our starting point index
  b.map{|x|       #Iterate through this array
    (v=a[w=x[0]]) #w is the current point in the path, v is its array value
    &&w>=0        #Ruby's support for negative indexing costs us 6 bytes :(
    ?             #If we are still within the bounds of the maze
      [w-v,w+v].map{|j| #Try moving in both directions
        x.index(j)? #If we have been there before, or stuck on zero
        0         #This is a dead-end, just assign a throwaway value
        :b<<[j]+x #Otherwise push the elongated path on top of our iterator
      } 
    :(break p x)  #Escaped! Exit the loop and report the path
  }  
}