Uma tartaruga encontra um portal

30

A tartaruga quer se mover ao longo da grade para chegar à sua comida. Ele quer saber quantos movimentos serão necessários para ele chegar lá.

Além disso, como é lento, ele tem teleportadores montados em torno de seu domínio, que ele utilizará se diminuir o seu caminho. Ou evite-os se prolongar seu caminho.

Conheça a tartaruga

🐢

As vidas de tartarugas em uma grade

XXXXXXXXXXXX🐢XXXXXXXXXXXX
A tartaruga pode mover para qualquer quadrado adjacente ...
XXXXXXXX🐢XXXXXXXX

No entanto, a tartaruga não pode se mover para um quadrado com uma montanha

X🌄XXXXXX🌄🐢XX🌄XX🌄XXX

A Tartaruga quer comer seu Morango, e gostaria de saber quanto tempo levará para chegar ao seu Morango

X🌄🍓🐢🌄XX🌄XXXX
Este exemplo levaria a tartaruga 5 voltas
X🌄🍓🌄🌄XX
Felizmente, a Tartaruga encontrou um teleportador! Existem dois teleports na grade que são mapeados um para o outro. Pisar no teleporter move imediatamente a tartaruga para o teleporter correspondente. Os teletransportadores são muito instáveis ​​e, depois de usá-los uma vez, desaparecem e não são mais utilizáveis.
🔵🌄🍓🐢🌄🔴X🌄XXXX
É agora mais rápido para a tartaruga para subir duas vezes. Agora, o tartarugas caminho mais curto é2
🔵🌄🐢🌄🔴X🌄XXXX

O desafio

Dada uma configuração inicial da grade, o número de movimentos necessários para a tartaruga alcançar seu morango.

Regras

  • Você pode assumir que a grade de entrada tem uma solução

  • Cada grade terá apenas um, strawberrydois portalse umturtle

  • A grade de entrada pode ser inserida em qualquer formato conveniente

  • Você deve tratar teleporterssão itens de uso único

  • Na vez em que a tartaruga se move para um teleporterquadrado, ele já está no correspondente teleporter. Ele nunca se muda para um teleportere fica lá para se mexer

  • O caminho mais curto não precisa fazer uso do portal

  • A tartaruga não pode passar para azulejos de montanha

  • Você pode usar qualquer caractere ASCII ou inteiro para representar mountains, turtle, empty grid square,strawberry

  • Você pode usar o mesmo caractere ou dois caracteres ASCII ou números inteiros diferentes para representar os teleporterpares

  • Uma grade pode ter mais de um caminho com o mesmo tamanho de caminho mais curto

  • Isso é

Esclarecimentos às Regras

  • Você deve tratar teleporterssão itens de uso único.

🐢X🔵X🍓🌄🌄🌄🌄🌄🔴XXXX

Só poderia ser resolvido entrando e saindo dos portais duas vezes. No momento de fazer esse esclarecimento, ambas as soluções agiram assumindo que eram de uso único ou que não havia razão para tentar quadrados usados ​​anteriormente. Para evitar quebrar suas soluções trabalhadas, essa parecia a melhor maneira de explicar essa configuração. Portanto, isso seria considerado uma grade inválida.

Casos de teste formatados como listas

[ ['T', 'X', 'X', 'S', 'X'], ['X', 'X', 'X', 'X', 'X'], ['X', 'X', 'X', 'X', 'X'] ] --> 3
[ ['T', 'M', 'X', 'S', 'X'], ['X', 'M', 'X', 'X', 'X'], ['O', 'X', 'X', 'X', 'O'] ] --> 4
[ ['T', 'M', 'X', 'S', 'O'], ['O', 'M', 'X', 'X', 'X'], ['X', 'X', 'X', 'X', 'X'] ] --> 2
[ ['T', 'M', 'X', 'S', 'X'], ['O', 'M', 'X', 'X', 'X'], ['O', 'X', 'X', 'X', 'X'] ] --> 4
[ ['T', 'M', 'S', 'X', 'O'], ['X', 'M', 'M', 'M', 'M'], ['X', 'X', 'X', 'X', 'O'] ] --> 7
[ ['T', 'X', 'X', 'S', 'X'], ['O', 'M', 'M', 'M', 'X'], ['X', 'X', 'O', 'X', 'X'] ] --> 3

Casos de teste formatados para humanos

T X X S X
X X X X X
X X X X X --> 3

T M X S X
X M X X X
O X X X O --> 4

T M X S O
O M X X X
X X X X X --> 2

T M X S X
O M X X X
O X X X X --> 4

T M S X O
X M M M M
X X X X O --> 7

T X X S X
O M M M X
X X O X X --> 3

Créditos

Projeto e estrutura via: Mouse faminto por Arnauld

Desafios propostos Editar conselhos: Kamil-drakari , beefster

Aviso geral de edição: okx nedla2004 mbomb007

akozi
fonte
2
Acho que seria uma boa ideia adicionar um caso de teste em que o uso do teletransporte levaria mais tempo.
Okx
@Okx Criando e adicionando agora.
akozi 03/02
Editado, obrigado.
akozi 03/02
1
@ xnor Eu sinto que isso pode ser abstrato das minhas regras originais. Então talvez seja melhor portais para um item de uso único?
akozi 03/02
1
Relacionado (eu acho).
Charlie

Respostas:

13

JavaScript (ES7),  140 139  138 bytes

Recebe entrada como uma matriz de números inteiros com o seguinte mapeamento:

  • -1
  • 0 0X
  • 1 = 🌄 (montanha)
  • 2 = 🐢 (tartaruga)
  • 3 = 🍓 (morango)
m=>(R=g=(t,X,Y,i)=>m.map((r,y)=>r.map((v,x)=>r[(u=0,t?v-t:(x-X)**2+(y-Y)**2<3?v-3?~v?v:u--:R=R<i?R:i:1)||g(u,x,y,u-~i,r[x]=1),x]=v)))(2)|R

Experimente online!

Quão?

gtt0 0(x,y)(X,Y)

EuRmin(R,Eu)

t=2

t=-1Eu

R

Comentado

m => (                        // m[] = input matrix
  R =                         // initialize R to a non-numeric value
  g = (t, X, Y, i) =>         // g = recursive search function taking t = expected tile,
                              //     (X, Y) = current coordinates, i = path length
    m.map((r, y) =>           // for each row r[] at position y in m[]:
      r.map((v, x) =>         //   for each tile v at position x in r[]:
        r[                    //     this statement will eventually restore r[x] to v
          ( u = 0,            //     u = next tile to look for, or 0 if none
            t ?               //     if we're looking for a specific tile:
              v - t           //       test whether we've found it
            :                 //     else:
              (x - X) ** 2 +  //       compute the squared Euclidean distance between
              (y - Y) ** 2    //       (x, y) and (X, Y)
              < 3 ?           //       if it's less than 3 (i.e. reachable from (X, Y)):
                v - 3 ?       //         if v is not equal to 3:
                  ~v ?        //           if v is not equal to -1:
                    v         //             test if v = 0
                  :           //           else (v = -1):
                    u--       //             set u = -1 to find the other portal
                :             //         else (v = 3):
                  R = R < i ? //           we've found the strawberry: set R = min(R, i)
                      R : i   //
              :               //       else (this tile can't be reached):
                1             //         yield 1
          ) ||                //     if the above result is falsy:
          g(                  //       do a recursive call:
            u,                //         t = u
            x, y,             //         move to (x, y)
            u - ~i,           //         unless u is set to -1, increment i
            r[x] = 1          //         set this tile to a mountain
          ),                  //       end of recursive call
          x                   //     restore r[x] ...
        ] = v                 //     ... to v
    ))                        // end of both map() loops
)(2) | R                      // initial call to g with t = 2; return R
Arnauld
fonte
1
"Cada peça visitada é temporariamente configurada em uma montanha para impedir que a tartaruga se mova duas vezes na mesma peça" Que truque adorável. Ótima resposta, e como sempre, agradeço respostas com explicações :)
akozi
5

Python 2 , 441 431 341 bytes

from itertools import*
G=input()
W=len(G[0])
H=len(G)
A=[0]*5
E=enumerate
for y,r in E(G):
 for x,C in E(r):A[C]=[x,y]
for L in count():
 for M in product(*[zip('UDLR'*2,'LRDU    ')]*L):
  x,y=A[0]
  for m in M:
    x+='R'in m;x-='L'in m;y+='D'in m;y-='U'in m
    if(x,y)==A[3]:x,y=A[2]
    if 1-(W>x>-1<y<H)or G[y][x]>3:break
  if[x,y]==A[1]:exit(L)

Experimente online!

Insira como listas, mas usando números em vez de caracteres (graças a Quintec) e um valor separado para o destino do teleportador. Esses recuos grandes devem ser caracteres de tabulação se o Stack Exchange os remover. Quaisquer dicas ou idéias especialmente bem-vindas, pois sinto que isso pode ficar um pouco mais curto.

A tabela para caracteres usados ​​no desafio para os números usados ​​para o meu programa está abaixo, mas você também pode usar este programa .

Challenge | My program
T         | 0
S         | 1
E         | 2
O         | 3
M         | 4
X         | -1

-10 bytes graças à Quintec, alterando a entrada de caracteres para números.

- Muitos bytes graças a Jonathan Frech, ElPedro e Jonathan Allan.

nedla2004
fonte
2
Provavelmente, você pode cortar alguns caracteres inserindo uma lista em que cada objeto é representado por um número em vez de um caractere de seqüência de caracteres.
Quintec 03/02
@Quintec Adicionado, obrigado. Eu gostaria de fazer o mesmo nas instruções, mas as diagonais teriam que ser feitas separadamente. Ainda pode ser possível movê-los para números.
nedla2004 3/02
1
@ElPedro Ahha eu posso raspar 4 assim
Jonathan Allan
1
... e mais 10 para 356
Jonathan Allan
2
@JonathanAllan e ElPedro e Jonathan French. Ótimas dicas de todos vocês, e eu as adicionei juntamente com algumas coisas que eu criei. (Depois de muito atraso)
nedla2004
2

Python 2 , 391 397 403 422 bytes

M=input()
from networkx import*
a=b=c=d=0
N,h,w,S=[-1,0,1],len(M),len(M[0]),[]
for i in range(h):
 for j in range(w):
  I,m=(i,j),M[i][j]
  if m>7:c,d=a,b;a,b=I
  if m<0:Z=I
  if m==5:F=I
  S+=[I+I]
S+=[(a,b,c,d),(c,d,a,b)]
print len(shortest_path(from_edgelist([((A+p,B+q),(C,D))for A,B,C,D in S for p,q in[(p,q)for p in N for q in N]if-1<A+p<h and-1<B+q<w and M[C][D]*M[A+p][B+q]]),Z,F))-1

Experimente online!

O problema é traduzido em um gráfico e a solução é encontrar o caminho mais curto entre a tartaruga e o morango.

Challenge | This code
T         | -1
S         |  5
O         |  8
M         |  0
X         |  1
mdahmoune
fonte