Aquí hay un rompecabezas de programación para ti:

Dada una lista de pares de cadenas y números correspondientes, por ejemplo [[A,37],[B,27],[C,21],[D,11],[E,10],[F,9],[G,3],[H,2]], genera otra lista que tendrá solo las cadenas de la siguiente manera:

1. El recuento total de cualquier cadena debe ser exactamente igual a su número correspondiente en los datos de entrada.

2. No se debe repetir ninguna cadena adyacente en la secuencia, y cada cadena debe aparecer en la lista de salida.

3. La selección de la siguiente cadena debe hacerse al azar siempre que no rompan por encima de dos reglas. Cada solución debe tener una probabilidad distinta de cero de ser elegida.

4. Si no es posible una combinación, la salida debería ser justa 0.

La lista de entrada se puede dar en cualquier orden (ordenada o no), y las cadenas de la lista pueden tener cualquier longitud.

Salida de muestra para la entrada de muestra anterior 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]

Muestra de entrada 2:

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

Salida para la segunda entrada:

0

ya que no es posible una lista basada en reglas.

Entrada de muestra 3:

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

salida válida: [AC,BD,AC,BD,AC]

salida inválida: [AC,BD,AC,AC,BD]

Si necesita más aclaraciones, no dude en informarme en los comentarios y actuaré de inmediato.

Este es el código de golf , por lo que gana el código más corto en bytes para cada idioma.

Jalea , 11 bytes

Œṙ'Œ!⁻ƝẠ$ƇX

Pruébalo en línea!

Œṙ'Œ!⁻ƝẠ$Ƈ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.

Jalea , 17 bytes

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

Pruébalo en línea!

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]

Pruébalo en línea!

¡Ay! Mucho más difícil con la regla 3 ... :). Todavía trato de evitar el O(n!)enfoque, para que pueda manejar todos los casos de prueba en algún momento antes de la muerte por calor del universo ...

Algoritmo: supongamos que la suma total de los recuentos de cadenas es t. Si cualquier cadena tiene un recuento ncon 2*n>t+1, entonces no es posible satisfacer las restricciones. Por lo tanto, si cualquier cadena (excluyendo el elegido previamente) tiene recuento ncon 2*n=t+1, entonces debemos elegir esa cadena siguiente. De lo contrario, podemos elegir al azar cualquier cadena que no sea la cadena elegida previamente.

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)

Pruébalo en línea! (He copiado combinat::permny lo llamé combinatXXpermnallí).

Fuerza bruta O (n!) Solución.

Usos permndel combinatpaquete para generar todos los pedidos posibles. Luego verifica si alguno sigue las reglas y elige uno de ellos al azar.

JavaScript, 112 bytes

Primer pase en esto, más golf para (con suerte) seguir.

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

Pruébalo en línea

J, 60 53 bytes

-7 gracias a FrownyFrog

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

original

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

sin golf

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

Sugerencias de mejora bienvenida.

Pruébalo en línea!

JavaScript (ES6), 160 bytes

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

Pruébalo en línea!

Carbón , 38 bytes

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

Pruébalo en línea! El enlace es a la versión detallada del código. Explicación:

ＷΦθ§κ¹«

Repita mientras haya al menos un recuento distinto de cero.

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

Encuentre cualquier conteo que represente más de la mitad del resto.

∨...ι

Si no hubo uno, simplemente tome los recuentos distintos de cero filtrados anteriormente.

Φ...¬⁼κυ

Filtre la cadena que salió la última vez.

≔‽∨...υ

Asigne un elemento aleatorio de la primera no vacía de las dos listas anteriores a la última cadena de salida. Tenga en cuenta que si se ingresa una combinación imposible, el programa se bloqueará en este punto.

§υ⁰

Imprime la cadena.

⊞υ⊖⊟υ

Disminuya su recuento.

Ruby , 85 bytes

El enfoque de la fuerza bruta (gracias a Jonás por la idea).

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

Pruébalo en línea!

Ruby , 108100 96 bytes

Anteriormente, el enfoque de 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)}

Pruébalo en línea!

Rust 633 bytes

Lo que hace que esto sea un poco diferente a los demás es que comenzó con la idea de reorganizar las cadenas simulando un sistema físico. Cada cadena se duplica primero el número apropiado de veces. Luego, cada cadena individual se trata como una Partícula en un espacio. Dos partículas con el mismo valor de cadena se "repelen" entre sí, mientras que dos partículas con valores diferentes se atraen entre sí. Por ejemplo, si comenzamos con AAAAAAABBBBCC, los As se derogarán entre sí, alejándose unos de otros, permitiendo que los Bs se muevan entre ellos. Con el tiempo esto alcanza una buena mezcla de partículas. Después de cada iteración de "movimiento de partículas", el programa verifica que no haya partículas iguales, luego se detiene e imprime el estado del sistema, que es simplemente la lista de cadenas en orden, tal como aparecen en el espacio unidimensional.

Ahora, cuando se trata de implementar ese sistema físico, comenzó utilizando la antigua técnica de demostración / juego de PC, para almacenar cada posición y velocidad de las partículas como números, luego pasa por iteraciones para actualizar la posición y la velocidad. En cada iteración, estamos agregando velocidad a la posición (movimiento), y agregando aceleración a la velocidad (cambio en la velocidad de movimiento), y calculando la aceleración (encontrando la fuerza sobre la partícula). Para simplificar, el sistema no calcula la fuerza sobre cada partícula en función de todas las demás partículas, solo verifica las partículas inmediatamente adyacentes. También hubo un efecto de 'amortiguación' para que las partículas no se aceleren demasiado y vuelen hasta el infinito (la velocidad se reduce en un porcentaje x cada paso, por ejemplo).

A través del proceso de golf, sin embargo, todo esto fue cortado y simplificado drásticamente. Ahora, en lugar de dos partículas iguales que se repelen, simplemente se "teletransportan". Las diferentes partículas simplemente se escapan un poco para evitar el estancamiento en el sistema. Por ejemplo, si A está al lado de A, se teletransportará. Si A está al lado de B, solo cambiará ligeramente. Luego verifica si se cumplen las condiciones (no hay partículas adyacentes) e imprime las cadenas en orden, en función de su posición en el espacio 1-d. Es casi más como un algoritmo de clasificación que una simulación; de nuevo, uno podría ver los algoritmos de clasificación como una forma de 'deriva' simulada basada en 'masa'. Estoy divagando.

De todos modos, este es uno de mis primeros programas de Rust, así que me di por vencido después de varias horas de golf, aunque todavía podría haber oportunidades allí. El análisis de bits es difícil para mí. Lee la cadena de entrada de la entrada estándar. Si lo desea, podría reemplazarse con "let mut s =" [[A, 3], [B, 2]] ". Pero ahora sí 'echo [[A, 3], [B, 2]] | carga "en la línea de comando.

El cálculo de la detención es un poco problemático. ¿Cómo detectar si nunca se alcanzará un estado válido del sistema? El primer plan fue detectar si el estado 'actual' alguna vez repitió un estado anterior, por ejemplo, si ACCC cambia a CACC pero luego regresamos a ACCC, sabemos que el programa nunca terminará, ya que es solo pseudoaleatorio. Entonces debería rendirse e imprimir 0 si eso sucediera. Sin embargo, esto parecía una gran cantidad de código Rust, por lo que en su lugar decidí que si pasa por un gran número de iteraciones, probablemente esté bloqueado y nunca alcanzará un estado estable, por lo que imprime 0 y se detiene. ¿Cuántos? El número de partículas al cuadrado.

Código:

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 bytes

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)

Pruébalo en línea!

Java (JDK 10) , 191 bytes

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

Pruébalo en línea!

Esto nunca vuelve si no hay soluciones.