Warcaby: King Me?

14

Wyzwanie:

Biorąc pod uwagę szachownicę, wypuszczaj najmniejszą liczbę ruchów, którą byś potrzebował (zakładając, że czarny w ogóle się nie rusza), aby królem czerwony kawałek, jeśli to możliwe.

Zasady :

Strona Czerwona zawsze będzie na dole, jednak ich pionki mogą zaczynać się w dowolnym rzędzie (nawet w rzędzie króla, do którego muszą się dostać). Czarne pionki są nieruchome , co oznacza, że ​​nie poruszają się między ruchami czerwieni, ale zostają schwytane z planszy. Pamiętaj, że pionki mogą zaczynać się na dowolnym polu na planszy, w tym obok siebie. Nie gra się w normalne warcaby, ale twój program musi być w stanie je rozwiązać. (Patrz wejście 5) Jednak elementy kontrolne mogą poruszać się tylko po przekątnej (patrz wejście 3). Przechwytywanie wstecz jest dozwolone, jeśli pierwsze przechwytywanie jest do przodu w łańcuchu (patrz dane wejściowe 7).

Wejście:

Szachownica 8x8, ze spacjami na planszy zdefiniowanymi jako następujące postacie (możesz swobodnie korzystać z alternatyw, o ile są spójne):

. - Pusty

R - Czerwony kawałek (i)

B - Czarny kawałek (i)

Wynik:

Najmniejszą liczbę ruchów zajęłoby czerwony kawałek za „kinged” wpisując wiersz królewskiego w górnym rzędzie na pokładzie (bocznej Blacka), 0 jeśli nie są wymagane żadne ruchy (czerwony kawałek rozpoczęto rzędu królewskim), lub liczba ujemna, jeśli nie jest możliwe królem czerwony kawałek (tzn. czarny zajmuje cały jego pierwszy rząd).

Wejście 1:

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

Wyjście 1:

7

Wejście 2:

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

Wyjście 2:

2

Wejście 3:

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

Wyjście 3:

-1

Wejście 4:

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

Wyjście 4:

0

Wejście 5:

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

Wyjście 5:

4

Wejście 6:

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

Wyjście 6:

2

Wejście 7:

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

Wyjście 7:

4

Punktacja:

To jest , więc wygrywa najkrótszy kod w bajtach.

Jodła
źródło
1
Czy drugi przypadek testowy nie powinien wynosić 2, ponieważ można skakać dwukrotnie / potrójnie?
James
Czy tablica stanu tablic liczb całkowitych jako dane wejściowe jest w porządku?
Jonathan Allan,
1
Dodałem kolejną próbę, która powinna okazać się trudna. Polega ona na wielokrotnym skakaniu, wielu elementach i skakaniu do tyłu w celu osiągnięcia najlepszego możliwego rozwiązania.
orlp
1
@orlp Hm, miałem zamiar powiedzieć, że żadna z czerwonych pionków nie może się cofać, ponieważ żaden z nich nie jest królem (stąd wyzwanie), ale wydaje się, że niektórzy grają z zasadami, w których przechwytywanie wstecz jest niedozwolone królestwo, jeśli pierwsze zdobycie było do przodu. Dodam to do zasad, ponieważ wcześniej nie zdawałem sobie z tego sprawy.
Yodle
1
ooooooooh, nie musisz wybierać tylko jednego czerwonego elementu, mogą połączyć siły! Rozumiem
Greg Martin

Odpowiedzi:

4

JavaScript (ES6), 354 322 bajtów

Pobiera tablicę jako dane wejściowe z:

  • 0 = pusty kwadrat
  • 1 = czerwony kawałek
  • 2 = czarny kawałek

Zwraca optymalną liczbę ruchów lub 99, jeśli nie ma rozwiązania.

Jest bardzo szybki, ale można grać w golfa znacznie więcej.

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
źródło
99 jest prawdopodobnie w porządku, nie wyobrażam sobie prawdziwego rozwiązania wymagającego 99 ruchów na planszy 8x8. Dobra robota!
Yodle,