Oto puzzle programowania dla Ciebie:

Biorąc na przykład listę par ciągów znaków i odpowiadających im liczb, [[A,37],[B,27],[C,21],[D,11],[E,10],[F,9],[G,3],[H,2]]wypisz inną listę, która będzie miała tylko ciągi znaków w następujący sposób:

1. Całkowita liczba dowolnego łańcucha powinna być dokładnie równa odpowiadającej mu liczbie w danych wejściowych.

2. Żaden ciąg nie powinien być powtarzany w sekwencji obok siebie, a każdy ciąg powinien pojawiać się na liście wyników.

3. Wyboru następnego ciągu należy dokonać losowo, o ile nie przekroczą one dwóch reguł. Każde rozwiązanie powinno mieć niezerowe prawdopodobieństwo wyboru.

4. Jeśli żadna kombinacja nie jest możliwa, wynik powinien być sprawiedliwy 0.

Lista wejściowa może być podana w dowolnej kolejności (posortowana lub nieposortowana), a ciągi na liście mogą mieć dowolną długość.

Przykładowy wynik dla powyższego przykładowego wejścia 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]

Próbka wejściowa 2:

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

Wyjście dla drugiego wejścia:

0

ponieważ żadna lista nie jest możliwa na podstawie reguł.

Przykładowe wejście 3:

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

prawidłowe wyjście: [AC,BD,AC,BD,AC]

nieprawidłowe wyjście: [AC,BD,AC,AC,BD]

Jeśli potrzebne są dalsze wyjaśnienia, proszę nie wahaj się powiedzieć mi w komentarzach, a niezwłocznie podejmę odpowiednie działania.

To jest golf golfowy , więc wygrywa najkrótszy kod w bajtach dla każdego języka!

Galaretka , 11 bajtów

Œṙ'Œ!⁻ƝẠ$ƇX

Wypróbuj 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.

Galaretka , 17 bajtów

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

Wypróbuj online!

Python 2 , 114 189 185 174 bajtów

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]

Wypróbuj online!

Auć! Znacznie trudniej z zasadą 3 ... :). Wciąż próbuję uniknąćO(n!) podejścia, aby mógł obsłużyć wszystkie przypadki testowe przed śmiercią wszechświata przed upałem ...

Algorytm: załóżmy, że całkowita suma ciągów znaków wynosi t. Jeśli dowolny ciąg ma liczyć nz 2*n>t+1, to nie jest możliwe do spełnienia ograniczeń. Dlatego też, jeśli dowolny ciąg znaków (z wyłączeniem wcześniej wybrańca) musi liczyć nsię 2*n=t+1, to musimy wybrać ten ciąg obok. W przeciwnym razie możemy wybrać losowo dowolny ciąg, który nie jest wcześniej wybranym ciągiem.

R , 148 141 bajtów

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)

Wypróbuj online! (Skopiowałem combinat::permni nazwałem to combinatXXpermntam.)

Rozwiązanie Brute Force O (n!).

Korzysta permnz combinatpakietu, aby wygenerować wszystkie możliwe uporządkowania. Następnie sprawdza, czy ktoś przestrzega zasad, i wybiera jedną z nich losowo.

JavaScript, 112 bajtów

Pierwsze przejście, więcej golfa do (miejmy nadzieję).

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

Wypróbuj online

J, 60 53 bajtów

-7 dzięki FrownyFrog

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

oryginalny

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

bez golfa

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

Sugestie dotyczące ulepszeń mile widziane.

Wypróbuj online!

JavaScript (ES6), 160 bajtów

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

Wypróbuj online!

Węgiel drzewny , 38 bajtów

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

Wypróbuj online! Link jest do pełnej wersji kodu. Wyjaśnienie:

ＷΦθ§κ¹«

Powtarzaj, dopóki jest co najmniej jedna niezerowa liczba.

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

Znajdź dowolną liczbę, która stanowi ponad połowę pozostałej części.

∨...ι

Jeśli nie było, po prostu weź niezerowe liczby przefiltrowane wcześniej.

Φ...¬⁼κυ

Odfiltruj ciąg, który został wyprowadzony ostatnim razem.

≔‽∨...υ

Przypisz losowy element z pierwszego niepustego z powyższych dwóch list do ostatniego ciągu wyjściowego. Zauważ, że jeśli zostanie wprowadzona niemożliwa kombinacja, program zawiesi się w tym momencie.

§υ⁰

Wydrukuj ciąg.

⊞υ⊖⊟υ

Zmniejsz jego liczbę.

Rubin , 85 bajtów

Podejście brutalnej siły (dzięki Jonasz za pomysł).

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

Wypróbuj online!

Ruby , 108 100 96 bajtów

Wcześniej podejście 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)}

Wypróbuj online!

Rdza 633 bajtów

To, co czyni to trochę innym niż pozostałe, to fakt, że zaczął się od pomysłu na zmianę kolejności ciągów poprzez symulację układu fizycznego. Każdy ciąg jest najpierw duplikowany odpowiednią liczbę razy. Następnie każdy pojedynczy ciąg znaków jest traktowany jako cząstka w przestrzeni. Dwie cząstki o tej samej wartości łańcucha „odpychają się”, a dwie cząstki o różnych wartościach przyciągają się. Na przykład, jeśli zaczniemy od AAAAAAABBBBCC, As zniesie się nawzajem, oddalając się od siebie, umożliwiając Bs przemieszczanie się między nimi. Z czasem osiąga to przyjemną mieszankę cząstek. Po każdej iteracji „ruchu cząstek” program sprawdza, czy żadne cząstki nie sąsiadują ze sobą, a następnie zatrzymuje się i drukuje stan układu, który jest po prostu listą łańcuchów w kolejności, tak jak pojawiają się w przestrzeni 1-wymiarowej.

Teraz, jeśli chodzi o rzeczywiste wdrożenie tego systemu fizycznego, zaczęło się od użycia staroświeckiej techniki demonstracyjnej / gry na PC, aby zapisać pozycję i prędkość każdej cząstki jako liczby, a następnie przejść przez iteracje, aby zaktualizować pozycję i prędkość. Przy każdej iteracji dodajemy prędkość do pozycji (ruch) i dodajemy przyspieszenie do prędkości (zmiana prędkości ruchu) i obliczamy przyspieszenie (znalezienie siły na cząsteczce). Aby uprościć, system nie oblicza siły na każdą cząsteczkę na podstawie wszystkich innych cząstek - sprawdza tylko cząstki bezpośrednio sąsiadujące. Był także efekt „tłumienia”, dzięki czemu cząstki nie przyspieszałyby zbytnio i nie odlatowały do ​​nieskończoności (na przykład prędkość jest zmniejszana o x procent z każdym krokiem).

Jednak w trakcie gry w golfa cała ta sprawa została zredukowana i drastycznie uproszczona. Teraz zamiast dwóch podobnych sobie cząstek odpychających się, po prostu „teleportują się”. Różne cząstki po prostu „odrobinę” skracają, aby zapobiec stagnacji w systemie. Na przykład, jeśli A znajduje się obok A, teleportuje się. Jeśli A znajduje się obok B, tylko nieznacznie się przesunie. Następnie sprawdza, czy warunki są spełnione (żadnych sąsiadujących cząstek) i drukuje ciągi w kolejności, na podstawie ich położenia w przestrzeni 1-d. Jest to prawie bardziej algorytm sortowania niż symulacja - z drugiej strony algorytmy sortowania można postrzegać jako formę symulowanego „dryfowania” opartego na „masie”. Robię dygresję.

Tak czy inaczej, jest to jeden z moich pierwszych programów Rust, więc zrezygnowałem po kilku godzinach gry w golfa, choć wciąż mogą tam być możliwości. Bit przetwarzania jest dla mnie trudny. Odczytuje ciąg wejściowy ze standardowego wejścia. W razie potrzeby można to zastąpić słowem „let mut s =” [[A, 3], [B, 2]] ”. Ale teraz„ echo [[A, 3], [B, 2]] | cargo run ”w wierszu poleceń.

Obliczenie zatrzymania jest trochę problemem. Jak wykryć, czy prawidłowy stan systemu nigdy nie zostanie osiągnięty? Pierwszym planem było wykrycie, czy „bieżący” stan kiedykolwiek powtórzył stary stan, na przykład, jeśli ACCC zmieni się na CACC, ale potem z powrotem na ACCC, wiemy, że program nigdy się nie zakończy, ponieważ jest tylko pseudolosowy. Następnie powinien się poddać i wydrukować 0, jeśli tak się stanie. Wydawało się to jednak ogromną ilością kodu Rust, więc zamiast tego zdecydowałem, że jeśli przejdzie przez dużą liczbę iteracji, prawdopodobnie utknie i nigdy nie osiągnie stanu ustalonego, więc wypisuje 0 i zatrzymuje się. Ile? Liczba cząstek podniesiona do kwadratu.

Kod:

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 bajtów

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)

Wypróbuj online!

Java (JDK 10) , 191 bajtów

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

Wypróbuj online!

To nigdy nie powraca, jeśli nie ma rozwiązań.