Damas: Rei eu?

14

Desafio:

Dado um tabuleiro de damas, faça a menor quantidade de movimentos necessários (assumindo que o preto não se mova) para reinar uma peça vermelha, se possível.

Regras :

O lado do vermelho sempre estará no fundo, no entanto, suas peças podem começar em qualquer linha (até na linha do rei que eles precisam chegar). As peças pretas são fixas , o que significa que elas não se movem entre os movimentos do vermelho, mas são removidas do tabuleiro quando capturadas. Observe que as peças podem começar em qualquer espaço no tabuleiro, inclusive um ao lado do outro. Não é assim que as damas normais são jogadas, mas seu programa deve ser capaz de resolvê-las. (Consulte a entrada 5) No entanto, as peças do verificador devem se mover apenas na diagonal (consulte a entrada 3). A captura para trás é permitida se a primeira captura estiver para frente na cadeia (consulte a entrada 7).

Entrada:

Um tabuleiro de damas 8x8, com espaços no tabuleiro definidos como os seguintes caracteres (fique à vontade para usar alternativas, desde que sejam consistentes):

. - Vazio

R - Peça (s) vermelha (s)

B - peça (s) preta (s)

Resultado:

O menor número de movimentos que uma peça vermelha levaria para ser 'dominada' entrando na linha do rei na linha superior do tabuleiro (lado do preto), 0 se nenhum movimento fosse necessário (uma peça vermelha iniciada na linha do rei) ou um número negativo, se for impossível rei uma peça vermelha (ou seja, o preto ocupa toda a primeira linha).

Entrada 1:

. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
R . . . . . . .

Saída 1:

7

Entrada 2:

. . . . . . . .
. . . . . . . .
. . . . . B . .
. . . . . . . .
. . . B . . . .
. . . . . . . .
. B . . . . . .
R . . . . . . .

Saída 2:

2

Entrada 3:

. B . B . B . B
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
R . . . . . . .

Saída 3:

-1

Entrada 4:

. . . . . . . R
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
R . . . . . . .

Saída 4:

0

Entrada 5:

. . . . . . . .
. . . . . . . .
. . . . . . . .
. B . . B . . .
B . . . . B . .
. B . B . . . .
. . B . . B . .
. . . R R . . .

Saída 5:

4

Entrada 6:

. . . . . . . .
. . . . . . . .
. B . . . . . .
. . B . . . . .
. B . B . . . .
. . . . R . . .
. . . B . . . .
. . . . R . . .

Saída 6:

2

Entrada 7:

. . . . . . . .
. . . . . . . .
. . B . . . . .
. . . . . . . .
. . B . . . . .
. B . B . B . .
. . . . B . . .
. . . . . R . R

Resultado 7:

4

Pontuação:

Isso é , então o código mais curto em bytes vence.

Yodle
fonte
1
O segundo caso de teste não deve ser 2, pois você pode dobrar / triplicar o salto?
DJMcMayhem
Uma matriz de estado de matrizes de números inteiros como entrada está OK?
Jonathan Allan
1
Adicionei outro caso de teste que deve ser difícil. Envolve vários saltos, várias peças e pulando para trás, a fim de alcançar a melhor solução possível.
precisa saber é
1
@orlp Hm, eu diria que nenhuma das peças vermelhas pode se mover para trás, uma vez que nenhuma delas é reis (daí o ponto do desafio), mas parece que algumas pessoas brincam com regras em que capturar para trás é permitido por não- peças dominadas se a primeira captura foi encaminhada. Vou acrescentar isso às regras, pois não tinha conhecimento disso antes.
Yodle 26/09/16
1
ooooooooh, você não precisa escolher apenas uma peça vermelha, eles podem se unir! Eu entendi
Greg Martin

Respostas:

4

JavaScript (ES6), 354 bytes

Toma uma matriz como entrada com:

  • 0 = quadrado vazio
  • 1 = peça vermelha
  • 2 = peça preta

Retorna o número ideal de movimentos, ou 99, se não houver solução.

É muito rápido, mas poderia ser jogado muito mais.

F=(b,n=0,C=-1,i)=>b.map((v,f,X,T,x=f&7,y=f>>3)=>v-1||(y&&n<m?[-9,-7,7,9].map(d=>(N=c=X=-1,r=(d&7)<2,T=(t=f+d)>=0&t<64&&(x||r)&&(x<7||!r)?(!b[t]&d<0)?t:b[t]&1?N:b[t]&2&&(d<0&y>1|d>0&C==f)?(X=t,x>1||r)&&(x<6|!r)&&!b[t+=d]?c=t:N:N:N)+1&&(b[f]=b[X]=0,b[T]=1,F(b,n+!(C==f&c>N),c,1),b[f]=1,b[X]=2,b[T]=0)):m=n<m?n:m),m=i?m:99)|m

var test = [
  [ 0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    1,0,0,0,0,0,0,0
  ],
  [ 0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,2,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,2,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,2,0,0,0,0,0,0,
    1,0,0,0,0,0,0,0
  ],
  [ 0,2,0,2,0,2,0,2,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    1,0,0,0,0,0,0,0
  ],
  [ 0,0,0,0,0,0,0,1,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    1,0,0,0,0,0,0,0
  ],
  [ 0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,2,0,0,2,0,0,0,
    2,0,0,0,0,2,0,0,
    0,2,0,2,0,0,0,0,
    0,0,2,0,0,2,0,0,
    0,0,0,1,1,0,0,0
  ],
  [ 0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,2,0,0,0,0,0,0,
    0,0,2,0,0,0,0,0,
    0,2,0,2,0,0,0,0,
    0,0,0,0,1,0,0,0,
    0,0,0,2,0,0,0,0,
    0,0,0,0,1,0,0,0
  ],
  [ 0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,2,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,2,0,0,0,0,0,
    0,2,0,2,0,2,0,0,
    0,0,0,0,2,0,0,0,
    0,0,0,0,0,1,0,1
  ]
];

test.forEach((b, n) => {
  console.log("Test #" + (n + 1) + " : " + F(b));
});

Arnauld
fonte
99 é provavelmente bom, não consigo imaginar uma solução real fazendo 99 movimentos em uma placa 8x8. Bom trabalho!
Yodle