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 kode-golf , jadi pengiriman dengan jumlah byte paling sedikit menang!
- Anda dapat menyediakan fungsi atau program.
Jawaban:
Pyth,
575149 byteSeperti 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 .
sumber
CJam (
5856 byte)Ini sangat lambat dan menggunakan banyak memori, tapi itu kode-golf untuk Anda.
Pembedahan
sumber
O(n a^n)
situlaha ~= 5.518
.C,
460456410407362351318 byteIni jawaban yang sangat buruk. Ini adalah pendekatan brute force yang sangat lambat.
Saya mencoba untuk bermain golf sedikit lebih dengan menggabungkanfor
loop.Uji Kasus
Tidak disatukan
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-rowsumber
#define d(x,y)b[x]*b[x+y]*b[x+y+y]
; dengan mengubah awals
untuks(i,m){for(m=n-2;
dan mengganti semua contohn-2
; dan dengan mengubahb[x]++
keb[x++]++
dan kemudian menggantix==n*n-1
denganx==n*n
,x+1
denganx
, danx
denganx-1
.C 263
264 283 309Sunting 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.
Tes saya:
Kurang bermain golf dan berusaha menjelaskan
sumber
buildRows
metode saya ; mungkin sebanyak 20 jikafor(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).999
berarti 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.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.
Uji kasus
Tidak disatukan
sumber
Haskell, 143 byte
Dalam beberapa hal ini tidak dilakukan, tetapi saya bersenang-senang jadi begini:
Ini kodenya:
sumber