Znajdziesz się na szachownicy, tak jak się to robi. Możesz zobaczyć wyjście, ale jest okropnie daleko i wolisz nie iść całą drogę. Na szczęście niektórzy miejscowi zaoferowali ci przejażdżkę. Rycerz, Wieża, Biskup i Król chętnie zabiorą cię do miejsca docelowego, ale widząc, jak to jest szachownica, muszą przestrzegać zasad szachowych w drodze do miejsca docelowego. Chcesz się stąd jak najszybciej wydostać, czyją ofertę akceptujesz?

Zadanie

Biorąc pod uwagę dowolnie ukształtowaną i wielkości szachownicę oraz dwa punkty na szachownicy, wyjmij pionek szachowy, który może przemieszczać się między dwoma miejscami w jak najmniejszej liczbie ruchów. Tablice niekoniecznie muszą być ciągłe, co oznacza, że ​​mogą występować przerwy między sekcjami planszy. Każdy z czterech elementów (król, wieża, rycerz i biskup) może poruszać się zgodnie z ich standardowymi zasadami w szachach. Królowa i pionki zostały celowo wykluczone z tego wyzwania.

I / O

Możesz przyjmować dane wejściowe w dowolnym rozsądnym formacie, a także dane wyjściowe w dowolnym wybranym przez siebie formacie. Twoje dane wejściowe i wyjściowe muszą być spójne. Jeśli wiele elementów może dotrzeć do celu w tej samej liczbie ruchów, musisz wydać wszystkie elementy, które mogą się tam dostać w jak najkrótszym czasie. Jeśli żaden z czterech elementów nie dotrze do końca, możesz wydać cokolwiek, o ile różni się ono od wszystkich innych możliwych wyników. Może to obejmować nie wysyłanie niczego lub zgłaszanie błędu.

Przypadki testowe

Kwadrat wskazuje punkt początkowy, a okrąg wskazuje punkt końcowy.

Biskup

Rycerz

Król

Wieża

Król, rycerz

Żaden

Haskell , 447 439 437 432 bajtów

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..]]

Zadzwoń za pomocą g <board> <start> <end>gdzie <board> :: [(Int, Int)], <start> :: (Int, Int)i <end> :: (Int, Int). Zwraca listę zawierającą 1dla Rycerza, 2Wieży, 3Biskupa i 4Króla. Jeśli nie zostaną znalezione żadne rozwiązania, konsekwentnie przepełnia stos (co jest liczone jako zgłaszanie błędu, prawda?).

Inspiracja pochodzi z rozdziałów LYAH w sprawie Monads- (%)tylko uogólnione i grałem inManyz (&)odpowiednikiem (Control.Monad.<=<). Wszystko inne powinno być mniej lub bardziej oczywiste.

Prawdopodobnie można grać w golfa o wiele więcej, ale na razie miałem dość zabawy.

Nie golfowany:

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 bajtów

Dzięki masterX224 za wskazanie oszczędności bajtów!

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}]]);

Definiuje funkcję fprzyjmującą trzy argumenty: gjest listą uporządkowanych par liczb całkowitych reprezentujących tablicę woraz xuporządkowanych par reprezentujących kwadraty początkowy i końcowy. Wyjściem jest podzbiór {b, k, n, r}(reprezentujący odpowiednio biskupa, króla, rycerza i wieżę), które mają ścieżkę minimalnego ruchu między dwoma kwadratami. Na przykład trzeci przypadek testowy jest wywoływany przez f[{{0, 0}, {1, 1}, {1, 2}, {0, 3}}, {0, 0}, {0, 3}]i zwraca {k}; dwa ostatnie przypadki testowe wrócić {k, n}i {}odpowiednio.

Strategią jest przełożenie kwadratów planszy na wierzchołki wykresu, gdzie krawędzie są określane przez ruchy każdego elementu, a następnie użycie wbudowanych procedur graficznych.

Bardziej przyjazna dla użytkownika wersja kodu:

 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  );

W linii 3 Select[g~Tuples~2, # - #2 & @@ # == dznajduje wszystkie uporządkowane pary wierzchołków, których różnicą jest wektor d; enastępnie przekształca każdą taką uporządkowaną parę w niekierowaną krawędź wykresu. Tak więc ajest funkcja, która tworzy krawędzie między wszystkimi wierzchołkami, które różnią się stałym wektorem.

To wystarcza do zdefiniowania, w linii 4 i 5, wykres króla y@k(co ma związek krawędzi uzyskanych przez wektory {1, 1}, {-1, 1}, {0, 1}i {-1, 0}) oraz wykresu rycerskiej y@n(która ma to samo z {1, 2}, {2, 1}, {-2, 1}i {-1, 2}).

W linii 7 ConnectedComponents@a@#pobiera jeden z tych sąsiednich wykresów, a następnie wyszukuje połączone elementy; odpowiada to zgrupowaniu wszystkich segmentów linii wierzchołków w danym kierunku (tak, aby wieża lub biskup nie musieli się przez nie przemieszczać jeden po drugim). Następnie e@t@#w linii 6 umieszcza krawędzie między każdą parą wierzchołków w tym samym połączonym składniku, które są następnie Flattenedytowane w pojedynczy wykres. Zatem linie od 6 do 8 definiują wykres wieży i wykres y@rbiskupa y@b.

Wreszcie linie od 9 do 11 wybierają elementy, {b, k, n, r}które dają najkrótszą ścieżkę między dwoma docelowymi wierzchołkami. FindShortestPathwyrzuci błąd i zwróci nieoceniony, jeśli wierzchołek docelowy nie pojawi się na wykresie (co się stanie, jeśli z niego nie wyprowadzą się żadne krawędzie), więc zamiast tego używamy h@__ -> 0powrotu 0. Brak ścieżki między prawidłowymi wierzchołkami zwraca listę długości 0, więc Min[z~Complement~{0}]oblicza długość najmniejszej ścieżki, która faktycznie istnieje, ignorując powyższe niepoprawne przypadki.