Hitung Mills di Nine Men's Morris

21

pengantar

Nine Mens's Morris (juga disebut Mills) adalah permainan papan untuk dua pemain yang dimainkan di papan berikut (gambar diambil dari halaman Wikipedia yang terhubung):

Papan pabrik

Setiap pemain memiliki 9 pemain, berwarna hitam dan putih. Aturan konkret tidak penting untuk tantangan ini, tetapi periksa halaman Wikipedia jika Anda tertarik.

Tantangan

Mengingat grid sebagai input, yang merupakan boardstate tertentu, output count pabrik keseluruhan mdengan 0<=m<=8.
Tiga pria dengan warna yang sama membentuk penggilingan ketika mereka berada di barisan lurus titik-titik yang terhubung. b2to f2bukan pabrik karena laki-laki memiliki warna yang berbeda. Juga d2untuk d5tidak akan membentuk pabrik sejak tiga poin harus terhubung.
Papan pada gambar di atas mengandung dua pabrik misalnya. Satu dari f2ke f6dan satu dari e3ke e5.

Memasukkan

Papan direpresentasikan sebagai kisi 2D dengan 24 titik yang terhubung seperti yang ditunjukkan pada contoh gambar di atas. Contoh ini menggunakan huruf dari a-guntuk kolom dan angka dari 1-7untuk baris, tetapi Anda dapat memilih format input yang wajar selama memetakan 24 koordinat unik ke salah satu negara berikut:

  • Kosong
  • Diambil oleh hitam
  • Diambil putih

Repersentasi beton terserah Anda, Anda tidak terbatas pada "b" atau "w" untuk warna.

Selain itu, input Anda mungkin tidak mengandung informasi tambahan.

Catatan tambahan

  • Anda tidak harus memetakan poin berdasarkan jenis nilai apa pun. Jika Anda ingin mengambil input sebagai array 2D, itu bagus juga. Tetapi perlu diingat bahwa tidak semua poin di sana digunakan dan Anda harus mempertimbangkan koneksi di antara mereka.
  • Input mungkin kosong, dalam hal ini Anda harus menghasilkan nol (papan kosong -> tidak ada pabrik).
  • Karena setiap pemain memiliki 9 pemain, input tidak akan pernah mengandung lebih dari 18 poin yang diambil.
  • Anda dapat meninggalkan poin emtpy di input dan oleh karena itu hanya input poin yang diambil.
  • Input dapat dipesan dengan cara apa pun. Anda tidak dapat mengandalkan pesanan tertentu.
  • Anda dapat mengasumsikan bahwa input akan selalu valid. Ini berarti bahwa tidak akan ada lebih dari 9 pria dari setiap warna dan bahwa setiap titik akan unik.

Aturan

  • Jelaskan format input mana yang Anda gunakan dalam solusi Anda. Memberikan contoh program Anda sangat dianjurkan.
  • Fungsi atau program lengkap diizinkan.
  • Aturan default untuk input / output.
  • Celah standar berlaku.
  • Ini adalah , sehingga byte-count terendah akan menang. Tiebreak adalah pengiriman sebelumnya.

Uji kasus

Format input di sini adalah daftar tupel dengan koordinat seperti pada contoh di atas sebagai elemen pertama dan keadaan elemen titik kedua. Titik yang diambil dengan warna putih ditandai sebagai "w" dan titik yang diambil dengan warna hitam sebagai "b". Semua poin lainnya ditinggalkan dan kosong.

[("a4", "w"), ("b2", "b"), ("b4", "b"), ("c4", "b"), ("d1", "w") , ("d2", "w"), ("e3", "w"), ("e4", "w"), ("e5", "w"), ("f2", "b") , ("f4", "b"), ("f6", "b"), ("g4", "w")] -> 2
[("a1", "b"), ("a4", "b"), ("a7", "b"), ("b4", "b"), ("c4", "b") , ("d3", "w"), ("d2", "w"), ("d1", "w")] -> 3
[] -> 0
[("b4", "b"), ("a4", b "), (" c4 ", w")] -> 0
[("b4", "b"), ("a4", b "), (" c4 ", b")] -> 1
[("a1", "b"), ("a4", "b"), ("a7", "b"), ("b2", "b"), ("b4", "b") , ("b6", "b"), ("c3", "b"), ("c4", "b"), ("c5", "b"), ("e3", "w") , ("e4", "w"), ("e5", "w"), ("f2", "w"), ("f4", "w"), ("f6", "w") , ("g1", "w"), ("g4", "w"), ("g7", "w")] -> 8

Selamat Coding!

Denker
sumber
Terkait - sedikit.
masukkan nama pengguna di sini
Saya berasumsi warna harus berdekatan dan selaras, tetapi agak tidak jelas. Misalnya, apakah d2, d3, d5 dengan warna yang sama membentuk gilingan?
Robert Benson
@RobertBenson Tidak itu tidak karena d3dan d5tidak terhubung. Aturan mengatakan: Three men of the same color form a mill when they are in a straight row of connected points.. Saya menambahkan beberapa contoh di bagian ini untuk menjelaskannya, terima kasih atas komentarnya!
Denker

Jawaban:

4

APL (Dyalog Classic) , 26 25 byte

-1 terima kasih kepada FrownyFrog

≢{|∊(+/⍵⍪↓⍵),⊢/4 2⍴+⌿⍵}∩≢

Cobalah online!

Argumennya adalah array 3x3x3 1(hitam), ¯1(putih), dan 0(kosong). Dimensi pertama sepanjang kedalaman bersarang kotak konsentris. Dua dimensi lainnya berada di sepanjang sumbu vertikal dan horizontal.

000---------001---------002
 |           |           |
 |  100-----101-----102  |
 |   |       |       |   |
 |   |  200-201-202  |   |
 |   |   |       |   |   |
010-110-210     212-112-012
 |   |   |       |   |   |
 |   |  220-221-222  |   |
 |   |       |       |   |
 |  120-----121-----122  |
 |           |           |
020---------021---------022

Kami memiliki gilingan setiap kali penjumlahan di sepanjang sumbu menghasilkan 3atau ¯3, kecuali kita harus membuang keempat sudut saat menjumlahkan sepanjang sumbu pertama.

{} adalah fungsi dengan argumen implisit

↓⍵adalah perpecahan - dalam kasus kami ternyata sebuah kubus 3x3x3 dalam matriks 3x3 dari bersarang panjang-3 vektor

⍵⍪↓⍵ mengambil kubus asli dan menempelkan matriks 3x3 dari 3-vektor di bawahnya, jadi kami mendapatkan array skalar dan vektor 4x3x3 campuran

+/menjumlahkan sepanjang sumbu terakhir; ini memiliki efek gabungan dari menjumlahkan kubus asli di sepanjang sumbu terakhir ( +/⍵) dan menjumlahkannya di sepanjang sumbu tengah karena pemisahan yang kami lakukan ( +/↓⍵)

Sekarang kita harus mengurus case khusus untuk sumbu pertama.

+⌿⍵ menjumlahkan sepanjang sumbu pertama, mengembalikan matriks 3x3

4 2⍴ tapi kita tidak harus menghitung sudut, jadi kita membentuk kembali ke matriks 4x2 seperti ini:

ABC      AB
DEF  ->  CD
GHI      EF
         GH  ("I" disappears)

sekarang kami hanya tertarik pada kolom terakhir ( BDFH), jadi kami menggunakan idiom⊢/

,bergabung BDFHdengan matriks yang kami peroleh sebelumnya untuk sumbu 2 & 3 ( BDFHdan matriks keduanya memiliki dimensi utama 4)

meratakan semua yang kami peroleh sejauh ini menjadi satu vektor

| mengambil nilai absolut

{ }∩≢ memfilter hanya bertiga - panjang (≢) input selalu 3

menghitungnya

ngn
sumber
Heh, aku baru saja akan menyarankan itu.
Adám
Bisakah Anda bergabung dengan chat.stackexchange.com/rooms/52405/apl sejenak?
Adám
≢{|∊(+/⍵⍪↓⍵),⊢/4 2⍴+⌿⍵}∩≢lebih pendek :)
FrownyFrog
@FrownyFrog terima kasih! diedit pada
ngn
4

JavaScript (ES6), 276 228 125 117 105 byte

a=>btoa`i·yø!9%z)ª»-ºü1j;ÝÈ%¥·¡ªÜ"·ç¹Ê1`.replace(/.../g,b=>(a[b[0]]+a[b[1]]+a[b[2]])/3&1||'').length

(di atas berisi beberapa karakter ascii yang tidak dapat dicetak yang tidak akan muncul di sini, jadi inilah versi tanpa btoayang dapat disalin dan dijalankan)

a=>'abcdefghijklmnopqrstuvwxajvdksglpbehqtwimrfnucox'.replace(/.../g,b=>(a[b[0]]+a[b[1]]+a[b[2]])/3&1||'').length

Memecah string referensi menjadi kembar tiga surat yang cocok dengan kunci grup pabrik. Input dalam bentuk objek, di mana tombol adalah huruf a-x, mulai dari kiri bawah dan berakhir di kanan atas, bergerak dari kiri ke kanan terlebih dahulu. Nilai 1untuk putih, -1hitam, dan 0kosong.

Contoh

{b:1,d:-1,e:1,f:-1,i:1,k:-1,l:-1,m:1,n:-1,r:1,u:-1} => 2
{j:1,d:-1,k:-1,l:-1,b:1,e:1,i:1,m:1,r:1,f:-1,n:-1,u:-1,o:1} => 2
{a:-1,j:-1,v:-1,k:-1,l:-1,h:1,e:1,b:1} => 3
{} => 0
{k:-1,j:-1,l:1} => 0
{k:-1,j:-1,l:1} => 1
{a:-1,j:-1,v:-1,d:-1,k:-1,s:-1,g:-1,l:-1,p:-1,i:1,m:1,r:1,f:1,n:1,u:1,c:1,o:1,x:1} => 8

Contoh-contoh ini diambil dari contoh OP, dikonversi ke objek kunci-huruf dan nilai-angka. Yang pertama adalah dari contoh gambar, sedangkan yang lain dari contoh set.

Mwr247
sumber
1
Pekerjaan yang baik! Anda dapat mengompres string besar dengan atob.
ETHproduksi
@ ETHproduk Terima kasih! Tampaknya menggunakan karakter ascii yang tidak dapat dicetak, jadi saya akan memasukkan satu tanpa itu btoa. Juga menemukan beberapa perbaikan lain yang membuatnya semakin turun.
Mwr247
2

Mathematica, 217 131 Bytes

Meskipun saya yakin ini tidak terlalu kompetitif, inilah entri untuk Anda.

Count[Total/@{{a1,d1,g1},{b2,d2,f2},{c3,d3,e3},{a4,b4,c4},{e4,f4,g4},{c5,d5,e5},{b6,d6,f6},{a7,d7,g7},{a1,a4,a7},{b2,b4,b6},{c3,c4,c5},{d1,d2,d3},{d5,d6,d7},{e3,e4,e5},{f2,f4,f6},{g1,g4,g7}}/.#/.{"w"->1,"b"->2},3|6]&

Contoh input:

{a4 -> "w", b2 -> "b", b4 -> "b", c4 -> "b", d1 -> "w", d2 -> "w", e3 -> "w", e4 -> "w", e5 -> "w", f2 -> "b", f4 -> "b", f6 -> "b", g4 -> "w"}

Mengizinkan nama koordinat karakter tunggal dengan mudah menghilangkan 51 karakter, menjadikan ini solusi 166 byte. Memberi nama pemain 1 dan 2 daripada "w" dan "b" golf dari 17 karakter lebih lanjut.

Jadi kita dapatkan

Count[Total/@{a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,a,j,v,d,k,s,g,l,p,b,e,h,q,t,w,r,i,m,f,u,n,c,o,x}~Partition~3,3|6]/.#&
A Simmons
sumber
Jika saya memahami aturan pemformatan input dengan benar, Anda harus dapat menerimanya sebagai 1dan 2. contoh yang digunakan wdan b, tapi saya cukup yakin kita tidak dibatasi untuk itu.
Mwr247
@ Mwr247 Anda benar. Anda dapat menggunakan format apa pun yang Anda inginkan, asalkan tidak menambahkan informasi tambahan. Saya akan mengklarifikasi ini ketika saya di rumah.
Denker
1

APL (Dyalog Unicode) , 50 byte

"Solusi Objek"

Meskipun lebih panjang (29 karakter) daripada solusi @ ngn , ia menggunakan pendekatan yang sama sekali berbeda: Input memiliki struktur keseluruhan yang sama dengan solusi itu, tetapi semua slot direpresentasikan sebagai objek. Slot kosong (termasuk kolom tengah yang tidak ada) harus berupa objek kosong. sementara semua pria kulit hitam harus menjadi referensi ke objek "pria kulit hitam", dan semua pria kulit putih harus menjadi referensi ke objek "pria kulit putih". Semua objek secara opsional memiliki D isplay F orm s yang bagus untuk dibaca, dan kolom tengah secara opsional dapat dibuat tidak terlihat.

+/1=(≢¨(,∪/,∪⌿⍤2),(⊢/4 2⍴∪⌿))

Cobalah online!

+/ jumlah dari

1=(... ) yang ada di

≢¨(... ) penghitungan

  , yang diratakan (diratakan)

  ∪/ set unik di seluruh

  , digabungkan ke

  ∪⌿⍤2 set unik ke bawah

,(... ) disatukan ke

  ⊢/ kolom paling kanan

  4 2⍴ itu, dibentuk kembali menjadi empat baris dan dua kolom,

  ∪⌿ set kolom unik

Sebuah atas operator, seperti yang disediakan dengan AGL ( ä), akan membawa panjang ke 27 karakter .

Adm
sumber