Na szachownicy znajduje się gra Get Home . W tej grze jest jeden element, który jest przesuwany po kolei przez obu graczy. Istnieją pewne zasady dotyczące przenoszenia elementu. Podczas tury gracz musi wykonać jeden z poniższych ruchów, aby uzyskać dodatnią n .
n odstępów w górę
n spacji po lewej stronie
n odstępów w górę i w lewo (przekątna)
Gracz, który przenosi pionek do lewego górnego rogu planszy, wygrywa.
Teraz zdefiniujemy pojęcie przegrywającego kwadratu. W tym filmie (skąd wpadłem na pomysł), przegrywający kwadrat jest definiowany jako kwadrat, na którym każdy gracz rozpoczynający swoją turę będzie zmuszony wykonać ruch umożliwiający przeciwnikowi wymuszenie wygranej. Najprostszym przykładem przegrywającego kwadratu byłby kwadrat przy (1,2). Kawałek w (1,2) może przenieść się do dowolnego z poniższych miejsc.
Wszystkie mają bezpośrednią ścieżkę do zwycięstwa dla następnego gracza.
Wynika z tego również, że każde pole, które ma ścieżkę jednego ruchu do kwadratu przegrywającego, pozwala graczowi na tym polu wymusić zwycięstwo. Oznacza to, że każdy kwadrat, który nie jest jednym ruchem od kwadratu tracącego, jest również kwadratem tracącym.
To prowadzi nas do tej dość zgrabnej definicji przegrywającego kwadratu:
Przegrywający kwadrat to kwadrat, z którego żaden ruch nie może nadejść na innym przegrywającym polu, a (0,0) to przegrywający kwadrat.
Zadanie
Biorąc pod uwagę współrzędne kwadratu na planszy szachowej o dowolnym rozmiarze, określ, czy jest to przegrywający kwadrat. Podaj dwie wartości: jedną dla utraty kwadratów i jedną dla innych.
To jest golf golfowy, więc odpowiedzi będą liczone w bajtach, przy czym mniej bajtów będzie lepszych.
Przypadki testowe
Oto wszystkie przegrane kwadraty na zwykłej szachownicy 8 na 8 (oznaczone 0).
0 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1
1 0 1 1 1 1 1 1
1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 0
1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1
Oto obraz planszy 100 na 100 ze zgubionymi kwadratami zaznaczonymi na czarno (każdy kwadrat ma 2 piksele na 2 piksele).
źródło
10, 7
przegrany jest kwadrat? Jest10, 8
? Co15, 11
?Odpowiedzi:
Python 3 ,
112504642 bajtów-4 bajty dzięki Jonathanowi Allanowi !
-2 bajty dzięki xnor !
Wypróbuj online!
Oparty na formule zimnych pozycji w grze Wythoffa i wprowadzeniu pewnych modyfikacji w celu uzyskania wyraźnej formuły. Wyjaśnienie przychodzące, gdy faktycznie zakończę właściwą metodologię wyprowadzania wzoru.
źródło
0<=x
, abyx>0
i zapisać bajt lub dwa?<=
albo>=
w celu objęcia stanowiska0, 0
.lambda r,c:int(abs(r-c)*(5**.5+1)**2/4)==max(r,c)
/2//1
wygląda tak samo jak//2
.Galaretka , 8 bajtów
Wypróbuj online! lub zobacz lewy górny 60 na 60 jako siatkę .
W jaki sposób?
Zimna pozycja w grze Wythoffa to pozycja przegrana. Współrzędne
[n,m]
dać pozycję podczas zimnejn = floor(kφ) = floor(mφ) - m
lubm = floor(kφφ) = ceil(nφ) = n + k
dla niektórych liczbą naturalną,k
a stosunek złoty,φ
. Pierwsza obowiązuje, gdyn
jest mniejsza niżm
; ten drugi, gdym
jest mniejszy niżn
(oba trzymają się0,0
).k
jest zatem bezwzględną różnicą pomiędzyn
im
afloor(abs(n-m)φ)=min(n,m)
warunkiem spełnienia.źródło
JavaScript (ES6), 64 bajty
Widzę teraz, że nie jest to najlepsza technika, ale musiałem ją wymyślić, ponieważ straciłem internet wkrótce po załadowaniu tej strony. (Napisałbym jakiś czas temu, gdyby nie te problemy z Internetem ...)
W idealnym świecie precyzja pływaka nie stanowiłaby problemu, a ja mogłem zaoszczędzić 9 bajtów:
Można by zapisać 6 dodatkowych bajtów, gdyby JS obsługiwał łańcuch porównawczy Pythona:
źródło
Pyth, 39 bajtów
Napisałem to z nazwaną funkcją (ew) i byłem bardzo leniwy w golfa. Planujesz zagrać w golfa później wieczorem
Wypróbuj online, z moimi własnymi wygenerowanymi testami, które mają na przemian Prawda / Fałsz
Wyjaśnienie:
Przekątne matrycy roztworu mają kwadrat przegrywający zgodnie z sekwencją powtarzanych liczb w OEIS A005206 . Od
L
through;
jest całkiem prosta polski notacja do zdefiniowaniay(b)=b-y(y(b-1))
.Reszta wyjaśnienia następuje
źródło
Partia, 204 bajty
Zwraca przez kod wyjścia. Objaśnienie: Ponieważ Batch ma tylko arytmetykę liczb całkowitych, musiałem opracować rozwiązanie czysto arytmetyczne. Wyłączając
0,0
wpis, pary utraty współrzędnych kwadratowych są zgodne z następującą regułą: jeśli nawet następna - bezpłatna11
liczba binarna jest równa, to dodaj w3,2
przeciwnym razie dodaj2,1
. Test na bezpłatną11
liczbę binarną ma miejsce, gdy nie ma żadnych przeniesień, gdy jest ona pomnożona przez trzy, innymi słowy, że(i*2)+i==(i*2)^i
. Oto kilka pierwszych11
darmowych liczb binarnych i ich współrzędne:itd. Tajemniczo ta reguła wystarcza, by sekwencje się uzupełniały. Następnie pozostaje obliczyć sekwencję, aż osiągnie większą współrzędną, w którym momencie możemy ustalić, czy kwadrat traci.
źródło