Tic-Tac-Toe mit nur so schnellen Kreuzen wie möglich

10

Gemäß Lukes Bitte und Peter Taylors Hinzufügung zu dieser Herausforderung.

Einführung

Jeder kennt das Spiel Tic-Tac-Toe, aber bei dieser Herausforderung werden wir eine kleine Wendung einführen. Wir werden nur Kreuze verwenden . Die erste Person, die drei Kreuze hintereinander platziert, 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-Platine der maximale Betrag beträgt 6 . 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 von Kreuzen 9 beträgt . Eine optimale Lösung für eine 12 x 12-Platine 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

Ihre Aufgabe ist es, die Ergebnisse so schnell wie möglich zu berechnen. Ich werde Ihren Code für den Testfall ausführen13 . Dies wird 5 Mal durchgeführt und dann wird der Durchschnitt der Laufzeiten ermittelt. Das ist dein Endergebnis. Je niedriger, desto besser.

Testfälle

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

Weitere Informationen finden Sie unter https://oeis.org/A181018 .

Regeln

  • Dies ist der , also gewinnt die schnellste Einreichung!
  • Sie müssen ein vollständiges Programm bereitstellen .
  • Bitte geben Sie auch an, wie ich das Programm ausführen muss. Ich bin nicht mit allen Programmiersprachen vertraut und weiß nicht, wie sie funktionieren. Deshalb brauche ich hier ein bisschen Hilfe.
  • Natürlich muss Ihr Code für jeden Testfall das richtige Ergebnis berechnen .

Einsendungen:

  • Feersum (C ++ 11): 28s
  • Peter Taylor (Java): 14 m 31 s
Adnan
quelle
Verwandte und verwandte .
Adnan
Ist das nicht nur ein Betrug der zweiten Frage, soweit ich das beurteilen kann, haben Sie gerade die Gewinnbedingung geändert?
Blue
1
@muddyfish Obwohl die Herausforderung selbst gleich aussieht, kann ich Ihnen versichern, dass sich der Ansatz für diese Herausforderung stark von meiner anderen Herausforderung unterscheidet.
Adnan
3
@muddyfish Relevante Metadiskussion . "Nur die Gewinnbedingung ändern" kann eine wesentliche Änderung für eine Herausforderung sein. Während es nicht sinnvoll ist, für jede mögliche Herausforderung einen Code-Golf , einen schnellsten Algorithmus und einen schnellsten Code zu veröffentlichen, gibt es einige Fälle, in denen das Erforschen eines Problems aus zwei Blickwinkeln der Website viel Wert verleihen kann. Ich denke, das ist so ein Fall.
Martin Ender
1
Wunderbare Herausforderung! (+1)

Antworten:

5

C ++ 11, 28s

Dies verwendet auch einen dynamischen Programmieransatz, der auf Zeilen basiert. Es dauerte 28 Sekunden, bis ich mit Argument 13 lief. Mein Lieblingstrick ist die nextFunktion, die ein bisschen Bashing verwendet, um die lexikografisch nächste Zeilenanordnung zu finden, die eine Maske und die Regel Nr. 3 in einer Reihe erfüllt.

Anleitung

  1. Installieren Sie den neuesten MinGW-w64 mit SEH- und Posix-Threads
  2. Kompilieren Sie das Programm mit g++ -std=c++11 -march=native -O3 <filename>.cpp -o <executable name>
  3. Laufen Sie mit <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;
}
Feersum
quelle
7

Java, 14m 31s

Dies ist im Wesentlichen das Programm, das ich bei OEIS gepostet habe, nachdem ich es zum Erweitern der Sequenz verwendet habe. Es ist also eine gute Referenz für andere Leute, die es zu schlagen gilt. Ich habe es so angepasst, dass die Boardgröße als erstes Befehlszeilenargument verwendet wird.

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

Speichern unter A181018.java; kompilieren als javac A181018.java; laufen als java A181018 13. Auf meinem Computer dauert die Ausführung dieser Eingabe ungefähr 20 Minuten. Es wäre wahrscheinlich eine Parallelisierung wert.

Peter Taylor
quelle
Wie lange laufen Sie schon? Ich verstehe, Sie fügen dem OEIS immer noch Begriffe hinzu.
mbomb007
1
@ mbomb007, ich laufe es noch nicht. Wie Sie den OEIS-Daten entnehmen können, dauerte die Ausführung mehrere Tage n=16. Ich habe hochgerechnet, dass es ungefähr einen Monat dauern würde n=17, also habe ich nicht versucht, es dafür auszuführen. Die Speichernutzung wurde ebenfalls zu einem großen Ärgernis. (PS Ich verwende derzeit 2 meiner 4 Kerne für eine Nicht-PPCG-Programmierherausforderung: azspcs.com/Contest/Tetrahedra/Standings )
Peter Taylor