Вы оказываетесь на шахматной доске, как и каждый. Вы можете видеть выход, но он ужасно далеко, и вы бы предпочли не идти весь путь. К счастью, некоторые местные жители предложили вам прокатиться. Рыцарь, Ладья, Епископ и Король готовы доставить вас к месту назначения, но, видя, что это шахматная доска, они должны соблюдать правила шахмат на пути к месту назначения. Вы хотели бы как можно скорее уйти отсюда, чье предложение вы принимаете?

задача

Учитывая шахматную доску произвольной формы и размера и две точки на шахматной доске, выведите шахматную фигуру, которая может перемещаться между двумя точками за минимальное количество ходов. Доски не обязательно будут непрерывными, что означает, что между разделами доски могут быть промежутки. Каждая из четырех фигур (Король, Ладья, Рыцарь и Епископ) может двигаться в соответствии со своими стандартными правилами в шахматах. Части ферзя и пешки были намеренно исключены из этого испытания.

I / O

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

Тестовые случаи

Квадрат обозначает начальную точку, а кружок обозначает конечную точку.

епископ

рыцарь

король

ладья

Король рыцарь

Никто

Haskell , 447 439 437 432 байта

t=[1,2]
p=[(+),(-)]
f=filter
a=abs
(#)=elem
x?y=[min x y..max x y]
f&g=(\x->g x>>=f)
(b!1)(c,r)=f(#b)[(c!d,r#s)|(!)<-p,(#)<-p,d<-t,s<-t,d/=s]
(b!2)(c,r)=f(\(d,s)->(c==d&&all(#b)[(c,z)|z<-r?s])||r==s&&all(#b)[(z,r)|z<-c?d])b
(b!3)(c,r)=f(\(d,s)->a(c-d)==a(r-s)&&all(#b)(zip(c?d)$r?s))b
(b!4)(c,r)=f(\(d,s)->a(c-d)<2&&a(r-s)<2)b
(b%p)n s=[s]>>=foldr(&)(:[])(replicate n$b!p)
g b s e=head$f(not.null)[[p|p<-[1..4],e#(b%p)n s]|n<-[0..]]

Вызов с использованием g <board> <start> <end>где <board> :: [(Int, Int)], <start> :: (Int, Int)и <end> :: (Int, Int). Возвращает список, содержащий 1для Рыцаря, 2Ладьи, 3Епископа и 4Короля. Если решения не найдены, он постоянно переполняет стек (что считается ошибкой, верно?).

Вдохновение, взятое из глав LYAH о Монадах (%)- это просто обобщение и игра в гольф inMany, с (&)эквивалентом (Control.Monad.<=<). Все остальное должно быть более или менее самоочевидным.

Это, вероятно, может быть гораздо больше, но я уже достаточно повеселился.

Ungolfed:

data Piece = Knight | Rook | Bishop | King deriving (Show)
type Place = (Int, Int)
type Board = [Place]

x `to` y = [min x y..max x y]

f <=< g = (\x -> g x >>= f)

moves
    :: Board    -- available spaces
    -> Piece    -- type of piece
    -> Place    -- starting place
    -> [Place]  -- places available in one move
moves b Knight (c,r) =
    filter (`elem` b) [(c!d, r#s) |
                       (!) <- [(+),(-)], (#) <- [(+),(-)],
                       d <- [1,2], s <- [1,2], d/=s]
moves b Rook   (c,r) =
    filter (\(d,s) -> (c == d && all (`elem` b) [(c,z) | z <- r `to` s])
                    || r == s && all (`elem` b) [(z,r) | z <- c `to` d]) b
moves b Bishop (c,r) =
    filter (\(d,s) -> abs(c-d) == abs(r-s)
                && all (`elem` b) (zip (c `to` d) (r `to` s))) b
moves b King   (c,r) =
    filter (\(d,s) -> abs(c-d) <= 1 && abs(r-s) <= 1) b

canGoIn
    :: Board    -- available spaces
    -> Piece    -- type of piece
    -> Int      -- number of moves
    -> Place    -- starting place
    -> [Place]  -- places available in the specified number of moves
canGoIn b p n s =
    return s >>= foldr (<=<) return (replicate n (moves b p))

quickestPieces
    :: Board    -- available spaces
    -> Place    -- starting place
    -> Place    -- ending place
    -> [Piece]  -- quickest pieces
quickestPieces b s e =
        head $ filter (not.null)
            [[p | p <- [Knight, Rook, Bishop, King], elem e (canGoIn b p n s)] |
                n<-[0..]]

Mathematica, 326 325 байт

Спасибо masterX224 за указание экономии байтов!

f[g_,w_,x_]:=(c={{1,1},{-1,1}};s=c.c/2;e=#<->#2&@@@#&;j=Join;h=FindShortestPath;t=#~Tuples~2&;a@d_:=e@Select[t@g,#-#2&@@#==d&];y@k=j@@(a/@j[s,c]);y@n=j@@(a/@{{1,2},{2,1},{-2,1},{-1,2}});v=Flatten[e@t@#&/@ConnectedComponents@a@#&/@#]&;y@r=v@s;y@b=v@c;Pick[p={b,k,n,r},z=Length[h[y@#,w,x]/.h@__->0]&/@p,Min[z~Complement~{0}]]);

Определяет функцию, fпринимающую три аргумента: gсписок упорядоченных пар целых чисел, представляющих доску, wи xупорядоченные пары, представляющие начальный и конечный квадраты. Выходные данные представляют собой подмножество {b, k, n, r}(представляющее слона, короля, рыцаря и ладью соответственно), которые имеют путь минимального перемещения между двумя квадратами. Например, третий тестовый пример вызывается f[{{0, 0}, {1, 1}, {1, 2}, {0, 3}}, {0, 0}, {0, 3}]и возвращает {k}; два последних тестовых случая возвращают {k, n}и {}, соответственно.

Стратегия состоит в том, чтобы перевести квадраты доски в вершины графа, где края определяются движениями каждого куска, а затем использовать встроенные подпрограммы графа.

Более удобная версия кода:

 1  f[g_, w_, x_] := ( c = {{1, 1}, {-1, 1}}; s = c.c/2;
 2    e = # <-> #2 & @@@ # &; j = Join; h = FindShortestPath; t = #~Tuples~2 &; 
 3    a@d_ := e@Select[t@g, # - #2 & @@ # == d &]; 
 4    y@k = j @@ (a /@ j[s, c]); 
 5    y@n = j @@ (a /@ {{1, 2}, {2, 1}, {-2, 1}, {-1, 2}}); 
 6    v = Flatten[e@t@# & /@
 7         ConnectedComponents@a@# & /@ #] &;
 8    y@r = v@s; y@b = v@c; 
 9    Pick[p = {b, k, n, r}, 
10      z = Length[h[y@#, w, x] /. h@__ -> 0] & /@ p, 
11      Min[z~Complement~{0}]]
12  );

В строке 3 Select[g~Tuples~2, # - #2 & @@ # == dнаходит все упорядоченные пары вершин, разность которых равна вектору d; eзатем преобразует каждую такую ​​упорядоченную пару в ребро неориентированного графа. Таким образом , aэто функция , которая создает ребра между всеми вершинами , которые отличаются от фиксированного вектора.

Этого достаточно , чтобы определить, в строках 4 и 5, график короля y@k(который занимает объединение ребер , порожденных векторами {1, 1}, {-1, 1}, {0, 1}, и {-1, 0}) и граф рыцаря y@n(который делает то же самое с {1, 2}, {2, 1}, {-2, 1}и {-1, 2}).

В строке 7 ConnectedComponents@a@#берет один из этих соседних графов и затем находит его связанные компоненты; это соответствует группированию всех линейных сегментов вершин в заданном направлении (чтобы ладья или слон не проходили через них один за другим). Затем e@t@#в строке 6 помещаются ребра между каждой парой вершин в одном и том же связанном компоненте, которые затем объединяются Flattenв один граф. Таким образом, строки с 6 по 8 определяют граф ладьи и граф y@rслона y@b.

Наконец, строки с 9 по 11 выбирают элементы, {b, k, n, r}которые дают кратчайший путь между двумя целевыми вершинами. FindShortestPathвыдаст ошибку и вернет неоцененную, если целевая вершина не появится в графе (что произойдет, если из нее не выйдут ребра), поэтому мы используем вместо этого h@__ -> 0возврат 0в этих случаях. А отсутствие пути между действительными вершинами возвращает список длины 0, поэтому Min[z~Complement~{0}]вычисляет длину наименьшего пути, который существует на самом деле, игнорируя описанные выше плохие случаи.