13
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Nice challenge! I do think it's a little underspecified by our standards. I highly recommend use of The Sandbox to get lots of feedback before posting a challenge so you don't get downvotes or close votes! :-) I'm looking forward to seeing more good challenges from you! \$\endgroup\$ – Giuseppe Jun 12 '18 at 20:35
  • \$\begingroup\$ @Giuseppe thanks I will try go through that. Let me know if I need to add any details if I have missed in this one. \$\endgroup\$ – Rohan Jun 12 '18 at 20:38
  • 1
    \$\begingroup\$ Can we take 2 inputs, just the strings and just the numbers? \$\endgroup\$ – FrownyFrog Jun 13 '18 at 8:43
  • \$\begingroup\$ there may be ambiguity in the use of the phrase 'random', several of these solutions are using "random" libraries that are in fact only pseudorandom. \$\endgroup\$ – don bright Jun 16 '18 at 5:00

12 Answers 12

6
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ If Œṙ didn't vectorize it would work without ' \$\endgroup\$ – dylnan Jun 12 '18 at 21:18
5
\$\begingroup\$

Jelly, 17 bytes

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

Try it online!

\$\endgroup\$
  • \$\begingroup\$ When I try ["A", 100], ["B", 3] it doesn't output anything it's stuck I think. \$\endgroup\$ – Rohan Jun 12 '18 at 20:42
  • 1
    \$\begingroup\$ @newguy Generating all permutations of 103 items isn't famous for its speed. For reference, the result after Œ! will have 99029007164861804075467152545817733490901658221144924830052805546998766658416222832141441073883538492653516385977292093222882134415149891584000000000000000000000000 elements. \$\endgroup\$ – Erik the Outgolfer Jun 12 '18 at 20:44
  • \$\begingroup\$ @newguy This solution is O(n!) but it's short and speed doesn't matter. Don't try it with anything where the numbers add up to more than about 6-8 or so :P \$\endgroup\$ – HyperNeutrino Jun 12 '18 at 20:45
  • \$\begingroup\$ Could Œṙ help? \$\endgroup\$ – Arnauld Jun 12 '18 at 20:47
  • 1
    \$\begingroup\$ @dylnan I don't think it is working for strings I tried with ["AT", 3], ["B", 3] and got TBATATBAB as output which is wrong \$\endgroup\$ – Rohan Jun 12 '18 at 20:59
5
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ @Arnauld: completely missed that! fixed now. \$\endgroup\$ – Chas Brown Jun 13 '18 at 20:20
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ n<-sum(n|1) is a byte shorter I believe. But the quirk of sample with a length-one input is pretty frustrating here. \$\endgroup\$ – Giuseppe Jun 13 '18 at 14:31
  • \$\begingroup\$ golfed it down a bit as well, try it here -- I had to remove the combinatXXpermn from the header to get the link small enough... \$\endgroup\$ – Giuseppe Jun 13 '18 at 14:38
  • \$\begingroup\$ I had something very similar taking input as a dataframe. The issue with bruteforce is it won't handle inputs that are too big... \$\endgroup\$ – JayCe Jun 13 '18 at 17:13
  • \$\begingroup\$ @JayCe is a non-brute force algorithm even possible, given rule 3 of this challenge? \$\endgroup\$ – ngm Jun 13 '18 at 17:37
  • \$\begingroup\$ I agree it might not. Would have been more interesting without rule 3. \$\endgroup\$ – JayCe Jun 13 '18 at 17:58
3
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks, @Arnauld, I'd missed that. Should've double checked the spec rather than just blindly following Chas' lead. Implemented a quick fix, will have to come back to it later to see if I can golf it better. \$\endgroup\$ – Shaggy Jun 13 '18 at 12:33
  • \$\begingroup\$ Yeah, the 3rd rule is OK for esolangs that can easily brute force all solutions anyway, but it makes it quite harder to implement shorter algorithms in other languages... BTW: this now seems to return 0 on valid entries from time to time. \$\endgroup\$ – Arnauld Jun 13 '18 at 12:43
  • \$\begingroup\$ Implemented another quick fix, @Arnauld - if that doesn't sort it, I'll have to delete again until I have more time to look into it. Note: I've taken the spec at its word that the next string needs to be chosen randomly, implying the first selection need not be random. \$\endgroup\$ – Shaggy Jun 13 '18 at 13:16
  • 1
    \$\begingroup\$ @Shaggy - I agree, you should never blindly follow anything I do! :) \$\endgroup\$ – Chas Brown Jun 13 '18 at 20:44
3
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Golfed to 53 \$\endgroup\$ – FrownyFrog Jun 13 '18 at 9:10
  • \$\begingroup\$ awesome tyvm @FrownyFrog , i’ll update post later \$\endgroup\$ – Jonah Jun 13 '18 at 12:35
  • \$\begingroup\$ oops, [:*/2~:/\|: is two shorter \$\endgroup\$ – FrownyFrog Jun 14 '18 at 9:37
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

Charcoal, 38 bytes

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

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

WΦθ§κ¹«

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

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

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.

\$\endgroup\$
  • \$\begingroup\$ This produces invalid outputs, such as in your example with ["h4x0r", 1337] included as a string. \$\endgroup\$ – ngm Jun 13 '18 at 17:44
  • \$\begingroup\$ @ngm I've rearranged the code and it now crashes if you do that... proper validation is going to cost more bytes unfortunately. \$\endgroup\$ – Neil Jun 13 '18 at 20:24
2
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ here's one for 93: Try it online! \$\endgroup\$ – Jonah Jun 13 '18 at 21:28
2
\$\begingroup\$

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!();
}
\$\endgroup\$
  • \$\begingroup\$ That's an interesting way of thinking about this problem, I like it. How well does it do in practice? I feel like the \$ l^2 \$ limit may be too low, that there may be too many false negatives where the algorithm thinks there's no valid output when there is - but I couldn't test that theory since TIO apparently doesn't have the regex crate. \$\endgroup\$ – sundar - Reinstate Monica Jul 19 '18 at 9:41
  • \$\begingroup\$ it passed the examples i fed it, although i did not fuzz it. i have modified it to work in TIO, you need to modify the 'let s=[("A",3),("B",2),("ZZ",4)];' line, bit.ly/2LubonO \$\endgroup\$ – don bright Jul 20 '18 at 0:32
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.