Selon la demande de Luke et l'ajout de Peter Taylor à ce défi.

introduction

Tout le monde connaît le jeu tic-tac-toe, mais dans ce défi, nous allons introduire un petit twist. Nous n'utiliserons que des croix . La première personne qui place trois croix d'affilée perd. Un fait intéressant est que le nombre maximum de croix avant que quelqu'un ne perde, est égal à 6 :

X X -
X - X
- X X

Cela signifie que pour une carte 3 x 3, le montant maximum est de 6 . Donc, pour N = 3, nous devons produire 6.

Un autre exemple, pour N = 4, ou une carte 4 x 4:

X X - X
X X - X
- - - -
X X - X

Ceci est une solution optimale, vous pouvez voir que le nombre maximum de croix est égal à 9 . Une solution optimale pour une carte 12 x 12 est:

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

Il en résulte 74 .

La tâche

Votre tâche consiste à calculer les résultats le plus rapidement possible. Je vais exécuter votre code sur le cas de test 13. Cela sera fait 5 fois, puis la moyenne des temps d'exécution est prise. C'est votre score final. Plus c'est bas, mieux c'est.

Cas de test

N     Output
1       1
2       4
3       6
4       9
5       16
6       20
7       26
8       36
9       42
10      52
11      64
12      74
13      86
14      100
15      114

Plus d'informations peuvent être trouvées sur https://oeis.org/A181018 .

Règles

• C'est le code le plus rapide, donc la soumission la plus rapide gagne!
• Vous devez fournir un programme complet .
• Veuillez également indiquer comment je dois exécuter le programme. Je ne connais pas tous les langages de programmation et leur fonctionnement, j'ai donc besoin d'un peu d'aide ici.
• Bien sûr, votre code doit calculer le résultat correct pour chaque scénario de test.

Soumissions:

• feersum (C ++ 11): 28s
• Peter Taylor (Java): 14 min 31 s

C ++ 11, 28s

Cela utilise également une approche de programmation dynamique basée sur des lignes. Il m'a fallu 28 secondes pour exécuter l'argument 13 pour moi. Mon astuce préférée est la nextfonction qui utilise un peu de dénigrement pour trouver l'arrangement lexicographiquement suivant de la ligne satisfaisant un masque et la règle no-3-in-a-row.

Instructions

1. Installez le dernier MinGW-w64 avec les threads SEH et Posix
2. Compilez le programme avec g++ -std=c++11 -march=native -O3 <filename>.cpp -o <executable name>
3. Courir avec <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;
}

Java, 14m 31s

C'est essentiellement le programme que j'ai publié sur OEIS après l'avoir utilisé pour étendre la séquence, c'est donc une bonne référence pour les autres. Je l'ai modifié pour prendre la taille de la carte comme premier argument de ligne de commande.

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;
    }
}

Enregistrer dans A181018.java; compiler en tant que javac A181018.java; exécuter comme java A181018 13. Sur mon ordinateur, l'exécution de cette entrée prend environ 20 minutes. Il vaudrait probablement la peine de le paralléliser.