Fun with strings and numbers

newguy 06/12/2018 at 20:14. 6 answers, 229 views
code-golf string number random combinatorics

Here's a programming puzzle for you:

Given a list of pairs of string and corresponding number e.g.

Input sample one

[[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. Total count of any string should be exactly equal to it's 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. Selection of next string should be done randomly as long as they don't break above two rules.

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


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 , so shortest code in bytes for each language wins!

6 Answers


Erik the Outgolfer 06/12/2018 at 21:31.

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.

HyperNeutrino 06/12/2018 at 21:30.

Jelly, 17 bytes

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

Try it online!


WaffleCohn 06/12/2018 at 22:12.

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!


Arnauld 06/12/2018 at 23:29.

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!


Chas Brown 06/13/2018 at 00:11.

Python 2, 114 bytes

a=input()
s=[];x=y=0
while a:a=sorted(a,key=lambda v:-v[1])+[[x,y-1]]*(y>1);x,y=a[0];s+=x,;a=a[1:]
print[s,0][y>1]

Try it online!

A "greedy" approach - Add the string which has the largest remaining count and which is different than the last added string.


Chas Brown 06/13/2018 at 01:12.

JavaScript (Node.js), 114 bytes

(a,s=[],y=0)=>{while(a>[]){a.sort((u,v)=>v[1]-u[1]);y>1?a.push([x,y-1]):0;[[x,y],...a]=a;s.push(x)}return y>1?0:s}

Try it online!

A JavaScript port of my Python answer.

Related questions

Hot questions

Language

Popular Tags