Zabawa z ciągami i liczbami

13

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 , więc wygrywa najkrótszy kod w bajtach dla każdego języka!

Stupid_Intern
źródło
Niezłe wyzwanie! Myślę, że jest to trochę nieokreślone przez nasze standardy. Gorąco polecam skorzystanie z The Sandbox, aby uzyskać dużo opinii przed opublikowaniem wyzwania, abyś nie otrzymywał głosów negatywnych ani nie zamykał głosów! :-) Nie mogę się doczekać, aby zobaczyć więcej dobrych wyzwań od ciebie!
Giuseppe,
@Giuseppe dziękuję Spróbuję przejść przez to. Daj mi znać, jeśli będę musiał dodać jakieś szczegóły, jeśli coś przeoczyłem.
Stupid_Intern
1
Czy możemy wziąć 2 dane wejściowe, tylko ciągi znaków i tylko liczby?
FrownyFrog,
użycie wyrażenia „losowy” może być dwuznaczne, kilka z tych rozwiązań używa bibliotek „losowych”, które w rzeczywistości są jedynie pseudolosowe.
Don Bright

Odpowiedzi:

6

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.
Erik the Outgolfer
źródło
Gdyby Œṙnie było wektoryzacji, działałoby bez niego'
dylnan
5

Galaretka , 17 bajtów

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

Wypróbuj online!

HyperNeutrino
źródło
Myślę, ["A", 100], ["B", 3]że kiedy próbuję , nic nie wychodzi.
Stupid_Intern
1
@newguy Generowanie wszystkich permutacji 103 przedmiotów nie jest znane ze swojej szybkości. Dla porównania, wynik po Œ!będzie miał 99029007164861804075467152545817733490901658221144924830052805546998766658416222832141441073883538492653516385977292093222882134415149891584000000000000000000.
Erik the Outgolfer
@newguy To rozwiązanie jest O(n!)krótkie, ale szybkość nie ma znaczenia. Nie próbuj tego z niczym, gdy liczby sumują się do więcej niż około 6-8 lub mniej więcej: P
HyperNeutrino
Może Œṙpomóc?
Arnauld
1
@dylnan Nie sądzę, że to działa na ciągi, z którymi próbowałem ["AT", 3], ["B", 3]i dostałem TBATATBABjako wyjście, co jest złe
Stupid_Intern
5

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.

Chas Brown
źródło
1
@Arnauld: całkowicie tego przegapiłem! naprawione teraz.
Chas Brown,
4

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.

ngm
źródło
n<-sum(n|1)to chyba bajt krótszy. Ale dziwactwo samplez wprowadzeniem długości jednego jest tutaj dość frustrujące.
Giuseppe,
trochę też grałem w golfa, spróbuj tutaj - musiałem usunąć combinatXXpermn z nagłówka, aby link był wystarczająco mały ...
Giuseppe
Miałem coś bardzo podobnego, biorąc dane wejściowe jako ramkę danych. Problem z bruteforce polega na tym, że nie poradzi sobie z wejściami, które są zbyt duże ...
JayCe
@JayCe jest możliwy algorytm nie brutalnej siły, biorąc pod uwagę zasadę 3 tego wyzwania?
ngm
Zgadzam się, że może nie. Byłoby bardziej interesujące bez reguły 3.
JayCe,
3

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

Kudłaty
źródło
1
Dzięki, @Arnauld, tęskniłem za tym. Powinienem był dwukrotnie sprawdzić specyfikację, a nie ślepo podążać za przykładem Chasa. Wdrożyłem szybką poprawkę, będę musiał do niej wrócić później, aby sprawdzić, czy mogę lepiej grać w golfa.
Kudłaty
Tak, trzecia reguła jest odpowiednia dla esolangów, które i tak mogą brutalnie wymusić wszystkie rozwiązania, ale znacznie trudniej jest wdrożyć krótsze algorytmy w innych językach ... BTW: od czasu do czasu wydaje się, że zwraca 0 dla poprawnych wpisów.
Arnauld
Zaimplementowano kolejną szybką poprawkę, @Arnauld - jeśli to nie posortuje, będę musiał usunąć ją ponownie, dopóki nie będę miał więcej czasu, aby się temu przyjrzeć. Uwaga: wziąłem pod uwagę jego słowo, że następny ciąg musi być wybrany losowo, co oznacza, że ​​pierwszy wybór nie musi być losowy.
Shaggy
1
@Shaggy - Zgadzam się, nigdy nie powinieneś ślepo śledzić niczego, co robię! :)
Chas Brown,
3

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!

Jonasz
źródło
Grał w golfa do 53
FrownyFrog,
niesamowity tyvm @FrownyFrog, zaktualizuję post później
Jonah
ups, [:*/2~:/\|:jest dwa razy krótszy
FrownyFrog
2

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!

Arnauld
źródło
2

Węgiel drzewny , 38 bajtów

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

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

WΦθ§κ¹«

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

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

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ę.

Neil
źródło
Powoduje to powstanie nieprawidłowych wyników, takich jak w twoim przykładzie z ["h4x0r", 1337]dołączonym jako ciąg.
ngm
@ngm Zmieniłem układ kodu i teraz ulega awarii, jeśli to zrobisz ... Prawidłowa weryfikacja będzie niestety kosztować więcej bajtów.
Neil
2

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!

GB
źródło
oto jeden za 93: Wypróbuj online!
Jonasz
2

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!();
}
Don Bright
źródło
l2regex
przekazał mi przykłady, które karmiłem, chociaż go nie zmęczyłem. zmodyfikowałem go do pracy w TIO, musisz zmodyfikować „lets = [(„ A ”, 3), („ B ”, 2), („ ZZ ”, 4)]; ' linia, bit.ly/2LubonO
don bright
1

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!

WaffleCohn
źródło
1

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ń.

Olivier Grégoire
źródło