Procurando Leapers

19

Recentemente, recebi um tabuleiro de xadrez irregular realmente estranho. Seus quadrados estão em todo lugar e nem todos estão conectados. Pelo menos eles ainda estão dispostos em uma grade regular. Quero adaptar as regras do xadrez para poder jogar no tabuleiro, mas, para começar, preciso de uma peça que possa ir a qualquer lugar do tabuleiro, e parece que o salto é a minha melhor aposta.

Os saltadores são a generalização dos cavaleiros no xadrez das fadas. Leapers são parametrizadas por dois números inteiros m e n e pode mover-se de m quadrados numa direcção e depois mais n quadrados em qualquer direcção perpendicular. Para o cavaleiro padrão, temos (m, n) = (2, 1) . O movimento inteiro é considerado um único salto, de modo que nenhum dos quadrados no caminho para o alvo precise estar vazio ou mesmo existir.

O desafio

Você recebe um "tabuleiro de xadrez" na forma de uma lista de coordenadas inteiras 2D positivas que representam os quadrados que fazem parte do tabuleiro. Sua tarefa é encontrar um saltador que, com movimentos suficientes, possa atingir qualquer quadrado no tabuleiro.

Vejamos alguns exemplos. O tabuleiro de xadrez padrão usa uma grade regular de quadrados 8x8 (observe que não fazemos distinção entre quadrados brancos e pretos para este desafio):

########
########
########
########
########
########
########
########

O cavaleiro padrão pode alcançar todos eles, portanto, (2, 1)seria uma saída válida. No entanto, (1, 1)por exemplo, não seria válido, uma vez que tal peça pode atingir apenas metade dos quadrados, não importa onde ela comece. (1, 0)por outro lado, também seria uma saída válida, pois todos os quadrados estão conectados ortogonalmente.

Agora, se tivermos uma placa irregular como:

#   #
 # # #
  # # #
 # #
    #

Então as soluções possíveis são (1, 1)e (3, 1). Também podemos ter uma placa com regiões completamente desconectadas, como:

#### ####
#### ####
#### ####
#### ####

O cavaleiro padrão (2, 1)ainda pode alcançar todos os quadrados aqui, o que é de fato a única solução.

E, finalmente, o quadro simples a seguir não pode ser completamente alcançado por qualquer saltador:

#
 ##

Observe que o formato de entrada não será uma representação ASCII, mas uma lista de coordenadas. Por exemplo, o segundo exemplo acima pode ser dado como:

[[1, 1], [5, 1], [2, 2], [4, 2], [6, 2], [3, 3], [5, 3], [7, 3], [2, 4], [4, 4], [5, 5]]

Regras

Você pode escrever um programa ou função, recebendo entrada via STDIN (ou alternativa mais próxima), argumento da linha de comando ou argumento da função e emitindo o resultado via STDOUT (ou alternativa mais próxima), valor de retorno da função ou parâmetro da função (saída).

As coordenadas de entrada podem ser obtidas em qualquer formato de lista conveniente (lista simples, lista de pares, lista de números inteiros complexos, string com separadores consistentes, etc.).

O resultado deve ser os dois números inteiros m e n que identificam o saltador se existe uma solução (como dois inteiros separados, uma lista, uma cadeia com delimitador não numérico, etc.). Se não houver solução, você poderá gerar qualquer valor consistente que não possa ser um saltador válido. Isso inclui o par de números inteiros (0, 0)em seu formato normal, além de qualquer coisa que não seja um par de números inteiros não negativos.

Seu programa precisa lidar com qualquer um dos casos de teste em um minuto . Essa é uma restrição um pouco confusa, mas use o bom senso: se levar 2 minutos na sua máquina, acho que podemos assumir que ela pode ser executada dentro de 1 na de outra pessoa, mas se levar 20, é menos provável. Não deve ser difícil resolver cada caso de teste em questão de segundos; portanto, essa regra age apenas para descartar a força bruta ingênua.

Aplicam-se as regras padrão de .

Casos de teste

Cada caso de teste é do formato board => all valid leapers. Lembre-se de que você só precisa produzir um desses. Se a lista de saltadores estiver vazia, retorne algo que não seja válido.

Examples above:
[[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [1, 8], [2, 1], [2, 2], [2, 3], [2, 4], [2, 5], [2, 6], [2, 7], [2, 8], [3, 1], [3, 2], [3, 3], [3, 4], [3, 5], [3, 6], [3, 7], [3, 8], [4, 1], [4, 2], [4, 3], [4, 4], [4, 5], [4, 6], [4, 7], [4, 8], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5], [5, 6], [5, 7], [5, 8], [6, 1], [6, 2], [6, 3], [6, 4], [6, 5], [6, 6], [6, 7], [6, 8], [7, 1], [7, 2], [7, 3], [7, 4], [7, 5], [7, 6], [7, 7], [7, 8], [8, 1], [8, 2], [8, 3], [8, 4], [8, 5], [8, 6], [8, 7], [8, 8]] => [[0, 1], [1, 2], [1, 4], [2, 3], [3, 4]]
[[1, 1], [5, 1], [2, 2], [4, 2], [6, 2], [3, 3], [5, 3], [7, 3], [2, 4], [4, 4], [5, 5]] => [[1, 1], [1, 3]]
[[1, 1], [2, 2], [3, 2]] => []
[[1, 1], [1, 2], [1, 3], [1, 4], [2, 1], [2, 2], [2, 3], [2, 4], [3, 1], [3, 2], [3, 3], [3, 4], [4, 1], [4, 2], [4, 3], [4, 4], [6, 1], [6, 2], [6, 3], [6, 4], [7, 1], [7, 2], [7, 3], [7, 4], [8, 1], [8, 2], [8, 3], [8, 4], [9, 1], [9, 2], [9, 3], [9, 4]] => [[1, 2]]

Square boards:
[[1, 1], [1, 2], [2, 1], [2, 2]] => [[0, 1]]
[[1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3]] => [[0, 1]]
[[1, 1], [1, 2], [1, 3], [1, 4], [2, 1], [2, 2], [2, 3], [2, 4], [3, 1], [3, 2], [3, 3], [3, 4], [4, 1], [4, 2], [4, 3], [4, 4]] => [[0, 1], [1, 2]]
[[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [2, 1], [2, 2], [2, 3], [2, 4], [2, 5], [3, 1], [3, 2], [3, 3], [3, 4], [3, 5], [4, 1], [4, 2], [4, 3], [4, 4], [4, 5], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5]] => [[0, 1], [1, 2]]
[[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [2, 1], [2, 2], [2, 3], [2, 4], [2, 5], [2, 6], [3, 1], [3, 2], [3, 3], [3, 4], [3, 5], [3, 6], [4, 1], [4, 2], [4, 3], [4, 4], [4, 5], [4, 6], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5], [5, 6], [6, 1], [6, 2], [6, 3], [6, 4], [6, 5], [6, 6]] => [[0, 1], [1, 2], [2, 3]]
[[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [2, 1], [2, 2], [2, 3], [2, 4], [2, 5], [2, 6], [2, 7], [3, 1], [3, 2], [3, 3], [3, 4], [3, 5], [3, 6], [3, 7], [4, 1], [4, 2], [4, 3], [4, 4], [4, 5], [4, 6], [4, 7], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5], [5, 6], [5, 7], [6, 1], [6, 2], [6, 3], [6, 4], [6, 5], [6, 6], [6, 7], [7, 1], [7, 2], [7, 3], [7, 4], [7, 5], [7, 6], [7, 7]] => [[0, 1], [1, 2], [2, 3]]

Miscellaneous:
[[1, 1], [2, 1]] => [[0, 1]]
[[1, 1], [1, 2]] => [[0, 1]]
[[1, 1], [12, 35]] => [[11, 34]]
[[1, 1], [1, 2], [2, 1], [2, 2], [6, 1], [6, 2], [6, 3], [6, 4], [7, 1], [7, 2], [7, 3], [7, 4], [8, 1], [8, 2], [8, 3], [8, 4], [9, 1], [9, 2], [9, 3], [9, 4]] => []
[[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [2, 1], [2, 2], [2, 3], [2, 4], [2, 5], [2, 6], [3, 1], [3, 2], [3, 5], [3, 6], [4, 1], [4, 2], [4, 5], [4, 6], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5], [5, 6], [6, 1], [6, 2], [6, 3], [6, 4], [6, 5], [6, 6]] => [[0, 1], [1, 2], [1, 4]]
[[2, 2], [2, 4], [2, 6], [2, 8], [4, 2], [4, 4], [4, 6], [4, 8], [6, 2], [6, 4], [6, 6], [6, 8], [8, 2], [8, 4], [8, 6], [8, 8]] => [[0, 2], [2, 4]]

Random boards:
[[1, 5], [1, 9], [2, 6], [2, 8], [2, 10], [2, 12], [3, 5], [3, 7], [3, 9], [3, 11], [3, 13], [4, 2], [4, 4], [4, 6], [4, 8], [4, 14], [5, 1], [5, 3], [5, 5], [5, 7], [6, 2], [6, 4], [7, 1], [8, 2]] => [[1, 1], [1, 3]]
[[1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [2, 1], [2, 2], [2, 3], [2, 4], [2, 7], [3, 1], [3, 2], [3, 3], [3, 4], [3, 6], [3, 7], [4, 2], [4, 3], [4, 4], [4, 5], [4, 6], [5, 3], [5, 4], [5, 6]] => [[0, 1], [1, 2]]
[[1, 8], [2, 6], [2, 10], [3, 3], [3, 4], [3, 8], [4, 1], [4, 11], [5, 3], [5, 9], [6, 12], [8, 11], [10, 10], [11, 12], [12, 6], [12, 8], [13, 6], [13, 8], [13, 10], [13, 11], [14, 5], [14, 7], [14, 8], [14, 13], [14, 14], [15, 7], [15, 9], [15, 11], [15, 12], [16, 6], [16, 7], [16, 9], [16, 13], [16, 14], [17, 10], [17, 12], [18, 8], [18, 12], [20, 9], [21, 11], [22, 13], [23, 10], [23, 11], [23, 15], [24, 12]] => [[1, 2]]
[[1, 17], [1, 21], [3, 11], [3, 15], [3, 19], [3, 23], [5, 13], [5, 21], [7, 11], [7, 15], [7, 19], [9, 1], [9, 13], [9, 17], [11, 3], [11, 7], [11, 15], [11, 19], [13, 5], [13, 9], [13, 13], [13, 17], [13, 21], [15, 11], [15, 15], [15, 19], [17, 13], [17, 17]] => [[2, 2], [2, 6], [2, 10]]
[[1, 3], [2, 4], [2, 5], [3, 6], [4, 1], [5, 3], [5, 6], [5, 7], [6, 12], [6, 14], [6, 21], [7, 9], [7, 19], [8, 9], [8, 15], [8, 17], [8, 18], [8, 24], [9, 12], [9, 19], [10, 12], [10, 14], [10, 17], [10, 21], [11, 22], [12, 15], [12, 17], [12, 24], [13, 16], [14, 20], [14, 21], [14, 26], [15, 13], [15, 19], [16, 18], [16, 23], [17, 16], [17, 24]] => [[2, 3]]
[[1, 11], [3, 13], [4, 10], [6, 14], [8, 12], [9, 9], [9, 15], [12, 8], [13, 5], [13, 19], [13, 21], [14, 8], [15, 1], [15, 17], [16, 4], [16, 14], [16, 18], [16, 20], [17, 21], [18, 2], [18, 16], [18, 18], [19, 9], [19, 13], [19, 15], [20, 12], [21, 1], [21, 17], [22, 4], [22, 10], [23, 7]] => [[1, 3]]
[[1, 39], [6, 37], [8, 32], [10, 27], [11, 31], [11, 35], [12, 22], [16, 21], [16, 29], [16, 33], [18, 34], [21, 3], [21, 9], [21, 19], [23, 8], [23, 14], [23, 22], [23, 24], [23, 36], [24, 6], [25, 13], [25, 17], [26, 1], [26, 11], [28, 6], [28, 20], [28, 26], [28, 30], [28, 34], [30, 11], [30, 15], [30, 21], [32, 6], [33, 28], [33, 32], [35, 13], [35, 23]] => [[2, 5]]

Como um caso especial, observe que, para uma placa que consiste em apenas uma célula, qualquer salto funciona, mas sua saída deve corresponder a um salto real, portanto, [0, 0]não é uma saída válida.

Martin Ender
fonte
Pergunta rápida. Como é um cavaleiro (2,1)? Corrija-me se eu estiver errado, mas tenho certeza de que os cavaleiros podem mover 3 quadrados em qualquer direção e depois 1 quadrado em qualquer direção perpendicular à anterior, então deve ser (3,1).
R. Kap
11
@ R.Kap Você está errado. ;) en.wikipedia.org/wiki/Knight_(chess)#Movement
DLosc
@DLosc Ok, uau. Eu acho que estava. Obrigado por isso!
R. Kap
Podemos exibir todos os saltadores válidos em uma lista? Se o fizermos, podemos produzir saltadores equivalentes [[1, 0], [0, 1]]?
FryAmTheEggman
@FryAmTheEggman Apenas qualquer um deles, por favor.
Martin Ender

Respostas:

12

Pyth, 41 35

hfqQu@+G+VM*s_BM*F_BMTGQ]hQ)maVhQdt

Sai em erro se não houver jumpers válidos, fornecendo a sequência vazia se STDERR for ignorado.

Experimente aqui ou execute um Conjunto de Testes

Guardado 6 bytes graças a isaacg ! Basicamente, apenas encontra todos os candidatos saltadores, selecionando cada saltador válido do primeiro bloco para o outro bloco. Em seguida, para cada uma delas, ele faz todas as oito configurações de [x, y]compensações que o saltador poderia executar. Em seguida, ele encontra todos os movimentos iniciando no primeiro bloco que se segue após o movimento e descarta aqueles que não estão na entrada. Ele continua fazendo isso até o resultado não mudar. Se esta lista final for igual à entrada, o salto será válido.

O tabuleiro de xadrez padrão demorou mais tempo quando eu estava testando, levou cerca de 3 segundos no meu computador não muito impressionante.

FryAmTheEggman
fonte