Tic-tac-toe with only crosses as quick as possible
Java, 14m 31s
This is essentially the program which I posted to OEIS after using it to extend the sequence, so it's a good reference for other people to beat. I've tweaked it to take the board size as the first command-line argument.
public class A181018 {
public static void main(String[] args) {
int n = Integer.parseInt(args[0]);
System.out.println(calc(n));
}
private static int calc(int n) {
if (n < 0) throw new IllegalArgumentException("n");
if (n < 3) return n * n;
// Dynamic programming approach: given two rows, we can enumerate the possible third row.
// sc[i + rows.length * j] is the greatest score achievable with a board ending in rows[i], rows[j].
int[] rows = buildRows(n);
byte[] sc = new byte[rows.length * rows.length];
for (int j = 0, k = 0; j < rows.length; j++) {
int qsc = Integer.bitCount(rows[j]);
for (int i = 0; i < rows.length; i++) sc[k++] = (byte)(qsc + Integer.bitCount(rows[i]));
}
int max = 0;
for (int h = 2; h < n; h++) {
byte[] nsc = new byte[rows.length * rows.length];
for (int i = 0; i < rows.length; i++) {
int p = rows[i];
for (int j = 0; j < rows.length; j++) {
int q = rows[j];
// The rows which follow p,q cannot intersect with a certain mask.
int mask = (p & q) | ((p << 2) & (q << 1)) | ((p >> 2) & (q >> 1));
for (int k = 0; k < rows.length; k++) {
int r = rows[k];
if ((r & mask) != 0) continue;
int pqrsc = (sc[i + rows.length * j] & 0xff) + Integer.bitCount(r);
int off = j + rows.length * k;
if (pqrsc > nsc[off]) nsc[off] = (byte)pqrsc;
if (pqrsc > max) max = pqrsc;
}
}
}
sc = nsc;
}
return max;
}
private static int[] buildRows(int n) {
// Array length is a tribonacci number.
int c = 1;
for (int a = 0, b = 1, i = 0; i < n; i++) c = a + (a = b) + (b = c);
int[] rows = new int[c];
int i = 0, j = 1, val;
while ((val = rows[i]) < (1 << (n - 1))) {
if (val > 0) rows[j++] = val * 2;
if ((val & 3) != 3) rows[j++] = val * 2 + 1;
i++;
}
return rows;
}
}
Save to A181018.java; compile as javac A181018.java; run as java A181018 13. On my computer it takes about 20 minutes to execute for this input. It would probably be worth parallelising it.
C++11, 28s
This also uses a dynamic programming approach based on rows. It took 28 seconds to run with argument 13 for me. My favorite trick is the next function which uses some bit bashing for finding the lexicographically next row arrangement satisfying a mask and the no-3-in-a-row rule.
Instructions
- Install the latest MinGW-w64 with SEH and Posix threads
- Compile the program with
g++ -std=c++11 -march=native -O3 <filename>.cpp -o <executable name> - Run with
<executable name> <n>
#include <vector>
#include <stddef.h>
#include <iostream>
#include <string>
#ifdef _MSC_VER
#include <intrin.h>
#define popcount32 _mm_popcnt_u32
#else
#define popcount32 __builtin_popcount
#endif
using std::vector;
using row = uint32_t;
using xcount = uint8_t;
uint16_t rev16(uint16_t x) { // slow
static const uint8_t revbyte[] {0,128,64,192,32,160,96,224,16,144,80,208,48,176,112,240,8,136,72,200,40,168,104,232,24,152,88,216,56,184,120,248,4,132,68,196,36,164,100,228,20,148,84,212,52,180,116,244,12,140,76,204,44,172,108,236,28,156,92,220,60,188,124,252,2,130,66,194,34,162,98,226,18,146,82,210,50,178,114,242,10,138,74,202,42,170,106,234,26,154,90,218,58,186,122,250,6,134,70,198,38,166,102,230,22,150,86,214,54,182,118,246,14,142,78,206,46,174,110,238,30,158,94,222,62,190,126,254,1,129,65,193,33,161,97,225,17,145,81,209,49,177,113,241,9,137,73,201,41,169,105,233,25,153,89,217,57,185,121,249,5,133,69,197,37,165,101,229,21,149,85,213,53,181,117,245,13,141,77,205,45,173,109,237,29,157,93,221,61,189,125,253,3,131,67,195,35,163,99,227,19,147,83,211,51,179,115,243,11,139,75,203,43,171,107,235,27,155,91,219,59,187,123,251,7,135,71,199,39,167,103,231,23,151,87,215,55,183,119,247,15,143,79,207,47,175,111,239,31,159,95,223,63,191,127,255};
return uint16_t(revbyte[x >> 8]) | uint16_t(revbyte[x & 0xFF]) << 8;
}
// returns the next number after r that does not overlap the mask or have three 1's in a row
row next(row r, uint32_t m) {
m |= r >> 1 & r >> 2;
uint32_t x = (r | m) + 1;
uint32_t carry = x & -x;
return (r | carry) & -carry;
}
template<typename T, typename U> void maxequals(T& m, U v) {
if (v > m)
m = v;
}
struct tictac {
const int n;
vector<row> rows;
size_t nonpal, nrows_c;
vector<int> irow;
vector<row> revrows;
tictac(int n) : n(n) { }
row reverse(row r) {
return rev16(r) >> (16 - n);
}
vector<int> sols_1row() {
vector<int> v(1 << n);
for (uint32_t m = 0; !(m >> n); m++) {
auto m2 = m;
int n0 = 0;
int score = 0;
for (int i = n; i--; m2 >>= 1) {
if (m2 & 1) {
n0 = 0;
} else {
if (++n0 % 3)
score++;
}
}
v[m] = score;
}
return v;
}
void gen_rows() {
vector<row> pals;
for (row r = 0; !(r >> n); r = next(r, 0)) {
row rrev = reverse(r);
if (r < rrev) {
rows.push_back(r);
} else if (r == rrev) {
pals.push_back(r);
}
}
nonpal = rows.size();
for (row r : pals) {
rows.push_back(r);
}
nrows_c = rows.size();
for (int i = 0; i < nonpal; i++) {
rows.push_back(reverse(rows[i]));
}
irow.resize(1 << n);
for (int i = 0; i < rows.size(); i++) {
irow[rows[i]] = i;
}
revrows.resize(1 << n);
for (row r = 0; !(r >> n); r++) {
revrows[r] = reverse(r);
}
}
// find banned locations for 1's given 2 above rows
uint32_t mask(row a, row b) {
return ((a & b) | (a >> 1 & b) >> 1 | (a << 1 & b) << 1) /*& ((1 << n) - 1)*/;
}
int calc() {
if (n < 3) {
return n * n;
}
gen_rows();
int tdim = n < 5 ? n : (n + 3) / 2;
size_t nrows = rows.size();
xcount* t = new xcount[2 * nrows * nrows_c]{};
#define tb(nr, i, j) t[nrows * (nrows_c * ((nr) & 1) + (i)) + (j)]
// find optimal solutions given 2 rows for n x k grids where 3 <= k <= ceil(n/2) + 1
{
auto s1 = sols_1row();
for (int i = 0; i < nrows_c; i++) {
row a = rows[i];
for (int j = 0; j < nrows; j++) {
row b = rows[j];
uint32_t m = mask(b, a) & ~(1 << n);
tb(3, i, j) = s1[m] + popcount32(a << 16 | b);
}
}
}
for (int r = 4; r <= tdim; r++) {
for (int i = 0; i < nrows_c; i++) {
row a = rows[i];
for (int j = 0; j < nrows; j++) {
row b = rows[j];
bool rev = j >= nrows_c;
auto cj = rev ? j - nrows_c : j;
uint32_t m = mask(a, b);
for (row c = 0; !(c >> n); c = next(c, m)) {
row cc = rev ? revrows[c] : c;
int count = tb(r - 1, i, j) + popcount32(c);
maxequals(tb(r, cj, irow[cc]), count);
}
}
}
}
int ans = 0;
if (tdim == n) { // small sizes
for (int i = 0; i < nrows_c; i++) {
for (int j = 0; j < nrows; j++) {
maxequals(ans, tb(n, i, j));
}
}
} else {
int tdim2 = n + 2 - tdim;
// get final answer by joining two halves' solutions down the middle
for (int i = 0; i < nrows_c; i++) {
int apc = popcount32(rows[i]);
for (int j = 0; j < nrows; j++) {
row b = rows[j];
int top = tb(tdim2, i, j);
int bottom = j < nrows_c ? tb(tdim, j, i) : tb(tdim, j - nrows_c, i < nonpal ? i + nrows_c : i);
maxequals(ans, top + bottom - apc - popcount32(b));
}
}
}
delete[] t;
return ans;
}
};
int main(int argc, char** argv) {
int n;
if (argc < 2 || (n = std::stoi(argv[1])) < 0 || n > 16) {
return 1;
}
std::cout << tictac{ n }.calc() << '\n';
return 0;
}