Tic-tac-toe dengan hanya umpan silang

32

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

Tugasnya sederhana, diberi bilangan bulat lebih besar dari 0, menampilkan jumlah maksimum persilangan yang dapat ditempatkan tanpa tiga X yang bersebelahan dalam garis di sepanjang baris, kolom, atau diagonal.

Uji kasus

N     Output
1     1
2     4
3     6
4     9
5     16
6     20
7     26
8     36
9     42

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

Aturan

  • Ini adalah , jadi pengiriman dengan jumlah byte paling sedikit menang!
  • Anda dapat menyediakan fungsi atau program.
Adnan
sumber
7
Jadi pertanyaannya adalah menggunakan formula di halaman yang Anda
tautkan
2
Posting terkait di Matematika.
AdmBorkBork
7
@nicael Sejauh yang saya bisa lihat, artikel OEIS hanya berisi batas bawah.
Martin Ender
6
Akan keren melihat ini sebagai tantangan kode tercepat.
Luke
4
Bukan solusi codegolf, tapi saya telah bermain dengan pemecah "visual" beberapa hari terakhir. Anda dapat mengakses jsfiddle di sini: jsfiddle.net/V92Gn/3899 Ia mencoba mencari solusi melalui mutasi acak. Itu tidak akan berhenti jika ia menemukan jawaban yang "benar", tetapi bisa mendapatkan banyak solusi yang benar lebih cepat daripada jawaban di bawah ini.
styletron

Jawaban:

11

Pyth, 57 51 49 byte

L.T.e+*]Ykbbsef!s.AMs.:R3ssmyBdsm_BdCBcTQsD^U2^Q2

Seperti solusi CJam @ PeterTaylor, ini brute-force, jadi itu berjalan dalam waktu O (n 2 2 n 2 ). Penerjemah online tidak selesai dalam satu menit untuk n = 4.

Cobalah di sini untuk N <4.

Coba fungsi diagonal .

L.T.e+*]Ykbb         y(b): diagonals of b (with some trailing [])
s e                  sum of the last (with most ones) array such that
f                    filter lambda T:
 ! s .AM                none of the 3 element sublists are all ones               
   s .:R3               all 3 element sublists
   s s                  flatten
   myBd                 add the diagonals
   sm_B d               add the vertically flipped array and transpose
   CBcTQ                array shaped into Q by Q square, and its transpose
 sD ^U2 ^Q2             all binary arrays of length Q^2 sorted by sum
lirtosiast
sumber
13

CJam ( 58 56 byte)

2q~:Xm*{7Yb#W=}:F,Xm*{ee{~0a@*\+}%zS*F},_Wf%:z&Mf*1fb:e>

Ini sangat lambat dan menggunakan banyak memori, tapi itu untuk Anda.

Pembedahan

2q~:Xm*        e# Read input into X and find Cartesian product {0,1}^X
{7Yb#W=}:F,    e# Filter with a predicate F which rejects arrays with a 111
Xm*            e# Take the Cartesian product possible_rows^X to get possible grids
{              e# Filter out grids with an anti-diagonal 111 by...
  ee{~0a@*\+}% e#   prepending [0]*i to the ith row
  zS*F         e#   transposing, joining on a non-1, and applying F
},
_Wf%:z         e# Copy the filtered arrays and map a 90 degree rotation
&              e# Intersect. The rotation maps horizontal to vertical and
               e# anti-diagonal to diagonal, so this gets down to valid grids
Mf*            e# Flatten each grid
1fb            e# Count its 1s
:e>            e# Select the maximum

Θ(aX)a1.83928675Θ(aX2)Θ(aX4)


O(Xa3X)

public class A181018 {
    public static void main(String[] args) {
        for (int i = 1; i < 14; i++) {
            System.out.format("%d:\t%d\n", i, calc(i));
        }
    }

    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;
    }
}
Peter Taylor
sumber
Di mana pendekatan efisien berjalan?
lirtosiast
@ ThomasKwa, oh, masih eksponensial, tapi saya pikir itu dibenarkan untuk menyebutnya efisien karena memungkinkan saya untuk memperpanjang urutan OEIS dengan 3 syarat.
Peter Taylor
@ ThomasKwa, tepatnya, di O(n a^n)situlah a ~= 5.518.
Peter Taylor
4

C, 460 456 410 407 362 351 318 byte

Ini jawaban yang sangat buruk. Ini adalah pendekatan brute force yang sangat lambat.Saya mencoba untuk bermain golf sedikit lebih dengan menggabungkan forloop.

#define r return
#define d(x,y)b[x]*b[x+y]*b[x+2*(y)]
n,*b;s(i){for(;i<n*(n-2);++i)if(d(i%(n-2)+i/(n-2)*n,1)+d(i,n)+(i%n<n-2&&d(i,n+1)+d(i+2,n-1)))r 1;r 0;}t(x,c,l,f){if(s(0))r 0;b[x]++;if(x==n*n-1)r c+!s(0);l=t(x+1,c+1);b[x]--;f=t(x+1,c);r l>f?l:f;}main(c,v)char**v;{n=atol(v[1]);b=calloc(n*n,4);printf("%d",t(0,0));}

Uji Kasus

$ ./a.out 1
1$ ./a.out 2
4$ ./a.out 3
6$ ./a.out 4
9$ ./a.out 5
16$

Tidak disatukan

n,*b; /* board size, board */

s(i) /* Is the board solved? */
{
    for(;i<n*(n-2);++i) /* Iterate through the board */
            if(b[i%(n-2)+i/(n-2)*n]&&b[i%(n-2)+i/(n-2)*n+1]&&b[i%(n-2)+i/(n-2)*n+2] /* Check for horizontal tic-tac-toe */
                    || b[i] && b[i+n] && b[i+2*n] /* Check for vertical tic-tac-toe */
                    || (i%n<n-2
                            && (b[i] &&b [i+n+1] && b[i+2*n+2] /* Check for diagonal tic-tac-toe */
                                    || b[i+2*n] && b[i+n+1] && b[i+2]))) /* Check for reverse diagonal tic-tac-toe */
                    return 1;
    return 0;
}

t(x,c,l,f) /* Try a move at the given index */
{
    if(s(0)) /* If board is solved, this is not a viable path */
            return 0;
    b[x]++;
    if(x==n*n-1) /* If we've reached the last square, return the count */
            return c+!s(0);

    /* Try it with the cross */
    l=t(x+1,c+1);

    /* And try it without */
    b[x]--;
    f=t(x+1,c);

    /* Return the better result of the two */
    return l>f?l:f;
}

main(c,v)
char**v;
{
    n=atol(v[1]); /* Get the board size */
    b=calloc(n*n,4); /* Allocate a board */
    printf("%d",t(0,0)); /* Print the result */
}

Sunting: Nyatakan variabel int sebagai parameter yang tidak digunakan; hapus koordinat y, cukup gunakan indeks; pindahkan variabel ke daftar parameter daripada global, perbaiki parameter yang tidak perlu diteruskan ke s(); menggabungkan untuk loop, menghapus tanda kurung yang tidak perlu; ganti &&dengan *, ||dengan +; makro-ify cek 3-in-a-row

Cole Cameron
sumber
Seberapa lambat?
Loovjo
@ Loojo mencoba di PC saya dengan beberapa perubahan kecil untuk membuatnya lebih cepat, 15 ms untuk n = 5, 12 detik untuk n = 6 (input +1, waktu * 800)!
edc65
@ edc65 Itulah pengalaman saya. Apa pun yang lebih besar dari 5 kinerjanya jauh lebih lambat. Saya tidak repot-repot mencoba input yang lebih besar dari 6.
Cole Cameron
Saya mulai dengan 7 ketika saya memposting komentar saya. Kita akan lihat
edc65
Anda dapat memeras beberapa karakter lagi dengan #define d(x,y)b[x]*b[x+y]*b[x+y+y]; dengan mengubah awal suntuk s(i,m){for(m=n-2;dan mengganti semua contoh n-2; dan dengan mengubah b[x]++ke b[x++]++dan kemudian mengganti x==n*n-1dengan x==n*n, x+1dengan x, dan xdengan x-1.
Peter Taylor
4

C 263 264 283 309

Sunting Beberapa byte yang disimpan thx @Peter Taylor - kurang dari yang saya harapkan. Kemudian 2 byte digunakan untuk mengalokasikan lebih banyak memori, sekarang saya dapat mencoba ukuran yang lebih besar, tetapi itu menjadi sangat memakan waktu.

Catatan Saat menambahkan penjelasan, saya menemukan bahwa saya membuang-buang byte yang menjaga grid dalam array R - sehingga Anda dapat melihat solusinya ditemukan ... itu tidak diminta untuk tantangan ini !!
Saya menghapusnya dalam versi golf

Program C golf yang benar-benar dapat menemukan jawaban untuk n = 1..10 dalam waktu yang wajar.

s,k,n,V[9999],B[9999],i,b;K(l,w,u,t,i){for(t=u&t|u*2&t*4|u/2&t/4,--l; i--;)V[i]&t||(b=B[i]+w,l?b+(n+2)/3*2*l>s&&K(l,b,V[i],u,k):b>s?s=b:0);}main(v){for(scanf("%d",&n);(v=V[i]*2)<1<<n;v%8<6?B[V[k]=v+1,k++]=b+1:0)V[k]=v,b=B[k++]=B[i++];K(n,0,0,0,k);printf("%d",s);}

Tes saya:

7 -> 26 dalam 10 detik
8 -> 36 dalam 18 detik
9 -> 42 dalam 1162 detik

Kurang bermain golf dan berusaha menjelaskan

#include <stdio.h>

int n, // the grid size
    s, // the result
    k, // the number of valid rows 
    V[9999], // the list of valid rows (0..to k-1) as bitmasks
    B[9999], // the list of 'weight' for each valid rows (number of set bits)
    R[99],  // the grid as an array of indices pointing to bitmask in V
    b,i; // int globals set to 0, to avoid int declaration inside functions

// recursive function to fill the grid
int K(
  int l, // number of rows filled so far == index of row to add
  int w, // number of crosses so far
  int u, // bit mask of the preceding line (V[r[l-1]])
  int t, // bit mask of the preceding preceding line (V[r[l-2]])
  int i) // the loop variables, init to k at each call, will go down to 0
{
  // build a bit mask to check the next line 
  // with the limit of 3 crosses we need to check the 2 preceding rows
  t = u&t | u*2 & t*4 | u/2 & t/4; 
  for (; i--; )// loop on the k possibile values in V
  {
    R[l] = i; // store current row in R
    b = B[i] + w; // new number of crosses if this row is accepted
    if ((V[i] & t) == 0) // check if there are not 3 adjacent crosses
      // then check if the score that we can reach from this point
      // adding the missing rows can eventually be greater
      // than the current max score stored in s
      if (b + (n + 2) / 3 * 2 * (n - l - 1) > s)
        if (l > n-2) // if at last row
          s = b > s ? b : s; // update the max score
        else  // not the last row
          K(l + 1, b, V[i], u, k); // recursive call, try to add another row
  }
}

int main(int j)
{
  scanf("%d", &n);

  // find all valid rows - not having more than 2 adjacent crosses
  // put valid rows in array V
  // for each valid row found, store the cross number in array B
  // the number of valid rows will be in k
  for (; i<1 << n; V[k] = i++, k += !b) // i is global and start at 0
    for (b = B[k] = 0, j = i; j; j /= 2) 
      b = ~(j | -8) ? b : 1, B[k] += j & 1;
  K(0,0,0,0,k); // call recursive function to find the max score
  printf("%d\n", s);
}
edc65
sumber
Ini pada dasarnya sama dengan program Java saya tetapi kedalaman-pertama daripada luas-pertama. Saya pikir Anda harus dapat menyimpan setidaknya selusin karakter dengan porting buildRowsmetode saya ; mungkin sebanyak 20 jika for(scanf("%d",&n);(v=2*V[i++])<1<<n;v%8<6&&V[++j]=v+1)v&&V[++j]=v;valid. (Saya tidak memiliki akses ke kompiler C sekarang).
Peter Taylor
1
@PeterTaylor aku akan melihatnya ... hanya kata tribonacci yang membuatku takut
edc65
Hard-coded Anda 999berarti Anda ingin mengabaikan bagian itu. Meskipun mungkin Anda harus benar-benar membuatnya bukan hard-kode, sehingga pada prinsipnya Anda dapat menangani input yang lebih besar dari 11 atau 12.
Peter Taylor
@ PeterTaylor akan bekerja dengan baik jika saya memiliki metode .bitCount di C untuk menghitung bit. Tetapi dalam fase awal itu saya cocok dengan hitungan bit dalam B, tidak hanya topeng bit di V
edc65
2

Ruby, 263 byte

Ini juga merupakan solusi brute force dan menghadapi masalah yang sama dengan jawaban C oleh Cole Cameron, tetapi bahkan lebih lambat karena ini ruby ​​dan bukan C. Tapi hei, ini lebih pendek.

c=->(b){b.transpose.all?{|a|/111/!~a*''}}
m=->(b,j=0){b[j/N][j%N]=1
x,*o=b.map.with_index,0
c[b]&&c[b.transpose]&&c[x.map{|a,i|o*(N-i)+a+o*i}]&&c[x.map{|a,i|o*i+a+o*(N-i)}]?(((j+1)...N*N).map{|i|m[b.map(&:dup),i]}.max||0)+1:0}
N=$*[0].to_i
p m[N.times.map{[0]*N}]

Uji kasus

$ ruby A181018.rb 1
1
$ ruby A181018.rb 2
4
$ ruby A181018.rb 3
6
$ ruby A181018.rb 4
9
$ ruby A181018.rb 5
16

Tidak disatukan

def check_columns(board)
  board.transpose.all? do |column|
    !column.join('').match(/111/)
  end
end

def check_if_unsolved(board)
  check_columns(board) && # check columns
    check_columns(board.transpose) && # check rows
    check_columns(board.map.with_index.map { |row, i| [0] * (N - i) + row + [0] * i }) && # check decending diagonals
    check_columns(board.map.with_index.map { |row, i| [0] * i + row + [0] * (N - i) }) # check ascending diagonals
end

def maximum_crosses_to_place(board, index=0)
  board[index / N][index % N] = 1 # set cross at index
  if check_if_unsolved(board)
    crosses = ((index + 1)...(N*N)).map do |i|
      maximum_crosses_to_place(board.map(&:dup), i)
    end
    maximum_crosses = crosses.max || 0
    maximum_crosses + 1
  else
    0
  end
end

N = ARGV[0].to_i
matrix_of_zeros = N.times.map{ [0]*N }

puts maximum_crosses_to_place(matrix_of_zeros)
Siim Liiser
sumber
1

Haskell, 143 byte

Dalam beberapa hal ini tidak dilakukan, tetapi saya bersenang-senang jadi begini:

  • Karena memeriksa pola "menang" horizontal mengembalikan tidak valid jika diterapkan pada baris yang berbeda, input N <3 mengembalikan 0
  • "Array" adalah bilangan bulat yang dibongkar menjadi bit, sehingga mudah dihitung
  • ((i! x) y) memberikan bit ke-x kali y, di mana indeks negatif mengembalikan 0 sehingga kisaran dapat konstan (tanpa batas memeriksa) dan kurung kurung lebih sedikit ketika dirantai
  • Karena batas tidak dicentang, ia memeriksa 81 * 4 = 324 pola untuk setiap kemungkinan maksimum, yang mengarah ke N = 3 mengambil laptop saya 9 detik dan N = 5 terlalu lama bagi saya untuk membiarkannya selesai
  • Logika Boolean pada 1/0 digunakan untuk T / F untuk menghemat ruang, misalnya (*) adalah &&, (1-x) adalah (bukan x), dll.
  • Karena memeriksa bilangan bulat alih-alih array, (div p1 L) == (div p2 L) diperlukan untuk memastikan pola tidak dicentang di baris yang berbeda, di mana L adalah panjang baris dan p1, p2 adalah posisi
  • Nilai maksimum yang mungkin adalah Berat Hamming-nya

Ini kodenya:

r=[0..81]
(%)=div
s=sum
i!x|i<0=(*0)|0<1=(*mod(x%(2^i))2)
f l=maximum[s[i!x$1-s[s[1#2,l#(l+l),(l+1)#(l+l+2),(1-l)#(2-l-l)]|p<-r,let  a#b=p!x$(p+a)!x$(p+b)!x$s[1|p%l==(p+mod b l)%l]]|i<-r]|x<-[0..2^l^2]]
Michael Klein
sumber