Черепаха находит портал

30

Черепаха хочет двигаться вдоль сетки, чтобы добраться до своей еды. Он хочет знать, сколько ходов ему понадобится, чтобы добраться туда.

Кроме того, поскольку он медлителен, у него установлены телепорты вокруг его домена, которые он будет использовать, если это сократит его путь. Или избегайте их, если это удлиняет его путь.

Встретить черепаху

🐢

Черепаха живет на сетке

XXXXXXXXXXXX🐢XXXXXXXXXXXX
Черепаха может двигаться в любой соседний квадрат ...
XXXXXXXX🐢XXXXXXXX

Однако, черепаха не может двигаться к квадрату с горы

X🌄XXXXXX🌄🐢XX🌄XX🌄XXX

Черепаха хочет съесть свою клубнику и хотела бы знать, сколько времени понадобится, чтобы добраться до его земляники.

X🌄🍓🐢🌄XX🌄XXXX
этом примере черепаха берет 5 ходов
X🌄🍓🌄🌄XX
к счастью, Черепаха нашла телепорт! В сетке есть два телепорта, которые отображаются друг на друга. Наступив на телепортер, немедленно перемещает черепаху к соответствующему телепорту. Телепорты очень нестабильны, и после их использования они исчезают и больше не используются.
🔵🌄🍓🐢🌄🔴X🌄XXXX
Теперь черепаха быстрее поднимается вверх в два раза. Теперь кратчайший путь черепах составляет2
🔵🌄🐢🌄🔴X🌄XXXX

Соревнование

Учитывая исходную конфигурацию сетки, выведите количество ходов, за которое черепаха доберется до своей клубники.

правила

  • Вы можете предположить, что входная сетка имеет решение

  • Каждая сетка будет иметь только один, strawberryдва portalsи одинturtle

  • Сетка ввода может быть введена в любом удобном формате

  • Вы должны относиться к teleportersпредметам одноразового использования

  • Поворот, что черепаха движется на teleporterквадрат, он уже на соответствующем teleporter. Он никогда не двигается на teleporterи остается там для движения

  • Кратчайший путь не нужно использовать портал

  • Черепаха не может перейти в горные плитки

  • Вы можете использовать любой ASCII символ или целое число , чтобы представить mountains, turtle, empty grid square,strawberry

  • Вы можете использовать либо один и тот же символ, либо два разных символа ASCII или целые числа для представления teleporterпар

  • Сетка может иметь более одного пути с одинаковой длиной кратчайшего пути.

  • Это

Разъяснения к правилам

  • Вы должны относиться к teleportersпредметам одноразового использования.

Обоснование : было указано, что случай:

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

Может быть решен только путем входа и выхода из порталов дважды. Во время этого разъяснения оба решения действовали, предполагая, что они были либо одноразовыми, либо не было никакой причины пытаться использовать ранее использованные квадраты. Чтобы избежать взлома их трудолюбивых решений, это казалось лучшим способом объяснить это. Следовательно, это будет считаться недействительной сеткой.

Тестовые случаи, отформатированные как списки

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

Тестовые случаи, отформатированные для людей

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

кредиты

Дизайн и структура: Голодная мышка от Arnauld

Предлагаемые вызовы Править совет: Камил-дракари , beefster

Советы главного редактора : okx nedla2004 mbomb007

akozi
источник
2
Я думаю, что было бы неплохо добавить тестовый пример, в котором использование телепорта могло бы занять больше времени.
Okx
@Okx Создание и добавление сейчас.
Акози
Отредактировано, спасибо.
Акози
1
@xnor Я чувствую, что это может быть абстрагироваться от моих первоначальных правил. Так что, возможно, лучше порталы одноразового использования?
Акози
1
Связанные (я думаю).
Чарли

Ответы:

13

JavaScript (ES7),  140 139  138 байт

Принимает ввод как матрицу целых чисел со следующим отображением:

  • 1
  • 0 =X
  • 1 = 🌄 (гора)
  • 2 = 🐢 (черепаха)
  • 3 = 🍓 (клубника)
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

Попробуйте онлайн!

Как?

gtt0(x,y)(X,Y)

iRmin(R,i) всякий раз, когда черепаха находит клубнику.

t=2

t=1i во время такой итерации.

R .

комментарии

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
источник
1
«Каждая посещенная плитка временно установлена ​​на гору, чтобы черепаха не двигалась дважды по одной и той же плитке». Какой прекрасный трюк. Отличный ответ, и как всегда я ценю ответы с объяснениями :)
akozi
5

Python 2 , 441 431 341 байт

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)

Попробуйте онлайн!

Ввод в виде списков, но с использованием цифр вместо символов (благодаря Quintec) и отдельного значения для пункта назначения телепорта. Эти большие отступы должны быть символами табуляции, если Stack Exchange удаляет их. Любые советы или идеи особенно приветствуются, так как я чувствую, что это может стать намного короче.

Таблица символов, используемых в вызове для чисел, используемых в моей программе, приведена ниже, но вы также можете использовать эту программу .

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

-10 байт благодаря Quintec, изменив ввод с использования символов на цифры.

- Большое количество байтов благодаря Джонатану Фреху, ЭльПедро и Джонатану Аллану.

nedla2004
источник
2
Вероятно, вы можете сбрить несколько символов, взяв список, в котором каждый объект представлен числом вместо строкового символа.
Квинтек
@Quintec Добавлено, спасибо. Я хотел бы сделать то же самое для указаний, но тогда диагонали должны были бы быть сделаны отдельно. Тем не менее, возможно, можно переместить их в числа.
Недла2004
1
@ElPedro Ahha я могу бриться 4 от , как это
Джонатан Аллана
1
... и еще 10 за 356
Джонатан Аллан
2
@JonathanAllan и ElPedro и Джонатан Френч. Хорошие советы от всех вас, и я добавил их вместе с парой вещей, которые я придумал. (После большой задержки)
nedla2004
2

Python 2 , 391 397 403 422 байта

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

Попробуйте онлайн!

Задача переводится в график, и решение состоит в том, чтобы найти кратчайший путь от черепахи до клубники.

Challenge | This code
T         | -1
S         |  5
O         |  8
M         |  0
X         |  1
mdahmoune
источник