Fun with strings and numbers

newguy 06/12/2018. 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.

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.

Jelly, 17 bytes

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

Try it online!


WaffleCohn 06/12/2018.

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.

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.

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.

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.


HighResolutionMusic.com - Download Hi-Res Songs

1 BLACKPINK

Kiss And Make Up flac

BLACKPINK. 2018. Writer: Soke;Kny Factory;Billboard;Chelcee Grimes;Teddy Park;Marc Vincent;Dua Lipa.
2 Martin Garrix

Waiting For Tomorrow flac

Martin Garrix. 2018. Writer: Pierce Fulton;Mike Shinoda;Martijn Garritsen;Brad Delson.
3 Martin Garrix

Access flac

Martin Garrix. 2018. Writer: Martin Garrix.
4 John Legend

Written In The Stars flac

John Legend. 2018. Writer: Kiana Brown;Santoy;Kevin White;Mike Woods;MZMC;The Heavy Group;Rice N' Peas.
5 Martin Garrix

Yottabyte flac

Martin Garrix. 2018. Writer: Martin Garrix.
6 Alan Walker

Diamond Heart flac

Alan Walker. 2018. Writer: Alan Walker;Sophia Somajo;Mood Melodies;James Njie;Thomas Troelsen;Kristoffer Haugan;Edvard Normann;Anders Froen;Gunnar Greve;Yann Bargain;Victor Verpillat;Fredrik Borch Olsen.
7 Cardi B

Taki Taki flac

Cardi B. 2018. Writer: Bava;Juan Vasquez;Vicente Saavedra;Jordan Thorpe;DJ Snake;Ozuna;Cardi B;Selena Gomez.
8 Bradley Cooper

Shallow flac

Bradley Cooper. 2018. Writer: Andrew Wyatt;Anthony Rossomando;Mark Ronson;Lady Gaga.
9 Post Malone

Sunflower flac

Post Malone. 2018. Writer: Louis Bell;Billy Walsh;Carter Lang;Swae Lee;Post Malone.
10 Dyro

Latency flac

Dyro. 2018. Writer: Martin Garrix;Dyro.
11 Zara Larsson

Ruin My Life flac

Zara Larsson. 2018. Writer: Delacey;Michael Pollack;Stefan Johnson;Jordan Johnson;Sermstyle;Jackson Foote.
12 ZAYN

Fingers flac

ZAYN. 2018. Writer: Zayn Malik;Alex Oriet;David Phelan.
13 Halsey

Without Me flac

Halsey. 2018. Writer: Halsey;Delacey;Louis Bell;Amy Allen;Justin Timberlake;Timbaland;Scott Storch.
14 Lady Gaga

I'll Never Love Again flac

Lady Gaga. 2018. Writer: Benjamin Rice;Lady Gaga.
15 Sia

I'm Still Here flac

Sia. 2018. Writer: Sia.
16 Dewain Whitmore

Burn Out flac

Dewain Whitmore. 2018. Writer: Dewain Whitmore;Ilsey Juber;Emilio Behr;Martijn Garritsen.
17 Little Mix

Woman Like Me flac

Little Mix. 2018. Writer: Nicki Minaj;Steve Mac;Ed Sheeran;Jess Glynne.
18 Mako

Rise flac

Mako. 2018. Writer: Riot Music Team;Mako;Justin Tranter.
19 Blinders

Breach (Walk Alone) flac

Blinders. 2018. Writer: Dewain Whitmore;Ilsey Juber;Blinders;Martin Garrix.
20 Rita Ora

Let You Love Me flac

Rita Ora. 2018. Writer: Rita Ora.

Related questions

Hot questions

Language

Popular Tags