Czy to przegrywający kwadrat?

19

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.

Ilustracja

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 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).

Tablica 100 na 100

Kreator pszenicy
źródło
2
Nie sądzę, aby było wystarczająco dużo przypadków testowych, aby znaleźć wzór. Myślę, że widzę wzór, ale nie mogłem powiedzieć na pewno. Czy 10, 7przegrany jest kwadrat? Jest 10, 8? Co 15, 11?
DJMcMayhem
1
@WheatWizard Czy masz coś przeciwko powiększeniu obrazu?
Erik the Outgolfer,
1
@WheatWizard Miałem na myśli większe piksele ... np. 5x5 pikseli zamiast 1x1, być może trochę siatki, jeśli nie za twarde (dzięki dzięki za 100x100)
Erik Outgolfer
2
Również powiązane (powrót optymalnego ruchu lub sygnał, że pozycja traci).
Zgarb,
1
Myślę, że normalne jest dopuszczanie niedokładności zmiennoprzecinkowych, które utrudniają działanie nawet przy dowolnie dużych liczbach całkowitych ...
Jonathan Allan

Odpowiedzi:

8

Python 3 , 112 50 46 42 bajtów

-4 bajty dzięki Jonathanowi Allanowi !

-2 bajty dzięki xnor !

lambda r,c:abs(r-c)*(3+5**.5)//2==max(r,c)

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.

notjagan
źródło
Nie można zmienić 0<=x, aby x>0i zapisać bajt lub dwa?
Jonathan Frech,
@JonathanFrech To musi być <=albo >=w celu objęcia stanowiska 0, 0.
notjagan
Masz rację, można zapisać tylko jeden bajt .
Jonathan Frech,
1
Jeden bajt mniej z inną implementacją tego samego:lambda r,c:int(abs(r-c)*(5**.5+1)**2/4)==max(r,c)
Jonathan Allan
1
/2//1wygląda tak samo jak //2.
xnor
5

Galaretka , 8 bajtów

ạ/×ØpḞ⁼Ṃ

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 zimnej n = floor(kφ) = floor(mφ) - mlub m = floor(kφφ) = ceil(nφ) = n + kdla niektórych liczbą naturalną, ka stosunek złoty, φ. Pierwsza obowiązuje, gdy njest mniejsza niż m; ten drugi, gdy mjest mniejszy niż n(oba trzymają się 0,0).

kjest zatem bezwzględną różnicą pomiędzy ni ma floor(abs(n-m)φ)=min(n,m)warunkiem spełnienia.

ạ/×ØpḞ⁼Ṃ - Link: list, c ([n,m])
 /       - reduce c by:
ạ        -   absolute difference = abs(n-m)
   Øp    - golden ratio yield
  ×      - multiply
     Ḟ   - floor
       Ṃ - minimum of c = min(n,m)
      ⁼  - equal?
Jonathan Allan
źródło
2

JavaScript (ES6), 64 bajty

f=(x,y,p=5**.5/2+.5)=>x<y?f(y,x):y/p%p<1&(y/p%p-x*p%++p)**2<1e-9

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:

f=(x,y,p=5**.5/2+.5)=>x<y?f(y,x):y/p%p<1&y/p%p==x*p%++p

Można by zapisać 6 dodatkowych bajtów, gdyby JS obsługiwał łańcuch porównawczy Pythona:

f=(x,y,p=5**.5/2+.5)=>x<y?f(y,x):y/p%p==x*p%++p<1
ETHprodukcje
źródło
0

Pyth, 39 bajtów

=SQL?!b0-byytb;q@myd+0.fqyZytZ@Q1)-F_Qh

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 Lthrough ;jest całkiem prosta polski notacja do zdefiniowania y(b)=b-y(y(b-1)).

Reszta wyjaśnienia następuje

=SQL?!b0-byytb;q@myd+0.fqyZytZ@Q1)-F_Qh    Full program, take stdin as [x, y], output True or False to stdout
=SQ                                        Sort input
   L?!b0-byytb;                            Named lambda as explained above
                    +0.f                   Make sequence of first max(x, y) numbers, starting with 0, 
                        qy y               For which are equal 
                          Z tZ             each element and the previous are equal
                myd                        Map this sequence to the y(index), not just index numbers
             q                             Check if are equal 
              @                  )-F_Q     the x-yth element of sequence (x-y represents which diagonal) 
                                     h(Q)  and the lower of [x,y] (Q is added by the interpreter to fix arity issues
Dave
źródło
0

Partia, 204 bajty

@if %1 lss %2 %0 %2 %1
@if %1==0 exit/b0
@set/au=l=i=0
:g
@set/au+=2+i%%2,l+=1+i%%2
@if %1==%n% if %2==%m% exit/b0
@if %1 leq %n% exit/b1
:l
@set/a"k=3*i^2*i^i,i+=1
@if %k%==0 goto g
@goto l

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,0wpis, pary utraty współrzędnych kwadratowych są zgodne z następującą regułą: jeśli nawet następna - bezpłatna 11liczba binarna jest równa, to dodaj w 3,2przeciwnym razie dodaj 2,1. Test na bezpłatną 11liczbę 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 pierwszych 11darmowych liczb binarnych i ich współrzędne:

   0     2,1  + 3,2 =  5,3
   1     5,3  + 2,1 =  7,4
  10     7,4  + 3,2 = 10,6
 100    10,6  + 3,2 = 13,8
 101    13,8  + 2,1 = 15,9
1000    15,9  + 3,2 = 18,11
1001    18,11 + 2,1 = 20,12
1010    20,12 + 3,2 = 23,14

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.

Neil
źródło