Connect 4: Spot the Fake!

35

Bank telah dibobol, dan semua preman mafia lokal memiliki alibi yang tidak biasa: mereka ada di rumah bermain Connect 4! Untuk membantu penyelidikan, Anda diminta untuk menulis sebuah program untuk memvalidasi semua papan Connect 4 yang telah disita untuk memeriksa apakah posisi tersebut memang posisi dari game Connect 4 yang valid, dan belum buru-buru disatukan. segera setelah polisi mengetuk pintu.

Aturan untuk menghubungkan pemain 4: Rdan Ybergiliran untuk menjatuhkan ubin warna mereka ke dalam kolom kotak 7x6. Ketika seorang pemain menjatuhkan ubin ke kolom, jatuh ke bawah untuk menempati posisi terendah yang tidak terisi dalam kolom itu. Jika seorang pemain berhasil mendapatkan empat ubin warna secara horizontal, vertikal atau diagonal, maka mereka menang dan permainan berakhir segera.

Misalnya (dengan Rmemulai), berikut ini adalah posisi Connect 4 yang mustahil.

| | | | | | | |
| | | | | | | |
| | | | | | | |
| | |R| | | | |
| | |Y| | | | |
|R| |Y| | | | |

Program atau fungsi Anda harus menggunakan papan Connect 4 dan kembali

  • Nilai palsu, menunjukkan bahwa posisi itu tidak mungkin atau
  • Sebuah string dari angka dari 1 sampai 7, menunjukkan satu urutan kemungkinan bergerak menuju posisi itu (kolom diberi nomor 1untuk 7dari kiri ke kanan, dan begitu urutan 112, misalnya, menunjukkan langkah merah di kolom 1, diikuti oleh langkah kuning di kolom 1, diikuti oleh gerakan merah di kolom 2). Anda dapat memilih penomoran kolom selain 1234567 jika suka, selama Anda tentukan dalam solusi Anda. Jika Anda ingin mengembalikan daftar dalam beberapa format lain; misalnya sebagai array [2, 4, 3, 1, 1, 3]maka itu juga baik-baik saja, asalkan mudah untuk melihat apa yang bergerak.

Anda dapat memilih untuk membaca papan dalam format apa pun yang masuk akal termasuk menggunakan huruf selain Rdan Yuntuk para pemain, tetapi Anda harus menentukan pemain mana yang lebih dulu. Anda dapat mengasumsikan bahwa dewan akan selalu 6x7, dengan dua pemain.

Anda dapat mengasumsikan bahwa posisi yang Anda terima setidaknya secara fisik memungkinkan untuk dibuat di papan Connect 4 standar; yaitu, bahwa tidak akan ada potongan 'mengambang'. Anda dapat mengasumsikan bahwa papan akan kosong.

Ini kode golf, jadi jawaban tersingkat menang. Celah standar berlaku.

Contohnya

| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | | --> 1234567 (one possible answer)
| | | | | | | |
|R|Y|R|Y|R|Y|R|

| | | | | | | |
| | | | | | | |
| | | | | | | |
| | |R| | | | | --> false
| | |Y| | | | |
|R| |Y| | | | |

| | | | | | | |
| | |Y| | | | |
| | |R| | | | |
| | |Y| | | | | --> 323333 (only possible answer)
| | |R| | | | |
| |Y|R| | | | |

| | | | | | | |
| | | | | | | |
| | | | | | | |     
| | | | | | | | --> false (this is the position arising after
| |Y|Y|Y|Y| | |     the moves 11223344, but using those moves
| |R|R|R|R| | |     the game would have ended once R made a 4)

| | | | | | | |
| | | | | | | |
|Y| | | | | | |     
|R|Y| | | | | | --> 2134231211 (among other possibilities)
|R|R|Y| | | | |
|Y|R|R|Y| | | |

| | | | | | | |
| | | | | | | |
|Y| | | | | | |     
|R|Y| | | | | | --> false (for example, 21342312117 does not
|R|R|Y| | | | |     work, because Y has already made a diagonal 4)
|Y|R|R|Y| | |R|

| | | | | | | |
| | | | | | | |
| | | | | | | |     
| | | | | | | | --> 112244553 or similar
|Y|Y| |Y|Y| | |
|R|R|R|R|R| | |
John Gowers
sumber
John, karena penasaran, apakah Anda tahu jika ada algoritma non-brute-force?
Jonah

Jawaban:

9

Jelly , 57 byte

ŒṪŒ!µ0ịŒṬ¬a³ZU,Ɗ;ŒD$€Ẏṡ€4Ḅo1%15;Ḋ€ṢṚ$Ƒƙ$Ȧȧœị³$2R¤ṁ$ƑµƇṪṪ€

Membawa sebuah matriks di mana 0tidak terisi, 1dimainkan pertama, dan 2dimainkan kedua. Menghasilkan daftar kolom 1-diindeks, kosong jika palsu diidentifikasi.

Cobalah online! (terlalu tidak efisien untuk menjalankan lebih dari 7 potong kurang dari satu menit)

catatan:

  1. Berasumsi bahwa tidak ada bagian "mengambang" yang hadir (perbaiki dengan prapengisian ZṠṢ€Ƒȧuntuk +6 byte)
  2. Menganggap bahwa papan kosong adalah palsu
Jonathan Allan
sumber
11

JavaScript (ES6),  202 194 187  183 byte

240

m=>(p=[...'5555555'],g=(c,s=o='')=>/2|4/.test(m)?['',0,2,4].some(n=>m.join``.match(`(1|3)(.{1${n}}\\1){3}`))?o:p.map((y,x)=>m[m[y][x]--^c||p[g(c^6,s+x,p[x]--),x]++,y][x]++)&&o:o=s)(2)

Cobalah online!

Bagaimana?

g2413

Saat melakukan hal itu, ia memastikan bahwa kami tidak memiliki menjalankan empat nilai ganjil berturut-turut sampai semua nilai genap menghilang (yaitu jika suatu pihak menang, itu harus menjadi langkah terakhir).

yxhal[x]

Berkomentar

m => (                            // m[] = input matrix
  p = [...'5555555'],             // p[] = next row for each column
  g = (c,                         // g = recursive function taking c = color,
          s = o = '') =>          //     s = current solution, o = final output
    /2|4/.test(m) ?               // if the matrix still contains at least a 2 or a 4:
      ['', 0, 2, 4]               //   see if we have four consecutive 1's or 3's
      .some(n =>                  //   by testing the four possible directions
        m.join``                  //   on the joined matrix, using
        .match(                   //   a regular expression where the number of characters
          `(1|3)(.{1${n}}\\1){3}` //   between each occurrence is either 1, 10, 12 or 14
        )                         //   (horizontal, diagonal, vertical, anti-diagonal)
      ) ?                         //   if we have a match:
        o                         //     abort and just return the current value of o
      :                           //   else:
        p.map((y, x) =>           //     for each cell at (x, y = p[x]):
          m[                      // 
            m[y][x]--             //       decrement the value of the cell
            ^ c ||                //       compare the original value with c
            p[                    //       if they're equal:
              g(                  //         do a recursive call with:
                c ^ 6,            //           the other color
                s + x,            //           the updated solution
                p[x]--            //           the updated row for this column
              ),                  //         end of recursive call
              x                   //         then:
            ]++,                  //         restore p[x]
            y                     //         and restore m[y][x]
          ][x]++                  //         to their initial values
        ) && o                    //     end of map(); yield o
    :                             // else:
      o = s                       //   we've found a solution: copy s to o
)(2)                              // initial call to g() with c = 2
Arnauld
sumber
Catatan saya telah bertanya, "Bolehkah kita berasumsi bahwa papan kosong tidak akan diberikan sebagai input?" - jika kita harus menangani ini maka kode Anda akan perlu di-tweak.
Jonathan Allan
saya tidak tahu mengapa, f([ [0,0,0,0,0,0,0], [0,0,0,0,0,0,0], [0,0,0,0,0,0,0], [0,0,2,0,2,0,0], [0,2,2,0,2,2,0], [1,1,1,1,1,1,1] ])diakhiri oleh 0 danf([ [0,0,0,0,0,0,0], [0,0,0,0,0,0,0], [0,0,0,0,0,0,0], [0,0,2,0,2,0,0], [2,2,2,0,2,2,1], [1,1,1,1,1,1,1] ]) seharusnya benar
Nahuel Fouilleul
@NahuelFouilleul Terima kasih telah melaporkan ini. Saya telah memperbaiki kode dan menambahkan kasus uji ini.
Arnauld
2

Python 2 , 295 285 byte

def f(a):
 if 1-any(a):return[]
 p=sum(map(len,a))%2
 for i in R(7):
	if a[i][-1:]==`p`:
	 b=a[:];b[i]=b[i][:-1];L=f(b)
	 if L>1>(`1-p`*4in','.join([J((u[j]+' '*14)[n-j]for j in R(7))for n in R(12)for u in[b,b[::-1]]]+b+map(J,zip(*[r+' '*7for r in b])))):return L+[i]
R=range;J=''.join

Cobalah online!

-10 thx kepada Jo King .

Input adalah daftar string yang mewakili kolom; dengan '1' untuk Merah dan '0' untuk Kuning. String tidak '-dipasang. Jadi kasus (falsey):

| | | | | | | |
| | | | | | | |
|Y| | | | | | |
|R|Y| | | | | |
|R|R|Y| | | | |
|Y|R|R|Y| | |R|

dimasukkan sebagai:

[
  '0110',
  '110',
  '10',
  '0',
  '',
  '',
  '1'
]

Output adalah daftar indeks kolom, 0-diindeks, yang dapat membuat papan; atau Nonejika itu tidak valid.

Terima papan kosong sebagai valid (mengembalikan daftar kosong []sebagai ganti None).

Pendekatan ini bersifat rekursif dari langkah terakhir ke langkah pertama: berdasarkan pada paritas dari total jumlah langkah yang diambil, kami menghapus langkah Merah terakhir atau langkah Kuning terakhir (atau gagal jika itu tidak mungkin); periksa papan yang dihasilkan untuk melihat apakah lawan memiliki 4-in-a-row (dalam hal ini gagal, karena permainan seharusnya sudah berhenti); jika tidak, ulangi sampai papan kosong (yang valid).

Kode 4-in-a-row adalah bagian yang paling menyenangkan. Semua string diagonal untuk matriks bdihasilkan oleh:

[
    ''.join(
        (u[j]+' '*14)[n-j] for j in range(7)
    )
    for u in[b,b[::-1]]for n in range(12) 
]

yang pertama mencantumkan diagonal yang 'miring ke bawah', dan kemudian diagonal yang 'miring ke atas'.

Chas Brown
sumber