Вытащи меня отсюда

12

Вызов

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

введите описание изображения здесь


вход

  • N : размер сеткиN x N
  • P : позиция игрока[playerposx, playerposy]
  • T : позиция цели[targetposx, targetposy]
  • O : позиции препятствий[[x1, y1], [x2, y2],...,[xn, yn]]

Выход

Путь : путь, по которому игрок может добраться до цели[[x1, y1], [x2, y2],...,[xn, yn]]


правила

  1. Точка [0,0]находится в верхнем левом углу сетки.
  2. Положение игрока всегда будет на левой стороне сетки.
  3. Положение цели всегда будет на правой стороне сетки.
  4. Сетка всегда будет иметь хотя бы одно препятствие.
  5. Вы можете предположить, что никакое препятствие не перекрывает игрока или целевую позицию.
  6. Вам не обязательно нужно найти минимальный путь.
  7. Игрок может двигаться только влево, вправо, сверху и снизу не по диагонали.
  8. Вы можете принять вход любым удобным способом.
  9. Вы можете предположить, что путь для игрока, чтобы добраться до цели, всегда будет существовать.
  10. Очевидно, что для каждого ввода существует несколько допустимых путей, выберите один.
  11. Предположим, N > 2что сетка будет как минимум 3 x 3.

Примеры

Входной сигнал: 9, [6, 0], [3, 8], [[0, 5], [2, 2], [6, 4], [8, 2], [8, 7]]
Возможный выход:[[6, 0], [6, 1], [6, 2], [6, 3], [5, 3], [5, 4], [5, 5], [5, 6], [5, 7], [5, 8], [4, 8], [3, 8]]

Входной сигнал: 6, [1, 0], [3, 5], [[1, 2], [2, 5], [5, 1]]
Возможный выход:[[1, 0], [1, 1], [2, 1], [2, 2], [2, 3], [2, 4], [3, 4], [3, 5]]


Заметка

Обратите внимание, что Xдля строк и Yстолбцов. Не путайте их с координатами на изображении.

редактировать

Как указал @digEmAll, из-за правил #2и #3, playerY = 0и targetY = N-1. Таким образом, если вы хотите, вы можете взять только в качестве входных данных playerXи и targetX(если это делает ваш код короче).

DimChtz
источник
1
«Позиция игрока всегда будет на левой стороне, а цель на правой стороне»: означает ли это, что player-y = 0 и target-y = N-1? Если так, можем ли мы просто принять x-координату (одно число) для игрока и цели?
digEmAll
1
@digEmAll Хороший вопрос. Честно говоря, я не думал об этом, и да, я могу это отредактировать.
ДимЧтц
Связано но проще. Связано, но сложнее.
user202729
Должен ли путь быть от начала до конца или в обратном порядке?
kamoroso94
1
@ kamoroso94 Да, начните стрелять (финишируйте) :)
DimChtz

Ответы:

5

JavaScript (ES6), 135 байт

Принимает ввод как (width, [target_x, target_y], obstacles)(source_x, source_y), где препятствия - это массив строк в "X,Y"формате.

Возвращает массив строк в "X,Y"формате.

(n,t,o)=>g=(x,y,p=[],P=[...p,v=x+','+y])=>v==t?P:~x&~y&&x<n&y<n&[...o,...p].indexOf(v)<0&&[0,-1,0,1].some((d,i)=>r=g(x+d,y-~-i%2,P))&&r

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

комментарии

(n, t, o) =>              // n = width of maze, t[] = target coordinates, o[] = obstacles
  g = (                   // g() = recursive search function taking:
    x, y,                 //   (x, y) = current coordinates of the player
    p = [],               //   p[] = path (a list of visited coordinates, initially empty)
    P = [                 //   P[] = new path made of:
      ...p,               //     all previous entries in p
      v = x + ',' + y     //     the current coordinates coerced to a string v = "x,y"
    ]                     //
  ) =>                    //
    v == t ?              // if v is equal to the target coordinates:
      P                   //   stop recursion and return P
    :                     // else:
      ~x & ~y             //   if neither x nor y is equal to -1
      && x < n & y < n    //   and both x and y are less than n
      & [...o, ...p]      //   and neither the list of obstacles nor the path
        .indexOf(v) < 0   //   contains a position equal to the current one:
      && [0, -1, 0, 1]    //     iterate on all 4 possible directions
        .some((d, i) =>   //     for each of them:
          r = g(          //       do a recursive call with:
            x + d,        //         the updated x
            y - ~-i % 2,  //         the updated y
            P             //         the new path
          )               //       end of recursive call
        ) && r            //     if a solution was found, return it
Arnauld
источник
5

R 227 байт

function(N,P,G,O){M=diag(N+2)*0
M[O+2]=1
b=c(1,N+2)
M[row(M)%in%b|col(M)%in%b]=1
H=function(V,L){if(all(V==G+2))stop(cat(L))
M[t(V)]=2
M<<-M
for(i in 0:3){C=V+(-1)^(i%/%2)*(0:1+i)%%2
if(!M[t(C)])H(C,c(L,C-2))}}
try(H(P+2,P),T)}

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

Не очень короткий, и определенно не дает кратчайший путь (например, проверьте первый пример).
Он в основном выполняет рекурсивный поиск в глубину и останавливается, как только цель достигнута, печатая путь.

Спасибо JayCe за улучшение форматирования вывода

digEmAll
источник
+1 Мне нравится, как вы печатаете вывод (не типичный скучный список списков) :)
DimChtz
@DimChtz: хорошо, но ... это вспомогательная функция, функция code-golf просто печатает список координат x1 y1 x2 y2 ... xn yn: D
digEmAll
1
Да, я знаю: P, но все равно приятно.
ДимЧтц
1
согласен с @DimChtz ... и я думаю, что это выглядит даже лучше, если вы write(t(mx),1,N)вместо printING :)
JayCe
@JayCe: хорошая идея, изменилась!
digEmAll
3

Haskell , 133 131 130 байт

  • -1 байт благодаря BWO
(n!p)o=head.(>>=filter(elem p)).iterate(\q->[u:v|v@([x,y]:_)<-q,u<-[id,map(+1)]<*>[[x-1,y],[x,y-1]],all(/=u)o,x`div`n+y`div`n==0])

Попробуйте онлайн! (с несколькими тестами)

Функция, !принимающая в качестве входных данных

  • n :: Int размер сетки
  • p :: [Int] позиция игрока в списке [xp, yp]
  • o :: [[Int]] позиция препятствий в виде списка [[x1, y1], [x2, y2], ...]
  • t :: [[[Int]]](неявная) позиция цели в виде списка [[[xt, yt]]](тройной список просто для удобства)

и возвращает правильный путь в виде списка [[xp, yp], [x1, y1], ..., [xt, yt]].

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

объяснение

(n ! p) o =                                                         -- function !, taking n, p, o and t (implicit by point-free style) as input
    head .                                                          -- take the first element of
    (>>= filter (elem p)) .                                         -- for each list, take only paths containing p and concatenate the results
    iterate (                                                       -- iterate the following function (on t) and collect the results in a list
        \q ->                                                       -- the function that takes a list of paths q...
            [u : v |                                                -- ... and returns the list of paths (u : v) such that:
                v@([x, y] : _) <- q,                                -- * v is an element of q (i.e. a path); also let [x, y] be the first cell of v
                u <- [id, map (+ 1)] <*> [[x - 1,y], [x, y - 1]],   -- * u is one of the neighbouring cells of [x, y]
                all (/= u) o,                                       -- * u is not an obstacle
                x `div` n + y `div` n == 0                          -- * [x, y] is inside the grid
            ]
    )

iteratekk1[[xt, yt]]

По-видимому, неясное выражение [id, map (+ 1)] <*> [[x - 1,y], [x, y - 1]]- это просто «версия для гольфа» (-1 байт) [[x + 1, y], [x, y + 1], [x - 1, y], [x, y - 1]].

Delfad0r
источник
2
Добро пожаловать в PPCG! Хороший первый ответ!
Арно
1
@ Arnauld Спасибо! На самом деле я потратил несколько часов, пытаясь выжать несколько байтов из моего решения, просто чтобы превзойти ваши 135 ^^
Delfad0r
1
Хороший гольф! Вы можете сохранить один байт, используя оператор вместо функции: попробуйте онлайн!
ბიმო
@BWO Спасибо за совет. Я новичок здесь, поэтому есть много уловок, о которых я никогда не слышал
Delfad0r
1
Btw. есть раздел с советами для Haskell, в частности, где вы можете найти этот и многие другие приемы. Да , и всегда есть чат тоже: монады и мужчины
ბიმო
1

Сетчатка 0.8.2 , 229 байт

.
$&$&
@@
s@
##
.#
{`(\w.)\.
$1l
\.(.\w)
r$1
(?<=(.)*)\.(?=.*¶(?<-1>.)*(?(1)$)\w)
d
}`\.(?=(.)*)(?<=\w(?(1)$)(?<-1>.)*¶.*)
u
+T`.`#`.(?=(.)*)(?<=d#(?(1)$)(?<-1>.)*¶.*)|(?<=(.)*.).(?=.*¶(?<-2>.)*(?(2)$)u#)|(?<=#r).|.(?=l#)
.(.)
$1

Попробуйте онлайн! Не уверен, подходит ли формат ввода / вывода. Объяснение:

.
$&$&

Дублируйте каждую клетку. Левая копия используется как временная рабочая зона.

@@
s@

Пометить начало лабиринта как посещенное.

##
.#

Отметьте конец лабиринта как пустой.

{`(\w.)\.
$1l
\.(.\w)
r$1
(?<=(.)*)\.(?=.*¶(?<-1>.)*(?(1)$)\w)
d
}`\.(?=(.)*)(?<=\w(?(1)$)(?<-1>.)*¶.*)
u

Пока существуют доступные рабочие ячейки, наведите их на соседние ранее посещенные ячейки.

+T`.`#`.(?=(.)*)(?<=d#(?(1)$)(?<-1>.)*¶.*)|(?<=(.)*.).(?=.*¶(?<-2>.)*(?(2)$)u#)|(?<=#r).|.(?=l#)

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

.(.)
$1

Удалить рабочие ячейки.

Нил
источник
1

JavaScript, 450 байт

Принимает вход как (n, {playerx, playery}, {targetx, targety}, [{obstaclex, obstacley}]). Возвращает массив {hopx, hopy}.

j=o=>JSON.stringify(o);l=a=>a.length;c=(a,o)=>{let i=l(a);while(i>0){i--;if(j(a[i])==j(o)){return 1;}}return 0;}h=(p,t,o)=>{if(p.y<t.y&&!c(o,{x:p.x,y:p.y+1})){return{x:p.x,y:p.y+1};}if(p.y>t.y&&!c(o,{x:p.x,y:p.y-1})){return{x:p.x,y:p.y-1};}if(p.x<t.x&&!c(o,{x:p.x+1,y:p.y})){return{x:p.x+1,y:p.y};}if(p.x>t.x&&!c(o,{x:p.x-1,y:p.y})){return{x:p.x-1,y:p.y};}return t;}w=(n,p,t,o)=>{let r=[];r.push(p);while(j(p)!==j(t)){p=h(p,t,o);r.push(p);}return r;}

Вот бесподобная версия моего беспорядка:

// defining some Array's function for proper comparaisons
json = (object) => { return JSON.stringify(object) };
length = (array) => { return array.length; }
contains = (array, object) => {
    let i = length(array);
    while (i > 0) {
    i--;
        if (json(array[i]) == json(object)) { return true; }
    }
    return false;
}
//return next found hop
getNextHop = (player, target, obstacles) => {
    //uggly serie of conditions
    //check where do we have to go and if there is an obstacle there
    if(player.y<target.y && !contains(obstacles, [x:player.x, y:player.y+1])) { return [x:player.x, y:player.y+1]; }
    if(player.y>target.y && !contains(obstacles, [x:player.x, y:player.y-1])) { return [x:player.x, y:player.y-1]; }
    if(player.x<target.x && !contains(obstacles, [x:player.x+1, y:player.y])) { return [x:player.x+1, y:player.y]; }
    if(player.x>target.x && !contains(obstacles, [x:player.x-1, y:player.y])) { return [x:player.x-1, y:player.y]; }
    return target;
}
//return found path
getPath = (gridsize, player, target, obstacles) => {
    let path = [];
    path.push(player);
    //while player is not on target
    while(json(player)!=json(target)) {
        player = getNextHop(player, target, obstacles); //gridsize is never used as player and target are in the grid boundaries
        path.push(player);
    }
    return path;
}
MinerBigWhale
источник