Inspirado por We do hopping de torre e relacionado a 2D Maze Minus 1D

Introdução

Sua tarefa é encontrar o caminho mais curto para sair de um labirinto de matrizes seguindo as regras especificadas.

Desafio

Uma matriz 1D a com n elementos pode ser considerada como um labirinto composto por n pontos, onde o ponto com o índice k é conectado aos pontos com k + a [ k ] ek - a [ k ] de maneira unidirecional. Em outras palavras, você pode pular para frente ou para trás exatamente a [ k ] etapas do ponto com o índice k . Pontos com um índice fora dos limites da matriz são considerados fora do labirinto.

Para ilustrar isso, considere a seguinte matriz,

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

Se estamos no 5º elemento agora, já que o elemento é 4, podemos pular 4 etapas para a frente para o 9º elemento ou 4 etapas para trás para o 1º elemento. Se fizermos o último, acabaremos com o elemento 0, que indica que não são possíveis outros movimentos. Se fizermos o primeiro, já que o 9º elemento é 2, podemos optar por pular para o 11º elemento, que é novamente um 2, e depois podemos pular novamente para o "13º elemento", que está fora dos limites do matriz e considerado uma saída para o labirinto.

Portanto, se começarmos do elemento do meio, uma maneira de sair do labirinto é dar um passo para trás, quatro passos para frente, dois passos para frente e novamente dois passos para frente, que podem ser expressos como a matriz [-1,4,2,2]. Como alternativa, você pode expressá-lo com a matriz [4,8,10,12]que registra o índice baseado em zero de todos os pontos intermediários e finais (o índice baseado em 1 também é bom) ou apenas os sinais [-1,1,1,1].

Escapar do labirinto a partir do final de baixo índice também é bom.

O uso da primeira notação e a partir do mesmo elemento [1,1,1,2,2]também é uma solução, mas não é ideal, pois há 5 etapas em vez de 4.

A tarefa é descobrir o caminho mais curto para sair do labirinto da matriz e gerar o caminho. Se houver mais de um caminho ideal, você poderá gerar um ou todos eles. Se não houver solução, você deve gerar um valor falso escolhido por você que seja discernível a partir de um caminho válido (não produzir nenhuma saída também é bom).

Por simplicidade, o número de elementos na matriz é sempre um número ímpar e sempre começamos a partir do elemento no meio.

Casos de teste

Os casos de teste ilustram várias formas de saída, mas você não está limitado a elas.

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]
[]

Especificações

• Você pode escrever uma função ou um programa completo.

• A matriz contém apenas números inteiros não negativos.

• Você pode receber e enviar informações através de qualquer formulário padrão , mas especifique na sua resposta qual formulário você está usando.

• Isso é código-golfe , o menor número de bytes vence.

• Como sempre, as brechas padrão se aplicam aqui.

JavaScript (ES6), 117 bytes

Retorna uma matriz de pontos intermediários e finais indexados a 0 ou uma matriz vazia, se não houver solução.

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

Experimente online!

Comentado

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

Casca , 22 bytes

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

Retorna uma lista de sinais ou uma lista vazia se uma solução não existir. Experimente online!

Explicação

Esta é uma solução de força bruta que verifica listas com -1,0,1comprimento cada vez maior e retorna a primeira que resulta em um salto para fora da matriz. Como é de tamanho mínimo, não conterá 0s.

ḟȯ¬€ŀ¹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 bytes

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]

Experimente online!

Editar:

• Salva 9 bytes por all(..)and s => all(..)*s: if u not in x => if{u}-x
  O primeiro explora boolean * list == int * list, o último usa a diferença do conjunto (o conjunto vazio também é falso).

Formato de saída: matriz aninhada de todas as respostas ideais, dados como índices baseados em zero de pontos intermediários e finais.

Por exemplo: f([0,8,5,9,4,1,1,1,2,1,2]) == [[4, 8, 10, 12]].

O algoritmo é simples BFS. sregistra todos os icaminhos de comprimento possível na iiteração, excluindo os índices já visitados. Observe que a notação estendida em estrela é (ab) usada porque o acesso repetido à matriz é caro. Descobri que essa notação também pode reduzir alguns espaços em branco se usada corretamente.

Também fiz uma versão recursiva (mas mais longa) da solução acima. Ambos s ande or ssão necessários, caso contrário, não funciona.

Python 3 , 210 bytes

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

Experimente online!

Haskell , 207 202 bytes

^{5 bytes salvos graças ao 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)]]

Experimente online!

Esta é uma função que leva uma lista de Int como parâmetro e retorna uma lista de caminhos em que cada caminho é uma lista de saltos relativos feitos para sair da matriz.

A versão não destruída:

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 bytes

#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}}}}

Experimente online!

Inicialmente tentei uma pesquisa de retorno recursivo, porque usar mainpara recursão é sempre divertido. No final, embora uma pesquisa direta e não-recursiva de largura pudesse ser reduzida, é essa a versão. Este programa usa a matriz de entrada como argumentos de linha de comando, sem chaves, por exemplo, 0 8 5 9 4 1 1 1 2 1 2para o primeiro exemplo fornecido. O programa gera no stdout uma lista de indexadas em 1 com índices de matriz com vírgula e em ordem inversa, iniciando no índice final, fora dos limites / 'escapado' e retornando aos índices intermediários alcançados (ele não gera o centro, índice inicial). O programa não gera chaves ao redor da matriz e deixa uma vírgula à direita porque separaprintfdeclarações têm muitos caracteres. A saída correspondente ao primeiro exemplo de teste acima é 13,11,9,5,, por exemplo.

Se não houver rota de escape do labirinto de matrizes, o programa não emitirá nada.

Degolfed e explicado abaixo (fortemente degolfed com algumas mudanças para facilitar a leitura):

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;
            }
        }
    }
}

Como de costume no código C, a saída da compilação incluirá, obviamente, uma parede amigável de avisos e notas.

Perl 5 , -a: 73 bytes

(contagem de estilo antigo: 75 bytes, +1para ae +1para substituir -//por -/$/e usar $`para $')

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

Dê a matriz de entrada como uma linha no STDIN, por exemplo 0 8 5 9 4 1 1 1 2 1 2

imprime as posições visitadas na ordem inversa, incluindo o ponto de partida, e depois trava

Imprime nada se não houver solução

Experimente online!

Ruby , 102 bytes

->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)}}

Experimente online!

Pega o labirinto de entrada como uma matriz e imprime o caminho de escape em sentido inverso, da saída ao ponto inicial (inclusive). Imprime nada se não houver escapatória.

Essa abordagem utiliza incorretamente o método map para iterar através de uma matriz temporária que armazena o histórico de caminhos, que é constantemente estendido em tempo real sempre que há outra etapa possível a ser executada.

Em princípio, eu poderia salvar outro byte usando em return xvez de break p x, mas isso significaria alegar que meu valor falso é igual a todo o lixo monstruoso armazenado b. Provavelmente, isso seria demais, mesmo considerando a flexibilidade permitida da saída ...

Passo a passo

->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
  }  
}