Caminhos e perda de tempo

22

Premissa

Recentemente, eu estava com meia hora de antecedência para um compromisso e decidi esperar do lado de fora. Eu também determinei que pareceria estranho se eu apenas ficasse imóvel na frente da casa. Por isso, decidi dar uma caminhada rápida, dentro de uma área limitada. Também concluí que, se eu começasse a andar em círculos, isso tornaria óbvio que eu estava demorando. Por isso, fui inspirado a criar meu primeiro desafio do Code Golf.

Especificação

Você receberá uma lista, um mapa da área, que conterá um " "ou outro "#", que representa espaços livres e obstáculos de algum tipo. Os espaços livres podem ser cruzados apenas uma vez e leva 1 minuto para cruzá-lo. Sua posição inicial será representada com uma "@"tradição parecida com um roguel, e o alvo será representado com um "$"porque é isso que você perderá lá. Você também receberá um número inteiro que representará quantos minutos você precisa perder antes de não parecer que estava se intrometendo. Quando você pousa no"$", terá que ter a quantidade exata de minutos (portanto, se você estiver em contagem regressiva, precisará ser 1 em um bloco adjacente e 0 no bloco). Sempre será possível chegar ao destino. Seu programa ou função precisará retornar uma lista mostrando o caminho mais curto com <,>, ^ e v para representar as quatro direções possíveis.

Exemplos

Entrada:

[[" ", " ", " ", " "],
 ["@", " ", " ", "$"],
 [" ", " ", " ", " "],
 [" ", " ", " ", " "]]

e

5

Ouput:

[[">", ">", ">", "v"],
 ["^", " ", " ", "$"],
 [" ", " ", " ", " "],
 [" ", " ", " ", " "]]

Entrada:

[[" ", "#", " ", " ", " "],
 [" ", "#", " ", " ", " "],
 ["@", "#", " ", "$", " "],
 [" ", " ", " ", " ", " "],
 [" ", "#", " ", " ", " "],
 [" ", "#", " ", " ", " "]]

e

7

Saída:

[[" ", "#", " ", " ", " "],
 [" ", "#", ">", "v", " "],
 ["v", "#", "^", "$", " "],
 [">", ">", "^", " ", " "],
 [" ", "#", " ", " ", " "],
 [" ", "#", " ", " ", " "]]

Entrada:

[[" ", "#", " ", " ", " "],
 [" ", "#", " ", " ", " "],
 ["@", "#", " ", "$", " "],
 [" ", " ", " ", " ", " "],
 [" ", "#", " ", " ", " "],
 [" ", "#", " ", " ", " "]]

e

17

Saída:

[[" ", "#", " ", "v", "<"],
 [" ", "#", " ", "v", "^"],
 ["v", "#", " ", "$", "^"],
 [">", ">", "v", ">", "^"],
 [" ", "#", "v", "^", "<"],
 [" ", "#", ">", ">", "^"]]

Regras

  • Aplicam-se brechas padrão
  • Cada bloco deve ser movido apenas uma vez
  • A quantidade exata de tempo deve ser gasta no quadro
  • Apenas um caminho precisa ser exibido no caso de vários caminhos
  • Esta é uma pergunta sobre código de golfe, para que a resposta mais curta seja ganha
  • Conforme a pergunta de user202729 nos comentários, você pode assumir uma entrada válida.

Adicione um comentário se precisar de mais esclarecimentos

LForchini
fonte
1
É garantido que "sempre será possível chegar ao destino no tempo especificado "?
usar o seguinte comando
Sim, ele vai, sempre haverá uma maneira, mesmo se complicado
LForchini
5
Bem-vindo ao PPCG! :) Bom primeiro desafio.
Giuseppe
O que aconteceu com o meio minuto em cada ponta ?! (não há necessidade de mudar nada, se não é óbvio)
Jonathan Allan

Respostas:

6

JavaScript (ES6), 171 bytes

Recebe entrada na sintaxe de currying (a)(n). Saídas modificando a matriz de entrada.

a=>g=(n,y=a[F='findIndex'](r=>~(i=r[F](v=>v>'?'))),x=i,R=a[y])=>!n--|[-1,0,1,2].every(d=>(R[x]='<^>v'[d+1],(c=(a[Y=y+~-d%2]||0)[X=x+d%2])<1?g(n,Y,X):n|c!='$')&&(R[x]=' '))

Experimente online!

Comentado

a =>                           // a[] = input matrix
g = (                          // g = recursive function taking:
  n,                           //   n = number of remaining moves
                               //   (x, y) = current coordinates, initialized as follows:
  y = a[F = 'findIndex'](r =>  //     y = index of the row containing the starting point,
    ~(i = r[F](v => v > '?'))  //         found by iterating over all rows r until we
  ),                           //         find some i such that r[i] > '?'
  x = i,                       //     x = index of the column of the starting point
  R = a[y]                     //   R[] = current row
) =>                           //
  !n-- |                       // decrement n; force failure if we're out of moves
  [-1, 0, 1, 2].every(d =>     // for each direction d, where -1 = left, 0 = up,
    (                          // 1 = right and 2 = down:
      R[x] = '<^>v'[d + 1], (  //   update the current cell with the direction symbol
        c = (                  //   c = content of the new cell at (X, Y) with:
          a[Y = y + ~-d % 2]   //     Y = y + dy
          || 0                 //     (use a dummy value if this row does not exist)
        )[X = x + d % 2]       //     X = x + dx
      ) < 1 ?                  //   if c is a space:
        g(n, Y, X)             //     we can go on with a recursive call
      :                        //   else:
        n | c != '$'           //     return false if n = 0 and we've reached the target
    ) &&                       //   unless the above result is falsy,
    (R[x] = ' ')               //   restore the current cell to a space
  )                            // end of every()
Arnauld
fonte
5

Python 2 , 310 256 bytes

Obrigado @cairdcoinheringaahing por except:0-3 bytes
Obrigado @Mnemonic por -8 bytes
Obrigado @ JonathanAllan por -3 bytes
Obrigado @ovs por -5 bytes

G,L=input()
R=[]
def S(x,y,G,c,R):
 try:
	if x>-1<y<G[y][x]in' @':i=0;exec"T=[r[:]for r in G];T[y][x]='<v^>'[i];S(x+~-i/2,y+~-(i^2)/2,T,c-1,R);i+=1;"*4
	R+=[G]*(0==c<'$'==G[y][x])
 except:0
for i,y in enumerate(G):"@"in y>S(y.index("@"),i,G,L,R)
print R[0]

Experimente online!

Alguma explicação:

try-excepté usado para garantir que ambas xe as ycoordenadas estejam nos limites. A exceção será gerada mediante o acesso a G[y][x]. Python é muito bom e índices negativos são aceitáveis, portanto, a verificação x>-1<yé adicionada.

T=[r[:]for r in G]usado para criar cópia de Gpor valores

~-i/2e ~-(i^2)/2são usados ​​para gerar pares (-1, 0), (0, 1), (0, -1), (1, 0), que costumavam se mover na grade (ainda deve haver um caminho mais curto!)

R+=[G]*(0==c<'$'==G[y][x])verifique, '$'atingido no número necessário de etapas. Ré usado para obter esse resultado de chamadas de função recursivas.

for i,y in enumerate(G):"@"in y>S(y.index("@"),i,G,L,R)Encontrada xe yde '@', em função de entrada e de chamada S.

print R[0] R pode conter mais de uma solução, então a saída é a primeira

Gambá morto
fonte
-4 bytes
caird coinheringaahing
1
Você pode salvar um byte, substituindo if G[y][x]=='$':por if'$'==G[y][x]:.
1
Na verdade, toda essa condição pode ser substituída R+=(G[y][x]=='$')*(c==0)*[G]por outro byte.
1
Huh, não sei o que estava vendo. Você pode salvar um par de bytes no primeiro estado comif(x>-1<y)*(G[y][x]in' @'):
1
Uma maneira mais curta para o seu y+cmp(i%2,i/2)seria y+~-(i^2)/2; pode muito bem ser mais curto ainda.
Jonathan Allan
2

Python 2 , 264 261 251 249 bytes

def f(a,n,r=-1,s=0):
 j=len(a[0]);x=1;z=y=0
 if r<0:s,r=divmod(sum(a,[]).index('@'),j)
 for c in'>v<^':
	u=r+x;v=s+y;x,y=-y,x
	if j>u>-1<v<len(a):b=[e[:]for e in a];b[s][r]=c;w=a[v][u];z=n*(w<'!')and f(b,n-1,u,v)or n==1and w=='$'and b
	if z:return z

Experimente online!

Chas Brown
fonte
1
@Arnauld: Opa! Ficou um pouco chique demais. Fixo.
quer