Katakanlah tugas Anda adalah melukis tiang, dan klien meminta Anda melukis tiang dengan 4 bagian merah dan 3 bagian kuning. Anda dapat melakukannya dengan mudah sebagai berikut:
r y r y r y r
Hanya dengan garis-garis kuning dan merah. Sekarang katakanlah klien Anda meminta Anda untuk melukis sebuah tiang dengan 2 bagian merah, 2 bagian kuning, dan 1 bagian hijau . Ada beberapa cara Anda bisa mengecat tiang Anda
g y r y r
y g r y r
y r g y r
y r y g r
y r y r g
g r y r y
r g y r y
r y g r y
r y r g y
r y r y g
y r g r y
r y g y r
Lebih tepatnya itulah 12 cara untuk melukis tiang. Ini memunculkan lebih banyak warna dan bagian yang terlibat
Sekarang jika klien Anda mengatakan mereka ingin 3 bagian merah dan 1 bagian kuning tidak ada cara untuk melukis tiang seperti itu. Karena tidak peduli bagaimana Anda mencoba mengatur bagian dua bagian merah akan menyentuh, dan ketika dua bagian merah menyentuh mereka menjadi bagian merah tunggal.
Dan itu adalah aturan kami untuk mengecat tiang
Bagian yang berdekatan mungkin tidak memiliki warna yang sama
Tugas
Diberi daftar warna dan bagian yang diperlukan, output jumlah cara yang mungkin untuk melukis tiang seperti yang diminta. Anda dapat mewakili warna dengan cara yang masuk akal (bilangan bulat, karakter, string), tetapi Anda tidak akan pernah diberikan lebih dari 255 warna berbeda sekaligus. Jika mau, Anda bahkan dapat memilih untuk tidak memiliki warna yang ditetapkan nama dan hanya mengambil daftar jumlah bagian jika itu lebih mudah.
Uji Kasus
Ini agak sulit untuk dihitung dengan tangan, terutama karena semakin besar. Jika ada yang memiliki test case yang disarankan, saya akan menambahkannya.
[4,3] -> 1
[2,2,1] -> 12
[3,1] -> 0
[8,3,2] -> 0
[2,2,1,1]-> 84
sumber
[1, 1, 1, 1, 2, 2, 2]
? Saya rasa begitu.Jawaban:
Mathematica, 37
44486062byteAmbil input sebagai daftar bilangan bulat
{1, 1, 1, 2, 2}
. Cobalah di Wolfram Sandbox .Metode pencocokan pola, terima kasih @Tidak pohon!
Split
membagi satu daftar menjadi sub daftar elemen yang berurutan, misalnya{1, 1, 2, 3, 4, 4}
menjadi{{1, 1}, {2}, {3}, {4, 4}}
{{_}..}
adalah, yaitu{{_}, {_}, {_}, ...}
,. Pola ini cocok dengan daftar sub daftar yang tidak disadari.Differences
metode, 48 byte:Kode digunakan
Differences
untuk menentukan apakah elemen yang berdekatan adalah sama.Selangkah demi selangkah:
Permutations@#
menghasilkan semua permutasi dari daftar input ke daftar N! * N.Differences/@
menghitung perbedaan antara elemen N, dan menghasilkan daftar N! * (N-1).1##&@@@
menghitung penggandaan semua daftar. Jika daftar berisi0
(dua elemen yang berdekatan adalah sama), hasilnya akan0
, jika tidak nol, ke N! daftar.Clip[]
bertindak sepertiSign[]
, mentransformasikan daftar dari (-inf, inf) ke [-1, 1]Tr@Abs
mengubah semua-1
menjadi1
dan sekarang daftar panjang N hanya berisi0
(tidak valid) dan1
(valid). Jadi kami hanya menjumlahkan daftarnya.sumber
Permutations@#~Count~Except@{___,x_,x_,___}&
.Count[Split/@Permutations@#,{{_}..}]&
:, 37 byte!Jelly , 7 byte
Cobalah online!
Mengambil input sebagai contoh
[1,1,1,1,2,2,2]
untuk[4,3]
. The[8,3,2]
testcase waktu terlalu lama untuk berjalan di TIO.Bagaimana itu bekerja
sumber
Œ!QIẠ€S
bekerja? Cobalah online!P
atom apa saja daripada semua karena kesederhanaannya.P€
bukannyaẠ€
tetap bekerja.05AB1E , 7 byte
Cobalah online!
-1 terima kasih kepada nmjcman101 pada jawaban lain.
sumber
Mathematica, 50 byte
Cobalah dalam Matematika , atau di kotak pasir Wolfram !
Mengambil input seperti pada kasus uji - mis.
{4,3}
Berarti "4 garis merah, 3 garis kuning".Ini adalah implementasi naif dari formula yang saya temukan di sini . "Naïve" berarti "Aku tidak tahu bagaimana matematika bekerja jadi tolong jangan tanya saya untuk penjelasan ..."
sumber
Python 3.5 , 65 byte
Cobalah online!
sumber
Ruby 2.4, 47 byte
Input adalah daftar karakter: Untuk kasus uji
[4,3]
, masukan bisa%w[a a a a b b b]
,"1111222".chars
, atau berbagai format metode lain yang berlaku di Ruby.Membutuhkan 2,4 untuk
Enumerator#uniq
(versi sebelumnya hanya tersedia diArray
kelas). Dengan demikian, tautan TIO menambahkan 5 byte untuk mengkonversi enumerator permutasi menjadi array terlebih dahuluto_a
, karena tidak memiliki fungsi di atas.Cobalah online!
sumber
R, 72 byte
Menciptakan fungsi
Mengambil input dalam formulir
[1,1,1,1,2,2,2]
sesuai komentar Erik the Outgolfer. Penggunaancombinat
'spermn
fungsi untuk membuat daftar semua permutasi, dan kemudianunique
untuk mendapatkan semua entri yang berbeda.sapply
kemudian menerapkan fungsi berikut pada semua entri:Yang dievaluasi menjadi
Perhatikan bahwa ini
x
tidak sama denganx
input dalam fungsi besar. Menggunakan karakter lain dalam fungsi ini akan membodohipryr::f
percaya bahwa fungsi besar membutuhkan argumen lain.Anyways, ketika diberi permutasi, fungsi ini mengambil perbedaan antara vektor:
2 1 3 4 2 1 -> -1 2 1 -2 -1
.!
mengubah bukan nol menjadiFALSE
dan nol menjadiTRUE
, sehingga vektor menjadiFALSE FALSE FALSE FALSE FALSE
. Menjumlahkan itu untuk memeriksa apakah adaTRUE
s (TRUE
akan menyiratkandiff=0
-> dua angka berurutan yang sama). Kita dapat kembali membalikkan ini dengan!
untuk mendapatkan boolean pada apakah ada nilai berturut-turut dalam permutasi.Penjumlahan dari boolean ini memberi kita jumlah total permutasi di mana ini bukan masalahnya.
Tidak berfungsi untuk
[8,3,2]
testcase karena membutuhkan vektor 46GB untuk menyimpan permutasi tersebut.sumber
Jelly , 11 byte
Cobalah online!
sumber
Python 2 ,
14089 byteFormat input
'aaaabbb'
untuk test case[4,3]
.Cobalah online!
sumber
Sekam , 8 byte
Cobalah online! Mengambil input dalam format
"aaabb"
untuk[3,2]
. Waktu habis pada test case terpanjang.Penjelasan
Tidak ada yang mewah di sini, hanya menghitung permutasi unik di mana semua kelompok elemen yang berdekatan memiliki panjang 1.
sumber
Ruby,
8476 byteFungsi lambda rekursif. Lihatlah setiap kemungkinan warna dan dosis pencarian pohon rekursif, menghitung berapa kali menggunakan semua garis.
Penjelasan (untuk versi lama):
sumber
x=p
sebagai kondisi awal?p
bertindak sebagai aliasnil
dalam kasus ini dan harus memenuhi cek yang digunakannya.MATL ,
118 byteFormat input
[1 1 1 1 2 2 2]
untuk[4 3]
, dll.Kehabisan memori untuk test case terakhir.
Cobalah online!
Penjelasan
sumber