Labirynt szachownicy

14

Figury szachowe (królowie, królowe, wieże, biskupi i rycerze) i pionki znajdują się na planszy, ale nie na polu A1 lub H8 . Twoim zadaniem jest podróż z pustych pól A1 do pustych pól H8 , przechodząc tylko przez puste pola. Zasady przemieszczania są następujące:

  1. Możesz przejść z dowolnego pustego kwadratu do dowolnego pustego kwadratu obok niego (ta sama ranga, następny lub poprzedni plik; lub ten sam plik, następny lub poprzedni stopień).
  2. Możesz przejść z dowolnego pustego kwadratu do dowolnego pustego kwadratu po przekątnej (następna lub poprzednia ranga, następny lub poprzedni plik), pod warunkiem, że kwadraty w narożnikach zawierają albo (a) dwa pionki, albo (b) pionki / kawałki przeciwnych kolor. (Dwa pionki lub pionek i pionek tego samego koloru są wystarczająco mocne, aby zablokować twój postęp w rogu, ale dwa pionki nie są; pionki / pionki w przeciwnych kolorach nie działają koncert, aby przeszkodzić ci na drodze.) Na przykład, jeśli jesteś na c4, a d5 jest puste, możesz przejść do niego, pod warunkiem, że c5 i d4 zawierają pionki lub zawierają pionki / pionki o przeciwnych kolorach. Zdjęcia znajdują się w sekcji „Przykładowe przekątne” poniżej.

Wejście

Opis płyty FEN . To znaczy: Dane wejściowe będą ciągiem zawierającym opis rangi 8 , ukośnik ( /), opis rangi 7 , ukośnik,… i opis rangi 1 . Opis każdej rangi zawiera cyfry i litery biegnące od pliku a do pliku h , gdzie litery oznaczają pionki i pionki (czarne to p= pionek, n= rycerz, b= biskup, r= wieża, q= królowa, k= król i biały te są wielkimi wersjami tego samego), a liczby wskazują kolejną liczbę pustych kwadratów. Na przykład, rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNjest to deska po jednym ruchu warstwy (pionek króla na e4) w szachach.

a1 i h8 będą puste na wejściu; tzn. pierwszy ukośnik ma cyfrę przed nim, a ostatni ukośnik ma cyfrę po nim.

Wynik

Prawda czy falsey, wskazując, czy możliwe jest udane przejście do h8 .

Jeśli dane wejściowe nie są poprawnym opisem płyty FEN (co oznacza, że ​​pasuje do mojego wyjaśnienia powyżej) lub jeśli a1 lub h8 jest zajęty, to wynik może być cokolwiek lub nic. (Innymi słowy: możesz założyć, że dane wejściowe spełniają powyższe wymagania).

Punktacja

To jest kod golfowy: wygrywa najmniej bajtów.

Przykładowe wejście i wyjście

Pamiętaj, że Twój kod musi działać dla wszystkich prawidłowych danych wejściowych, nie tylko dla przykładów.

Dodaj spację i wpo każdym FEN, aby go wizualizować http://www.dhtmlgoodies.com/scripts/chess-fen/chess-fen-3.html. (Należy pamiętać, że niektóre inne internetowe wizualizatory FEN nie zezwalają na planszę, która jest nielegalna w szachach, np. Z pionkiem o randze 1 lub 8 , więc nie można jej użyć do naszych celów.)

Prawdziwe przykłady

  • 8/8/8/8/8/8/8/8 - pusta tablica
  • 1p1Q4/2p1Q3/2p1Q3/2p1Q3/2p1Q3/2p1Q3/Q1p1Q3/1q3q2- istnieje ścieżka a1 , b2 , b3 , b4 , b5 , b6 , b7 , c8 , d7 , ( nie e8 , to jest zablokowane, ale) d6 , d5 , d4 , d3 , d2 , d1 , e1 , f2 , f3 , f4 , f5 , f6 , f7 , f8 , g8 , h8
  • 8/8/KKKKK3/K3K3/K1K1p3/Kp1K4/K1KK4/2KK4 - przykład, w którym kwadrat, który jest zablokowany w jednym punkcie, musi zostać przepuszczony później (aby upewnić się, że nie ustawisz kwadratów jako nieprzekraczalnych)
  • K1k1K1K1/1K1k1K1k/K1K1k1K1/1k1K1K1k/K1k1K1k1/1K1k1k1K/K1K1k1K1/1k1k1K1k- istnieje jedna ścieżka (wystarczy podążać za nosem: na każdym kroku jest tylko jeden kwadrat, chyba że cofniesz się o krok); jest to również przykład, w którym kwadrat jest blokowany w jednym punkcie, ale jest potrzebny później

Przykłady Falsey

  • 6Q1/5N2/4Q3/3N4/2Q5/1N6/2Q5/1N6 - każda próba ścieżki będzie musiała przejść przez dwa ukośne kawałki tego samego koloru
  • N1q1K1P1/1R1b1p1n/r1B1B1Q1/1p1Q1p1b/B1P1R1N1/1B1P1Q1R/k1k1K1q1/1K1R1P1r- jedyną drogą przez przekątną a8-h1 jest f2-g3 , ale wymagałoby to przejścia przez e1-d2 lub f2-e3 , które są niemożliwe.
  • 4Q3/4q3/4Q3/5Q2/6Q1/3QqP2/2Q5/1Q6
  • 4q3/4Q3/4q3/5q2/6q1/3qQp2/2q5/1q6

Przykładowe przekątne

W przypadku, gdy powyższa proza ​​była niejasna, oto kilka zdjęć.

Przejezdne przekątne

pionki tego samego koloru pionki o przeciwnych kolorach gawrony o przeciwnych kolorach

Nieprzejezdne przekątne

wieża i pionek tego samego koloru gawrony tego samego koloru

msh210
źródło
Przepraszam, nie jestem pewien co do standardowych zasad golfa: Co się stanie, jeśli wstawisz niedozwolony ciąg znaków? Czy może wystąpić jakieś zachowanie?
alex berne
@alexberne Wierzę, że to obejmuje: „Twój kod musi działać dla wszystkich prawidłowych danych wejściowych”.
Rainbolt
@alexberne, edytowałem. Czy to już jasne?
msh210
Tak, dziękuję. Jestem tu nowy, więc może to być zwykły użytek dla golfisty, ale dla mnie było niejasne :)
Alex Berne
Chciałem tylko podziękować za świetną łamigłówkę @ msh210. Nie rozumiem, dlaczego nie ma więcej odpowiedzi.
Joffan

Odpowiedzi:

6

VBA 668 666 633 622 548 510 489 435 331 322 319 315 bajtów

Function Z(F):Dim X(7,7):While Q<64:R=R+1:V=Asc(Mid(F,R))-48:If V>9 Then X(Q\8,Q Mod 8)=(3+(V\8=V/8))*Sgn(48-V):V=1
Q=Q-V*(V>0):Wend:X(7,0)=1:For W=0 To 2E3:Q=W Mod 8:P=W\8 Mod 8:For T=Q+(Q>0) To Q-(Q<7):For S=P+(P>0) To P-(P<7):If X(S,T)=0 Then X(S,T)=(1=X(P,Q))*(6>X(P,T)*X(S,Q))
Next S,T,W:Z=X(0,7):End Function

Odczytywanie ciągu wejściowego zajmuje do „Wend”. Niezły efekt uboczny - porzuca kod wejściowy, gdy tablica [X] jest w pełni zakodowana, więc możesz zostawić opis na końcu.

W kodowaniu planszowym pionki mają 2, inne elementy 3, czarny jest ujemny. Pionki są rozpoznawane przez „P” i „p” posiadające kody znaków podzielne przez 8.

„X (7,0) = 1”, ustawienie dostępnego a1 , rozpoczyna się od sprawdzenia ścieżki. Powoduje to wielokrotne skanowanie planszy, próbując dodać dostępne kwadraty z dotychczas oznaczonych jako dostępne (1). Dostęp po przekątnej i obłożenie są sprawdzane za pomocą logiki IF +, która kiedyś mieszkała w funkcji, ale teraz znajduje się w zagnieżdżonych pętlach sąsiada. Kontrola dostępu po przekątnej zależy od iloczynu dwóch kwadratów narożnych kotka, które mają tylko 6 lub więcej, jeśli elementy mają ten sam kolor, a co najmniej jeden jest pionkiem, a nie pionkiem.

Zadzwoń w arkuszu kalkulacyjnym; zwraca wartość w X (0,7) - 1, jeśli h8 jest dostępny i 0, jeśli nie - co Excel rozpoznaje jako prawda / fałsz. = JEŻELI (Z (C2), „tak”, „nie”)

wprowadź opis zdjęcia tutaj

Być może wciągnęło mnie wyskrobywanie kodu powyżej, więc oto wersja z komentarzem na wpół nieposkromiona:

Function MazeAssess(F)  'input string F (FEN)
Dim X(7, 7)             'size/clear the board; also, implicitly, Q = 0: R = 0
'Interpret string for 8 rows of chessboard
While Q < 64
    R = R + 1           ' next char
    V = Asc(Mid(F, R)) - 48  ' adjust so numerals are correct
    If V > 9 Then X(Q \ 8, Q Mod 8) = (3 + (V \ 8 = V / 8)) * Sgn(48 - V): V = 1 ' get piece type (2/3) and colour (+/-); set for single column step
    Q = Q - V * (V > 0) ' increment column (unless slash)
Wend
'Evaluate maze
X(7, 0) = 1             ' a1 is accessible
For W = 0 To 2000       ' 1920 = 30 passes x 8 rows x 8 columns, golfed to 2E3
    Q = W Mod 8         ' extracting column
    P = W \ 8 Mod 8     ' extracting row
    For T = Q + (Q > 0) To Q - (Q < 7)     ' loop on nearby columns Q-1 to Q+1 with edge awareness
        For S = P + (P > 0) To P - (P < 7) ' loop on nearby rows (as above)
            If X(S, T) = 0 Then X(S, T) = (1 = X(P, Q)) * (6 > X(P, T) * X(S, Q)) ' approve nearby empty squares if current square approved and access is possible
        Next 'S
    Next 'T
Next 'W
MazeAssess = X(0, 7)    ' report result for h8
End Function

Oceny postępu

Edycja 1: Kod nie jest już tak 666-diabelski :-D i utracił swoje funkcje; Znalazłem wystarczająco krótki sposób, aby je napisać, aby uniknąć kosztów ogólnych.

Edycja 2: Kolejny wielki krok naprzód, skutecznie kończąc pracę nad usunięciem funkcji inc / dec, westchnieniem i użyciem kilku globali. Może w końcu zrozumiem ...

Kodowanie elementów i kwadratów uległo zmianie. Bez wpływu na długość kodu.

Edycja 3: Powrót (fałszywych) funkcji, usunięcie wszystkich irytujących Callbajtów i kilka innych poprawek.

Edycja 4: Przebijając się przez wielką 500, woohoo - zgarnął pętle 3 For w 1.

Edycja 5: Jiminy Cricket, kolejna wielka kropla, kiedy zgarnąłem dwie funkcje razem - moja kontrola dostępu po przekątnej zawsze przechodzi na sąsiednie kwadraty, więc ...

Edycja 6: Święte stalówki, kolejna wielka kropla. Żegnajcie z funkcjami zewnętrznymi, a tym samym globalnymi ... Zrobiłem mniej niż połowę pierwotnie opublikowanej długości ...

Edycja 7: Dodaj wersję bez golfa

Edycja 8: Zmieniono proces odczytu o kilka dolarów więcej

Edycja 9: Nacisnąłem kilka wyrażeń na kilka ostatnich kropli krwi

Edycja 10: Instrukcja Compund Nextzrzuca kilka bajtów


Dla zainteresowania grafika kart po analizie dostępności (numery kodów są nieaktualne, ale ...) dostępne kwadraty są zielone, niedostępne kwadraty białe, a inne kolory to części lub pionki.

3 udane tablice 3 zablokowane tablice

Kilka plansz wyzwań: h8 jest dostępny zarówno:

  • P1Pq2p1 / 1P1R1R1p / 1K2R1R1 / 1p1p1p2 / p1b1b1np / 1B1B1N1k / Q1P1P1N1 / 1r1r1n2 - 10 przejść do rozwiązania
  • P1P3r1 / 1P1R2r1 / 1N1R1N2 / 1P1P1P2 / 1n1p1ppp / 1B1B4 / 1b1pppp1 / 1P6 - ścieżka uzwojenia
Joffan
źródło
1
Bardzo fajnie i +1, ale: (1) Czy na pewno wystarczy 960 kroków? (2) Czy możesz zaoszczędzić kilka bajtów, patrząc na tablicę do góry nogami? If V>9 Then X(7-P,C)=pomyślałbym (nie żebym wiedział VBA) If V>9 Then X(P,C)=.
msh210
W rzeczywistości ta technika oszczędza inicjowanie P, więc dziękuję za pytanie :-). I tak, jestem pewien, że 15 przebiegów planszy wystarczy; Sporo sprawdziłem. W rzeczywistości nie byłem w stanie przekroczyć 10 przejść, ale 640 i 960 mają tę samą liczbę znaków, więc zagram to bezpiecznie. ALE, jeśli rozwalę deskę do góry nogami, Mógłbym wziąć więcej niż 10 podań, a może więcej niż 15 - chyba że przejdę również deskę do góry nogami, co miałoby narzut.
Joffan
@ msh210 1 dodatkowej obserwacji - 15 pętli jest tylko na tyle, aby przeanalizować całą planszę, najgorszy przypadek, ale 10 pętle wystarczy, aby uzyskać status H8, więc mam naprawdę duży margines. Powodem jest to, że wyszukiwanie ścieżek działa znacznie szybciej w kierunku oceny, zwiększając numer wiersza i kolumny # - dopóki ścieżka idzie w górę lub w prawo, będzie ona ukończona w jednym przejściu. Idąc w lewo lub w dół dostajesz tylko jeden krok dalej na przejście.
Joffan
@ msh210 W ramach przeróbki procesu odczytu - która wąsko utrzymywała możliwość pozostawienia komentarza na końcu ciągu FEN - dodałem sugerowane odwrócenie planszy - niektóre tablice przejmują teraz 15 przebiegów (do 17), więc funkcja wzrosła do 30 przejść planszy.
Joffan
@Joffan można upuścić 3 bajty przez kondensację wszystkich wystąpień [some non-letter character] Todo[some non-letter character]To
Taylor Scott
3

Matlab, 636 887 bajtów jako zapisane (w tym wcięcia)

To rozwiązanie nie jest bardzo golfowe, ale chciałem je rozwinąć.

function[n] = h(x)
o=[];
for i=x
 b={blanks(str2num(i)),'K','k',i};o=[o b{~cellfun(@isempty,regexp(i,{'\d','[NBRQK]','[nbrqk]','p|P'}))}];
end
o=fliplr(reshape(o,8,8))
for i=1:64
 b=i-[-8,8,7,-1,-9,1,9,-7];
 if mod(i,8)==1
  b=b(1:5);
 elseif mod(i,8)==0
  b=b([1,2,6:8]);
 end
 b=b(b<65&b>0);c=o(b);dn=b(isspace(c)&ismember(b,i-[9,7,-9,-7]));
 for j=dn
  g=o(b(ismember(b,j-[-8,8,7,-1,-9,1,9,-7])));
  if ~isempty(regexp(g,'pk|kp|PK|KP|kk|KK'));c(b==j)='X';end;
 end
 Bc{i}=b(c==32);
end
n=Bc{1};
on=[];
while length(n)>length(on)
 on=n;
 for i=1:length(n)
  n=unique([n Bc{n(i)}]);
 end
end
any(n==64)
end

Odczytuje ciąg planszy, xjak określono powyżej, i zamienia go w bardziej dokładnie przedstawiony o, a następnie znajduje wszystkie ruchy (krawędzie wykresu) między spacjami, następnie określa, które ruchy są możliwe (nie w wypełnionych spacjach), a następnie określa, które możliwe ruchy mają „ bramki ”z dwóch części, które należy przepuścić, a następnie dowiedzieć się, czy brama jest otwarta (pionki, przeciwne kolory) lub zamknięta (ten sam kolor i zawiera pionek). Następnie przechodzi, aby znaleźć lokalizacje, do których można dotrzeć ścieżkami z lewego dolnego kwadratu, a jeśli ścieżka może dotrzeć do pola 64, jest to tablica Tak.

sintax
źródło
1
Chłodny. Czy przetestowałeś go na moich przykładowych FEN w pytaniu, aby upewnić się, że zwraca poprawny wynik dla każdego? Ponieważ jest to pytanie do gry w golfa , naprawdę powinieneś zagrać w golfa. Jeśli nic więcej, czy możesz pozbyć się wcięcia (lub uczynić z niego pojedynczą spację lub tabulator zamiast czterech spacji)? i / lub upuścić spacje wokół =s? (Nie wiem MATLAB: może to niemożliwe).
msh210,
Tak, a może zrobię to podczas mojej następnej przerwy. Przetestowałem to na wszystkich twoich przykładach, a potem na niektórych. Czy powinienem to w jakiś sposób zaznaczyć?
sintax,
Dunno; Właśnie się zastanawiałem.
msh210,