Tic-tac-toe dengan hanya memotong secepat mungkin

10

Sesuai permintaan Luke dan penambahan Peter Taylor untuk tantangan ini.

pengantar

Semua orang tahu permainan tic-tac-toe, tetapi dalam tantangan ini, kami akan memperkenalkan sedikit twist. Kami hanya akan menggunakan salib . Orang pertama yang menempatkan tiga umpan silang berturut-turut kalah. Fakta yang menarik adalah bahwa jumlah maksimum salib sebelum seseorang kalah, sama dengan 6 :

X X -
X - X
- X X

Itu berarti bahwa untuk papan 3 x 3, jumlah maksimum adalah 6 . Jadi untuk N = 3, kita perlu output 6.

Contoh lain, untuk N = 4, atau papan 4 x 4:

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

Ini adalah solusi optimal, Anda dapat melihat bahwa jumlah maksimum salib sama dengan 9 . Solusi optimal untuk papan 12 x 12 adalah:

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

Ini menghasilkan 74 .

Tugas

Tugas Anda adalah menghitung hasilnya secepat mungkin. Saya akan menjalankan kode Anda pada test case 13. Ini akan dilakukan 5 kali dan kemudian rata-rata diambil dari run time. Itu adalah skor akhir Anda. Semakin rendah, semakin baik.

Uji kasus

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

Informasi lebih lanjut dapat ditemukan di https://oeis.org/A181018 .

Aturan

  • Ini adalah , jadi pengiriman tercepat menang!
  • Anda harus menyediakan program lengkap .
  • Harap berikan juga bagaimana saya harus menjalankan program. Saya tidak terbiasa dengan semua bahasa pemrograman dan bagaimana mereka bekerja, jadi saya perlu sedikit bantuan di sini.
  • Tentu saja, kode Anda perlu menghitung hasil yang benar untuk setiap kasus uji.

Pengajuan:

  • feersum (C ++ 11): 28s
  • Peter Taylor (Jawa): 14m 31s
Adnan
sumber
Terkait dan terkait .
Adnan
Bukankah ini hanya sebuah dupe dari pertanyaan kedua sejauh yang saya tahu, Anda baru saja mengubah kondisi kemenangan?
Biru
1
@uddyfish Meskipun tantangannya sendiri terlihat sama, saya dapat memastikan Anda bahwa pendekatan untuk tantangan ini sangat berbeda dari tantangan saya yang lain.
Adnan
3
@muddyfish Diskusi meta yang relevan. "Hanya mengubah kondisi kemenangan" bisa menjadi perubahan besar untuk sebuah tantangan. Meskipun tidak masuk akal untuk memposting kode-golf , algoritme tercepat, dan kode tercepat untuk setiap tantangan yang mungkin, ada beberapa kasus, di mana menjelajahi masalah dari dua sudut dapat menambah banyak nilai pada situs. Saya pikir ini adalah kasus seperti itu.
Martin Ender
1
Tantangan yang luar biasa! (+1)

Jawaban:

5

C ++ 11, 28s

Ini juga menggunakan pendekatan pemrograman dinamis berdasarkan baris. Butuh 28 detik untuk menjalankan argumen 13 untuk saya. Trik favorit saya adalah nextfungsi yang menggunakan sedikit bashing untuk menemukan pengaturan baris leksikografis berikutnya yang memuaskan topeng dan aturan no-3-in-a-row.

Instruksi

  1. Instal MinGW-w64 terbaru dengan utas SEH dan Posix
  2. Kompilasi program dengan g++ -std=c++11 -march=native -O3 <filename>.cpp -o <executable name>
  3. Jalankan dengan <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
sumber
7

Java, 14m 31s

Ini pada dasarnya adalah program yang saya posting ke OEIS setelah menggunakannya untuk memperpanjang urutan, jadi ini adalah referensi yang baik untuk dikalahkan oleh orang lain. Saya telah men-tweak untuk mengambil ukuran papan sebagai argumen baris perintah pertama.

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

Simpan ke A181018.java; kompilasi sebagai javac A181018.java; jalankan sebagai java A181018 13. Di komputer saya, dibutuhkan sekitar 20 menit untuk menjalankan input ini. Mungkin akan layak untuk diparalelkan.

Peter Taylor
sumber
Berapa lama Anda menjalankannya? Anda masih menambahkan istilah ke OEIS, saya mengerti.
mbomb007
1
@ mbomb007, saya belum menjalankannya. Seperti yang Anda ketahui dari tanggal OEIS, butuh beberapa hari untuk mencalonkan diri n=16; Saya memperkirakan bahwa itu akan memakan waktu sekitar satu bulan n=17, jadi saya tidak mencoba menjalankannya untuk itu. Penggunaan memori juga menjadi gangguan utama. (PS Saat ini saya menggunakan 2 dari 4 core saya untuk tantangan pemrograman non-PPCG: azspcs.com/Contest/Tetrahedra/Standings )
Peter Taylor