Saling Menyerang Queens

26

Biarkan papan catur 8x8 diwakili oleh dua nilai berbeda, dengan satu nilai menjadi kotak kosong dan yang lainnya menjadi ratu. Dalam contoh berikut, saya menggunakan 0s sebagai kotak kosong dan 1s sebagai ratu. Sebagai contoh:

Ratu di papan catur

diberikan oleh

1 0 1 1 1 0 0 0
1 0 1 0 1 0 1 1
1 0 1 0 1 1 0 1
0 1 0 1 0 1 0 0
0 1 1 0 0 1 0 1
1 0 0 0 1 0 0 0
0 1 0 0 0 1 1 1
0 1 1 1 0 1 0 1

Pertimbangkan jumlah pasangan ratu yang menyerang masing-masing yang setidaknya berjarak satu kuadrat (sebagai pengingat, ratu menyerang secara ortogonal dan diagonal). Dalam contoh di atas, diagram jelek luar biasa berikut ini menunjukkan semua pasangan ini sebagai panah.

Menyerang ratu

Ada 43 pasangan yang ditemukan di atas yang memberikan test case berikut:

Input:
1 0 1 1 1 0 0 0
1 0 1 0 1 0 1 1
1 0 1 0 1 1 0 1
0 1 0 1 0 1 0 0
0 1 1 0 0 1 0 1
1 0 0 0 1 0 0 0
0 1 0 0 0 1 1 1
0 1 1 1 0 1 0 1
Output: 43

Tantangan

Tulis sebuah program yang, diberi status papan yang diwakili oleh dua nilai berbeda, menampilkan jumlah pasangan ratu yang saling serang dengan setidaknya satu kotak di antaranya.

  • Anda dapat memasukkan dalam format apa pun yang paling nyaman yang menggunakan dua nilai untuk mewakili kotak kosong dan ratu, misalnya, string 64 "." S untuk kotak kosong dan "Q" untuk queens dengan baris dari bawah ke atas, 8x8 matriks booleans, daftar bilangan bulat 0 dan 1 dll, selama dijelaskan dalam solusi Anda
  • Output adalah bilangan bulat
  • Metode I / O standar berlaku dan lubang standar dilarang
  • Ini kode golf sehingga jawaban tersingkat dalam byte menang

Kasus uji:

Menggunakan format 0 dan 1, dengan 0 kotak kosong dan 1 menjadi ratu:

Input:
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
Output: 0

Input:
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
Output: 0

Input:
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 1 0 0 0 0 1 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
Output: 1

Input:
0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0
0 1 0 0 0 0 1 0
0 0 0 0 1 0 1 0
0 0 0 0 0 0 0 0
0 0 0 1 0 0 1 0
0 0 0 0 0 0 0 0
Output: 10

Input:
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
Output: 4

Input:
1 1 0 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1
1 1 1 1 0 1 1 1
1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
Output: 11
JMigst
sumber
Saya seharusnya bertanya sebelum memposting versi 2 saya: apakah 254 untuk seorang ratu dan 0 untuk nilai input persegi yang dapat diterima?
Arnauld
@Arnauld Anda dapat memasukkan dalam format apa pun yang paling nyaman yang menggunakan dua nilai untuk mewakili kotak dan ratu kosong. Jadi itu tidak masalah
JMigst
Terima kasih. Saya bertanya karena saya pikir aturan ini mungkin agak terlalu permisif jika diambil secara harfiah. Saya bisa meminta untuk melewatkan string yang berisi sebagian besar kode JS untuk ratu dan hanya mengevaluasi itu di program. (Tapi itu bisa dicegah dengan celah default. Saya tidak yakin.)
Arnauld

Jawaban:

14

Python 2 , 105 byte

lambda b:sum(b[i+d::d][:(8,7-i%8,i%8)[d%8%5]].find('1')*int(c)>0for i,c in enumerate(b)for d in[1,7,8,9])

Cobalah online!

Penjelasan

Kami mengambil input sebagai string 64 karakter '0'atau '1'. Menggunakan irisan langkah, kami melemparkan empat "garis pandang" dari setiap ratu yang kami temui. Misalnya, ketika i = 10 dan d = 7 , tandai ratu sebagai ♥ dan ubin dipilih oleh b[i+d::d]as:

1 0 1 1 1 0 0 0
1 0  0 1 0 1 1
1  1 0 1 1 0 1
 1 0 1 0 1 0 
0 1 1 0 0 1  1
1 0 0 0 1  0 0
0 1 0 0  1 1 1
0 1 1  0 1 0 1

Jelas, kami sebenarnya tidak ingin visi membungkus papan seperti ini. Jadi kami menghitung seberapa jauh ujung papan di setiap arah, dan melihat ubin di b[i+d::d][:…].

Untuk setiap pasangan arah ubin kami menghitung:

ray.find('1')*int(c)>0

Ini akan gagal kapan saja

  • cbukan ratu; atau
  • ratu yang dilihat ray ini terlalu dekat ( findmenghasilkan 0); atau
  • sinar ini tidak melihat ratu ( findpengembalian −1).

Setiap pasangan ratu hanya diperiksa satu kali, karena sinar selalu dilemparkan ke depan dalam urutan membaca, dari ratu "sebelumnya" ke ratu "nanti".

Lynn
sumber
10

JavaScript (ES7), 86 byte

Mengambil input sebagai array 64 bilangan bulat dengan 254 untuk queen dan 0 untuk kotak kosong.

a=>[s=0,6,7,8].map(d=>a.map(g=(n,p)=>(p%8-(p+=~d)%8)**2<n%4?a[p]?s+=n&1:g(n/2,p):0))|s

Cobalah online!

Versi ini menyalahgunakan aritmatika underflow untuk mendapatkan kondisi berhenti di bagian rekursif.


JavaScript (ES7), 89 byte

Mengambil input sebagai array 64 bit.

a=>[s=0,6,7,8].map(d=>a.map(g=(n,p,x)=>(p%8-(p+=~d)%8)**2>1|p<0?0:a[p]?s+=!x&n:g(n,p)))|s

Cobalah online!

Bagaimana?

Kami secara rekursif memanggil fungsi callback bernama map()untuk berjalan melalui kotak dalam arah tertentu. Meskipun kita tidak benar-benar membutuhkan konten dari parameter ketiga dari callback (array map()dipanggil), kita secara tidak langsung menggunakannya untuk mengetahui apakah itu adalah iterasi pertama atau tidak.

arr.map (function callback (currentValue [, index [, array]])

Ini adalah variabel x dalam kode.

a =>                        // given the input array a[]
  [ s = 0,                  // initialize the sum s to 0
    6, 7, 8 ].map(d =>      // for each direction d in [0, 6, 7, 8]:
    a.map(g = (n, p, x) =>  //   for each square n at position p in a[]:
      (                     //     we are out of the board if:
        p % 8 -             //       - abs(p % 8 - p' % 8) is greater than 1
        (p += ~d) % 8       //         where p' = p - (d + 1)
      ) ** 2 > 1 |          //         (squaring is shorter than using Math.abs)
      p < 0 ?               //       - or p' is less than 0
        0                   //       if so, stop recursion
      :                     //     else:
        a[p] ?              //       if there's a queen on the target square:
          s +=              //         increment s if:
            !x &            //           x is undefined (this is not the 1st iteration)
            n               //           and n = 1 (there's a queen on the source square)
        :                   //       else:
          g(n, p)           //         do a recursive call to g(), with x undefined
    )                       //   end of inner map()
  ) | s                     // end of outer map(); return s
Arnauld
sumber
8

Siput , 14 byte

A
rdaa7\1\0+\1

Cobalah online!

Input adalah format 0/1, tanpa spasi di dalam garis.

Siput telah dibuat untuk tantangan PPCG desain bahasa pencocokan pola 2D . Yang paling penting, secara default menampilkan jumlah kecocokan yang ditemukan, yang sempurna untuk tantangan ini.


A menetapkan opsi "semua jalur", sehingga jika seorang ratu berada dalam banyak pasangan, masing-masing pasangan itu akan menghasilkan kecocokan.

rdaa7menyetel arah pertandingan ke S, SE, E, dan NE. Pengaturan ke semua arah ( z) akan menyebabkan penghitungan ganda.

\1\0+\1cocok dengan 1, lalu satu atau lebih 0, lalu yang lain 1.

TwiNight
sumber
6

APL (Dyalog Classic) , 41 39 32 byte

(+/+⌿-⌈⌿)2<⌿0⍪⊢,⍉,8 31⍴⊢,≠⍨,⌽,≠⍨

Cobalah online!

≠⍨ adalah "tidak sama dengan dirinya sendiri" - sebuah matriks all-zero 8x8

⊢,≠⍨,⌽,≠⍨- jika matriks asli adalah ABC..., ekspresi ini mengembalikan:

A B C D E F G H 0 0 0 0 0 0 0 0 H G F E D C B A 0 0 0 0 0 0 0 0
I J K L M N O P 0 0 0 0 0 0 0 0 P O N M L K J I 0 0 0 0 0 0 0 0
Q R S T U V W X 0 0 0 0 0 0 0 0 X W V U T S R Q 0 0 0 0 0 0 0 0
Y Z A B C D E F 0 0 0 0 0 0 0 0 F E D C B A Z Y 0 0 0 0 0 0 0 0
G H I J K L M N 0 0 0 0 0 0 0 0 N M L K J I H G 0 0 0 0 0 0 0 0
O P Q R S T U V 0 0 0 0 0 0 0 0 V U T S R Q P O 0 0 0 0 0 0 0 0
W X Y Z A B C D 0 0 0 0 0 0 0 0 D C B A Z Y X W 0 0 0 0 0 0 0 0
E F G H I J K L 0 0 0 0 0 0 0 0 L K J I H G F E 0 0 0 0 0 0 0 0

8 31⍴ membentuk kembali dari 8x32 ke 8x31, menggunakan kembali elemen dalam urutan baris-utama:

A B C D E F G H 0 0 0 0 0 0 0 0 H G F E D C B A 0 0 0 0 0 0 0
0 I J K L M N O P 0 0 0 0 0 0 0 0 P O N M L K J I 0 0 0 0 0 0
0 0 Q R S T U V W X 0 0 0 0 0 0 0 0 X W V U T S R Q 0 0 0 0 0
0 0 0 Y Z A B C D E F 0 0 0 0 0 0 0 0 F E D C B A Z Y 0 0 0 0
0 0 0 0 G H I J K L M N 0 0 0 0 0 0 0 0 N M L K J I H G 0 0 0
0 0 0 0 0 O P Q R S T U V 0 0 0 0 0 0 0 0 V U T S R Q P O 0 0
0 0 0 0 0 0 W X Y Z A B C D 0 0 0 0 0 0 0 0 D C B A Z Y X W 0
0 0 0 0 0 0 0 E F G H I J K L 0 0 0 0 0 0 0 0 L K J I H G F E

⊢,⍉, tambahkan awal matriks asli dan transposinya (ruang ekstra untuk kejelasan):

A B C D E F G H  A I Q Y G O W E  A B C D E F G H 0 0 0 0 0 0 0 0 H G F E D C B A 0 0 0 0 0 0 0
I J K L M N O P  B J R Z H P X F  0 I J K L M N O P 0 0 0 0 0 0 0 0 P O N M L K J I 0 0 0 0 0 0
Q R S T U V W X  C K S A I Q Y G  0 0 Q R S T U V W X 0 0 0 0 0 0 0 0 X W V U T S R Q 0 0 0 0 0
Y Z A B C D E F  D L T B J R Z H  0 0 0 Y Z A B C D E F 0 0 0 0 0 0 0 0 F E D C B A Z Y 0 0 0 0
G H I J K L M N  E M U C K S A I  0 0 0 0 G H I J K L M N 0 0 0 0 0 0 0 0 N M L K J I H G 0 0 0
O P Q R S T U V  F N V D L T B J  0 0 0 0 0 O P Q R S T U V 0 0 0 0 0 0 0 0 V U T S R Q P O 0 0
W X Y Z A B C D  G O W E M U C K  0 0 0 0 0 0 W X Y Z A B C D 0 0 0 0 0 0 0 0 D C B A Z Y X W 0
E F G H I J K L  H P X F N V D L  0 0 0 0 0 0 0 E F G H I J K L 0 0 0 0 0 0 0 0 L K J I H G F E

2<⌿0⍪menambahkan 0s di atas dan membandingkan menggunakan <setiap elemen terhadap elemen di bawahnya, jadi kami mendapatkan 1 untuk 1 terkemuka di setiap grup vertikal 1s, dan kami mendapatkan 0s di tempat lain

+⌿-⌈⌿ jumlah per kolom dikurangi jumlah maksimum per kolom - kami menghitung jumlah celah antara 1-grup di setiap kolom, 0 jika tidak ada

+/ jumlah

ngn
sumber
5

Jelly , 22 20 byte

t0ŒgL:2
Z,U;ŒD$€ẎÇ€S

Cobalah online!

pengguna202729
sumber
Bagaimana cara kerjanya?
lirtosiast
@ lirtosiast Saya tidak ingat ...
user202729
@ lirtosiast Tautan pertama menghitung jumlah pasangan dalam 1D, tautan kedua mengambil jumlah dari tautan pertama di atas semua baris dalam tabel.
user202729
3

Retina 0.8.2 , 60 58 byte

1
¶1$';___¶
_
$n$%`7$*_
(.)(?=.*;(_)*)(?<-2>.)*
$1
m`^10+1

Cobalah online! Mengambil input sebagai 8 string biner 8-karakter yang dipisahkan koma, tetapi header mengkonversi format yang disediakan untuk Anda. Penjelasan:

1
¶1$';___¶

Buat semua substring papan mulai dari ratu. Sufikskan nilai marker ke setiap substring. Sunting: Disimpan 2 byte dengan meninggalkan beberapa string sampah; ini diabaikan secara efektif.

_
$n$%`7$*_

Pisahkan setiap marker ke dalam rentang inklusif, dan tambahkan 7 ke elemen yang tidak nol.

(.)(?=.*;(_)*)(?<-2>.)*
$1

Hapus setiap karakter yang sama dengan panjang marker. Ini sama dengan menemukan setiap sinar timur, barat daya, selatan atau tenggara dari masing-masing ratu.

m`^10+1

Hitung semua sinar yang melewati setidaknya satu kotak kosong sebelum bertemu ratu lain.

Neil
sumber
3

JavaScript (ES6) + SnakeEx , 38 byte

s=>snakeEx.run('m:<*>10+1',s).length/2

Mengambil input dalam formulir '10111000\n10101011\n10101101\n01010100\n01100101\n10001000\n01000111\n01110101'. Ternyata, SnakeEx masih bisa digunakan di luar tantangan aslinya!

LegionMammal978
sumber