На шахматной доске есть игра Get Home . В этой игре есть одна фигура, которая перемещается обоими игроками по очереди. Есть несколько правил, как часть может быть перемещена. На ходу игрок должен сделать один из следующих ходов для положительного n .

• N пробелов

• n пробелов слева

• n пробелов вверх и влево (диагональ)

Игрок, который перемещает фигуру в верхний левый угол доски, выигрывает игру.

Теперь мы определим понятие проигрышного квадрата. В этом видео (откуда я понял) проигрышный квадрат определяется как квадрат, на котором любой игрок, начинающий свой ход, будет вынужден сделать ход, позволяющий противнику добиться победы. Простейшим примером проигрышного квадрата будет квадрат в (1,2). Часть в (1,2) может перемещаться в любое из следующих мест.

Все из которых имеют прямой путь к победе для следующего игрока.

Из этого также следует, что любой квадрат, который имеет путь одного хода к проигрышному квадрату, позволяет игроку, стартовавшему на этом поле, добиться победы. Это означает, что любой квадрат, который находится не на расстоянии одного шага от проигрышного квадрата, также является проигрышным квадратом.

Это подводит нас к этому довольно аккуратному определению проигрышного квадрата:

Потерянный квадрат - это квадрат, из которого ни один ход не может прийти на другой проигрышный квадрат, а (0,0) - проигрышный квадрат.

задача

По заданным координатам квадрата на шахматной доске произвольного размера определите, является ли он проигрышным квадратом. Выведите два значения, одно для потерянных квадратов и одно для других.

Это код-гольф, поэтому ответы будут оцениваться в байтах, причем меньше байтов будет лучше.

Тестовые случаи

Вот все проигрышные квадраты на обычной шахматной доске 8 на 8 (отмечены 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

Вот изображение доски 100 на 100 с потерянными квадратами, отмеченными черным (каждый квадрат - 2 на 2 пикселя).

Python 3 , 112 50 46 42 байта

^{-4 байта благодаря Джонатану Аллану !}

^{-2 байта благодаря xnor !}

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

Попробуйте онлайн!

На основе формулы для холодных позиций в игре Витоффа и внесения некоторых модификаций для получения явной формулы. Объяснение входящего, как только я закончу правильную методологию для получения формулы.

Желе , 8 байт

ạ/×ØpḞ⁼Ṃ

Попробуйте онлайн! или посмотрите верхний левый 60 на 60 как сетку .

Как?

Холодная позиция в игре Витоффа - проигрышная позиция. Координаты [n,m]дают положение , когда холодному n = floor(kφ) = floor(mφ) - mили m = floor(kφφ) = ceil(nφ) = n + kдля некоторого натурального числа, kи золотое сечение, φ. Первый имеет место, когда nменьше, чем m; последний, когда mменьше чем n(оба держатся в 0,0).

kТаким образом, абсолютная разница между nи mи если floor(abs(n-m)φ)=min(n,m)условие выполняется.

ạ/×Ø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?

JavaScript (ES6), 64 байта

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

Теперь я вижу, что это не самый лучший метод, но мне пришлось придумать его сам, потому что я потерял интернет вскоре после загрузки этой страницы. (Если бы не эти интернет-проблемы, выложили бы некоторое время назад ...)

В идеальном мире точность с плавающей точкой не была бы проблемой, и я мог бы сэкономить 9 байт:

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

Можно сохранить еще 6 байтов, если JS поддерживает цепочку сравнения Python:

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

Pyth, 39 байт

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

Я написал это с именованной функцией (ew) и очень лениво играл в гольф. Планируем сыграть в гольф сегодня вечером довольно много байтов

Попробуйте онлайн с моими собственными сгенерированными тестами, предназначенными для чередования True / False

Объяснение:

Диагонали матрицы решений имеют квадрат проигрыша в соответствии с последовательностью повторяющихся чисел в OEIS A005206 . От Lсквозной ;довольно проста польская нотация определить y(b)=b-y(y(b-1)).

Остальная часть объяснения следует

=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

Пакетный, 204 байта

@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

Возвращает через код выхода. Пояснение: поскольку в пакетном режиме используется только целочисленная арифметика, мне пришлось придумать чисто арифметическое решение. Исключая 0,0запись, пары теряющих квадратные координаты следуют следующему правилу: если следующее 11-свободное двоичное число является четным, то добавить добавить 3,2иначе 2,1. Проверка на наличие 11свободного двоичного числа заключается в том, что нет переносов, если его умножить на три, другими словами,(i*2)+i==(i*2)^i . Вот первые несколько 11свободных двоичных чисел и их координаты:

   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

и т.д. Таинственным образом этого правила достаточно, чтобы сделать последовательности дополнительными. Затем остается вычислить последовательность, пока она не достигнет большей координаты, и в этот момент мы можем определить, проигрывает ли квадрат.