Einführung
Jeder kennt das Tic-Tac-Toe-Spiel, aber in dieser Herausforderung werden wir eine kleine Wendung einführen. Wir werden nur Kreuze verwenden . Die erste Person, die drei Kreuze hintereinander setzt, verliert. Eine interessante Tatsache ist, dass die maximale Anzahl an Kreuzen, bevor jemand verliert, gleich 6 ist :
X X -
X - X
- X X
Das bedeutet, dass für eine 3 x 3-Karte die maximale Anzahl 6 beträgt . Für N = 3 müssen wir also 6 ausgeben.
Ein weiteres Beispiel für N = 4 oder eine 4 x 4-Karte:
X X - X
X X - X
- - - -
X X - X
Dies ist eine optimale Lösung, Sie können sehen, dass die maximale Anzahl der Kreuze gleich 9 ist . Eine optimale Lösung für ein 12 x 12-Board ist:
X - X - X - X X - X X -
X X - X X - - - X X - X
- X - X - X X - - - X X
X - - - X X - X X - X -
- X X - - - X - - - - X
X X - X X - X - X X - -
- - X X - X - X X - X X
X - - - - X - - - X X -
- X - X X - X X - - - X
X X - - - X X - X - X -
X - X X - - - X X - X X
- X X - X X - X - X - X
Dies ergibt 74 .
Die Aufgabe
Die Aufgabe ist einfach: Geben Sie bei einer Ganzzahl größer als 0 die maximale Anzahl von Kreuzen aus, die platziert werden können, ohne dass drei X in einer Zeile, Spalte oder Diagonale benachbart sind.
Testfälle
N Output
1 1
2 4
3 6
4 9
5 16
6 20
7 26
8 36
9 42
Weitere Informationen finden Sie unter https://oeis.org/A181018 .
Regeln
- Das ist Code-Golf , also gewinnt die Einsendung mit der geringsten Anzahl von Bytes!
- Sie können eine Funktion oder ein Programm bereitstellen.
Antworten:
Pyth,
575149 BytesWie bei der CJam-Lösung von @ PeterTaylor handelt es sich um Brute-Force-Lösung, die in O-Zeit (n 2 2 n 2 ) ausgeführt wird. Der Online-Dolmetscher ist für n = 4 nicht innerhalb einer Minute fertig.
Probieren Sie es hier für N <4.
Probieren Sie die Diagonalen-Funktion .
quelle
CJam (
5856 Bytes)Das ist unglaublich langsam und verbraucht viel Speicher, aber das ist Code-Golf für Sie.
Präparation
quelle
O(n a^n)
woa ~= 5.518
.C,
460456410407362351318 BytesDas ist eine wirklich schlechte Antwort. Es ist ein unglaublich langsamer Brute-Force-Ansatz.
Ich versuche, ein bisschen mehr Golf zu spielen, indem ich diefor
Loops kombiniere .Testfälle
Ungolfed
Bearbeiten: Deklarieren Sie int-Variablen als nicht verwendete Parameter. y-Koordinate entfernen, nur Index verwenden; Verschieben Sie die Variable in die Parameterliste und nicht in die globale Liste. Korrigieren Sie unnötige Parameter, die an übergeben wurden
s()
. kombiniere für Schleifen, entferne unnötige Klammern; ersetzen&&
mit*
,||
mit+
; Makro-ify die 3-in-eine-Reihe-Prüfungquelle
#define d(x,y)b[x]*b[x+y]*b[x+y+y]
; durch den Beginn der Wechsels
zus(i,m){for(m=n-2;
und ersetzt alle Instanzenn-2
; und durch Ändernb[x]++
zub[x++]++
und dann ersetztx==n*n-1
mitx==n*n
,x+1
mitx
, undx
mitx-1
.C 263
264 283 309Bearbeiten Ein paar Bytes gespart dank @Peter Taylor - weniger als ich gehofft hatte. Dann 2 Bytes, um etwas mehr Speicher zuzuweisen, jetzt kann ich es mit einer größeren Größe versuchen, aber es wird sehr zeitaufwendig.
Hinweis Beim Hinzufügen der Erklärung habe ich festgestellt, dass ich Bytes verschwenden muss, um das Raster im R-Array zu halten - damit Sie die gefundene Lösung sehen können ... für diese Herausforderung ist sie nicht erforderlich !!
Ich habe es in der Golfversion entfernt
Ein Golf-C-Programm, das tatsächlich die Antwort für n = 1..10 in angemessener Zeit finden kann.
Mein Test:
Weniger golfen und versuchen zu erklären
quelle
buildRows
Methode portieren. Vielleicht bis zu 20, wennfor(scanf("%d",&n);(v=2*V[i++])<1<<n;v%8<6&&V[++j]=v+1)v&&V[++j]=v;
es gültig ist. (Ich habe momentan keinen Zugriff auf einen C-Compiler).999
bedeutet, dass Sie diesen Teil ignorieren möchten. Obwohl vielleicht sollte man es wirklich nicht hartcodieren, damit man prinzipiell größere Eingaben als 11 oder 12 angehen kann.Ruby, 263 Bytes
Dies ist auch eine Brute-Force-Lösung und hat dieselben Probleme wie die C-Antwort von Cole Cameron, ist aber noch langsamer, da dies rubinrot und nicht C ist. Aber hey, es ist kürzer.
Testfälle
Ungolfed
quelle
Haskell, 143 Bytes
In mancher Hinsicht wird das nicht gemacht, aber ich hatte Spaß, und so geht es weiter:
Hier ist der Code:
quelle