Você se encontra em um tabuleiro de xadrez, como se faz. Você pode ver a saída, mas é muito longe e você prefere não andar até o fim. Felizmente, alguns locais ofereceram uma carona. Um cavaleiro, uma torre, um bispo e um rei estão todos dispostos a levá-lo ao seu destino, mas, vendo como este é um tabuleiro de xadrez, cada um deve respeitar as regras do xadrez no caminho para o seu destino. Gostaria de sair daqui o mais rápido possível, cuja oferta você aceita?

Tarefa

Dado um tabuleiro de xadrez de tamanho e formato arbitrário e dois pontos no tabuleiro, produza a peça de xadrez que pode se mover entre os dois locais no menor número de movimentos possível. Os painéis não serão necessariamente contínuos, o que significa que pode haver lacunas entre as seções do painel. Cada uma das quatro peças (rei, torre, cavaleiro e bispo) pode se mover de acordo com suas regras padrão no xadrez. As peças da rainha e do peão foram intencionalmente deixadas de fora desse desafio.

I / O

Você pode receber entradas em qualquer formato razoável e também pode imprimir em qualquer formato que escolher. Sua entrada e saída devem ser autoconsistentes. Se várias peças puderem chegar ao destino com o mesmo número de movimentos, você deverá produzir todas as peças que podem chegar lá no período mínimo de tempo. Se nenhuma das quatro peças chegar ao fim, você poderá produzir qualquer coisa, desde que seja distinto de todas as outras saídas possíveis. Isso pode incluir não produzir nada ou gerar um erro.

Casos de teste

Um quadrado indica o ponto inicial e um círculo indica o ponto final.

Bispo

Cavaleiro

Rei

Torre

Cavaleiro Rei

Nenhum

Haskell , 447 439 437 432 bytes

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

Ligue usando g <board> <start> <end>onde <board> :: [(Int, Int)], <start> :: (Int, Int)e <end> :: (Int, Int). Retorna uma lista contendo 1Knight, 2Rook, 3Bishop e 4King. Se nenhuma solução for encontrada, ela transborda consistentemente a pilha (que conta como um erro, certo?).

A inspiração tirada dos capítulos de LYAH sobre Mônadas - (%)é apenas uma generalização e um jogo de golfe inMany, com o (&)equivalente a (Control.Monad.<=<). Tudo o resto deve ser mais ou menos auto-explicativo.

Provavelmente isso pode ser jogado muito mais, mas já me diverti bastante.

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 bytes

Obrigado a masterX224 por apontar uma economia de bytes!

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

Define uma função que faceita três argumentos: gé uma lista de pares ordenados de números inteiros representando o quadro we xpares ordenados e representando os quadrados inicial e final. A saída é o subconjunto de {b, k, n, r}(representando bispo, rei, cavaleiro e torre, respectivamente) que tem um caminho de movimentos mínimos entre os dois quadrados. Por exemplo, o terceiro caso de teste é invocado por f[{{0, 0}, {1, 1}, {1, 2}, {0, 3}}, {0, 0}, {0, 3}]e retorna {k}; os dois últimos casos de teste retornam {k, n}e {}, respectivamente.

A estratégia é converter os quadrados do tabuleiro em vértices de um gráfico, onde as arestas são determinadas pelos movimentos de cada peça e, em seguida, usar rotinas gráficas incorporadas.

Versão mais amigável do código:

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

Na linha 3, Select[g~Tuples~2, # - #2 & @@ # == dencontra todos os pares ordenados de vértices cuja diferença é o vetor d; edepois, transforma cada par ordenado em uma aresta do gráfico não direcionada. Assim aé uma função que cria arestas entre todos os vértices que diferem por um vetor fixo.

Isso é suficiente para definir, nas linhas 4 e 5, o gráfico de rei y@k(o que leva a união de bordas gerados pelos vectores {1, 1}, {-1, 1}, {0, 1}, e {-1, 0}) e gráfico do cavaleiro y@n(que faz o mesmo com {1, 2}, {2, 1}, {-2, 1}, e {-1, 2}).

Na linha 7, ConnectedComponents@a@#pega um desses gráficos vizinhos e encontra seus componentes conectados; isso corresponde ao agrupamento de todos os segmentos de linha dos vértices na direção especificada (para que uma torre ou bispo não precise passar por eles um por um). Então e@t@#na linha 6 coloca arestas entre cada par de vértices no mesmo componente conectado, que são então Flatteneditados em um único gráfico. Assim, as linhas 6 a 8 definem o gráfico da torre y@re o gráfico do bispo y@b.

Finalmente, as linhas 9 a 11 escolhem os elementos {b, k, n, r}que produzem o caminho mais curto entre os dois vértices de destino. FindShortestPathlançará um erro e retornará sem avaliação se um vértice de destino não aparecer no gráfico (o que acontecerá se nenhuma borda emanar dele), então usamos h@__ -> 0para retornar 0nesses casos. E a falta de um caminho entre vértices válidos retorna uma lista de comprimento 0, Min[z~Complement~{0}]calcula o comprimento do menor caminho que realmente existe, ignorando os casos ruins acima.