Is this a losing square?

Question

There is a game called Get Home that is played on the a chess board. In this game there is a single piece that is moved by both players in turns. There are some rules to how the piece can be moved. On a turn a player must make one of the following moves for positive n.

• n spaces up

• n spaces to the left

• n spaces up and to the left (a diagonal)

The player who moves the piece into the top left corner of the board wins the game.

Now we will define the concept of a losing square. In this video (from where I got the idea) a losing square is defined as a square on which, any player starting their turn will be forced to make a move allowing their opponent to force a win. The simplest example of a losing square would be the square at (1,2). A piece at (1,2) can move to any of the following places.

All of which have a direct path to victory for the next player.

It also follows that any square that has a one move path to a losing square allows the player starting on that square to force a win. This means that any square that is not one move away from a losing square is also a losing square.

This brings us to this rather neat definition of a losing square:

A losing square is a square from which no move can arrive on another losing square and (0,0) is a losing square.

Task

Given the coordinates of a square on an arbitrarily sized chess board determine if it is a losing square. Output two values one for losing squares and one for others.

This is code-golf so answers will be scored in bytes with less bytes being better.

Test Cases

Here are all the losing squares on a regular 8 by 8 chess board (marked with 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

Here is an image of a 100 by 100 board with losing squares marked in black (each square is 2 pixels by 2 pixels).

Answer 1

Python 3, 112 50 46 42 bytes

^{-4 bytes thanks to Jonathan Allan!}

^{-2 bytes thanks to xnor!}

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

Try it online!

Based on the formula for cold positions in Wythoff's game and making some modifications in order to produce an explicit formula. Explanation inbound once I actually finish a proper methodology for the derivation of the formula.

Answer 2

Jelly, 8 bytes

ạ/×ØpḞ⁼Ṃ

Try it online!, or see the top-left 60 by 60 as a grid.

How?

A cold position in Wythoff's game is a losing position. The coordinates [n,m] give a cold position when n = floor(kφ) = floor(mφ) - m or m = floor(kφφ) = ceil(nφ) = n + k for some natural number, k, and the golden ratio, φ. The former holds when n is less than m; the latter when m is less than n (both holding at 0,0).

k is thus the absolute difference between n and m and if floor(abs(n-m)φ)=min(n,m) the condition is met.

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

Answer 3

JavaScript (ES6), 64 bytes

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

I see now that this is not the best technique, but I had to come up with it myself because I lost internet shortly after loading this page. (Would've posted a while ago if not for these internet issues...)

In a perfect world, float precision wouldn't be an issue and I could save 9 bytes:

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

6 more bytes could be saved if JS supported Python's comparison chaining:

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

Answer 4

Pyth, 39 Bytes

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

I wrote this with a named function (ew), and was extremely lazy with golfing. Planning to golf off quite a number of bytes later tonight

Try it online, with my own generated tests, meant to alternate True / False

Explanation:

Diagonals of the solution matrix have a losing square according to the sequence of repeated numbers in OEIS A005206. From L through ; is pretty straightforward polish notation to define y(b)=b-y(y(b-1)).

The rest of the explanation follows

=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

Answer 5

Batch, 204 bytes

@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

Returns via exit code. Explanation: Since Batch only has integer arithmetic I had to devise a purely arithmetical solution. Excluding the 0,0 entry, the pairs of losing square coordinates follow the following rule: if the next 11-free binary number is even then add 3,2 otherwise add 2,1. A test for a 11-free binary number is if there are no carries when it is multiplied by three, in other words that (i*2)+i==(i*2)^i. Here are the first few 11-free binary numbers and their coordinates:

   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

etc. Mysteriously this rule suffices to make the sequences complementary. It then remains to compute the sequence until it reaches the larger coordinate, at which point we can determine whether the square is losing.