Hier ist ein Programmierpuzzle für Sie:

Wenn Sie beispielsweise eine Liste mit Paaren von Zeichenfolgen und entsprechenden Zahlen angeben, [[A,37],[B,27],[C,21],[D,11],[E,10],[F,9],[G,3],[H,2]]geben Sie eine weitere Liste aus, die nur die Zeichenfolgen enthält:

1. Die Gesamtanzahl aller Zeichenfolgen sollte genau der entsprechenden Anzahl in den Eingabedaten entsprechen.

2. In der Sequenz sollte keine Zeichenfolge nebeneinander wiederholt werden, und jede Zeichenfolge sollte in der Ausgabeliste angezeigt werden.

3. Die Auswahl der nächsten Zeichenfolge sollte nach dem Zufallsprinzip erfolgen, sofern nicht mehr als zwei Regeln verletzt werden. Jede Lösung sollte mit einer Wahrscheinlichkeit ungleich Null ausgewählt werden.

4. Wenn keine Kombination möglich ist, sollte die Ausgabe gerade sein 0.

Die Eingabeliste kann in beliebiger Reihenfolge (sortiert oder unsortiert) angegeben werden, und die Zeichenfolgen in der Liste können beliebig lang sein.

Sample Output für den obigen Sample Input 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]

Eingabebeispiel 2:

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

Ausgang für zweiten Eingang:

0

da keine liste nach regeln möglich.

Beispieleingang 3:

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

gültige Ausgabe: [AC,BD,AC,BD,AC]

ungültige Ausgabe: [AC,BD,AC,AC,BD]

Wenn weitere Klarstellungen erforderlich sind, zögern Sie bitte nicht, mich in den Kommentaren darauf hinzuweisen, und ich werde unverzüglich entsprechend handeln.

Das ist Code-Golf , also gewinnt der kürzeste Code in Bytes für jede Sprache!

Gelee , 11 Bytes

Œṙ'Œ!⁻ƝẠ$ƇX

Probieren Sie es 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.

Gelee , 17 Bytes

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

Probieren Sie es 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]

Probieren Sie es online!

Autsch! Viel schwieriger mit Regel 3 ... :). Ich versuche immer noch, das zu vermeidenO(n!) Ansatz , damit er alle Testfälle irgendwann vor dem Hitzetod des Universums bewältigen kann ...

Algorithmus: Angenommen, die Gesamtsumme der Zeichenfolgenanzahl ist t. Wenn eine beliebige Zeichenfolge eine Zählung hat nmit 2*n>t+1, dann ist es nicht möglich , die Auflagen zu erfüllen. Deshalb, wenn eine beliebige Zeichenfolge ( mit Ausnahme der zuvor Auserwählte) Zahl hat nmit 2*n=t+1, dann müssen wir als nächstes die Zeichenfolge wählen. Andernfalls können wir zufällig eine beliebige Zeichenfolge auswählen, die nicht die zuvor ausgewählte Zeichenfolge ist.

R , 148 141 Bytes

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)

Probieren Sie es online! (Ich habe es kopiert combinat::permnund genanntcombinatXXpermn dort .)

Brute Force O (n!) Lösung.

Verwendet permnaus dem combinatPaket, um alle möglichen Bestellungen zu generieren. Überprüfen Sie dann, ob die Regeln eingehalten werden, und wählen Sie eine davon nach dem Zufallsprinzip aus.

JavaScript, 112 Bytes

Beim ersten Durchgang folgt (hoffentlich) noch mehr Golf.

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

Probieren Sie es online aus

J 60 53 Bytes

-7 danke an FrownyFrog

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

Original

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

ungolfed

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

Verbesserungsvorschläge willkommen.

Probieren Sie es 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

Probieren Sie es online!

Holzkohle , 38 Bytes

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

Probieren Sie es online!Link ist eine ausführliche Version des Codes. Erläuterung:

ＷΦθ§κ¹«

Wiederholen, solange mindestens eine Zählung ungleich Null vorliegt.

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

Finden Sie eine Zahl, die mehr als die Hälfte des Restes ausmacht.

∨...ι

Wenn es keinen gab, nehmen Sie einfach die früher gefilterten Zählungen ungleich Null.

Φ...¬⁼κυ

Filtern Sie den zuletzt ausgegebenen String heraus.

≔‽∨...υ

Ordnen Sie der letzten Ausgabezeichenfolge ein zufälliges Element aus der ersten nicht leeren der beiden obigen Listen zu. Beachten Sie, dass das Programm an dieser Stelle abstürzt, wenn eine unmögliche Kombination eingegeben wird.

§υ⁰

Drucken Sie die Zeichenfolge.

⊞υ⊖⊟υ

Verringern Sie die Anzahl.

Ruby , 85 Bytes

Der Brute-Force-Ansatz (danke Jonah für die Idee).

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

Probieren Sie es online!

Rubin , 108 100 96 Bytes

Bisher der Bogosort-Ansatz

->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)}

Probieren Sie es online!

Rust 633 Bytes

Was dies ein wenig anders macht als die anderen, ist die Idee, die Strings durch Simulation eines physikalischen Systems neu anzuordnen. Jede Zeichenfolge wird zuerst die entsprechende Anzahl von Malen dupliziert. Dann wird jede einzelne Zeichenfolge als ein Teil in einem Raum behandelt. Zwei Partikel mit demselben String-Wert "stoßen" sich gegenseitig ab, während sich zwei Partikel mit unterschiedlichen Werten gegenseitig anziehen. Wenn wir zum Beispiel mit AAAAAAABBBBCC beginnen, hebt sich das As gegenseitig auf, entfernt sich voneinander und ermöglicht den Bs, sich zwischen ihnen zu bewegen. Mit der Zeit entsteht eine schöne Partikelmischung. Nach jeder Iteration der 'Partikelbewegung' prüft das Programm, ob keine Partikel nebeneinander liegen, stoppt und gibt den Status des Systems aus, bei dem es sich einfach um die Liste der Zeichenfolgen in der angegebenen Reihenfolge handelt, wie sie im eindimensionalen Raum erscheinen.

Wenn es nun darum geht, dieses physikalische System tatsächlich zu implementieren, wurde zunächst die altmodische PC-Demo / Spieltechnik verwendet, um die Position und Geschwindigkeit der einzelnen Partikel als Zahlen zu speichern und dann durch Iterationen zu aktualisieren, um Position und Geschwindigkeit zu aktualisieren. Bei jeder Iteration addieren wir Geschwindigkeit zu Position (Bewegung) und Beschleunigung zu Geschwindigkeit (Änderung der Bewegungsrate) und berechnen die Beschleunigung (Ermittlung der Kraft auf das Teilchen). Zur Vereinfachung berechnet das System nicht die Kraft auf jedes Partikel basierend auf allen anderen Partikeln, sondern überprüft nur die Partikel, die unmittelbar benachbart sind. Es gab auch einen "Dämpfungseffekt", damit Partikel nicht zu stark beschleunigen und ins Unendliche fliegen (Geschwindigkeit wird zum Beispiel bei jedem Schritt um x Prozent verringert).

Durch den Prozess des Golfspiels wurde das Ganze jedoch drastisch reduziert und vereinfacht. Jetzt "teleportieren" sie sich einfach, anstatt dass zwei Teilchen sich gegenseitig abstoßen. Verschiedene Partikel "scooten" einfach ein bisschen, um Stagnation im System zu verhindern. Wenn beispielsweise A neben A steht, wird es teleportiert. Wenn A neben B steht, verschiebt es sich nur geringfügig. Anschließend wird geprüft, ob die Bedingungen erfüllt sind (keine ähnlichen Partikel nebeneinander), und die Zeichenfolgen werden in der Reihenfolge gedruckt, basierend auf ihrer Position im 1-d-Raum. Es ist fast eher ein Sortieralgorithmus als eine Simulation - andererseits könnte man Sortieralgorithmen als eine Form des simulierten "Driftens" auf der Basis von "Masse" sehen. Ich schweife ab.

Wie auch immer, dies ist eines meiner ersten Rust-Programme, also habe ich nach einigen Stunden Golfspielen aufgegeben, obwohl es dort immer noch Gelegenheiten geben könnte. Das Parsing-Bit ist schwierig für mich. Es liest die Eingabezeichenfolge von der Standardeingabe. Falls gewünscht, könnte dies durch "let mut s =" [[A, 3], [B, 2]] "ersetzt werden. Aber im Moment mache ich ein Echo [[A, 3], [B, 2]] cargo run 'in der Kommandozeile.

Die Berechnung des Anhaltens ist ein kleines Problem. Wie kann festgestellt werden, ob ein gültiger Status des Systems niemals erreicht wird? Der erste Plan bestand darin, festzustellen, ob der 'aktuelle' Zustand jemals einen alten Zustand wiederholt hat, beispielsweise wenn sich ACCC in CACC ändert, aber dann wieder in ACCC, wissen wir, dass das Programm niemals beendet wird, da es nur pseudozufällig ist. Es sollte dann aufgeben und 0 ausgeben, wenn das passiert ist. Dies schien jedoch eine enorme Menge an Rust-Code zu sein. Stattdessen entschied ich, dass es wahrscheinlich hängen bleibt und niemals einen stabilen Zustand erreichen wird, wenn es eine große Anzahl von Iterationen durchläuft. Daher gibt es 0 aus und stoppt. Wie viele? Die Anzahl der Partikel im Quadrat.

Code:

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)

Probieren Sie es 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;}

Probieren Sie es online!

Dies kehrt niemals zurück, wenn es keine Lösungen gibt.