Inilah teka-teki pemrograman untuk Anda:

Diberikan daftar pasangan string dan angka yang sesuai, misalnya [[A,37],[B,27],[C,21],[D,11],[E,10],[F,9],[G,3],[H,2]],, menampilkan daftar lain yang hanya memiliki string dengan cara berikut:

1. Jumlah total dari string apa pun harus sama persis dengan angka terkait dalam data input.

2. Tidak ada string yang harus diulang berdekatan dalam urutan, dan setiap string harus muncul dalam daftar output.

3. Pemilihan string selanjutnya harus dilakukan secara acak selama mereka tidak melanggar dua aturan di atas. Setiap solusi harus memiliki probabilitas yang tidak nol untuk dipilih.

4. Jika tidak ada kombinasi yang memungkinkan, hasilnya harus adil 0.

Daftar input dapat diberikan dalam urutan apa pun (diurutkan atau tidak disortir), dan string dalam daftar mungkin panjang.

Output sampel untuk input sampel di atas 1

[A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,C,A,C,A,C,A,C,A,C,A,C,A,C,A,C,A,C,A,C,D,C,D,C,D,C,D,C,D,C,D,C,D,C,D,C,D,C,D,C,D,C,E,F,E,F,E,F,E,F,E,F,E,F,E,F,E,F,E,F,E,G,H,G,H,G]

Masukkan sampel 2:

[[A,6],[B,1],[C,1]]

Output untuk input kedua:

0

karena tidak ada daftar yang mungkin berdasarkan aturan.

Masukan sampel 3:

[[AC,3],[BD,2]]

output yang valid: [AC,BD,AC,BD,AC]

keluaran tidak valid: [AC,BD,AC,AC,BD]

Jika klarifikasi lebih lanjut diperlukan, tolong, jangan ragu untuk memberi tahu saya di komentar dan saya akan segera bertindak sesuai.

Ini adalah kode-golf , jadi kode terpendek dalam byte untuk setiap bahasa akan menang!

Jelly , 11 byte

Œṙ'Œ!⁻ƝẠ$ƇX

Cobalah online!

Œṙ'Œ!⁻ƝẠ$ƇX Arguments: z
  '         Flat: Apply link directly to x, ignoring its left and right depth properties
Œṙ            Run-length decode
   Œ!       Permutations of x
         Ƈ  Filter; keep elements of x for which the link returns a truthy result
        $     ≥2-link monadic chain
      Ɲ         Apply link on overlapping pairs (non-wrapping)
     ⁻            x != y
       Ạ        Check if all elements of x have a truthy value (+vacuous truth)
          X Pick a random element of x; return 0 if the list is empty.

Jeli , 17 byte

Wẋ¥Ɲ€ẎẎŒ!Œɠ’SƊÐḟX

Cobalah online!

Python 2 , 114 189 185 174 bytes

from random import*
a=input()
s=u=[]
while a:x,y=a.pop(a.index(next((w for w in a if w[1]>sum(v[1]for v in a+u)/2),choice(a))));s=s+[x];a+=u;u=[[x,y-1]]*(y>1)
print[s,0][y>1]

Cobalah online!

Aduh! Jauh lebih sulit dengan aturan 3 ... :). Masih berusaha menghindariO(n!) pendekatan, sehingga dapat menangani semua kasus uji sebelum kematian panas alam semesta ...

Algoritma: anggap jumlah total jumlah string adalah t. Jika string memiliki jumlah ndengan 2*n>t+1, maka tidak mungkin untuk memenuhi kendala. Oleh karena itu, jika string (tidak termasuk orang yang dipilih sebelumnya) memiliki count ndengan 2*n=t+1, maka kita harus memilih string yang berikutnya. Jika tidak, kita dapat memilih secara acak string apa pun yang bukan string yang dipilih sebelumnya.

R , 148 141 byte

function(x,y,p=combinatXXpermn(rep(seq(y),y)),q=which(sapply(lapply(p,diff),all)))"if"(n<-sum(q|1),"if"(n-1,x[p[[sample(q,1)]]],x[p[[q]]]),0)

Cobalah online! (Saya sudah menyalin combinat::permndan memanggilnya di combinatXXpermnsana.)

Solusi Brute force O (n!).

Penggunaan permndari combinatpaket untuk menghasilkan semua kemungkinan pemesanan. Kemudian periksa untuk melihat apakah ada yang mengikuti aturan, dan mengambil salah satu dari mereka secara acak.

JavaScript, 112 byte

Pass pertama di ini, lebih banyak golf untuk (mudah-mudahan) mengikuti.

f=([i,...a],o=[])=>a.sort((x,y)=>(y[1]-x[1])*Math.random()-n*.5,n=--i[1],o.push(i[0]))+a?f(n?[...a,i]:a,o):n?0:o

Cobalah online

J, 60 53 byte

-7 Terima kasih kepada FrownyFrog

(?@#{])@(#~*/@(2~:/\])"1)@(]i.@!@#@;A.;) ::0(#~>)/&.>

asli

(?@#{])@(#~2&([:*/~:/\)"1)@(A.~i.@!@#)@;@:(([#~>@])/&.>) ::0

ungolfed

(?@# { ])@(#~ 2&([: */ ~:/\)"1)@(A.~ i.@!@#)@;@:(([ #~ >@])/&.>) ::0

Saran untuk penyambutan selamat datang.

Cobalah online!

JavaScript (ES6), 160 byte

a=>(g=(a,m=[])=>a.map((v,n)=>v==m[0]||g(a.filter(_=>n--),[v,...m]))>[]?0:r=m)(a.reduce((p,[v,n])=>[...p,...Array(n).fill(v)],r=[]).sort(_=>Math.random()-.5))||r

Cobalah online!

Arang , 38 byte

ＷΦθ§κ¹«≔‽Φ∨Φι›⊗§κ¹ΣＥι§μ¹ι¬⁼κυυ§υ⁰⊞υ⊖⊟υ

Cobalah online! Tautan adalah untuk mengucapkan versi kode. Penjelasan:

ＷΦθ§κ¹«

Ulangi sementara setidaknya ada satu hitungan bukan nol.

Φι›⊗§κ¹ΣＥι§μ¹

Temukan hitungan yang membentuk lebih dari setengah sisanya.

∨...ι

Jika tidak ada, maka ambil saja hitungan non-nol yang difilter sebelumnya.

Φ...¬⁼κυ

Memfilter string yang keluar terakhir kali.

≔‽∨...υ

Tetapkan elemen acak dari non-kosong pertama dari dua daftar di atas ke string keluaran terakhir. Perhatikan bahwa jika kombinasi mustahil dimasukkan, program akan macet pada saat ini.

§υ⁰

Cetak string.

⊞υ⊖⊟υ

Kurangi jumlahnya.

Ruby , 85 byte

Pendekatan brute force (terima kasih kepada Jonah atas idenya).

->l{l.flat_map{|a,b|[a]*b}.permutation.select{|p|r=0;p.all?{|a|a!=r&&r=a}}.sample||0}

Cobalah online!

Ruby , 108 100 96 byte

Sebelumnya, pendekatan Bogosort

->l{w=[];l.map{|a,b|w+=[a]*b;b}.max*2>w.size+1?0:(w.shuffle!until(r='';w.all?{|a|a!=r&&r=a});w)}

Cobalah online!

Karat 633 byte

Apa yang membuat ini sedikit berbeda dari yang lain adalah bahwa itu dimulai dengan ide untuk mengatur ulang string dengan mensimulasikan sistem fisik. Setiap string pertama kali diduplikasi sesuai jumlah kali. Kemudian setiap string individu diperlakukan sebagai Partikel dalam ruang. Dua partikel dengan nilai string yang sama "saling tolak", sementara dua partikel dengan nilai yang berbeda saling menarik. Sebagai contoh jika kita mulai dengan AAAAAAABBBBCC, As akan saling mencabut, menjauh satu sama lain, memungkinkan B untuk bergerak di antara mereka. Seiring waktu, ini mencapai campuran partikel yang bagus. Setelah setiap iterasi dari 'gerakan partikel', program memeriksa bahwa tidak ada partikel yang sama berbatasan, kemudian berhenti dan mencetak keadaan sistem, yang hanya daftar string dalam urutan, karena mereka muncul dalam ruang 1 dimensi.

Sekarang, ketika benar-benar menerapkan sistem fisik itu, ia mulai menggunakan teknik demo / game PC kuno, untuk menyimpan setiap posisi dan kecepatan partikel sebagai angka, kemudian melalui iterasi untuk memperbarui posisi dan kecepatan. Pada setiap iterasi, kami menambahkan kecepatan ke posisi (gerakan), dan menambahkan akselerasi ke kecepatan (perubahan laju gerakan), dan menghitung akselerasi (menemukan gaya pada partikel). Untuk menyederhanakan, sistem tidak menghitung kekuatan pada setiap partikel berdasarkan pada semua partikel lain - hanya memeriksa partikel yang berdekatan. Ada juga efek 'redaman' sehingga partikel tidak akan berakselerasi terlalu banyak dan terbang hingga tak terbatas (kecepatan berkurang oleh x persentase setiap langkah, misalnya).

Namun, melalui proses bermain golf, semua ini ditebang dan disederhanakan secara drastis. Sekarang, alih-alih dua partikel yang sama saling tolak, mereka hanya 'berteleportasi'. Partikel yang berbeda hanya 'bergeser' sedikit untuk mencegah stagnasi dalam sistem. Sebagai contoh jika A di sebelah A ia akan teleport. Jika A di sebelah B hanya sedikit bergeser. Kemudian memeriksa apakah kondisi terpenuhi (tidak seperti partikel yang berdekatan) dan mencetak string secara berurutan, berdasarkan posisi mereka dalam ruang 1-d. Ini hampir lebih seperti algoritma penyortiran daripada simulasi - sekali lagi, orang bisa melihat algoritma penyortiran sebagai bentuk simulasi 'drifting' berdasarkan 'massa'. Saya ngelantur.

Bagaimanapun, ini adalah salah satu program Rust pertama saya jadi saya menyerah setelah beberapa jam bermain golf, meskipun mungkin masih ada peluang di sana. Agak sulit bagi saya. Bunyinya string input dari input standar. Jika diinginkan, itu bisa diganti dengan "let mut s =" [[A, 3], [B, 2]] ". Tetapi sekarang saya melakukan 'echo [[A, 3], [B, 2]] | kargo berjalan 'di baris perintah.

Perhitungan berhenti sedikit masalah. Bagaimana cara mendeteksi jika keadaan sistem yang valid tidak akan pernah tercapai? Rencana pertama adalah untuk mendeteksi apakah keadaan 'saat ini' pernah mengulangi keadaan lama, misalnya jika ACCC berubah menjadi CACC tetapi kemudian kembali ke ACCC, kita tahu program tidak akan pernah berakhir, karena itu hanya pseudo-acak. Maka harus menyerah dan mencetak 0 jika itu terjadi. Namun ini tampaknya seperti sejumlah besar kode Rust, jadi alih-alih saya hanya memutuskan bahwa jika melewati banyak iterasi, mungkin macet dan tidak akan pernah mencapai kondisi mapan, sehingga mencetak 0 dan berhenti. Berapa banyak? Jumlah partikel kuadrat.

Kode:

extern crate regex;
struct P {s:String,x:i32,v:i32}
fn main() {
    let (mut i,mut j,mut p,mut s)=(0,0,Vec::new(),String::new());
    std::io::stdin().read_line(&mut s);
    for c in regex::Regex::new(r"([A-Z]+),(\d+)").unwrap().captures_iter(&s) {
        for _j in 0..c[2].parse().unwrap() {p.push(P{s:c[1].to_string(),x:i,v:0});i+=1;}
    }
    let l=p.len(); while i>1 {
        j+=1;i=1;p.sort_by_key(|k| k.x);
        for m in 0..l {
            let n=(m+1)%l;
            if p[m].s==p[n].s {p[m].v=p[m].x;if n!=0 {i=2}} else {p[m].v=1}
            p[m].x=(p[m].x+p[m].v)%l as i32;
        }
        if j>l*l{p.truncate(1);p[0].s="0".to_string();i=1}
    }
    for k in &p{print!("{}",k.s)};println!();
}

JavaScript (Node.js) , 249 byte

l=>(a=[],g=(r,s)=>s.length?s.forEach((x,i)=>g([...r,x],s.filter((y,j)=>j-i))):a.push(r),g([],l.reduce(((a,x)=>[...a, ...(x[0]+' ').repeat(x[1]).split(' ')]),[]).filter(x=>x)),p=a.filter(a=>a.every((x,i)=>x!=a[i+1])),p[~~(Math.random()*p.length)]||0)

Cobalah online!

Java (JDK 10) , 191 byte

S->N->{var l=new java.util.Stack();int i=0,j;for(var s:S)for(j=N[i++];j-->0;)l.add(s);for(;i>0;){i=0;java.util.Collections.shuffle(l);for(var s:S)if(s.join("",l).contains(s+s))i++;}return l;}

Cobalah online!

Ini tidak pernah kembali jika tidak ada solusi.