Apakah papan Tic-Tac-Toe ini valid?

48

Tantangan

Diberi papan tic-tac-toe dalam format apa pun, tentukan apakah itu valid atau tidak. Jika papan dapat menjadi hasil dari permainan tic-tac-toe, maka itu valid. Misalnya, forum ini valid:

XOX
OXO
XOX
Sebaliknya, forum ini tidak valid:

XXX
XXO
OOO

Memasukkan

  • Papan tic tac toe penuh (9/9) (hasilnya, bukan game).

Aturan

  • Format input harus dapat menggambarkan semua 512 papan input yang mungkin. Itu harus ditentukan, bersama dengan instruksi untuk membuatnya jika tidak jelas / tidak jelas. Anda harus menyatakan tanda-tanda papan secara individual.
  • Harus ada dua kemungkinan keluaran, satu untuk validitas dan satu untuk ketidakabsahan.
  • Anda dapat menganggap papan tidak memiliki tempat kosong.

Uji kasus

Sah:

XOX
OXO
XOX

XOX
XOX
OXO

XOO
OOX
OXX

OXO
XOX
OXO

Tidak valid:

XXX
XXX
XXX

OOO
OOO
OOO

XXX
OOO
XXX

OOO
OOX
XXX

XXO
OXO
OOX

Sedikit bantuan?

Papan dianggap sah (untuk tantangan ini) jika dan hanya jika dua syarat berikut berlaku:

  • Ada 5 X dan 4 O, atau 4 X dan 5 O. Misalnya,
    XXX
    OXO
    XXX
    dianggap tidak valid, karena ada 7 X dan 2 Os.
  • Hanya pemain dengan 5 nilai yang menang, atau tidak ada yang menang. Sebagai contoh,
    XXX
    OOO
    OOX
    dianggap tidak valid, karena baris Os atau baris Xs akan dibentuk terlebih dahulu. Kedua pemain tidak bisa mendapatkan giliran secara bersamaan.

Pemenang saat ini adalah ...

... jawaban Jelly ais523 , dengan 26 byte yang menakjubkan!

Erik the Outgolfer
sumber
2
Mungkin juga tambahkan test-case like O O O X O X X O X, untuk menunjukkan bahwa pemain yang sama mungkin memiliki baris horizontal dan vertikal.
smls
2
Anda harus menyatakan tanda-tanda papan secara individual. Saya tidak yakin untuk memahami bagian itu. Bisakah Anda memberikan contoh tandingan?
Arnauld
3
@Tim X memiliki 4 tanda.
Martin Ender
2
@Sparr "Hanya pemain dengan 5 nilai yang menang, atau tidak ada yang menang."
Martin Ender
2
@Kevin (Membalas komentar 1) Karena tidak ada papan 9/9 yang akan selesai jika pemain kedua (pemain dengan 4 nilai) menang.
Erik the Outgolfer

Jawaban:

11

Jelly , 26 byte

ṢŒrṪ4=$$Ðfx3ðœ-µẆm€6R¤;/µL

Cobalah online!

Format input sedikit tidak biasa; itu adalah string yang mewakili papan, tetapi dengan baris baru Windows (carriage return diikuti oleh baris baru). Sebagai contoh XXO\r\nOXO\r\nOOX,. (Sebenarnya, string padding dua karakter di antara garis berfungsi, tetapi baris baru Windows jauh lebih dapat dipertahankan daripada opsi lainnya.)

Ide dasarnya adalah kita mencari karakter yang muncul 4 kali dalam input, tetapi tidak memiliki tiga kejadian spasi secara merata dalam string asli. Dengan dua atau lebih karakter padding di antara garis-garis kisi 3 × 3, semua garis horizontal, vertikal, dan diagonal diberi spasi secara merata, tetapi tidak ada garis spasi merata lainnya yang dapat memiliki tiga elemen.

Penjelasan:

The ðdan µs adalah pemisah rantai , yang membagi program ke dalam beberapa bagian yang masing-masing independen. Saya telah menggantinya dengan spasi di bawah ini, untuk membuat semuanya lebih jelas.

ṢŒrṪ4=$$Ðfx3 œ- Ẇm€6R¤;/ L
Ṣ                           sorted version of the input
 Œr                         run-length-encode it
        Ðf                  keep only elements where
   Ṫ                        delete the last element, and it was
    4=                      equal to 4
      $$                    parse Ṫ4= as a group
          x3                repeat each element three times

                Ẇ           all sublists of the input
                 m€         take every nth element of each (€) sublist
                   6R       for each n in 1..6
                     ¤      parse 6R as a group
                      ;/    flatten one level (m€ creates a nested structure)

             œ-             multiset difference
                         L  length of that difference

Dengan kata lain, kami menemukan daftar karakter yang muncul tepat empat kali di input, dan membuat daftar yang terdiri dari tiga salinan dari masing-masing; kami menemukan daftar semua urutan yang ditempatkan secara merata di string asli; dan jika kita mengurangi yang kedua dari yang pertama, kita ingin hasilnya memiliki panjang 1 (yaitu seorang pemain bermain empat kali tetapi tidak menang). Perhatikan bahwa karena kita berada di kotak 3 × 3 dan setiap kotak penuh, mustahil bagi kedua pemain untuk bermain empat kali. Dalam Jelly, 1 benar, 0 adalah palsu, jadi kita tidak perlu melakukan hal khusus untuk mengubah daftar yang dihasilkan menjadi boolean. (Namun µLdiperlukan, karena jika tidak keduanya “XXX”dan “OOO”akan menjadi nilai output yang mungkin benar, dan pertanyaannya mengharuskan semua papan yang valid memberikan output yang sama.)

Greg Martin
sumber
3
Ini bisa dibaca.
pabrams
21

JavaScript (ES6), 88 87 byte

s=>(a=[...s]).sort()[5]-a[3]&[7,56,73,84,146,273,292,448].every(j=>j&i,i=`0b`+s^~-a[4])

Mengambil input sebagai string 9 0dan 1karakter dan mengembalikan 1untuk valid, 0untuk tidak valid. Kami mengurutkan karakter ke dalam urutan. Jika tiga karakter tengah sekarang sama maka papan tidak valid karena ada terlalu banyak bagian. Kalau tidak, kami mengubah papan asli menjadi biner, membalik bit jika ada lebih 0dari 1s. Pada titik ini papan valid jika 0tidak memiliki garis tiga, jadi kami cukup menguji semua delapan garis melalui array bitmask. Sunting: Disimpan 1 byte berkat @ETHproductions.

Neil
sumber
@ ETHproductions Ah, tentu saja, hasilnya hanya akan menjadi 0 atau 1 saja.
Neil
14

Python 3, 131 127 125 100 96 byte

Untuk pendekatan algoritmik yang berbeda (dan yang akan sangat cocok untuk bahasa golf multi-byte ini dengan kompresi bawaan), daripada menghitung apakah papan tersebut valid, mari kita memiliki angka 512-bit di mana setiap bit mewakili apakah atau tidak papan tertentu valid atau tidak, dan meneruskan nilai biner yang mewakili papan. Selanjutnya, karena simetri, bagian kedua tabel dapat dihilangkan, bersama dengan sekelompok nol:

def z(b):return int('agqozfx67wwye6rxr508ch2i8qicekpreqkap0725pk',36)<<24&1<<b+(b>255)*(511-b-b)

Nilai tes:

X X X
O X O
X X X

Diwakili sebagai nilai biner 0b111010111, dan fungsi mengembalikan nilai bukan nol jika papan valid.

Ken YN
sumber
Variabel antara yang dihapus untuk 4 byte lebih sedikit
Ken YN
Dua byte lebih sedikit karena a&(1<<b)tidak perlu tanda kurung.
Ken YN
Merobohkan 25 byte dengan menggunakan simetri dan satu lagi dengan menyingkat 24 bit nol terendah - pasti ada cara golf untuk melakukannya if b>255:b=511-b!
Ken YN
Menemukan cara bermain golf untuk melakukan if.
Ken YN
11

Batch, 140 byte

@set/aXXX=OOO=O=0
@for %%l in (%* %1%2%3 %1%4%7 %1%5%9 %2%5%8 %3%5%7 %3%6%9 %4%5%6 %7%8%9)do @set/a%%l+=1
@cmd/cset/a!XXX*!(O-=5)+!OOO*!~O

Mengambil input sebagai sembilan argumen baris perintah dan keluaran terpisah 1untuk valid dan 0tidak valid. Bekerja dengan melacak berapa kali ia melihat Ogaris ortogonal OOOatau XXX. Mudah Batch memungkinkan kita untuk melakukan bilangan bulat aritmatika secara tidak langsung, jadi kami tidak menambah %%ltetapi beberapa variabel sebagai gantinya (meskipun kami hanya tertarik pada tiga variabel yang disebutkan). Kami kemudian perlu menguji apakah Xbelum menang dan ada lima Os atau yang Obelum menang dan ada empat Os.

Neil
sumber
10

Mathematica, 82 75 byte

Terima kasih kepada Martin Ender karena telah menghemat 7 byte!

t=Total;3<(b=#~t~2)<6&&{t[c=If[b>4,1-#,#]],t/@c,Tr@c,Tr@Reverse@c}~FreeQ~3&

Fungsi tanpa nama mengambil daftar bersarang 3x3 dari 1s dan 0s sebagai input dan keluaran Trueatau False.

Menggunakan beberapa fleksibilitas Totalfungsi (di sini di-golf t): diberikan contoh array e = { {1,2,3} , {4,5,6} , {7,8,9} }, perintah ini t[e]menjumlahkan tiga vektor (di sini menghasilkan {12,15,18}); perintah ini t/@emerangkum setiap sublist secara individual (di sini menghasilkan {6,15,24}); dan perintah itu e~t~2merangkum semua sembilan elemen (di sini menghasilkan 45).

Jadi pertama-tama kita menguji, dengan 3<(b=#~t~2)<6, apakah jumlah total 1 adalah 4 atau 5; jika tidak kita keluar dengan False. Jika demikian, kita gunakan c=If[b>4,1-#,#]untuk memaksa ada empat 1, bukan lima. Kemudian kita menghitung jumlah kolom t[c], jumlah baris t/@c, jumlah diagonal utama Tr@c, dan jumlah diagonal yang berlawanan Tr@Reverse~c, dan digunakan ~FreeQ~3untuk memeriksa yang 3gagal muncul pada tingkat mana pun dalam jumlah yang dihitung tersebut.

Catatan samping yang mengasyikkan: tidak seperti kebanyakan penampilan di situs ini, di sini Trtidak digunakan untuk menjumlahkan daftar satu dimensi tetapi sebenarnya digunakan sebagaimana dirancang — untuk menghitung jejak matriks dua dimensi!

Greg Martin
sumber
6

Pyth - 36 byte

Saya memasukkan diagas dan menggunakan dua terner sebagai gantinya.

JsM+sCBQm@VdU3_BQ?q5KssQ*FJ?qK4!}3JZ

Test Suite

Maltysen
sumber
5

JavaScript (ES6), 101 byte

Mengambil input sebagai topeng biner 9-bit di mana X = 1dan O = 0(MSB = sel kiri atas, LSB = sel kanan bawah).

n=>[7,56,73,84,146,273,292,448,o=x=0].map((m,i)=>(c-=n>>i&1,m&n^m?m&n||o++:m&&x++),c=4)&&!(c|x&&~c|o)

Uji kasus

Arnauld
sumber
Saya tahu harus ada solusi bitwise (agak) sederhana. Kerja bagus
ETHproduk
5

Python 2, 158 132 109 92 91 123 byte

def v(b):f=sum(b,());w={x[0]for x in b+zip(*b)+[f[::4],f[-3:1:-2]]if len(set(x))==1};return sum(map(`b`.count,w))==len(w)*5

Input adalah daftar / tupel baris, masing-masing tiga tupel string, misalnya:
[('X', 'O', 'X'), ('O', 'X', 'O'), ('X', 'O', 'X')]

Menyimpan beberapa byte dengan mengabaikan diagonal per jawaban Maltysen, yang juga mempersingkat ekspresi berikut.

Terima kasih @vaultah untuk menyimpan 17 18 byte.

Memeriksa diagonal ternyata diperlukan, yang menghilangkan banyak penghematan di atas.

Coba di sini.

Penjelasan

def v(b):
  f=sum(b,())
  w={x[0]for x in b+zip(*b)+[f[::4],f[-3:1:-2]]if len(set(x))==1}
  return sum(map(`b`.count,w))==len(w)*5

fadalah input rata untuk memotong.
wberisi karakter dengan urutan kemenangan.
Hitung kemunculan setiap karakter yang menang, yang akan menjadi 0 jika wkosong atau 5 jika len(w)1. Jumlah 10 ketika keduanya memiliki urutan kemenangan tidak mungkin. Pemenang memiliki 5 berarti pecundang memiliki 4. Anda tidak dapat memiliki> 5 tanpa urutan kemenangan.

Jake Cobb
sumber
lambda b:len({x[0]for x in b+zip(*b)if len(set(x))==1})<2and set(map(b .count,'XO'))=={4,5}menyimpan beberapa byte.
vaultah
dan saya baru memperhatikan bahwa ...and{4,5}==set(map(b .count,'XO'))menyimpan satu byte lagi.
vaultah
Saya pikir ini salah menganggap contoh "Tidak Valid" terakhir dari pertanyaan sebagai valid, karena tidak memastikan bahwa pemenangnya adalah pemain dengan 5 nilai.
sml
@ smls Anda benar. Memeriksa kondisi itu membutuhkan banyak byte, mungkin bisa di-golf lebih lanjut.
Jake Cobb
5

R, 88 82 byte

x=scan();`if`(sum(x)%in%4:5,all(apply(combn(which(x==(sum(x)<5)),3),2,sum)!=15),F)

Semua kombinasi dari tiga bilangan bulat dari 1 hingga 9 yang berjumlah hingga 15 adalah baris / kolom / diagonal kotak yang ditunjukkan di bawah ini.

2 7 6
9 5 1
4 3 8

Fungsi mengambil input sebagai vektor boolean, T untuk "X", F untuk "O", yang merupakan representasi rata dari papan. NAMUN, ini disusun ulang sehingga indeks mereka sama dengan angka di dalam kotak, dalam urutan (2,7,6,9,5,1,4,3,8). Agar itu dapat dicapai dengan meratakan papan dengan cara normal, dan kemudian mengiris dengan c (6,1,8,7,5,3,2,9,4). Jadi ini

X O X
O X O
X O X

direpresentasikan sebagai:

c(T, F, T, F, T, F, T, F, T)[c(6,1,8,7,5,3,2,9,4)]

yang mana:

c(F, T, F, T, T, T, F, T, F)

Fungsi pertama menentukan apakah ada pemain dengan tepat empat tanda. Jika demikian, fungsi menggunakan fakta-hal-yang-menambahkan-ke-15 untuk menentukan apakah pemain itu memiliki tiga-dalam-baris (papan tidak valid jika pemain itu melakukannya).

Jika Anda ingin menggunakan papan yang rata secara konvensional sebagai input, kodenya akan terlihat seperti ini:

f=function(x)ifelse(sum(x)%in%4:5,all(apply(combn(c(2,7,6,9,5,1,4,3,8)[which(x==(sum(x)<5))],3),2,sum)!=15),F)

Saya baru dalam hal ini, saran akan sangat dihargai.

ixodesbeta
sumber
1
Simpan 2 byte jika Anda gunakan if()sebagai gantinya: f=function(x)jika (sum(x)%in%4:5,all(apply(combn(which(x==(sum(x)<5)),3),2,sum)!=15),F). Tidak diuji secara luas pikiran Anda. Backticks merusak kode, tapi itu backtick if backtick(.
Jonathan Carroll
1
Lebih baik; x=scan();jika (sum(x)%in%4:5,all(apply(combn(which(x==(sum(x)<5)),3),2,sum)!=15),F)dan masukan sebagai 1dan 0. 82 byte
Jonathan Carroll
3

JavaScript (ES6), 145 139 131 127 byte

s=>!(q="XO"[s.split`O`.length-5])|![...s].some((c,i)=>c==q&!/(.)(\1|..(\1|.(\1|.\1.).)..)\1/.test(s.slice(0,i)+0+s.slice(i+1)))

Input sebagai string yang dipisahkan oleh spasi, seperti "XOX OXO XOX". Output 1untuk papan tidak valid, 0untuk papan yang valid. Ini jelas bukan teknik terbaik, setidaknya tidak dengan JavaScript ...

Ini pada dasarnya memeriksa apakah kedua penahanan berikut:

  • Tepatnya ada 4 atau 5 Os, DAN
  • setidaknya ada satu dari 5 instance yang menciptakan game yang belum diputuskan ketika dihapus.

Regex adalah untuk memeriksa apakah suatu game telah diputuskan. Ini cocok dengan papan jika ada panjang berjalan tiga dari satu karakter dengan 0 (baris), 2 (diagonal kanan bawah), 3 (kolom), atau 4 karakter (diagonal kiri bawah) yang memisahkan masing-masing pasangan.

Cuplikan tes

Produksi ETH
sumber
2

Ruby, 104 99 91 byte

->x{[7,56,448,292,146,73,84,273].none?{|y|b=x.to_i 2;((a=x.count'1')==4?b:a==5?~b:7)&y==y}}

Format input: string biner dari 9 simbol (0s dan 1s) mewakili papan, misalnya test case pertama adalah 101010101. Pertama-tama konversikan ke nomor biner, periksa apakah popcount adalah 4 atau 5, jika 5 membalikkan angka sehingga kita selalu memiliki 4. Periksa apakah tiga dari mereka disejajarkan (masking dengan horisontal, vertikal, diagonal).

TL; DR : Return false jika pemain dengan 4 nilai menang, benar sebaliknya.

Terima kasih Jordan atas komentarnya,

Saya tidak dapat mereproduksi string UTF-8 yang akan menghemat byte lain.

GB
sumber
Anda bisa menggantinya .select{...}[0]dengan .find{...}.
Jordan
Dan Anda dapat menyimpan satu byte lagi dengan mengganti array angka dengan "8ǀĤITđ".unpack("U*")(jika ada sesuatu yang hilang dalam terjemahan, string adalah hasil dari memanggil pack("U*")array asli; itu 12 byte).
Jordan
bisa Anda gunakan any?sebagai pengganti none?, membalik output dan menyimpan seluruh byte seluruh?
Alexis Andersen
Saya sudah mencoba dengan satu? bukannya tidak? tapi kemudian aku butuh! untuk membalik output.
GB
1

Perl 6 , 103 99 byte

{my \c=%(.flat.Bag.invert)<5>;?all c,|(.[0]===c if [eq] $_ for |.flat[<0 4 8>,<2 4 6>],|$_,|.&zip)}

Lambda yang menerima daftar daftar suka (('X','O','X'), ('O','X','O'), ('X','O','X')), dan mengembalikan Bool.

Ini berfungsi seperti ini:

  1. Periksa tanda yang muncul tepat 5 kali, dan simpan di c. (Jika tidak ada tanda yang muncul tepat 5 kali, ini akan mengandung nilai falsy)
  2. Iterasi semua diagonal, baris, dan kolom, dan saring yang "menang" (yaitu yang ketiga hurufnya sama) .
  3. Periksa apakah citu benar, dan setiap baris yang menang adalah tipe c.
seseorang
sumber
1

PHP, 125 byte

for($p=$n=$argv[1];$p;$p/=2)$i+=$p&1;foreach([7,56,448,73,146,292,273,84]as$m)$n&$m^$m?$n&$m||$o++:$x++;echo!$x|!$o&&2>$i^=4;

Aku punya ide yang sama seperti Arnauld : papan ini berlaku jika ada 4 atau 5 bit menetapkan dan baik Xatau Oatau tidak ada yang memiliki beruntun (tapi tidak keduanya).

Untuk menghasilkan input dari bidang, ganti Xdengan 1dan Odengan 0, gabungkan baris dan konversi biner ke desimal, berikan sebagai argumen baris perintah.

cetakan 1untuk valid; output kosong untuk tidak valid. Jalankan dengan -r.

kerusakan

// count set bits
for($p=$n=$argv[1];$p;$p/=2)$i+=$p&1;
    /* ($p/=2 takes longer than $p>>=1, but eventually
       $p will come close enough to 0 for the loop to finish */
// count streaks for X and O
foreach([7,56,448,73,146,292,273,84]as$m)
    $n&$m^$m            // ($n masked with streak)!=streak <=> no streak for X
        ?$n&$m||$o++    // true: O has a streak if ($n masked with streak) is empty
        :$x++;          // false: X has a streak
echo!$x|!$o&&2>$i^=4;   // valid if not both have a streak
                        // AND $i is 4 or 5 (toggle 4 -> result 0 or 1)
Titus
sumber
1

Swift, 178 byte

func t(i:String)->Bool{let r=i.characters.filter({$0=="X"}).count;let g=i.characters.split(separator:"\n").map(String.init).contains;return(r==5||r==4)&&(!g("XXX") && !g("OOO"))}
Caleb Kleveter
sumber
0

ES6 (Javacript), 130, 138, 117 byte

EDIT:

  • Off 21 byte berkat saran luar biasa dari @Neil!
  • Versi awal rentan terhadap bug, yang sekarang harus diperbaiki dengan biaya +8 byte. (Terima kasih @ETHproduk untuk menunjukkannya)

Pendekatan lurus ekstrim. Mungkin bisa bermain golf lebih jauh.

Menerima input sebagai 9 argumen terpisah, 1es dan 0es

  • 1 untuk X
  • 0 untuk O

Argumen: 1-3 - baris pertama, 4-6 - baris kedua, 7-9 - baris ketiga.

Golf

(a,b,c,d,e,f,g,h,j)=>![a+b+c,d+e+f,g+h+j,a+d+g,b+e+h,c+f+j,a+e+j,g+e+c,7].some(x=>x=="7777307777"[a+b+c+d+e+f+g+h+j])

Interaktif "Tempat Tidur Test"

var a=b=c=d=e=f=g=h=j=0;

T=(a,b,c,d,e,f,g,h,j)=>![a+b+c,d+e+f,g+h+j,a+d+g,b+e+h,c+f+j,a+e+j,g+e+c,7].some(x=>x=="7777307777"[a+b+c+d+e+f+g+h+j]);

function test() {
  if(T(a,b,c,d,e,f,g,h,j)) {
     grid.style.backgroundColor='green';
     msg.innerHTML="GOOD"
  } else {
     grid.style.backgroundColor='red';
     msg.innerHTML="BAD"
  }
}
<table id=grid style="background: red">
<thead>
  <tr>
     <td id=msg align="center" colspan="3">BAD</td>
    </tr>
  </thead>
  <tr>
      <td><input type="checkbox" onchange="a=this.checked*1;test();" id="ca"/></td>
      <td><input type="checkbox" onchange="b=this.checked*1;test();" id="cb"/></td>
      <td><input type="checkbox" onchange="c=this.checked*1;test();" id="cc"/></td>
    </tr>
    <tr>
      <td><input type="checkbox" onchange="d=this.checked*1;test();" id="cd"/></td>
      <td><input type="checkbox" onchange="e=this.checked*1;test();" id="ce"/></td>
      <td><input type="checkbox" onchange="f=this.checked*1;test();" id="cf"/></td>
    </tr>
    <tr>
      <td><input type="checkbox" onchange="g=this.checked*1;test();" id="cg"/></td>
      <td><input type="checkbox" onchange="h=this.checked*1;test();" id="ch"/></td>
      <td><input type="checkbox" onchange="j=this.checked*1;test();" id="cj"/></td>
    </tr>
 </table>

zeppelin
sumber
Saya mungkin salah, tetapi sepertinya ini hanya memeriksa apakah ada pemenang. Papan yang valid tidak boleh memiliki pemenang; misalnya, [1,0,1,1,0,1,0,1,0]( XOX XOX OXO).
ETHproductions
Yap, saya kehilangan negasi saat bermain golf. Seharusnya memeriksa bahwa pihak yang berlawanan bukan pemenang. Harus diperbaiki sekarang. Terima kasih !
zeppelin
(Saya mulai berkomentar sebelum edit terakhir) Bisakah Anda a) menulis a+b+c+d+e+f+g+H+ialih-alih F.reduce((r,c)=>r+=c*1)(pada saat itu Anda tidak perlu F) b) menulis .includes(C)(dan lanjutkan ke nilai inline C)?
Neil
@ Neil, ini mungkin akan berhasil, saya akan mencobanya besok. Terima kasih !
zeppelin
Apakah OOO XXX OXOgagal?
Ismael Miguel