Kółko i krzyżyk z tylko krzyżami tak szybko, jak to możliwe

10

Zgodnie z prośbą Luke'a i dodatkiem Petera Taylora do tego wyzwania.

Wprowadzenie

Wszyscy znają grę w kółko i krzyżyk, ale w tym wyzwaniu wprowadzimy mały zwrot akcji. Będziemy używać tylko krzyży . Pierwsza osoba, która stawia trzy krzyże z rzędu, przegrywa. Ciekawym faktem jest to, że maksymalna liczba krzyży, zanim ktoś straci, wynosi 6 :

X X -
X - X
- X X

Oznacza to, że dla planszy 3 x 3 maksymalna kwota wynosi 6 . Więc dla N = 3 musimy wyprowadzić 6.

Kolejny przykład, dla N = 4 lub płyty 4 x 4:

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

To optymalne rozwiązanie, widać, że maksymalna liczba krzyży wynosi 9 . Optymalne rozwiązanie dla płyty 12 x 12 to:

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

Daje to 74 .

Zadanie

Twoim zadaniem jest jak najszybsze obliczenie wyników. Uruchomię twój kod na przypadku testowym 13. Zostanie to wykonane 5 razy, a następnie zostanie pobrana średnia z czasów pracy. To twój końcowy wynik. Im niższy, tym lepiej.

Przypadki testowe

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

Więcej informacji można znaleźć na https://oeis.org/A181018 .

Zasady

  • Jest to , więc najszybsze zgłoszenie wygrywa!
  • Musisz podać pełny program .
  • Podaj także, jak mam uruchomić program. Nie znam wszystkich języków programowania i sposobu ich działania, dlatego potrzebuję tutaj trochę pomocy.
  • Oczywiście Twój kod musi obliczyć poprawny wynik dla każdego przypadku testowego.

Zgłoszenia:

  • feersum (C ++ 11): 28s
  • Peter Taylor (Java): 14m 31s
Adnan
źródło
Czy nie jest to tylko duplikat drugiego pytania, o ile wiem, że właśnie zmieniłeś warunki wygranej?
Blue
1
@muddyfish Chociaż samo wyzwanie wygląda tak samo, mogę zapewnić, że podejście do tego wyzwania różni się bardzo od mojego innego wyzwania.
Adnan
3
@muddyfish Odpowiednia meta dyskusja. „Zmiana warunków wygranej” może być istotną zmianą dla wyzwania. Chociaż nie ma sensu umieszczać kodu golfa , najszybszego algorytmu i najszybszego kodu dla każdego możliwego wyzwania, istnieją jednak przypadki, w których badanie problemu z dwóch stron może wnieść znaczną wartość do strony. Myślę, że to taki przypadek.
Martin Ender
1
Cudowne wyzwanie! (+1)

Odpowiedzi:

5

C ++ 11, 28s

Wykorzystuje to także dynamiczne podejście programistyczne oparte na wierszach. Uruchomienie argumentu 13 zajęło mi 28 sekund. Moją ulubioną sztuczką jest nextfunkcja, która używa nieco bashowania w celu znalezienia leksykograficznie uporządkowanego następnego wiersza spełniającego maskę i reguły „3 w jednym rzędzie”.

Instrukcje

  1. Zainstaluj najnowszą wersję MinGW-w64 z gwintami SEH i Posix
  2. Skompiluj program za pomocą g++ -std=c++11 -march=native -O3 <filename>.cpp -o <executable name>
  3. Biegnij z <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
źródło
7

Java, 14m 31s

Jest to zasadniczo program, który wysłałem do OEIS po użyciu go do przedłużenia sekwencji, więc jest to dobre odniesienie dla innych osób do pokonania. Poprawiłem go tak, aby przyjmował rozmiar tablicy jako pierwszy argument wiersza poleceń.

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

Zapisz do A181018.java; skompiluj jako javac A181018.java; uruchomić jako java A181018 13. Na moim komputerze wykonanie tego wejścia zajmuje około 20 minut. Prawdopodobnie warto by to zrównoważyć.

Peter Taylor
źródło
Jak długo go używasz? Rozumiem, że nadal dodajesz warunki do OEIS.
mbomb007
1
@ mbomb007, wciąż go nie uruchamiam. Jak można stwierdzić po datach OEIS, bieganie trwało kilka dni n=16; Ekstrapolowałem, że zajmie to około miesiąca n=17, więc nie próbowałem tego uruchomić. Wykorzystanie pamięci stało się również poważnym utrapieniem. (PS Obecnie używam 2 z 4 rdzeni do wyzwania programistycznego niezwiązanego z PPCG: azspcs.com/Contest/Tetrahedra/Standings )
Peter Taylor