Ist das ein Platz zum Verlieren?

19

Es gibt ein Spiel namens Get Home , das auf dem Schachbrett gespielt wird. In diesem Spiel gibt es eine einzelne Figur, die von beiden Spielern abwechselnd bewegt wird. Es gibt einige Regeln, wie das Teil bewegt werden kann. In einem Zug muss ein Spieler einen der folgenden Schritte ausführen, um ein positives n zu erhalten .

  • n Leerzeichen nach oben

  • n Leerzeichen nach links

  • n Felder nach oben und links (eine Diagonale)

Der Spieler, der die Figur in die obere linke Ecke des Bretts legt, gewinnt das Spiel.

Nun definieren wir das Konzept eines Verlustquadrats. In diesem Video (von dem ich die Idee hatte) wird ein Verlierquadrat als ein Quadrat definiert, auf dem jeder Spieler, der seinen Zug beginnt, einen Zug ausführen muss, damit sein Gegner einen Sieg erzwingen kann. Das einfachste Beispiel für ein Verlustquadrat wäre das Quadrat bei (1,2). Ein Teil von (1,2) kann an eine der folgenden Stellen verschoben werden.

Illustration

Alle haben einen direkten Weg zum Sieg für den nächsten Spieler.

Daraus folgt auch, dass jeder Spieler, der einen Ein-Zug-Weg zu einem verlierenden Feld hat, dem Spieler, der auf diesem Feld beginnt, einen Gewinn erzwingen kann. Dies bedeutet, dass jedes Quadrat, das sich nicht von einem verlierenden Quadrat entfernt, auch ein verlierendes Quadrat ist.

Dies bringt uns zu dieser ziemlich ordentlichen Definition eines Verlustquadrats:

Ein Verlustquadrat ist ein Quadrat, von dem aus keine Bewegung auf ein anderes Verlustquadrat gelangen kann, und (0,0) ist ein Verlustquadrat.

Aufgabe

Anhand der Koordinaten eines Quadrats auf einem beliebig großen Schachbrett können Sie feststellen, ob es sich um ein verlorenes Quadrat handelt. Geben Sie zwei Werte ein, um Quadrate zu verlieren, und einen für andere.

Dies ist daher werden die Antworten in Bytes bewertet, wobei weniger Bytes besser sind.

Testfälle

Hier sind alle Verlustquadrate auf einem regulären 8 x 8-Schachbrett (mit 0 markiert).

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

Hier ist ein Bild von einem 100 x 100-Brett mit schwarzen Verlustquadraten (jedes Quadrat ist 2 x 2 Pixel groß).

100 mal 100 Brett

Weizen-Assistent
quelle
2
Ich glaube nicht, dass es genug Testfälle gibt, um ein Muster zu finden. Ich glaube, ich sehe ein Muster, aber ich konnte es nicht sicher sagen. Ist 10, 7ein Platz zu verlieren? Ist 10, 8? Was ist 15, 11?
DJMcMayhem
1
@ WheatWizard Hast du etwas dagegen, das Bild ein bisschen größer zu machen?
Erik der Outgolfer
1
@ WheatWizard Ich meinte größere Pixel ... zB 5x5 Pixel anstelle von 1x1, möglicherweise etwas Gitter auch, wenn nicht zu hart (übrigens danke für die 100x100)
Erik der Outgolfer
2
Auch verwandt (optimale Bewegung zurückgeben oder signalisieren, dass die Position verliert).
Zgarb
1
Ich denke, es ist normal, Gleitkommaungenauigkeiten zuzulassen, um die Leistung auch bei beliebig großen Ganzzahlen zu beeinträchtigen ...
Jonathan Allan

Antworten:

8

Python 3 , 112 50 46 42 Bytes

-4 Bytes danke an Jonathan Allan !

-2 Bytes dank xnor !

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

Probieren Sie es online!

Basiert auf der Formel für kalte Positionen in Wythoffs Spiel und nimmt einige Änderungen vor, um eine explizite Formel zu erstellen. Erklärung eingehend, sobald ich eine korrekte Methode für die Ableitung der Formel tatsächlich beendet habe.

notjagan
quelle
Könnten Sie nicht ändern 0<=xzu x>0und speichern ein Byte oder zwei?
Jonathan Frech
@ JonathanFrech Es muss entweder sein <=oder >=um Position einzuschließen 0, 0.
Notjagan
Sie haben Recht, es kann nur ein Byte gespeichert werden.
Jonathan Frech
1
Ein Byte weniger mit einer anderen Implementierung desselben:lambda r,c:int(abs(r-c)*(5**.5+1)**2/4)==max(r,c)
Jonathan Allan
1
/2//1sieht genauso aus wie //2.
17.
5

Gelee , 8 Bytes

ạ/×ØpḞ⁼Ṃ

Probieren Sie es online! , oder sehen Sie links oben 60 mal 60 als Gitter .

Wie?

Eine kalte Position in Wythoffs Spiel ist eine verlorene Position. Die Koordinaten [n,m]geben eine kalte Stellung , wenn n = floor(kφ) = floor(mφ) - moder m = floor(kφφ) = ceil(nφ) = n + kfür eine natürliche Zahl, kund das goldene Verhältnis φ. Ersteres gilt, wenn nkleiner ist als m; Letzterer mist kleiner als n(beide halten an 0,0).

kist also der absolute Unterschied zwischen nund mund wenn floor(abs(n-m)φ)=min(n,m)die Bedingung erfüllt ist.

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

JavaScript (ES6), 64 Byte

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

Ich sehe jetzt, dass dies nicht die beste Technik ist, aber ich musste es mir selbst einfallen lassen, weil ich kurz nach dem Laden dieser Seite das Internet verloren habe. (Hätte vor einiger Zeit gepostet, wenn nicht für diese Internetprobleme ...)

In einer perfekten Welt wäre Float-Präzision kein Problem und ich könnte 9 Bytes einsparen:

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

6 weitere Bytes könnten eingespart werden, wenn JS Pythons Vergleichsverkettung unterstützt:

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

Pyth, 39 Bytes

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

Ich schrieb dies mit einer benannten Funktion (ew) und war extrem faul beim Golfen. Wir planen, heute Abend einige Bytes später Golf zu spielen

Probieren Sie es online aus, mit meinen selbst erstellten Tests, die Richtig / Falsch abwechseln sollen

Erläuterung:

Diagonalen der Lösungsmatrix haben ein Verlustquadrat gemäß der Folge von Wiederholungszahlen in OEIS A005206 . Von LAnfang an ;ist die polnische Notation ziemlich einfach zu definieren y(b)=b-y(y(b-1)).

Der Rest der Erklärung folgt

=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
quelle
0

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

Rückgabe über Exit-Code. Erklärung: Da Batch nur Ganzzahlarithmetik hat, musste ich eine rein arithmetische Lösung finden. Mit Ausnahme der 0,0Eingabe folgen die Paare von verlierenden Quadratkoordinaten der folgenden Regel: Wenn die nächste 11freie Binärzahl gerade ist, addieren Sie 3,2ansonsten addieren 2,1. Ein Test für eine 11-freie Binärzahl ist, wenn es keine Überträge gibt, wenn es mit drei multipliziert wird, mit anderen Worten, dass (i*2)+i==(i*2)^i. Hier sind die ersten paar 11-freien Binärzahlen und ihre Koordinaten:

   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. Mysteriöserweise reicht diese Regel aus, um die Sequenzen komplementär zu machen. Es bleibt dann die Sequenz zu berechnen, bis es die größere Koordinate erreicht, an welchem ​​Punkt wir bestimmen können, ob das Quadrat verliert.

Neil
quelle