Fun with strings and numbers

Question

Here's a programming puzzle for you:

Given a list of pairs of strings and corresponding numbers, for example, [[A,37],[B,27],[C,21],[D,11],[E,10],[F,9],[G,3],[H,2]], output another list which will have just the strings in the following manner:

1. The total count of any string should be exactly equal to its corresponding number in the input data.

2. No string should be repeated adjacently in the sequence, and every string should appear in the output list.

3. The selection of the next string should be done randomly as long as they don't break above two rules. Each solution should have a non-zero probability of being chosen.

4. If no combination is possible, the output should be just 0.

The input list may be given in any order (sorted or unsorted), and the strings in the list may be of any length.

---

Sample output for the above 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]

---

Input sample 2:

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

Output for second input:

0

since no list possible based on rules.

---

Sample input 3:

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

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

invalid output: [AC,BD,AC,AC,BD]

---

If further clarification is needed, please, do not hesitate to tell me in the comments and I will promptly act accordingly.

This is code-golf, so shortest code in bytes for each language wins!

Answer 1

Jelly, 11 bytes

Œṙ'Œ!⁻ƝẠ$ƇX

Try it 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.

Answer 2

Jelly, 17 bytes

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

Try it online!

Answer 3

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]

Try it online!

Ouch! Much harder with rule 3... :). Still trying to avoid the O(n!) approach, so it can handle all the test cases sometime before the heat death of the universe...

Algorithm: suppose the total sum of the string counts is t. If any string has a count n with 2*n>t+1, then it is not possible to satisfy the constraints. Therefore, if any string (excluding the previously chosen one) has count n with 2*n=t+1, then we must choose that string next. Otherwise, we can choose at random any string which is not the previously chosen string.

Answer 4

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)

Try it online! (I've copied combinat::permn and called it combinatXXpermn there.)

Brute force O(n!) solution.

Uses permn from the combinat package to generate all possible orderings. Then checks to see if any follow the rules, and picks one of those at random.

Answer 5

JavaScript, 112 bytes

First pass at this, more golfing to (hopefully) follow.

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

Try it online

Answer 6

J, 60 53 bytes

-7 thanks to FrownyFrog

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

original

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

ungolfed

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

Suggestions for improvement welcome.

Try it online!

Answer 7

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

Try it online!

Answer 8

Charcoal, 38 bytes

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

Try it online! Link is to verbose version of code. Explanation:

ＷΦθ§κ¹«

Repeat while there is at least one non-zero count.

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

Find any count that makes up more than half the remainder.

∨...ι

If there wasn't one, then just take the non-zero counts filtered earlier.

Φ...¬⁼κυ

Filter out the string that was output last time.

≔‽∨...υ

Assign a random element from the first non-empty of the above two lists to the last output string. Note that if an impossible combination is entered, the program will crash at this point.

§υ⁰

Print the string.

⊞υ⊖⊟υ

Decrement its count.

Answer 9

Ruby, 85 bytes

The brute force approach (thanks Jonah for the idea).

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

Try it online!

Ruby, 108 100 96 bytes

Previously, the Bogosort approach

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

Try it online!

Answer 10

Rust 633 bytes

What makes this a little different than the others is that it started with the idea to rearrange the strings by simulating a physical system. Each string is first duplicated the appropriate number of times. Then each individual string is treated as a Particle in a space. Two particles with the same string value "repel" each other, while two particles with different values attract each other. For example if we begin with AAAAAAABBBBCC, the As will repeal each other, moving away from each other, allowing the Bs to move inbetween them. Over time this reaches a nice mixture of particles. After each iteration of 'particle movement', the program checks that no same-particles are adjacent, then stops and prints the state of the system, which is simply the list of strings in order, as they appear in the 1 dimensional space.

Now, when it comes to actually implementing that physical system, it started out as using the old fashiond PC demo/game technique, to store each particles position and velocity as numbers, then go through iterations to update position and velocity. At each iteration, we are adding velocity to position (movement), and adding acceleration to velocity (change in rate of movement), and calculating acceleration (finding the force on the particle). To simplify, the system doesn't calculate force on each particle based on all other particles - it only checks the particles immediately adjacent. There was also a 'damping' effect so that particles wouldn't accelerate too much and fly off to infinity (velocity is reduced by x percentage each step, for example).

Through the process of golfing, however, this whole thing was cut down and simplified drastically. Now, instead of two alike particles repelling each other, they simply 'teleport'. Different particles simply 'scoot' a wee bit to prevent stagnation in the system. For example if A is next to A it will teleport. If A is next to B it will only slightly shift. Then it checks if the conditions are met (no like particles adjacent) and prints the strings in order, based on their position in 1-d space. It is almost more like a sorting algorithm than a simulation - then again, one could see sorting algorithms as a form of simulated 'drifting' based on 'mass'. I digress.

Anyways, this is one of my first Rust programs so I gave up after several hours of golfing, although there might be opportunities there still. The parsing bit is difficult for me. It reads the input string from standard input. If desired, that could be replaced with "let mut s = "[[A,3],[B,2]]". But right now I do 'echo [[A,3],[B,2]] | cargo run' on the command line.

The calculation of stopping is a bit of a problem. How to detect if a valid state of the system will never be reached? The first plan was to detect if the 'current' state ever repeated an old state, for example if ACCC changes to CACC but then back to ACCC we know the program will never terminate, since it's only pseudo-random. It should then give up and print 0 if that happened. However this seemed like a huge amount of Rust code, so instead I just decided that if it goes through a high number of iterations, its probably stuck and will never reach a steady state, so it prints 0 and stops. How many? The number of particles squared.

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!();
}

Answer 11

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)

Try it online!

Answer 12

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

Try it online!

This never returns if there are no solutions.