# Question
Title: Recursion bracketed; or Dyck words generation
We already have challenges to check if a string of brackets is fully matched and to count the number of balanced strings. It remains for us to generate these strings, but it will not be so easy…

A Dyck word is a string, of length *2n*, consisting of *n* opening and *n* closing parentheses (`(` and `)`) fully matched (that is to say: for all prefixes of the string, the number of opening parentheses is greater than or equal to the number of closing ones).

It is interesting to note that the number of different Dyck words of length *2n* is equal to the *(n + 1)*-th Catalan number.

It’s pretty straightforward to write a program that generates these words with a recursive function. But the goal here is to do the same thing without.

# Challenge

Write a full program or function that takes a positive integer, *n*, using `stdin` or an acceptable alternative, and outputs all the different Dyck words of length *2n*. The words can appear in any order and each must be separated from each other by a line break. Moreover, your program should not use recursive functions (see details below).

## Rules

* The output of your program should only contain Dyck words of length *2n*, separated by line breaks. Each word must appear only once.
* Your program must work at minimum for inputs 0 to 15.
* You may not write recursive functions, neither direct (a function that calls itself) nor indirect (e.g. a function *f* that calls another function *g* that calls function *f*). That being said, you can still use the standard functions of your language without worry of how they work internally.
* Similarly, your program should not call itself.
* You may not use non-standard librairies.
* Your program may not read or write files.
* Your program must be able to run in a reasonable time for *0 ≤ n ≤ 15* (hence, naively generate all arrangements is probably not a good idea). Let’s say less than 20 minutes with a memory limit of 4 GB (my reference implementation in C manages *n = 15* in less than 5 seconds).
* All standard loopholes are forbidden.

As usual in , the shortest code in bytes wins. But if you have found an interesting way to achieve this challenge in your language, please do not hesitate.

# Test I/O

For this input:

```
3

```

The output could be (any other order is correct too):

```
((()))
()()()
(()())
(())()
()(())

```

# Answer
> 5 votes
# Pyth, ~~26~~ 23 bytes

```
jeuaGsMs*VjRL`()_GGQ]]k

```

Try it online

```
                    ]]k   starting at G=[['']],
  u                Q      repeat the given number of times:
                _G          reversed G
          jRL`()            parenthesize each level-2 element
        *V        G         take Cartesian products of corresponding
                              elements of that and G
       s                    concatenate, yielding a list of pairs
     sM                     concatenate each resulting pair
   aG                       append the resulting list to G
je                        finally, join the last result on newlines

```

This directly follows the Catalan recurrence (with a non-recursive dynamic programming implementation) and doesn’t use any filtering. On my laptop, it runs in 55 seconds using 2.67 GiB RAM for *n* = 15.

# Pyth, 33 bytes, *O*(*n*) memory

```
=S*Q`()Wn2J+3x
Q"(()"=+.<S<QJ1>QJ

```

Try it online

```
  *Q`()                  build a string with Q copies of "()"
 S                       sort it
=                        assign it to Q

       W                 while the following is true:
(newline)                  print Q
Q
             x             take the index of the first occurrence of "(()"
 "(()"
           +3              add 3
          J                assign to J
        n2                 is this not equal to 2 (i.e. was "(()" found)?
                         do the following:
           <QJ             take the first J characters of Q
          S                sort them
        .<    1            cyclically shift them left by 1
       +       >QJ         add the remaining characters of Q
      =                    assign to Q

```

This algorithm outputs all Dyck words in a stream, with each word being generated from the previous one and no additional state. On my laptop, it runs in 170 seconds using basically no RAM for *n* = 15.

As an example illustrating how it works:

```
()()()()((()()(())))(())
         ^^^               becomes
(((((()))))(()(())))(())

```

Similarly computing the words in the reverse of this order also takes 33 bytes:

```
=*QK`()WJhx
Q_K=+t.iFc2_<QJ+K>QhJ

```

Try it online

# Answer
> 6 votes
# C99, 105 bytes

```
i,j,s;f(n){for(char a[31]={};++i%(1<<2*n);s||puts(a))for(j=s=0;~s&&j<2*n;)s+=1-(a[j]=40+(i>>j++)%2)%2*2;}

```

Iterates over all strings of **2n** parentheses.

With piped output and compiler flag `-O3`, input **n = 15** takes roughly *15.5 seconds* on my machine. Memory consumption is 1.2 MB.

Test it on Ideone.

# Answer
> 5 votes
## CJam (48 bytes)

```
ri"()"*${_p_,{1$>_)-,\(-,<},_{W=/(\s$1m>+}{&}?}h

```

Online demo. This effectively takes one obvious recursive solution and makes it iterative. Instead of actually simulating the steps back up the stack, it applies a successor rule:

> Find the last `(` which starts a suffix with strictly more `)` than `(`; sort that suffix, and rotate once.

Note that this is deliberately designed to avoid keeping the full list of solutions in memory, because I don't think it fits (at least, not if run on a 64-bit machine. It might on a 32-bit machine). There are `9694845` Dyck paths for `n=15`, so that's `30*9694845` characters, and `92*9694845 = 891925740` bytes of memory just for the (Java) String objects. But then the `List` holding the objects probably wraps an array with space for `16777216` elements, which is a further 256MB, and the CJam interpreter itself seems to add quite a bit of overhead.

---

### (42 bytes)

```
Ma{{_'(+\')+}%{"()"\f{\-,}I+_$=},}ri:I2**,

```

This builds the strings up one character at a time, filtering to ensure that no string has more than `n` opening parentheses or more closing than opening parentheses. However, it runs out of memory with 3GB for `n=15`.

The same idea at 39 bytes, but this runs out of memory earlier.

```
Ma{"()":Sm*::+{S\f{\-,}I+_$=},}ri:I2**`

```

Online demo

---

### (24 bytes)

My original answer, now disqualified by rule changes.

```
{"()"*e!{0\+{~_}*]1&!},}

```

This is an anonymous function which takes input on the stack. Online demo.

It works by the obvious approach of taking all permutations of `n` pairs of parentheses and filtering for those which are balanced.

# Answer
> 4 votes
## JavaScript (ES6), 125 bytes

```
n=>{for(i=m=1<<n+n-1;i&m;i++){for(j=m,z=o=0;o>=z;j>>=1)i&j?o++:z++;o-n||console.log(i.toString(2).replace(/./g,d=>")("[d]))}}

```

Actually printing the results slows things down horribly, but with `console.log` set to `()=>{}` this takes my machine about 7 seconds for n=12, which presumably translates to 7 minutes for n=15. If that's not fast enough, you can replace `i++` with `i+=2` or even `i+=j||2` but that made only a few percent difference in my testing. Works by generating all 2n-digit binary numbers and checking whether they represent a Dyck word. Ungolfed:

```
function dyck(n) {
    // Don't bother generating words that begin with ),
    // so start half-way though 4 ** n.
    for (var i = 4 ** n / 2; i < 4 ** n; i += 2) {
        // Convert to the string of ()s.
        var word = i.toString(2);
        word = word.replace(/1/g, "(");
        word = word.replace(/0/g, ")");
        // Count the (s and )s separately.
        var left = 0;
        var right = 0;
        for (var j = 0; j < n + n; j++) {
            if (word[j] == "(") left++;
            else right++;
            // Abort if there are too many )s
            if (right > left) break;
        }
        // If we got exactly n (s then it's a Dyck word.
        if (left == n) console.log(word);
    }
}

```

# Answer
> 3 votes
# C, ~~748~~ ~~746~~ 651 bytes

```
#define C(v,n) for(v=n==D;v<=(n<=D);v++)
void p(Z){unsigned long long R,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,A,B,C,D=Z*2,E,F;C(C,30)C(B,29)C(A,28)C(z,27)C(y,26)C(x,25)C(w,24)C(v,23)C(u,22)C(t,21)C(s,20)C(r,19)C(q,18)C(p,17)C(o,16)C(n,15)C(m,14)C(l,13)C(k,12)C(j,11)C(i,10)C(h,9)C(g,8)C(f,7)C(e,6)C(d,5)C(c,4)C(b,3)C(a,2){R=C<<29|B<<28|A<<27|z<<26|y<<25|x<<24|w<<23|v<<22|u<<21|t<<20|s<<19|r<<18|q<<17|p<<16|o<<15|n<<14|m<<13|l<<12|k<<11|j<<10|i<<9|h<<8|g<<7|f<<6|e<<5|d<<4|c<<3|b<<2|a<<1;if(__builtin_popcount(R)!=Z)goto X;F=0;for(E=D-1;E;E--)if(R&1<<E)F++;else if(F)F--;else goto X;for(;E<D;E++)putchar(40+!(R&1<<D-E-1));puts("");X:;}}

```

At a whopping \>600 bytes, this isn't really much of a contender...but it's pretty fast and memory efficient.

Works by encoding the parentheses strings as integers, with a set bit representing `(` and an unset bit representing `)`. For instance, `(())` would be `1100`. I made the following observations:

* All permutations must begin with `(` and end with `)`; otherwise, it won't be valid.
* Every valid permutation must have `n` left parentheses and `n` right parentheses, where `n` is the input number. I used `__builtin_popcount` for this.

When built via `icc -march=native -O3`, it takes 17s on my computer, though others have reported better times (~3-7s) on their (presumably faster) computers. In addition, it uses around 1.5 KB of memory.

Here's the code with explanatory comments:

```
// Z is the input number.
void p(Z){
    // All the variables.
    // R is the resulting paren number, with 1 bits for open parens and 0s for closed ones.
    // a-C are used to hold the state of each paren (1 if open, 0 if closed).
    // D holds Z*2, or the total length of the paren string.
    // E and F are used later on.
    unsigned long long R,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,A,B,C,D=Z*2,E,F;
    /* Each loop performs a basic check. If D is equal to the corresponding
       number, then the variable will start at 1 (since the first paren must
       always be open). If D is greater than or equal to the number, then the loop
       will only be run once with the variable set to 0, and a later check will
       cause the variable to be ignored. Otherwise, it will loop twice; one for a
       closed paren (0), and one for an open one (1). Of course, if D == the
       number, then it will only loop for the open paren (as stated above). */
    for (C = (D == 30); C <= (30 <= D); C++)
    for (B = (D == 29); B <= (29 <= D); B++)
    for (A = (D == 28); A <= (28 <= D); A++)
    for (z = (D == 27); z <= (27 <= D); z++)
    for (y = (D == 26); y <= (26 <= D); y++)
    for (x = (D == 25); x <= (25 <= D); x++)
    for (w = (D == 24); w <= (24 <= D); w++)
    for (v = (D == 23); v <= (23 <= D); v++)
    for (u = (D == 22); u <= (22 <= D); u++)
    for (t = (D == 21); t <= (21 <= D); t++)
    for (s = (D == 20); s <= (20 <= D); s++)
    for (r = (D == 19); r <= (19 <= D); r++)
    for (q = (D == 18); q <= (18 <= D); q++)
    for (p = (D == 17); p <= (17 <= D); p++)
    for (o = (D == 16); o <= (16 <= D); o++)
    for (n = (D == 15); n <= (15 <= D); n++)
    for (m = (D == 14); m <= (14 <= D); m++)
    for (l = (D == 13); l <= (13 <= D); l++)
    for (k = (D == 12); k <= (12 <= D); k++)
    for (j = (D == 11); j <= (11 <= D); j++)
    for (i = (D == 10); i <= (10 <= D); i++)
    for (h = (D == 9); h <= (9 <= D); h++)
    for (g = (D == 8); g <= (8 <= D); g++)
    for (f = (D == 7); f <= (7 <= D); f++)
    for (e = (D == 6); e <= (6 <= D); e++)
    for (d = (D == 5); d <= (5 <= D); d++)
    for (c = (D == 4); c <= (4 <= D); c++)
    for (b = (D == 3); b <= (3 <= D); b++)
    for (a = (D == 2); a <= (2 <= D); a++) {
        /* R is the result here. Each variable is shifted and bitwise-ORd with the
           others to generate a number representing the string.

           For instance, (()) would be 1100, and ()(()) would be 101100. */
        R=C<<29|B<<28|A<<27|z<<26|y<<25|x<<24|w<<23|v<<22|u<<21|t<<20|s<<19|r<<18|
          q<<17|p<<16|o<<15|n<<14|m<<13|l<<12|k<<11|j<<10|i<<9|h<<8|g<<7|f<<6|
          e<<5|d<<4|c<<3|b<<2|a<<1;
        // If there is an uneven balance of parens, then just jump to the loop end.
        if(__builtin_popcount(R)!=Z) goto X;
        // F here is the number of opening parens.
        F=0;
        // E is a counter used to extract each bit.
        for(E=D-1;E;E--)
            // If the bit is set, then increment the number of open parens.
            if(R&1<<E) F++;
            // If the bit wasn't set, then decrement the number of open parens...
            else if(F) F--;
            // ...but, if there were no open parens, then it's unbalanced; jump to the end
            else goto X;
        // E (the bit counter) is already 0.
        // Loop through each bit...
        for(;E<D;E++)
            /* ...and print it out. 40 is the ASCII code for `(`. If the bit
               is set, the ! will negate it, and 0 will be added to the `(`.
               Otherwise, it will turn the left paren into a right paren. */
            putchar(40+!(R&1<<D-E-1));
        // Newline.
        puts("");
        // End of loop.
        X:;
    }
}

```

## 746-byte version

```
#define C(v,n) for(v=(n==D);v<=(n<=D);v++){
void p(Z){unsigned long long R,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,A,B,C,D=Z*2,E,F;C(C,30)C(B,29)C(A,28)C(z,27)C(y,26)C(x,25)C(w,24)C(v,23)C(u,22)C(t,21)C(s,20)C(r,19)C(q,18)C(p,17)C(o,16)C(n,15)C(m,14)C(l,13)C(k,12)C(j,11)C(i,10)C(h,9)C(g,8)C(f,7)C(e,6)C(d,5)C(c,4)C(b,3)C(a,2)R=(C<<29)|(B<<28)|(A<<27)|(z<<26)|(y<<25)|(x<<24)|(w<<23)|(v<<22)|(u<<21)|(t<<20)|(s<<19)|(r<<18)|(q<<17)|(p<<16)|(o<<15)|(n<<14)|(m<<13)|(l<<12)|(k<<11)|(j<<10)|(i<<9)|(h<<8)|(g<<7)|(f<<6)|(e<<5)|(d<<4)|(c<<3)|(b<<2)|(a<<1);if(__builtin_popcount(R)!=Z)continue;F=0;for(E=D-1;E;E--)if(R&(1<<E))F++;else if(F)F--;else goto X;for(;E<D;E++)putchar('('+!(R&(1<<D-E-1)));puts("");X:;}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}

```

# Answer
> 2 votes
# JavaScript (ES6), 203

Implementing this algorithm (point 3, totally iterative)

Within the limits of script executing in Firefox, I managed to have the 200K console output for input 12 in about 1.5 minutes

```
n=>{
for(b=[...Array(n)].map((_,i)=>1+2*i),z=0;!z;)
for(c=[...'('.repeat(n+n)],b.map(n=>c[n]=')'),console.log(c.join``),z=i=n;i--&&z;)
if(b[i]<n+i)for(z=0,b[j=i]++;++j<n-1;)b[j]=Math.max(b[j-1],2*j)+1
}

```

*Less golfed*

```
n=>{
  b=[...Array(n)].map((_,i)=>1+2*i)
  q=0
  for(z=0;!z;)
  {
    c=[...'('.repeat(n+n)],
    b.map(n=>c[n]=')'),
    console.log(++q,c.join``)
    for(z=i=n;i--&&z;)
      if(b[i]<n+i)
        for(z=0,b[j=i]++;++j<n-1;)
          b[j]=Math.max(b[j-1],2*j)+1
  }
}

```

**Ported to C** just for fun, run in 5 secs for input 15 (it compiles and works without #includes)

```
f(n){int i,j,z,b[49];char c[99];
for(i=n;i--;)b[i]=2*i+1;
for(z=0;!z;){memset(c,40,n+n);c[n+n]=0;
for(i=n;i--;)c[b[i]]=41;puts(c);
for(z=i=n;i--&&z;)if(b[i]<n+i)for(z=0,b[j=i]++;++j<n;)b[j]=(b[j-1]>2*j?b[j-1]:2*j)+1;
}}

```

**Test** generating all output but do not display it, just counting output rows

I got 90 sec for input 15

```
F=n=>{
for(b=[...Array(n)].map((_,i)=>1+2*i),z=0;!z;)
for(c=[...'('.repeat(n+n)],b.map(n=>c[n]=')'),console.log(c.join``),z=i=n;i--&&z;)
if(b[i]<n+i)for(z=0,b[j=i]++;++j<n-1;)b[j]=Math.max(b[j-1],2*j)+1
}

console.log=x=>o++ // console.log display no output, just count rows

function test() {
  n=+I.value,o=0,t=+new Date
  O.textContent='...wait...'
  setTimeout(_=>(F(n),O.textContent=['rows='+o,'time sec '+(new Date-t)/1000]), 10)

}

test()
```

```
N:<input id=I value=12 type=number max=20><button onclick='test()'>go</button>
<pre id=O></pre>
```

# Answer
> 2 votes
# Python 2, ~~117~~ 116 bytes

```
def f(n):r='',;exec"r=[s+c for s in r for t in[s.count('(')]for c in')('[t+t==len(s):2-t/n]];"*2*n;print'\n'.join(r)

```

This builds the strings character by character, without filtering.

With piped output and input **n = 15**, this takes roughly 39 seconds with CPython and *7.5 seconds* with PyPy on my machine. Memory consumption is 1.6 GB with CPython and 2.5 GB with PyPy.

Test it on Ideone.

# Answer
> 2 votes
# J, ~~97~~ ~~70~~ ~~69~~ ~~68~~ ~~60~~ 59 bytes

```
'()'{~(,:'')((((>:#-+/)*(]#>:2*+/))"1#]),.&0,,.&1)^:(2*[)~]

```

Now tacit!

This is a monad that uses binary digits to create pairs of parentheses. In order to meet the requirements, a non-recursive approach is used along with optimization by use of certain primitives to ensure that mostly boolean (1 byte) values are used to keep memory requirements low.

On my computer, using an i7-4770k, it takes about 50 seconds to compute the result for *n* = 15 and uses about 1.5 GB of memory.

In the interests of maximizing speed, this version with **70 bytes** computes the result for *n* = 15 in 0.5 seconds while using about 800 MB of memory. It's also tacit!

```
'()'{~[:;@(<@([:,/],"1/0=|."1)/.~+/"1)<:1&(],(+/<:#-+/)"1@,.~#,.~)1$0:

```

## Usage

```
   f =: '()'{~(,:'')((((>:#-+/)*(]#>:2*+/))"1#]),.&0,,.&1)^:(2*[)~]
   timer =: 6!:2
   f 3
()()()
(())()
()(())
(()())
((()))
   10 timer 'r =: f 15'  NB. Average time over 10 runs
49.9951
   # r
9694845

```

# Answer
> 1 votes
# Pyth, 47 bytes

```
                                                               <-empty line
Musm?<J/d\(Q?>-J/d\)0,+d\(+d\)]+d\(]+d\)G*2Q]k

```

Took 18 minutes on my machine, and over 2GB RAM.

In pythonic pseudocode:

```
// newline means "print"
M                                              map(print,
 u                                               reduce(lambda G,H:
  sm                                               sum(map(lambda d:
                     ,+d\(+d\)                       ([d+"(",d+")"] if
            ?>-J/d\)0                                   J-d.count(")") > 0
                              ]+d\(                     else [d+"("]) if
    ?<J/d\(Q                                           (J=d.count("(") < Q
                                   ]+d\)               else [d+")"],
                                        G              G)),
                                         *2Q]k     2*input(),[""]))

```

In words:

1. create a function that maps any string to a list of strings that can be formed by adding "(" or ")"
if the parentheses are already matched, only "(" can be added; if there are already n "(", only ")" can be added; otherwise a pair is returned
2. create a new function that maps the old function over its param, and then sum up the map, so that it takes a list of strings, maps to a list of lists of strings, and then de-nests it back into a list of strings
each call essentially "grows" its params by one `(` or `)`
3. reduce this new function over `range(2*input())`, with `[""]` as base case
essentially just passing `[""]` through the new function 2n times
4. map `print` over the return value of `reduce` to print each string in new lines

# Answer
> 1 votes
## Haskell, ~~111~~ 105 bytes

```
import Data.Function
id=<<fix(\h a z->id=<<[('(':)<$>h(a-1)z|a>0]++[(')':)<$>h a(z-1)|a<z]++[[""]|a+z<1])

```

Usage example: `id=<<fix(\h a z->id=<<[('(':)<$>h(a-1)z|a>0]++[(')':)<$>h a(z-1)|a<z]++[[""]|a+z<1]) $ 3` -\> `["((()))","(()())","(())()","()(())","()()()"]`.

The Dyck word building algorithm used here expressed in a classic recursive way looks like

```
dyck a z =                    -- take two numbers, `a` (the number of `(` to use)
                              -- and `z` (the number of `)` to use)
                 [[""]|a+z<1] -- base case if both numbers are 0, the result
                              -- is an empty word
    [('(':)<$>dyck(a-1)z|a>0] -- if there are `(` left, prepend one to every result
                              -- from a recursive call with one `(` less
   [(')':)<$>dyck a(z-1)|a<z] -- same for `)` if there are more than `(`.
id=<<  ...  ++  ...  ++       -- combine those results in to a flat list

```

As recursion is not allowed, we pass the function to call as a third parameter `h` (and use a lambda instead of a named function):

```
\h a z ->   ....  h(a-1)z  ....  h a(z-1)

```

and let the fixpoint combinator `fix` create this function for us:

```
fix(\h a z ...)

```

finally, the leftmost `id=<<` duplicates the input parameter: `(id=<<) f n` is `f n n`, so when the whole function is called, the parameter `n` is used as `a` and `z`.

For input `15` it takes about 3min within ghci (25s when compiled) and a few MB on my 5 year old laptop.

# Answer
> 0 votes
# Haskell, ~~140~~ 132 bytes

Thanks @nimi for saving a few bytes!

```
import Data.List
h s|m<-length s=nub[k|l<-s!!0,k<-('(':l++")"):[u++v|n<-[0..m-2],u<-s!!n,v<-s!!(m-2-n)]]:s
f n=iterate h[[""]]!!n!!0

```

First of all: `iterate` does create a recursion sequecnce of `h`, but this is a builtin, and by the rules we may use builtins that use recursion.

This is just a very simple recursive approach, we can generate the n-Dyck-words by putting (n-1)-Dyck-words between paranthesis, or by concatenating from shorter Dyck words. This approach however does generate duplicates, that is why we filter for unique elements using `nub`.

As Haskell is a functional language, it is almost impossible to do this without recursion. There is an even more direct approach, but that one is banned under the current rules.

---
Tags: code-golf, restricted-source, combinatorics, balanced-string
---


title: Autonest an array

text:
# Question
Title: Autonest an array
Everybody loves nested lists! However, sometimes it's hard to make a nested list. You have to decide if you want to nest it deeper, or if you need to nest it shallower. So for your challenge, you must "Autonest" a list. To autonest a list, compare every pair of items in the list.

* If the second item is smaller, separate the two elements by inserting closing and opening brackets between them, like this:

```
  } {
{2 , 1}

```

For example, `{2, 1}` becomes `{2}, {1}`, and `{3, 2, 1}` becomes `{3}, {2}, {1}`
* If the second item is the same, then change nothing. For example, `{1, 1, 1}` stays the same, and `{2, 1, 1, 1}` would become `{2}, {1, 1, 1}`.
* If the second item is larger, then nest every following item one level deeper. For example, `{1, 2}` would become `{1, {2}}` and `{1, 2, 3}` would become `{1, {2, {3}}}`

# The Challenge

You must write a program or function that takes in a list of numbers, and returns the same list after being autonested. Take this input in your languages native list format (or the closest alternative) or as a string. You do not have to use curly braces like I did in my examples. You can use whichever type of brackets are most natural in your language, as long as this is consistent. You can safely assume the list will only contain integers. You can also assume the list will have at least 2 numbers in it. Here is some sample IO:

```
{1, 3, 2}                         -->   {1, {3}, {2}}
{1, 2, 3, 4, 5, 6}                -->   {1, {2, {3, {4, {5, {6}}}}}}
{6, 5, 4, 3, 2, 1}                -->   {6}, {5}, {4}, {3}, {2}, {1}
{7, 3, 3, 2, 6, 4}                -->   {7}, {3, 3}, {2, {6}, {4}}
{7, 3, 1, -8, 4, 8, 2, -9, 2, 8}  -->   {7}, {3}, {1}, {-8, {4, {8}, {2}, {-9, {2, {8}}}}}

```

Standard loopholes apply, and the shortest answer in bytes wins!

# Answer
# MATL, ~~48~~ 43 bytes

```
YY_XKx"@K<?93]44@K-?91]@XKV]v93Gd0>sQY"h4L)

```

This uses square brackets in input and output. The output has commas without spaces as separators.

Note that the output would not be interpreted as a nested list in MATL. It would in other languages, and it satisfies the output specification in the challenge.

**Try it online!**

### Explanation

```
YY_XKx   % Push -inf. Copy to clipboard K (represents previous input entry). Delete
"        % Take numerical array implicitly. For each entry:
  @K<    %   Is current entry less than the previous one?
  ?93]   %   If so, push 93 (ASCII for ']')
  44     %   Push 44 (ASCII for comma)
  @K-    %   Is current entry different from the previous one?
  ?91]   %   If so, push 91 (ASCII for '[')
  @XKV   %   Push current entry, copy into clipboard K, convert to string
]        % End for each
v        % Concat vertically all stack contents, converting to char
93       % Push 93 (ASCII for ']') (to be repeated the appropriate number of times)
Gd0>sQ   % Determine how many times the input increases, plus 1
Y"       % Repeat 93 that many times
h        % Concat horizontally with previous string. Gives a row array, i.e. string
4L)      % Remove first char, which is an unwanted comma. Display implicitly

```
> 1 votes

# Answer
## Haskell, 96 bytes

```
a#b|a<b=",{"|a>b="},{"|1<2=","
f(a:b:c)=show a++a#b++f(b:c)++['}'|a<b]
f[x]=show x++"}"
('{':).f

```

Usage example: `('{':).f $ [7,3,3,2,6,4]` -\> `"{7},{3,3},{2,{6},{4}}"`.

As Haskell doesn't have nested lists, I return the result as a string. The nesting algorithm is easy: a) print number, b) if the next number is greater (less, equal), print `,{` ( `},{`, `,`), c) make a recursive call with the rest of the list, d) print `}` if the number is less than the next one, e) enclose everything in `{` and `}`.
> 3 votes

# Answer
# Python 3, 98 bytes

```
p,*i=eval(input())
c=[p]
a=b=[c]
for x in i:
 if x>p:b=c
 if x!=p:c=[];b+=[c]
 c+=[x];p=x
print(a)

```

Example:

```
$ python3 autonest.py <<< "[7, 3, 1, -8, 4, 8, 2, -9, 2, 8]"
[[7], [3], [1], [-8, [4, [8], [2], [-9, [2, [8]]]]]]

```
> 3 votes

# Answer
# Java 8 197 187 193 192 bytes

---

Thanks to all the commenters who worked with me on this monstrosity. It was golfed down to 187 bytes until I found a costly bug. However due to the power of Black Magic the "runs down to" operator "--\>" the byte count is at a healthy 192 bytes.

---

```
String a(int[]b){int l=b.length,d=1,i=0;String c="{";for(;i<l-1;i++)if(b[i]>b[i+1])c+=b[i]+"},{";else if(b[i]<b[i+1]){d++;c+=b[i]+",{";}else c+=b[i]+",";c+=b[l-1];while(d-->0)c+="}";return c;}

```
> 2 votes

# Answer
# C, ~~145~~ 138 bytes

Thanks to Giacomo for 7 bytes!

```
#define P printf(
n;main(c,v,p,t)char**v;{p=-101;for(v++;*v;v++){t=atoi(*v);if(t<p)P"}{");if(t>p)P"{",n++);P"%d ",p=t);}for(;n--;)P"}");}

```

Input is taken through command line arguments and output is given though stdout.

sample run:

```
$ ./autonest 7 3 1 -8 4 8 2 -9 2 8
{7 }{3 }{1 }{-8 {4 {8 }{2 }{-9 {2 {8 }}}}}

```
> 2 votes

# Answer
# Retina, ~~71~~ 70 bytes

Lists are space separated, with curly braces: `{1 2 3}`. Negative numbers are not supported, so if that's a problem, I'll just delete my answer. Retina + negative numbers = not worth it.

```
\d+
$*
+`\b(1+) (1+\1\b.*)
$1 {$2}
+`\b(1(1+)1*) (\2)\b
$1} {$2
1+
$.0

```

**Try it online**
> 1 votes

# Answer
# CJam, ~~51~~ ~~49~~ ~~48~~ 46 bytes

Exploits the fact that the number of last bracket is one more than number of adjacent pair that is increasing in array.

And I don't know `ew` operator before that I had to reimplement.

The input is space separated list delimited by square brackets.

```
'[q~_W=\2ew_{~\_@-g)["["S"]["]=}%@@{~>M']?}%']

```

Explanation

```
'[q~_W=\2ew_{~\_@-g)["["S"]["]=}%@@{~>M']?}%']
'[                                             e# Opening bracket
  q~                                           e# Read the input
    _W=\2ew                                    e# Save the last item and turn array into array of pair of next item and the item itself.
            _                                  e# We need two copies of that item
             {~\_@-g)["["S"]["]=}%             e# Build the "body" that consist of the item and the suitable delimiter, space if equal, opening brace if the first item is the smallest, otherwise, closing bracket and opening bracket.
                                  @@           e# Put in the last item. (It was omitted in previous phase)
                                    {~<']""?}% e# Create the closing bracket as many as the number of increasing adjacent pair
                                               '] e# And one more bracket.

```

I will find out how to do this with actual nested array instead of relying on prettyprinting.

Finally, ~~at par with~~ beaten MATL's answer.
> 1 votes

# Answer
## JavaScript (ES6), 73 bytes

```
a=>a.map(r=>l-r?(n=l<r?m:n).push(m=[l=r]):m.push(l),l=a[0],o=n=[m=[]])&&o

```

Explanation: The case of consecutive equal items is easy; the item is just added to the innermost array (here represented by the `m` variable; `n` is the array that contains `m` as its last element, while `o` is the output). For the case of different items, the item always goes in a new innermost array, the only difference being whether that array is a sibling or a child of the previous innermost array. For extra golfiness I set up the arrays so that the initial item counts as a consecutive equal item.
> 0 votes

---
Tags: code-golf, array, balanced-string
---


# Question
Title: Choose from an existing set of weights to make a target sum
When doing weightlifting, I want to make a specific weight by attaching several plates to a bar.

I have the following plates:

* 6 plates of 1 kg each
* 6 plates of 2.5 kg each
* 6 plates of 5 kg each
* 6 plates of 10 kg each

The bar itself weighs 10 kg.

It's only allowed to attach the plates in pairs - they are attached at each end of the bar, and the arrangement at the two ends must be completely symmetrical (e.g. attaching two 5-kg plates at one end, and one 10-kg plate at the other end is forbidden for reasons of safety).

Make a program or a function that tells me how many plates of each kind I have to use in order to get a given total weight. The input is an integer greater than 11; the output is a list/array/string of 4 numbers. If it's impossible to combine existing plates to get the target weight, output a zero/empty array, an invalid string, throw an exception or some such.

If there are several solutions, the code must output only one (don't make the user choose - he is too busy with other things).

Test cases:

```
12 -> [2 0 0 0] - 2 plates of 1 kg plus the bar of 10 kg
13 -> [0 0 0 0] - a special-case output that means "impossible"
20 -> [0 0 2 0] - 2 plates of 5 kg + bar
20 -> [0 4 0 0] - a different acceptable solution for the above
21 -> [6 2 0 0] - 6 plates of 1 kg + 2 plates of 2.5 kg + bar
28 -> [0 0 0 0] - impossible
45 -> [0 2 6 0] - a solution for a random number in range
112 -> [2 4 6 6] - a solution for a random number in range
121 -> [6 6 6 6] - maximal weight for which a solution is possible

```

If your code outputs the numbers in the opposite order (from the heavy plate to the light one), please specify this explicitly to avoid confusion.

# Answer
# Jelly, 22 bytes

```
4ṗạµ×2,5,10,20S€+⁵iƓịḤ

```

Try it online! or verify all test cases.

### How it works

```
4ṗạµ×2,5,10,20S€+⁵iƓịḤ  Main link. No arguments

4                       Set the left argument and initial return value to 4.
 ṗ                      Take the Cartesian power of [1, 2, 3, 4] and 4, i.e.,
                        generate all 4-tuples of integers between 1 and 4.
  ạ                     Take the absolute difference of all integers in the
                        4-tuples and the integer 4. This maps [1, 2, 3, 4] to
                        [3, 2, 1, 0] and places [0, 0, 0, 0] at index 0.
   µ                    Begin a new, monadic chain. Argument: A (list of 4-tuples)
     2,5,10,20          Yield [2, 5, 10, 20].
    ×                   Perform vectorized multiplication with each 4-tuple in A.
              S€        Sum each resulting 4-tuple.
                +⁵      Add 10 to each sum.
                   Ɠ    Read an integer from STDIN.
                  i     Find its first index in the array of sums (0 if not found).
                     Ḥ  Unhalve; yield the list A, with all integers doubled.
                    ị   Retrieve the 4-tuple at the proper index.

```
> 5 votes

# Answer
# MATL, ~~29~~ 28 bytes

```
4t:qEZ^!"[l2.5AX]@Y*10+G=?@.

```

For inputs that have no solution this produces an empty output (without error).

**Try it online!**

### Explanation

```
4           % Push 4
t:q         % Duplicate 4 and transform into range [0 1 2 3]
E           % Multiply by 2: transform into [0 2 4 6]
Z^          % Cartesian power. Each row is a "combination" of the four numbers
!           % Transpose
"           % For each column
  [l2.5AX]  %   Push [1 2.5 5 10]
  @         %   Push current column
  Y*        %   Matrix multiply. Gives sum of products
  10+       %   Add 10
  G=        %   Compare with input: are they equal?
  ?         %   If so
    @       %     Push current column, to be displayed
    .       %     Break loop
            %   Implicit end
            % Implicit end
            % Implicit display

```
> 6 votes

# Answer
# Mathematica, 70 bytes

```
Select[FrobeniusSolve[{2,5,10,20},2#-20],AllTrue[EvenQ@#&&#<7&]][[1]]&

```

Anonymous function. Takes a number as input, and either outputs a list or errors and returns `{}[[1]]` if there is no solution.
> 5 votes

# Answer
# Jelly, 25 bytes

```
×2,5,10,20S+⁵⁼³
4ṗ4’ÇÐfḢḤ

```

Try it here.
> 4 votes

# Answer
# Python 3, 112 bytes

```
lambda n:[i for i in[[i//4**j%4*2for j in range(4)]for i in range(256)]if i[0]+2.5*i[1]+5*i[2]+10*i[3]+10==n][0]

```

An anonymous function that takes input, via argument, of the target mass and returns the number of each plate as a list. If no solution exists, an error is thrown. This is pure brute force.

**How it works**

```
lambda n                                   Anonymous function with input target mass n
...for i in range(256)                     Loop for all possible arrangement indices i
[i//4**j%4*2for j in range(4)]             Create a base-4 representation of the index i,
                                           and multiply each digit by 2 to map from
                                           (0,1,2,3) to (0,2,4,6)
[...]                                      Package all possible arrangements in a list
...for i in...                             Loop for all possible arrangements i
i...if i[0]+2.5*i[1]+5*i[2]+10*i[3]+10==n  Return i if it gives the target mass
[...]                                      Package all solutions in a list
:...[0]                                    Return the first list element. This removes any
                                           multiple solutions, and throws an error if there
                                           being no solutions results in an empty list

```

Try it on Ideone
> 3 votes

# Answer
# Brachylog, 50 bytes

```
,L##l4,L:{.~e[0:3]}a:[2:5:10:20]*+:10+?,L:{:2*.}a.

```

Returns `false` when not possible.
> 2 votes

# Answer
# Pyth, ~~34~~ ~~31~~ 25 bytes

```
~~h+fqQ+;s*VT[1 2.5 5;)yMM^U4 4]*4]0~~
~~yMh+fqQ+;s*VT[2 5;y;)^U4 4]*4]0~~
yMhfqQ+;s*VT[2 5;y;)^U4 4

```

Test suite.

Errors in impossibility.

This is essentially a brute-force.

This is quite fast, since there are only 256 possible arrangements.
> 1 votes

# Answer
# Scala, 202 bytes

Decided Scala doesn't get much love here, so I present a (probably not optimal) solution in Scala.

```
def w(i:Int){var w=Map(20->0,10->0,5->0,2->0);var x=i-10;while(x>0){
var d=false;for(a<-w.keys)if(a<=x & w(a)<6 & !d){x=x-a;w=w.updated(a,w(a)+2);d=true;}
if(!d){println(0);return;}}
println(w.values);}

```

The program outputs in reverse order and with extra junk compared to solutions in post. When a solution is not found, prints 0.

Note: I could **not** remove any of the newlines or spaces because Scala is dumb, so I think to reduce size, the method must be redone unless I missed something obvious.
> 1 votes

# Answer
## APL, 40 bytes

```
{2×(4⍴4)⊤⍵⍳⍨10+2×,⊃∘.+/↓1 2.5 5 10∘.×⍳4}

```

In ⎕IO←0. In English:

1. `10+2×,∘.+⌿1 2.5 5 10∘.×⍳4`: build the array of all the possible weights, by computing the 4D outer sum of the weights per weight type;
2. `⍵⍳⍨`: search the index of the given. If not found the index is 1+the tally of the array at step 1;
3. `(4⍴4)⊤`: represent the index in base 4, that is, compute the coordinate of the given weigth in the 4D space;
4. : bring the result to problem space, where the coordinates should be interpreted as half the number of the plates.

Example: {2×(4⍴4)⊤⍵⍳⍨10+2×,⊃∘.+/↓1 2.5 5 10∘.×⍳4}112 2 4 6 6

Bonus: since APL is an array language, several weights can be tested at once. In this case the result is transposed:

```
      {2×(4⍴4)⊤⍵⍳⍨10+2×,⊃∘.+/↓1 2.5 5 10∘.×⍳4}12 13 20 21 28 45 112 121
2 0 0 6 0 0 2 6
0 0 0 2 0 2 4 6
0 0 2 0 0 2 6 6
0 0 0 0 0 2 6 6

```
> 1 votes

# Answer
## JavaScript (ES6), 109 bytes

```
n=>`000${[...Array(256)].findIndex((_,i)=>i+(i&48)*9+(i&12)*79+(i&3)*639+320==n*32).toString(4)*2}`.slice(-4)

```

Returns `00-2` on error. Alternative solution that returns `undefined` on error, also 109 bytes:

```
n=>[...Array(256)].map((_,i)=>`000${i.toString(4)*2}`.slice(-4)).find(s=>+s[0]+s[1]*2.5+s[2]*5+s[3]*10+10==n)

```
> 1 votes

---
Tags: code-golf, arithmetic
---


title: Generalised Array Riffle

text:
# Question
Title: Generalised Array Riffle
A simple golf to start the week! You're given three arrays: the *base array* `B`, the *value array* `V` and the *index array* `I`. You should produce another array where the values from `V` are inserted into `B` at the indices specified by `I`. Here is an example:

```
Base:    [5, 1, 4, 1, 3]
Values:  [0, 0, 7]
Indices: [5, 0, 3]

```

The indices point at the following positions in the base array:

```
[ 5, 1, 4, 1, 3 ]
 ^        ^    ^
 0        3    5

```

So inserting the corresponding elements from the value array, the result should be:

```
[0, 5, 1, 4, 7, 1, 3, 0]

```

## Rules

You may write a program or function, taking input via STDIN (or closest alternative), command-line arguments or function arguments and output the result via STDOUT (or closest alternative), function return value, or by modifying the array given as the `B` parameter.

If your submission is a function, `I` and `V` can be modified in any way, as well as `B` if it isn't used for output.

You may make the following assumptions about the input:

* All elements of the base and value array will be non-negative integers.
* The value array will have at most one more element than the base array.
* The value array and index array will have the same number of elements.
* The index array will not contain repeated indices, and all indices will be in range.
* The base and value arrays *may* contain repeated elements.
* Any or all of the arrays may be empty.
* You must not assume that the indices are given in any particular order.
* You may receive input and produce output in any convenient, unambiguous string or list format. You may also choose to receive the three arrays in a different order.
* You may choose between 0-based and 1-based indexing.

This is code golf, so the shortest answer (in bytes) wins.

## Test Cases

Given in the format `B V I => Result` for 0-based indexing. If you're using 1-based indexing, increment the elements of the third array by 1.

```
[] [] [] => []
[] [1] [0] => [1]
[1,2] [] [] => [1,2]
[1,2] [3] [0] => [3,1,2]
[1,2] [3] [1] => [1,3,2]
[1,2] [3] [2] => [1,2,3]
[0,0,0] [1,1,1,1] [0,1,2,3] => [1,0,1,0,1,0,1]
[5,1,4,1,3] [0,0,7] [5,0,3] => [0,5,1,4,7,1,3,0]
[1,2,3,4] [4,3,2,1] [4,0,3,1] => [3,1,1,2,3,2,4,4]

```

Let me know if you come across other interesting edge cases, and I'll add them.

## Leaderboard

Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

```
# Language Name, N bytes

```

where `N` is the size of your submission. If you improve your score, you *can* keep old scores in the headline, by striking them through. For instance:

```
# Ruby, <s>104</s> <s>101</s> 96 bytes

```

```
var QUESTION_ID=50369;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),e.has_more?getAnswers():process()}})}function shouldHaveHeading(e){var a=!1,r=e.body_markdown.split("\n");try{a|=/^#/.test(e.body_markdown),a|=["-","="].indexOf(r[1][0])>-1,a&=LANGUAGE_REG.test(e.body_markdown)}catch(n){}return a}function shouldHaveScore(e){var a=!1;try{a|=SIZE_REG.test(e.body_markdown.split("\n")[0])}catch(r){}return a}function getAuthorName(e){return e.owner.display_name}function process(){answers=answers.filter(shouldHaveScore).filter(shouldHaveHeading),answers.sort(function(e,a){var r=+(e.body_markdown.split("\n")[0].match(SIZE_REG)||[1/0])[0],n=+(a.body_markdown.split("\n")[0].match(SIZE_REG)||[1/0])[0];return r-n});var e={},a=1,r=null,n=1;answers.forEach(function(s){var t=s.body_markdown.split("\n")[0],o=jQuery("#answer-template").html(),l=(t.match(NUMBER_REG)[0],(t.match(SIZE_REG)||[0])[0]),c=t.match(LANGUAGE_REG)[1],i=getAuthorName(s);l!=r&&(n=a),r=l,++a,o=o.replace("{{PLACE}}",n+".").replace("{{NAME}}",i).replace("{{LANGUAGE}}",c).replace("{{SIZE}}",l).replace("{{LINK}}",s.share_link),o=jQuery(o),jQuery("#answers").append(o),e[c]=e[c]||{lang:c,user:i,size:l,link:s.share_link}});var s=[];for(var t in e)e.hasOwnProperty(t)&&s.push(e[t]);s.sort(function(e,a){return e.lang>a.lang?1:e.lang<a.lang?-1:0});for(var o=0;o<s.length;++o){var l=jQuery("#language-template").html(),t=s[o];l=l.replace("{{LANGUAGE}}",t.lang).replace("{{NAME}}",t.user).replace("{{SIZE}}",t.size).replace("{{LINK}}",t.link),l=jQuery(l),jQuery("#languages").append(l)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",answers=[],page=1;getAnswers();var SIZE_REG=/\d+(?=[^\d&]*(?:<(?:s>[^&]*<\/s>|[^&]+>)[^\d&]*)*$)/,NUMBER_REG=/\d+/,LANGUAGE_REG=/^#*\s*([^,]+)/;
```

```
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script><link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"><div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table></div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table></div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody></table><table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody></table>
```

# Answer
# Pyth, 14 bytes

```
s.icFPQmedSCtQ

```

Demonstration.

This program takes the inputs as a 3-tuple of lists in the order Base, Indices, Values.

Explanation on the example `[5, 1, 4, 1, 3], [5, 0, 3], [0, 0, 7]`:

1. Take the input: implicit, Q is the input.
2. Make the index, value pairs: `CtQ` = `[(5, 0), (0, 0), (3, 7)]`
3. Sort the pairs into increasing index order: `SCtQ` = `[(0, 0), (3, 7), (5, 0)]`
4. Take the value out of each pair: `medSCtQ` = `[0, 7, 0]`
5. Split the base list at the location of the indicies: `cFPQ` = `[[], [5, 1, 4], [1, 3], []]`
6. Interleave 3 and 4: `.icFPQmedSCtQ` = `[[], 0, [5, 1, 4], 7, [1, 3], 0, []]`
7. Combine into one list: `s.icFPQmedSCtQ` = `[0, 5, 1, 4, 7, 1, 3, 0]`
> 13 votes

# Answer
# Python 2, 54

```
lambda B,*X:map(B.insert,*zip(*sorted(zip(*X))[::-1]))

```

Takes input as `B,I,V`. Modifies the input `B` when called (thanks to Martin Büttner for reminding me this is possible).

Uses `map` to call `B.insert` on each index/element pair. To avoid the issue of the list indices shifting as elements are inserted, sorts the pairs in decreasing order of index by an ugly zip/sort/unzip. If not for the shifting issue, we could just do `map(B.insert,*X)`.

**Old method (65):**

```
B,V,I=input()
for i,v in sorted(zip(I,V))[::-1]:B[i:i]=v,
print B

```
> 16 votes

# Answer
# Haskell, 62 bytes

```
import Data.List
f b v i=map snd$sort$zip[0.5,1.5..]b++zip i v

```

Usage example: `f [5,1,4,1,3] [0,0,7] [5,0,3]` -\> `[0,5,1,4,7,1,3,0]`.

How it works: augment the base list with "and-a-half" indices starting at `0.5` (e.g. `[(0.5,5),(1.5,1),(2.5,4),(3.5,1),(4.5,3)]`) and concatenate it with the index-value pairs. Sort and discard the index.

**Remark**: don't know if I'm cheating here. From a mathematical point of view it's fine, but a programmer might argue that the list of indices `[5,0,3]` is not a list of `Integers` as requested, but a list of `Fractionals` (to be exact, the type is polymorphic, but must belong to the `Fractional` class, e.g. `Float` or `Double`).
> 5 votes

# Answer
# K, ~~22~~ 21 bytes

```
{,//+(y@<z;(z@<z)_ x)}

```

We define a 3 argument function `{…}` with the implicit variables `x`, `y` and `z` representing the starting list, the value list and the index list, respectively. The "cut" operator (`_`) is used to split the starting list apart at the sorted list of given indices (`(z@<z)`). We interleave values (after sorting them correspondingly) with the split up chunks of the original array by forming a list (`(a;b)`), taking its transpose (`+`) and flattening the result (`,//`).

Usage example:

```
  f:{,//+(y@<z;(z@<z)_ x)}
{,//+(y@<z;(z@<z)_ x)}

  f[1 2 3 4;4 3 2 1;4 0 3 1]
3 1 1 2 3 2 4 4

  f[5 1 4 1 3;0 0 7;5 0 3]
0 5 1 4 7 1 3 0

```

Spaces around the underscore are necessary because K allows underscores in identifiers. K5 removes this potential ambiguity. If we could count on the indices coming in ascending order and underscores were not valid identifiers, we could use the much nicer 13 byte program:

```
{,//+(y;z_x)}

```

(sigh.)

## edit:

```
{,//+(y@<z;(z@<z)_ x)} / before
{,//+(y@<z;z[<z]_ x)}  / after

```

Breaks symmetry, but we can save a byte by using bracket-indexing (`[…]`) instead of the infix `@` indexing operator. Usually this makes programs longer, but in this case we needed parens anyway to sort `z` before performing the cut.
> 5 votes

# Answer
# Ruby, ~~60~~ ~~59~~ 53 bytes

```
->a,b,c{c.zip(b).sort.reverse.map{|i,v|a.insert i,v}}

```

And the ungolfed version

```
def riffle(array, values, indices)
    indices.zip(values).sort.reverse.each do |index, value|
        array.insert(index, value)
    end
end

```
> 5 votes

# Answer
# CJam, ~~34~~ ~~23~~ 18 bytes

```
{.\2/\ee+{0=}$1f=}

```

My first CJam submission. Advices are welcome, I'm sure there is a lot to golf.

16 bytes saved with the help of @MartinBüttner and @Dennis.

Function expecting input on the stack in order `B V I` (I is the topmost).

Example usage:

```
[5 1 4 1 3] [0 0 7] [5 0 3] {.\2/\ee+{0=}$1f=}~

```

Method:

* pair the array's `i`th element with `i+0.5`
* pair insert values with insert positions
* merge the resulting two arrays
* sort array based on position elements
* keep value elements
> 5 votes

# Answer
# Pyth, 17 bytes

```
ssC,cFPQamedSCtQ]

```

@isaacg beat my solution already. But since I had my documentation finished, I'm just gonna post it anyways.

This takes the input in the format `B, I, V`. You can try it here: Demonstration or Test Suite

### Explanation:

I'm using the example `B = [5,1,4,1,3], I = [5,0,3], V = [0,0,7]` from the OP.

```
                    implicit: Q = input()
      PQ            all elements but last of Q   => [[5,1,4,1,3], [5,0,3]]
    cF              split B it the indices in I  => [[], [5,1,4], [1,3], []]

              tQ    all elements but first of Q  => [[5,0,3], [0,0,7]]
             C      zip                          => [(5,0), (0,0), (3,7)]
            S       sort                         => [(0,0), (3,7), (5,0)]
         med        extract the end of each pair => [0,7,0]
        a       ]   append an empty list         => [0,7,0,[]]

   ,                create a pair => ([[], [5,1,4], [1,3], []], [0,7,0,[]])
  C                 zip           => [([],0), ([5,1,4],7), ([1,3],0), ([],[])]
 s                  sum           => ([],0,[5,1,4],7,[1,3],0,[],[])
s                   sum           => [0,5,1,4,7,1,3,0]

```
> 4 votes

# Answer
# JavaScript (ES6), 75

A function with 3 array parameters, returnning an array. Weirdly, this function modifies its `i` parameter (as kindly allowed by OP)

Test running the snippet, Firefox only as usual.

```
f=(b,v,i,j=0)=>b.concat(v).map(p=>(p=i.indexOf(j))<0?b[j++]:(i[p]=-1,v[p]))

// TEST
out=x=>O.innerHTML+=x+'\n'

test=[
{ b:[], v:[], i:[], k:[] },
{ b:[], v:[1], i:[0], k:[1] },
{ b:[1,2], v:[], i:[], k:[1,2] },
{ b:[1,2], v:[3], i:[0], k:[3,1,2] },
{ b:[1,2], v:[3], i:[1], k:[1,3,2] },
{ b:[1,2], v:[3], i:[2], k:[1,2,3] },
{ b:[0,0,0], v:[1,1,1,1], i:[0,1,2,3], k:[1,0,1,0,1,0,1] },
{ b:[5,1,4,1,3], v:[0,0,7], i:[5,0,3], k:[0,5,1,4,7,1,3,0] },
{ b:[1,2,3,4], v:[4,3,2,1], i:[4,0,3,1], k:[3,1,1,2,3,2,4,4] }
];

test.forEach(x=>{
  r = f(x.b,x.v,x.i.slice(0)) // pass a copy of i, as the function will alter it
  ok = ''+r==''+x.k
  s='Test ' + (ok?'OK':'FAIL')
  +'\n B ['+x.b
  +']\n V ['+x.v
  +']\n I ['+x.i
  +']\n Result ['+r
  +']\n Check  ['+x.k
  +']\n'
  out(s)

})
```

```
<pre id=O></pre>
```
> 4 votes

# Answer
# Mathematica, ~~52~~ 51 bytes

```
Last/@(Tr@#2->#&~MapIndexed~#⋃Thread[#3+.5->#2])&

```

### Example:

```
In[1]:= f = Last/@(Tr@#2->#&~MapIndexed~#⋃Thread[#3+.5->#2])&;

In[2]:= f[{5, 1, 4, 1, 3}, {0, 0, 7}, {5, 0, 3}]

Out[2]= {0, 5, 1, 4, 7, 1, 3, 0}

```

### Explanation:

Using the example above.

* `Tr@#2->#&~MapIndexed~#` =\> `{1 -> 5, 2 -> 1, 3 -> 4, 4 -> 1, 5 -> 3}`
* `Thread[#3+.5->#2]` =\> `{5.5 -> 0, 0.5 -> 0, 3.5 -> 7}`
* Then take the (sorted) union of these two lists. (=\> `{0.5 -> 0, 1 -> 5, 2 -> 1, 3 -> 4, 3.5 -> 7, 4 -> 1, 5 -> 3, 5.5 -> 0}`)
* And then take the last element of each pair. (=\> `{0, 5, 1, 4, 7, 1, 3, 0}`)
> 4 votes

# Answer
# CJam, ~~30~~ 29 bytes

```
q~.\2/$z~0@+2ew@f{\~@<>}.\e_p

```

This is tooo long. I feel like this is not a golfing language submission :|

Try it online here
> 3 votes

# Answer
# R, 75 bytes

```
function(b,v,i){n=b;j=0;for(g in v)n=append(n,g,i[j<-j+1]+sum(i<i[j])-1);n}

```

This creates an unnamed function. To call it, give it a name, e.g. `f=function...`. Note that the arrays must be 1-indexed because that's just how R rolls.

Ungolfed + explanation:

```
f <- function(b, v, i) {
    # Initialize the output vector to b
    n <- b

    # Initialize an index over the indices
    j <- 0

    # Loop over the values to insert
    for(g in v) {
        # Get the index of the next given insertion index
        j <- j + 1

        # Insert g into n.
        # The position at which to insert the value is determined by
        # adding the number of indices less than the current one and
        # subtracting 1. The subtraction is because we're using the
        # `after` argument in the `append` function.

        n <- append(n, g, i[j] + sum(i < i[j]) - 1)
    }

    # Return n
    n
}

```

Examples:

```
> f(c(), c(), c())
[1] NULL

> f(c(0, 0, 0), c(1, 1, 1, 1), c(1, 2, 3, 4))
[1] 1 0 1 0 1 0 1

> f(c(5, 1, 4, 1, 3), c(0, 0, 7), c(6, 1, 4))
[1] 0 5 1 4 7 1 3 0

```

Suggestions are welcome as always!
> 3 votes

# Answer
# CJam, 19 bytes

```
l~_,)N*q~.{t}~.\N-p

```

This is a full program that the reads the arrays **B**, **I** and **V** (one per line, in that order) from STDIN.

Try it online in the CJam interpreter.

### How it works

```
l~    e# Evaluate the first line of input.
_,)   e# Compute the array length and add 1.
N*    e# Push a string of that many linefeeds.
q~    e# Evaluate the remaining input.
.{t}~ e# Vectorized array set: for each index in the array from line 2, replace the
      e# LF at that index by the corresponding element of the array from line 3.
.\    e# Interleave the two arrays on the stack.
N-    e# Remove the linefeeds.
p     e# Print.

```

---

# CJam, 20 bytes

```
{Qa+@@.{a2$2$=+t}e_}

```

This is an anonymous function that pops **B**, **V** and **I** (top to bottom) from the stack and leaves a single array on the stack in return.

Try it online in the CJam interpreter.

### How it works

```
Qa+      e# Append [[]] to B.
@@       e# Rotate V and I on top of B.
.{       e# For each v in V and the corresponding i in I:
   a     e#     Push [v].
   2$2$= e#     Retrieve b := B[i].
   +     e#     Append to push [v b].
         e#     The stack now consists of: B i [v b]
   t     e#     Set B[i] := [v b].
}        e#
e_       e# Flatten B.

```
> 2 votes

# Answer
# Ruby, 48 bytes

I think this complies with the rules, but please check.

```
->b,v,i{l=-1;i.map{|j|b[j]=[v[l+=1],b[j]]};b*?:}

```

Unnamed function taking the three arrays as input. Outputs a string that can be parsed unambiguously into an array of numbers with the ruby expression `x.split(/:+/).map(&:to_i)`.

Test cases on ideone.

I could save 3 more bytes, but the output format `[1,2,[nil,5]]` is stretching the rules a bit too mych imo, although it is unambiguous.
> 1 votes

# Answer
# R, 60

As an unnamed function that takes b, v and i

```
function(b,v,i){e=c(NA,rbind(b,NA));e[i*2+1]=v;e[!is.na(e)]}

```

Expands b with NAs Fills the gaps where required with v Returns the vector without NAs

```
> f=function(b,v,i){e=c(NA,rbind(b,NA));e[i*2+1]=v;e[!is.na(e)]}
> f(c(), c(), c())
logical(0)
> f(c(0, 0, 0), c(1, 1, 1, 1), c(0, 1, 2, 3))
[1] 1 0 1 0 1 0 1
> f(c(5, 1, 4, 1, 3), c(0, 0, 7), c(5, 0, 3))
[1] 0 5 1 4 7 1 3 0

```
> 1 votes

# Answer
# Java, ~~253, 226, 219,~~ 209

not exactly a winner, but oh well.

Assuming that B, V, and I are not null. v (lowercase v) is the length of the Values/Indicies arrays. R is the returned array. r is the length of the returned array. x, y, and i are all temporary ints.

```
int[]f(int[]B,int[]V,int[]I){int v=V.length,r=B.length+v,x,y,i;int[]R=java.utils.Arrays.copyOf(B,r);for(x=0;x<v;x++){i=I[x];for(y=0;y<x;y++)if(I[x]>I[y])i++;for(y=r-2;y>=i;y--)R[y+1]=R[y];R[i]=V[x];}return R;}

```

expanded:

```
int[]f( int[] B, int[] V, int[] I ) {
    int v = V.length, //length of Values
        r = B.length + v, //length of the result
        x, y, i; //temps
        int[] R = java.utils.Arrays.copyOf( B, r );
        for( x = 0; x < v; x++ ) {
        i = I[x];
        for( y = 0; y < x; y++ )
            if( I[x] > I[y] )
                i++;
        for( y = r - 2; y >= i; y-- )
            R[y+1] = R[y];
        R[i] = V[x];
    }
    return R;
}

```
> 1 votes

# Answer
## APL, 22 bytes

```
{(∊⌽2↑⍵)[⍋(2⊃⍵),⍳≢⊃⍵]}

```

In ⎕IO←0 to match the test cases.

It's a standard algorithm: the index vector of the first argument is appended to the given indexes (3rd argument).  computes the permutation that would sort the indexes in ascending order. Since APL's sorting algorithm is stable by definition, the permutation computed puts the element of the catenation of the second and first argument in the right place.

For instance:

```
    {(∊⌽2↑⍵)[⍋(2⊃⍵),⍳≢⊃⍵]}(5 1 4 1 3)(0 0 7)(5 0 3)
0 5 1 4 7 1 3 0

```
> 1 votes

---
Tags: code-golf, array
---


title: Rank a list of scores with "skips"

text:
# Question
Title: Rank a list of scores with "skips"
Given a list of scores (non-negative integers) pre-sorted from greatest to least:

```
[ 10, 10, 6,  6,  4,  0]

```

Assign each score an integer rank, beginning with 1 and ascending, such that equal scores have the same rank (i.e. they are tied):

```
[ 1, 1, 3, 3, 5, 6 ]

```

In the case of ties, ranks are "skipped," e.g. since the first and second-greatest scores (10 and 10) are tied, they both have rank 1, and rank 2 is "skipped," so the third-greatest score (6) has rank 3.

Output a list of non-descending ranks corresponding to the input scores.

## Examples

```
In:  10 10  6  6  4  0
Out:  1  1  3  3  5  6

```

```
In:  10  9  8
Out:  1  2  3

```

```
In:   0  0  0
Out:  1  1  1

```

```
In:  16 15 15 12 11 11 10  9  9  9  8  2  2  2  0
Out:  1  2  2  4  5  5  7  8  8  8 11 12 12 12 15

```

## Input

Assume all scores will be between 0 and 1,000 inclusive, and the input will have no more than 500 scores. Input can be in whatever format is convenient for your language of choice (including but not limited to STDIN, arguments to a function, an array already stored in a variable, etc.).

## Output

Return or store in a variable the resulting ordered list of ranks, or write it to STDOUT in a human-readable way (e.g. `1 2 3`, `[1,2,3]`, `1\n2\n3\n`, and `{ 1, 2, 3 }` are all fine; `123` is not, for want of a delimiter). The input scores may be stored/printed along with their corresponding output ranks, but that's not required.

## Restrictions

You may use any standard library your language offers. Standard loopholes apply.

## Winning conditions

This is , so the smallest program (in bytes) wins. In case of a tie, the answer with the most votes wins.

### Notes

This is based on a Ruby question on SO that generated some interesting answers, including one very short one. I encourage you to come up with your own solutions before looking there.

# Answer
# J (~~7~~ 6)

EDIT: Oh, wait! It doesn't need to be a function!

```
>:i.~y

```

Thank god for `i.~`...

```
>:@:i.~

```

Or as a named function (3 chars more, but not functionally different):

```
f=:>:@:i.~

```

Run tests:

```
   f=:>:@:i.~
   f 10 10  6  6  4  0
1 1 3 3 5 6
   f 10  9  8
1 2 3
   f 0  0  0
1 1 1
   f 16 15 15 12 11 11 10  9  9  9  8  2  2  2  0
1 2 2 4 5 5 7 8 8 8 11 12 12 12 15

```
> 8 votes

# Answer
## T-SQL (40)

```
SELECT RANK()OVER(ORDER BY B DESC)
FROM @

```

Assume `@` is a table containing the scores as rows.
> 8 votes

# Answer
# Python (33 characters)

```
lambda x:[1+x.index(i)for i in x]

```

Functionally the same as my J answer.
> 3 votes

# Answer
# Pyth, 6

```
m'XYdY

```

List is stored in Y to begin with. This is functionally the same as the 22 character ruby solution: map over d in Y to index of d in Y plus 1, then print.

Example:

```
$ echo "=Y[16 15 15 12 11 11 10 9 9 9 8 2 2 2 0)m'XYdY" | python3 pyth.py

[1, 2, 2, 4, 5, 5, 7, 8, 8, 8, 11, 12, 12, 12, 15]

```
> 3 votes

# Answer
## APL, 2 bytes

```
⍳⍨

```

In `⎕IO←1`. Dyadic iota searches its right argument into its left argument. The operator  copies the right argument to the left argument if the operand is used monadically. Hence the solution simply searches the position of each one of the elements of the vector given in itself.

Samples:

```
    ⍳⍨10 10 6  6  4  0
1 1 3 3 5 6
    ⍳⍨0  0  0
1 1 1
    ⍳⍨16 15 15 12 11 11 10  9  9  9  8  2  2  2  0
1 2 2 4 5 5 7 8 8 8 11 12 12 12 15

```
> 3 votes

# Answer
# STATA (16)

```
egen b=rank(c),f

```

Result is in b.

Assumes c is a variable in the dataset containing the input.
> 2 votes

# Answer
## Haskell (31)

```
f x=succ.(`elemIndexJust`x)<$>x -- Requires the Safe module

```

**Usage:**

```
f [10,10,6,6,4,0] --evaluates to [1,1,3,3,5,6]

```
> 2 votes

# Answer
So as to establish a baseline:

# Ruby (38)

Assuming `a` is an array:

```
r,i=1,0;a.map{|x|i+=1;x==a[i-2]?r:r=i}

```

(This is based on falsetru's answer on the original SO thread and isn't my original work. I know there's a Ruby solution that's 22 characters, but I'd like to see someone come up with one shorter than that in Ruby.)
> 1 votes

# Answer
# JavaScript (E6) 41

A function with an array argument, returning an array

```
F=s=>s.map((n,i)=>p-n?(p=n,r=i+1):r,p=-1)

```

**Test** In Firefox console

```
F([10,10,6,6,4,0])

```

Output: \[1, 1, 3, 3, 5, 6\]

```
F([16, 15, 15, 12, 11, 11, 10, 9, 9, 9, 8, 2, 2, 2, 0])

```

Output: \[1, 2, 2, 4, 5, 5, 7, 8, 8, 8, 11, 12, 12, 12, 15\]
> 1 votes

# Answer
## R, 15

with input stored as vector `x`,

```
rank(-x,T,"mi")

```
> 1 votes

# Answer
## Powershell (70)

```
$n=1;$c=0;$l=$a[0];$a|%{if($l-eq$_){$n}else{$n=$c+1;$n}$l=$a[$c];$c++}

```

It's only 51 characters if you take out the variable assignments at the beginning, which makes me feel slightly less inadequate.

Assumes $a is assigned and sorted as specified by the problem. $n tracks rank, $c is just a counter which works with $l, the last element checked in the array.

If there's anything I can do to improve this, I'd love to know.
> 1 votes

# Answer
# Java (57)

Using the same 'rules' as Allbeert:

Constant `i` is defined as `int[]` array and contains the input, `z` contains the size of the input. Others, `l`,`c`,`x` and `n`, are defined as `int`.

The left over snippet of code is:

```
l=0;c=1;for(x=0;x<z;x++){n=i[x];i[x]=n==l?c:(c=x+1);l=n;}

```

The result is in the input array.
> 1 votes

# Answer
# Ruby, 22

I haven't looked at the SO thread but I imagine this is what they came up with.

```
a.map{|i|a.index(i)+1}

```

Edit: Yep, it is. I doubt it's possible to get smaller in Ruby, unless you assume you're defining it as an Array method, then you can do it in 18 characters with

```
map{|i|index(i)+1)

```

But of course the full program around that snippet looks like

```
class Array
  def ranks
    map{|i|index(i)+1)
  end
end

p [1, 2, 2, 4, 5, 5, 7, 8, 8, 8, 11, 12, 12, 12, 15].ranks

```
> 1 votes

# Answer
# \>\<\> (47)

Not particularly optimized, just testing the water with my first golf.

```
r:1:nr2&>ao$:@=?vr~&:|
&1+&l3)?^;      >r:nr

```

Assumes that the input is prepopulated in the stack, such that the first element of the input is the first to be popped off.

Testing:

```
fish.py ranks.fish -v 1 2 3 4 5 6 7 8 9 9 10 10

```

outputs

```
1
1
3
3
5
6
7
8
9
10
11
12

```
> 1 votes

# Answer
# Clojure, 35

With some Java interop mixed in:

```
(fn[l](map #(+ 1(.indexOf l %)) l))

```

REPL session:

```
golf> ((fn[l](map #(+ 1(.indexOf l %)) l)) [10 10  6  6  4  0])
(1 1 3 3 5 6)
golf> ((fn[l](map #(+ 1(.indexOf l %)) l)) [16 15 15 12 11 11 10  9  9  9  8  2  2  2  0])
(1 2 2 4 5 5 7 8 8 8 11 12 12 12 15)

```
> 1 votes

# Answer
# C - 62

As a code snippet, since there was no requirement for function or full program.

Assumes `a`, `n`, `j`, and `k` are already defined as `int*`, `int`, `int`, and `int` respectively, where `a` is an array containing the input, and `n` contains the length of the input.

This fails for input of length 0, in which case 3 more characters are needed.

```
printf("1");for(k=j=1;++j<=n;)printf(" %d",*a-*(a+++1)?k=j:k);

```
> 0 votes

---
Tags: code-golf, array
---


title: Golf me an HQ9+ Compiler

text:
# Question
Title: Golf me an HQ9+ Compiler
Your task is "simple" should you choose to accept it.

Write an HQ9+ compiler in a language of your choice.

HQ9+ has four commands (as you may be able to tell) H prints "Hello, World!" Q prints out the source code (this can either be the compiled source or HQ9+ source for the purpose of this challenge),9 prints out the lyrics to 99 bottles of beer on the wall, and + is essentially a noop.

Your submission should be written in some language X, and should take input of HQ9+ source and output a program in X.

Wait, I know what you're thinking. This is not a duplicate of Creating a HQ9+ interpreter as it should not run HQ9+ code, but rather compile it. It should output a fully functional program.

---

Rules 1. Language X should satisfy the traditional definition of a language
2. Standard loopholes disallowed
3. This is code golf (shortest program in bytes wins)
4. Your solution must be testable
5. X cannot be HQ9+ or an extension of HQ9+

---

Clarifications

There has been some confusion as to what the q command should do. I had originally thought that it would output the compiled code (i.e code in langauge X), but my reference implementation outputs the hq9+ code. I would like to see either one depending on your golfing preferences.

# Answer
> 11 votes
## Actually, 17 bytes

```
"HQ9"∩εj'N'9(t'.j

```

Try it online!

This program compiles HQ9+ to Actually.

Actually is (almost) a superset of HQ9+ - the only difference is that the `9` command in HQ9+ is `N` in Actually. Because `+` is a NOP in HQ9+ (the accumulator is never actually used or displayed, and thus many implementations treat it as a NOP), it is stripped out.

Explanation:

```
"HQ9"∩εj'N'9(t'.j
"HQ9"∩εj           strip all characters not in "HQ9", preserving order
        'N'9(t     replace all occurrences of "9" with "N"
              '.j  insert a "." between every pair of characters

```

-1 byte from Christian Irwin

# Answer
> 5 votes
# Java only 551 bytes

Joined in on the fun! This is a java compiler which compilers HQ9+ to java.Java is not verbose at all. Some code shamelssly stolen borrowed from "99 Bottles of Beer".

---

```
public class a{public static void main(String[]a){System.out.printf("public class a{public static void main(String[]z){String p=\"%s\";for(char a:p.toCharArray()){if(a=='H')p(\"Hello, World\\n\");if(a=='Q')p(p);if(a=='9'){String b=\" of beer\",c=\" on the wall\",n=\".\\n\",s;for(int i=100;i-->1;){s=\" bottle\"+(i>1?\"s\":\"\");p(i+s+b+c+\", \"+i+s+b+n+(i<2?\"Go to the store and buy some more, 99\":\"Take one down and pass it around, \"+(i-1))+\" bottle\"+(i!=2?\"s\":\"\")+b+c+n);}}}}public static void p(String s){System.out.print(s);}}",a[0]);}}

```

# Answer
> 3 votes
# Mathematica, 453 bytes

```
"("<>#~StringReplace~{"H"->"Print[\"Hello, world!\"]; ","Q"->"Print[ToString[#0, InputForm]]; ","9"->"a = StringJoin[ToString[#1], {\" bottle\", If[#1 < 2, \"\", \"s\"], \" of beer\"}] & ; b = StringJoin[a[#1], \" on the wall\"] & ; Do[Print[b[i], \", \", a[i], c = \".\n\", If[i < 2, StringJoin[\"Go to the store and buy some more, \", b[99], \".\"], StringJoin[\"Take one down and pass it around, \", b[i - 1], c]]], {i, 99, 1, -1}]; ",_->""}<>") & "&

```

"99 Bottles" code adapted from @alephalpha's program. Outputs a function that, when run, will print the output. (Could probably still find a less verbose quine method.)

# Answer
> 2 votes
# Haskell, 383 bytes

```
    s#'Q'="putStrLn\""++s++"\"\n"
    s#'H'="putStr\"Hello, World\\n\"\n"
    s#'9'="f\n"
    s#_=""
    c s="o=\" of beer on the wall\"\na 1=\"1 bottle\" \na n=shows n\" bottles\"\nb 1=\"Go to the store and buy some more, \"++a 99\nb n=\"Take one down and pass it around, \"++a(n-1)\nf=putStr$[99,98..1]>>= \\n->[a n,o,\", \",a n,\" of beer.\\n\",b n,o,\".\\n\\n\"]>>=id\nmain=do\n"++(concat.map(s#)$s)

```

Thanks to nimi for the beer.

# Sample outout

```
o=" of beer on the wall"
a 1="1 bottle"
a n=shows n" bottles"
b 1="Go to the store and buy some more, "++a 99
b n="Take one down and pass it around, "++a(n-1)
f=putStr$[99,98..1]>>= \n->[a n,o,", ",a n," of beer.\n",b n,o,".\n\n"]>>=id
main=do
putStr"Hello, World\n"
putStrLn"HQ9+"
f

```

# Answer
> 1 votes
# Dyalog APL, 244

```
H P
h←'''hello, world'''
q←M,(P/⍨1+P=M),M←''''
n←'∊{z←8↑k←'' of beer on the wall''⋄r←{r←'' bottles''↑⍨8-⍵=1⋄⍵=0:''No'',r⋄r,⍨⍕⍵}⋄m,k,g,(m←r⍵),z,g,''Take one down and pass it around'',z,g,(r⍵-1),k,g,g←3⌷⎕tc}¨⌽⍳99'
⎕FX'F',h h q q n''['HhQq9'⍳P]

```

This is a tfn `H`, which takes a HQ9+ program as its input and defines in the workspace a tfn `F`, which runs that program.

Example:

```
      H 'QhqH' ⍝ compile 'QhqH'
      F ⍝ run compiled function F
QhqH
hello, world
QhqH
hello, world
      ⎕CR 'F' ⍝ source code for function F
 F
 'QhqH'
 'hello, world'
 'QhqH'
 'hello, world'

```

---
Tags: code-golf, code-generation, compiler
---


title: Marching Through A City

text:
# Question
Title: Marching Through A City
There is a parade marching through a city! There are 3 main groups of marchers: the (B)and, Poster (C)arriers, and (F)lag Holders. Also, every (P)oliceman in the whole city is on duty.

Flag holders (F) can march anywhere in the parade, but two flag holders cannot march next to each other, unless three or more flag holders are together.

The band (B) has to be together. The poster carriers (C) all have to be behind the band (either together, or in two groups).

Given the number of flag holders, poster carriers, band members, and policemen separated by your choice of delimiter, print one line for every possible configuration, organized in alphabetical order.

Test case 1:

```
Input:
2 2 2 0
Output:
CCFBBF
CFCBBF
CFCFBB
FCCBBF
FCCFBB
FCFCBB

```

Test case 2:

```
Input:
3 3 3 0
Output:
CCCBBBFFF
CCCFFFBBB
CCFCFBBBF
CCFFFCBBB
CFCCFBBBF
CFCFCBBBF
CFFFCCBBB
FCCCFBBBF
FCCFCBBBF
FCFCCBBBF
FCFCFCBBB
FFFCCCBBB

```

Test case 3:

```
Input:
2 2 2 1
Output:
CCBBFPF
CCFBBFP
CCFBBPF
CCFPBBF
CCFPFBB
CCPFBBF
CFCBBFP
CFCBBPF
CFCFBBP
CFCFPBB
CFCPBBF
CFCPFBB
CFPCBBF
CFPCFBB
CFPFCBB
CPCFBBF
CPFCBBF
CPFCFBB
FCCBBFP
FCCBBPF
FCCFBBP
FCCFPBB
FCCPBBF
FCCPFBB
FCFCBBP
FCFCPBB
FCFPCBB
FCPCBBF
FCPCFBB
FCPFCBB
FPCCBBF
FPCCFBB
FPCFCBB
FPFCCBB
PCCFBBF
PCFCBBF
PCFCFBB
PFCCBBF
PFCCFBB
PFCFCBB

```

This is code-golf, so the shortest source code in bytes wins.
\*Note: It doesn't count if it takes longer than 3 seconds to run each test case. I won't use integers more than 20.

# Answer
> 2 votes
## CJam, 49 bytes

```
l~"BCFP".*(a\s+m!:s{_"FP"-W%_$=\e`[2'F]e=!&},_&N*

```

Try it online!

Input format is `[B C F P]`.

# Answer
> 3 votes
# Pyth, 56 bytes

```
jf&!},2\FrT8!:T"B.*C|C([^C]+C+){2}|B[^B]+B"0{S.ps*V"FCBP

```

Try it online!

---
Tags: code-golf, combinatorics, permutations
---


title: Reverse and subtract

text:
# Question
Title: Reverse and subtract
# Challenge description

Let's take a positive integer `n`, reverse its digits to get `rev(n)` and get the absolute value of the difference of these two numbers: `|n - rev(n)|` (or `abs(n - rev(n))`).

Example:

```
n = 5067
rev(n) = 7605
|n - rev(n)| = |5067 - 7605| = |-2538| = 2538

```

After repeating this operation sufficiently many times, most numbers will become `0` (thus terminating the loop)...

```
5067 -> 2538 -> 5814 -> 1629 -> 7632 -> 5265 -> 360 -> 297 -> 495 -> 99 -> 0

```

...though some numbers (like `1584`) get stuck in an infinite loop:

```
1584 -> 3267 -> 4356 -> 2178 -> 6534 -> 2178 -> 6534 -> 2178 -> 6534 -> ...
                        ^ infinite loop starts here

```

Your job is to determine if a given integer gets stuck in an infinite loop.

# Input description

A positive integer.

# Output description

A truthy value (`True`, `1`) if the number gets stuck in an infinite loop, a falsy value (`False`, `0`) otherwise.

# Notes

* Trailing zeroes should be ommited. i.e. `rev(5020) = 205`.
* Remember that this is , so make your code as short as possible!
* Relevant sequence: A072140

# Answer
# Pyth, 5 bytes

4 bytes thanks to FryAmTheEggman

```
uas_`

```

Test suite.

The truthy value is one of the numbers in the loop.

The falsey value is `0`.

## Explanation

```
uas_`      Input:Q
uas_`GGQ   Implicit filling of variables.

u      Q   Set G as Q: do this repeatedly until result seen before: Set G as
 a             the absolute difference of
     G             G
    `              convert to string
   _               reverse
  s                convert to integer
      G        and G

```
> 18 votes

# Answer
## Mathematica, ~~39~~ 37 bytes

```
Nest[Abs[#-IntegerReverse@#]&,#,#]<1&

```

Simply applies the reverse/subtract transformation `n` times to the input `n` and then checks whether the result is `0`. It can never take more than `10n` steps to reach a loop, because the transformation cannot increase the number of digits, and there are less than `10n` numbers with no more digits than `n`. See Dennis's proof for how to reduce this bound to `n`.
> 11 votes

# Answer
# Jelly, ~~6~~ 5 bytes

```
ṚḌạµ¡

```

Try it online!

### Background

This uses @MartinEnder's upper bound of **10n** iterations and the following observations.

1. There are **9 × 10k - 1** positive integers **n** with **k** digits.
2. The difference of a number and its reverse is always a multiple of **9**, so only **10k - 1** of them can occur after the first iteration.
3. Of the multiples, more than **1 / 10** will lose a digit in the next iteration (for starters, all that start and end with the same digits, and roughly twice as many if the first digit is neither a **1** nor a **9**), so it takes at most **9 × 10k - 2** to either enter a loop or lose a digit.
4. Applying the same reasoning to the eventual resulting integer of **k - 1** digits and so on, it takes at most **9 × 10k - 2 \+ 9 × 10k - 2 \+ … ≤ 10k - 1 ≤ n** iterations to enter a loop or reach **0**.

### How it works

```
ṚḌạµ¡  Main link. Argument: n

   µ¡  Iteratively apply the chain to the left n times.
Ṛ      Reverse n (casts to digits).
 Ḍ     Undecimal; convert from base 10 to integer.
  ạ    Take the absolute difference of the result and the argument.

```
> 11 votes

# Answer
# Oracle SQL 11.2, 136 bytes

```
WITH v(n)AS(SELECT :1 FROM DUAL UNION ALL SELECT ABS(n-REVERSE(n||''))FROM v WHERE n>0)CYCLE n SET c TO 0 DEFAULT 1 SELECT MIN(c)FROM v;

```

Un-golfed

```
WITH v(n) AS
(
  SELECT :1 FROM DUAL
  UNION ALL
  SELECT ABS(n-REVERSE(n||''))FROM v WHERE n>0
) CYCLE n SET c TO 0 DEFAULT 1
SELECT MIN(c)FROM v

```
> 5 votes

# Answer
## APL, 26 chars

```
0∘{⍵∊⍺:×⍵⋄(⍺,⍵)∇|⍵-⍎⌽⍕⍵}

```

We use the left argument as the accumulator of the values we've seen already. We initialise it to "0", which is one of the two termination conditions. The guard `⍵∊⍺:×⍵` is read: "is the right argument something we've seen already (and that includes zero)? If so return the sign of the number, that is 1 or 0". Otherwise let's recurse by calling ourselves with the absolute value of the subtraction after having catenated the current value to the left argument.

A recast of the Mathematica solution by Martin Ender would clock at **21 chars**:

```
 {×{|⍵-⍎⌽⍕⍵}⍣(10×⍵)⊣⍵}

```

It reads: "what is the sign of the result after applying the wanted 10n times"?
> 5 votes

# Answer
## CJam, ~~15~~ 13 bytes

```
ri_{_sW%i-z}*

```

Test it here.

Same as my Mathematica answer.
> 4 votes

# Answer
# Python 2, 50 bytes

```
n=input()
exec'n=abs(n-int(`n`[::-1]));'*n
print n

```

Test it on Ideone.

### Background

This uses @MartinEnder's upper bound of **10n** iterations and the following observations.

1. There are **9 × 10k - 1** positive integers **n** with **k** digits.
2. The difference of a number and its reverse is always a multiple of **9**, so only **10k - 1** of them can occur after the first iteration.
3. Of the multiples, more than **1 / 10** will lose a digit in the next iteration (for starters, all that start and end with the same digits, and roughly twice as many if the first digit is neither a **1** nor a **9**), so it takes at most **9 × 10k - 2** to either enter a loop or lose a digit.
4. Applying the same reasoning to the eventual resulting integer of **k - 1** digits and so on, it takes at most **9 × 10k - 2 \+ 9 × 10k - 2 \+ … ≤ 10k - 1 ≤ n** iterations to enter a loop or reach **0**.
> 4 votes

# Answer
## Python, ~~129~~ ~~120~~ 96 bytes

If a exception is caught (normally the only exception that can be throwed with this function is a RuntimeError, due to the infinite recursion), print 1. Otherwise, print the result, 0.

```
def r(n):a=abs(n-int(str(n)[::-1]));return a and r(a)
try:print(r(int(input())))
except:print(1)

```

Thanks to @LeakyNun
Thanks to @shooqie
> 3 votes

# Answer
# Python, ~~101~~ 98 bytes

Tortoise and hare algorithm.

Truthy is any value in loop, falsey is `0`.

```
g=lambda n:abs(n-int(str(n)[::-1]))
def r(n):
    t=g(n);h=g(t)
    while t-h:h=g(g(h));t=g(t)
    return h

```

Ideone it!
> 3 votes

# Answer
## Python 2, ~~85~~ ~~84~~ 83 bytes

```
L=[]
def f(n,L=L):
    if n<1or n in L:print n<1
    else:L+=[n];f(abs(n-int(`n`[::-1])))

```

Another Python answer. It adds n to a list for every iteration, and if n is already in the list, it outputs `False`. Otherwise, it works down to 0.

*Thanks @NonlinearFruit for one byte.*
> 3 votes

# Answer
## 05AB1E, ~~11~~ ~~8~~ 6 bytes

```
DFÂï-Ä

```

**Explained**

```
DF          # input number of times do
  Â         # push current number and its reverse
   ï-       # convert reverse to int and subtract
     Ä      # absolute value
            # implicitly print after loop ends

```

Truthy value is a number from the loop.
Falsy value is 0.

Try it online

Uses the upper bound explained in Dennis' Jelly answer

Saved 2 bytes thanks to @Adnan

In version 7.9 of 05AB1E the following 5-byte solutions works as noted by @Adnan

```
DFÂ-Ä

```
> 3 votes

# Answer
# Brachylog, ~~49~~ ~~32~~ 23 bytes

```
:10*N,?:N:{r:?-+.}itT'0

```

Returns `true` for infinite loops and `false` otherwise.

This is a shameless adaptation of Martin Ender's algorithm.

### Previous answer, 32 bytes

```
g{tTr:T-+U(0!\;?:ImU;?:[U]c:1&)}

```

### Explanation of the previous answer

```
g{                             } Call predicate with [Input] as input
  tT                             T is the last element of Input
    r:T-                         Subtract T from the reverse of T
        +U                       U is the absolute value of T
          (0!\                   If U is 0, return false
              ;                  Or
               ?:ImU             If U is in Input, return true
                    ;            Or
                     ?:[U]c:1&)  Recursive call with U concatenated to the Input

```
> 2 votes

# Answer
# Java 7, 161 bytes

This requires an import but I wrote it as a function. Yell at me in the comments if a full program is preferred in this scenario. Outputs 1 if there's an infinite loop and 0 if the value gets to 0.

```
import java.util.*;int z(int a){int o,r,c=a;Set s=new HashSet();while(c!=0){for(r=0,o=c;o!=0;r=r*10+o%10,o/=10);c=Math.abs(c-r);if(!s.add(c))return 1;}return 0;}

```
> 1 votes

# Answer
## PowerShell v2+, 94 bytes

```
param($n)for($a=,0;){if(($n=[math]::Abs($n-(-join"$n"["$n".length..0])))-in$a){$n;exit}$a+=$n}

```

Takes input `$n`, starts an infinite `for` loop, with `$a=,0` as the initial condition (this uses the comma operator to set `$a` to an array of one element, `0`). This `$a` is our array of already-seen values.

Each loop iteration we check an `if`. The condition first sets the next value of `$n` using string-reversing and the `[math]::Abs` .NET call, and checks whether that value is already `-in` `$a`. If so, we output `$n` and `exit`. Otherwise, we add that value to the array and continue the loop.

Outputs `0` for input values where it does not go into an infinite loop (which is falsey in PowerShell) and outputs the value where the loop was encountered otherwise (non-zero integers are truthy). For example, outputs `2178` for input `1584`.
> 0 votes

# Answer
## Haskell, 65 bytes

```
_#0=0
a#n|elem n a=1|1<2=(n:a)#abs(n-(read$reverse$show n))
([]#)

```

Returns `0` for False and `1` for True. Usage example: `([]#) 1584` -\> `1`.

The obvious approach: keep a list with all results seen so far. Calculate the next number until `0` or it's in the list.
> 0 votes

# Answer
## JavaScript (ES6), 75 bytes

```
f=(n,...a)=>a.includes(n=n<0?-n:n)?n:f([...n+``].reverse().join``-n,n,...a)

```

`n<0?n=-n:n` and `n*=n>0||-1` also work. Algorithm somewhat resembles the PowerShell answer, although this is a recursive formulation.
> 0 votes

# Answer
# Ruby, 57 bytes

```
->n,*h{h[n]=n=(n-"#{n}".reverse.to_i).abs until h[n];n>0}

```

The initially empty array `h` tracks previously hit values. We iterate the number until we hit a previous value, then check the value on the last iteration. Since 0 is a cycle of 1, it'll be 0 if and only if there's no larger cycle. I take an extra 2 bytes to convert this to a Boolean because 0 is truthy in Ruby.
> 0 votes

# Answer
# Perl 6  ~~58 53 33~~  30 bytes

```
~~sub {$/=%;$^a,{return ?1 if $/{$_}++;abs $_-.flip}...0;?0}
{$/=%;?($_,{last if $/{$_}++;abs $_-.flip}...0)[*-1]}
{?($_,{abs $_-.flip}...0)[10**$_]}~~

{?($_,{abs $_-.flip}...0)[$_]}
```

### Explanation:

```
{ # block lambda with implicit parameter $_

  # coerce the following to Bool
  # ( False for Nil or 0, True otherwise )
  ?

  (

    $_, # start a sequence with the input

    # block lambda with implicit parameter $_
    # subtracts the previous value in the sequence and its reverse
    # ( .flip is short for $_.flip where a term is expected )
    { abs $_ - .flip }

    ... # repeat that lambda
    0   # until you get 0

  # get the element indexed with the block's input
  # may be 0, Nil, or a number that is part of a repeating sequence
  )[ $_ ]
}

```

( relies on the previous observation that you only need to do this transformation at most `n` times )
> 0 votes

# Answer
# Perl 5 `-p`, 25 bytes

```
eval'$_=abs$_-reverse'x$_

```

Try it online!

It iterates `n=|n-rev(n)|` n times, so output is 0 if there is no loop, \>0 otherwise. Dennis already proved this is enough.
> 0 votes

# Answer
## Matlab, ~~89~~ 84 bytes

```
n=input('');z=n;while n
z=abs(z-str2num(fliplr(num2str(z))));n=[n z]*all(n~=z);end
z

```

Simple approach - stacks all numbers and checks if a number appeared before.

**Explanation**

```
n=input('');z=n;  -- take input, initiate z
while n           -- n is said to be positive
z=abs(z-str2num(fliplr(num2str(z)))) -- calculate the "reverse and substract"
n=[n z]           -- put the value at the end of the vector
       *all(n~=z) -- make the n all zeroes if z is previously in the vector (break the loop)
end
z                 -- print z (0 when not entered loop, >0 otherwise)

```
> 0 votes

---
Tags: code-golf, number-theory
---


title: Meta Obfuscate a String

text:
# Question
Title: Meta Obfuscate a String
There are numerous reasons for trying to obfuscate input. These include preventing decompiling, and being a nuiscance.

---

With this in mind your challenge should your choose to accept it is to write a meta-obfuscator. Your code must in some Language X receive input as a String, and output a program in language X that outputs the input String.

---

Rules 1. Standard loopholes disallowed
2. It should be hard to tell whether the output prints anything (I.E the code should be heavily obfuscated)
3. Your program should be testable
4. Cryptographic approaches are permitted, but it should not be obvious.
5. Try to submit an interesting solution as this is a popularity contest

---

Winning Criterion
Although it is up to you to decide which question deserves your upvote. Here are the guidelines.
1. Hardest to reverse engineer output based on the source code (i.e most encrypted/obfuscated)
2. Effort and quality of answer

---

tl;dr Output a program which prints the input, but make it hard to understand what is going on. Although many people have discussed this (especially for javascript) and even python. I have seen no formal repository of such programs in any arbitrary languages.

# Answer
# Java

Just out of curiosity I decided to write a simple block of code that outputs code that does not look obfuscated. Here is the generator code

```
package metaobfuscate;

import java.util.Random;
import java.util.Scanner;

/**
 *
 * @author rohan
 */
public class MetaObfuscate {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        String s = (new Scanner(System.in)).nextLine().toLowerCase();
        int i = 0;
        int numChar = s.length();

        String randomlyGenerated;
        String alphabet = " abcdefghijklmnopqrstuvwxyz!?.";
        do {
            Random rand = new Random(i);
            randomlyGenerated = "";
            i++;
            for (int j = 0; j < numChar; j++) {
                randomlyGenerated += alphabet.charAt((int) (rand.nextDouble() * alphabet.length()));
            }
        } while (!s.equals(randomlyGenerated));
        i--;
        System.out.println("import java.util.Random;\n//Simple demonstration of generating random characters");
        System.out.println("public class RandomNessTest {");
        System.out.println("\t//args are the command line arguments");
        System.out.println("\tpublic static void main(String[] args){");
        System.out.println("\tRandom rand = new Random(" + i + ");//replace the seed with whatever seed you want");
        System.out.println("\t//the seed was generated by random keyboard mashing");
        System.out.println("\tString alphabet = \" abcdefghijklmnopqrstuvwxyz!?.\";");
        System.out.println("\tfor(int i = 0;i<" + numChar + ";i++)");
        System.out.println("\t\tSystem.out.print(alphabet.charAt((int)(rand.nextDouble()*alphabet.length())));");
        System.out.println("\t//print out a few random characters");
        System.out.println("\t}\n}");
    }

}

```

It takes in whatever string you wish to obfuscate and outputs a program that looks reliable as output. It takes exponential runtime with larger strings, but it works great for strings of length 1-5. The outputted program claims to be a tutorial, and is even formatted nicely!

```
import java.util.Random;
//Simple demonstration of generating random characters
public class RandomNessTest {
    //args are the command line arguments
    public static void main(String[] args){
    Random rand = new Random(2727915);//replace the seed with whatever seed you want
    //the seed was generated by random keyboard mashing
    String alphabet = " abcdefghijklmnopqrstuvwxyz!?.";
    for(int i = 0;i<5;i++)
        System.out.print(alphabet.charAt((int)(rand.nextDouble()*alphabet.length())));
    //print out a few random characters
    }
}

```
> 2 votes

---
Tags: code-challenge, popularity-contest, code-generation
---


title: Borders of overlapping circles

text:
# Question
Title: Borders of overlapping circles
Given the coordinates of several points on a plane, and the radius of a circle surrounding each point, draw polygons representing the circles and the edges where the circles meet. Straight edges will always fall along circle-circle intersection lines, but might not follow the full length of these lines.

~~Per mbomb007's suggestion, imagine the behavior of 2D soap bubbles.~~ That's technically wrong, because soap bubbles would always meet at 120° angles to minimize energy, while these circles may meet at any angle.

~~**This is a Voronoi diagram, minus a defined area plane.** Thanks Andreas.~~ This is actually a generalization of a Voronoi diagram called a power diagram.

## Examples

For example, given two points and two radii, the output might look like this:

Add another point and radius and the output might look like this:

## Input

You can structure the input however you wish. Please post results with the following inputs.

**Test 1**

* x: 10, y: 10, r: 10
* x: 25, y: 12, r: 8

**Test 2**

* x: 8, y: 10, r: 6
* x: 20, y: 8, r: 4
* x: 18, y: 20, r: 12

## Output

Output should be graphical and should include polygon borders, but nothing else is required. Points and intersections do not need to be represented like they are in the examples.

## Constraints

* No point will exist within the radius of another circle.
* Standard codegolf rules.
* No answers with loopholes will be accepted, but feel free to have fun with it.

# Answer
> 18 votes
# Python 2, ~~473~~ 355 bytes

```
L=input()
m=min
a,b,c,d=eval('m(%s-r for u,v,r in L),'*4%('u','v','-u','-v'))
e=(-c-a)/499.
H=lambda x,y:x*x+y*y
I=500
J=int(2-(d+b)/e)
print'P2',I,J,255
i=I*J
P=lambda(u,v,r):H(c+i%I*e+u,b+i/I*e-v)-r*r
while i:i-=1;p,k=m((P(k)/[1,k[2]][P(k)>0],k)for k in L);u,v,r=k;print int(255*m(1,[m([-p/r]+[(P(l)-p)/H(u-l[0],v-l[1])**.5for l in L-{k}]),p][p>0]/2/e))

```

This reads a set of circles as `(x,y,r)` tuples on stdin, and outputs an image in PGM format to stdout. It works roughly by computing a distance function of the diagram at each pixel, and shading each pixel less than one pixel away proportionally to its distance.

```
{(10,10,10),(25,12,8)}

```

```
{(8,10,6),(20,8,4),(18,20,12)}

```

```
{(6, 63, 4), (16, 88, 9), (64, 94, 11), (97, 96, 3), (23, 32, 13), (54, 14, 7), (41, 81, 3), (7, 7, 4), (77, 18, 8), (98, 55, 4), (2, 56, 7), (62, 18, 5), (13, 74, 2), (33, 56, 12), (49, 48, 4), (6, 76, 2), (82, 70, 9), (21, 71, 2), (27, 5, 10), (3, 32, 6), (70, 62, 6), (74, 46, 4), (21, 60, 7), (18, 47, 7), (94, 2, 4), (39, 97, 7), (62, 63, 2), (87, 29, 8), (19, 17, 4), (61, 23, 2), (73, 1, 8), (40, 17, 13), (99, 41, 4), (81, 57, 7), (1, 68, 5), (38, 3, 4), (46, 36, 9), (4, 39, 2), (73, 77, 3), (93, 19, 10), (67, 42, 3), (96, 65, 2), (2, 16, 3), (28, 92, 3), (54, 58, 2), (39, 86, 5), (84, 82, 5), (79, 43, 4), (5, 47, 1), (34, 41, 8), (65, 5, 2), (9, 44, 3), (53, 3, 6), (1, 12, 1), (81, 95, 7), (74, 31, 2), (63, 61, 1), (35, 72, 1), (44, 71, 2), (57, 35, 5), (46, 65, 6), (57, 45, 4), (93, 94, 1), (99, 81, 13), (13, 58, 4), (68, 32, 6), (11, 2, 6), (52, 98, 7), (51, 25, 5), (84, 2, 2), (44, 92, 3), (23, 72, 2), (32, 99, 7), (13, 19, 3), (97, 29, 8), (58, 80, 3), (67, 82, 5), (59, 60, 3), (86, 87, 5), (29, 73, 2), (5, 93, 4), (42, 74, 1), (75, 85, 8), (91, 53, 5), (23, 82, 4), (19, 97, 8), (51, 88, 3), (67, 12, 6), (60, 53, 1), (66, 72, 2), (57, 64, 2), (66, 49, 2), (44, 0, 4), (11, 69, 1), (93, 60, 5), (56, 50, 3), (19, 68, 3), (64, 75, 3), (6, 17, 2), (82, 5, 2)}

```

Here the distance function has been divided by 32 to make it visible:

```
{(7, 9, 7), (1, 3, 2), (4, 0, 4), (9, 2, 4), (0, 8, 5)}

```

# Answer
> 9 votes
**C# ~2746**

This is a solution in C#. Probably far from optimal but C# wont win this anyway. Just wanted myself to prove that i can do it.

Input via commandline by specifying the values seperated with a space in the order x y r Output is a file 'l.bmp' within the executing directory.

Program accepts any ammount of circles.

Test 1 : 10 10 10 25 12 8

Test 2 : 8 10 6 20 8 4 18 20 12

```
using System;
using System.Collections.Generic;
using System.Drawing;
using System.Drawing.Imaging;
using System.Linq;

class Program
{
    static void Main(params string[] args) => new Program().run(args);

    class Circle
    {
        public PointF P;
        public float R;
    }

    class Line
    {
        public PointF S;
        public PointF E;
        public Circle C1;
        public Circle C2;
        public Line(Circle c1, Circle c2, PointF s, PointF e)
        {
            S = s;
            E = e;
            C1 = c1;
            C2 = c2;
        }
    }

    List<Line> lines = new List<Line>();
    List<Circle> circles = new List<Circle>();

    void run(string[] args)
    {
        for (int i = 0; i < args.Length; i += 3)
            addcircle(args[i], args[i + 1], args[i + 2]);
        circles.Sort((c1, c2) => c1.P.X.CompareTo(c2.P.X));

        int mx = (int)circles.Max(c => c.P.X + c.R) + 1;
        int my = (int)circles.Max(c => c.P.Y + c.R) + 1;

        for (int i = 0; i < circles.Count; i++)
            for (int j = i + 1; j < circles.Count; j++)
            {
                var c1 = circles[i];
                var c2 = circles[j];

                var d = dist(c1.P, c2.P);
                var a = 1 / d * sqrt((-d + c1.R - c2.R) * (-d - c1.R + c2.R) * (-d + c1.R + c2.R) * (d + c1.R + c2.R));
                var x = (sqr(d) - sqr(c2.R) + sqr(c1.R)) / (2 * d);

                var ap = angle(c1.P, c2.P);
                var la = rotate(c1.P, new PointF(c1.P.X + x, c1.P.Y + a / 2), ap);
                var lb = rotate(c1.P, new PointF(c1.P.X + x, c1.P.Y - a / 2), ap);
                var l = new Line(c1, c2, la, lb);
                lines.Add(l);
            }
        foreach (Line l in lines)
            foreach (Line lo in lines)
            {
                if (l == lo) continue;
                var intersection = intersect(l, lo);

                if (intersection != null && online(intersection.Value, l) && online(intersection.Value, lo))
                {
                    foreach (Circle circle in circles)
                    {
                        if (l.C1 == circle || l.C2 == circle)
                            continue;
                        if (dist(intersection.Value, circle.P) >= circle.R)
                            continue;

                        if (dist(l.E, circle.P) < circle.R)
                            l.E = intersection.Value;

                        if (dist(l.S, circle.P) < circle.R)
                            l.S = intersection.Value;
                    }
                }
            }

        using (Bitmap bmp = new Bitmap(mx, my))
        {
            using (Graphics g = Graphics.FromImage(bmp))
            {
                g.Clear(Color.White);
                foreach (var c in circles)
                    draw(g, c);

                for (int i = 0; i < circles.Count; i++)
                {
                    var c1 = circles[i];
                    var p = new PointF(c1.P.X + c1.R, c1.P.Y);
                    for (int j = 0; j < circles.Count; j++)
                    {
                        if (i == j) continue;
                        var c2 = circles[j];
                        for (var f = 0f; f <= 360f; f += 0.1f)
                        {
                            var pl = rotate(c1.P, p, f);
                            if (dist(pl, c2.P) <= c2.R)
                            {
                                g.DrawRectangle(new Pen(Color.White), (int)pl.X, (int)pl.Y, 1, 1);
                            }

                        }
                    }
                }

                foreach (var l in lines)
                    draw(g, l);

            }
            bmp.Save("t.bmp");
        }
    }

    private float dist(PointF p1, PointF p2) => sqrt(sqr(p1.X - p2.X) + sqr(p1.Y - p2.Y));

    bool online(PointF p, Line l)
    {
        var lx = l.S.X < l.E.X ? l.S.X : l.E.X;
        var hx = l.S.X > l.E.X ? l.S.X : l.E.X;
        var ly = l.S.Y < l.E.Y ? l.S.Y : l.E.Y;
        var hy = l.S.Y > l.E.Y ? l.S.Y : l.E.Y;

        return p.X >= lx && p.X <= hx && p.Y >= ly && p.Y <= hy;
    }

    static PointF? intersect(Line l1, Line l2)
    {
        //Line1
        float A1 = l1.E.Y - l1.S.Y;
        float B1 = l1.S.X - l1.E.X;
        float C1 = A1 * l1.S.X + B1 * l1.S.Y;

        //Line2
        float A2 = l2.E.Y - l2.S.Y;
        float B2 = l2.S.X - l2.E.X;
        float C2 = A2 * l2.S.X + B2 * l2.S.Y;

        float det = A1 * B2 - A2 * B1;
        if (det == 0)
        {
            return null; //parallel lines
        }
        float x = (B2 * C1 - B1 * C2) / det;
        float y = (A1 * C2 - A2 * C1) / det;
        return new PointF(x, y);
    }

    void addcircle(string x, string y, string r)
    {
        var SCALE = 20f;
        Circle c1 = new Circle
        {
            P = new PointF(float.Parse(x) * SCALE, float.Parse(y) * SCALE),
            R = float.Parse(r) * SCALE
        };
        circles.Add(c1);
    }

    void draw(Graphics g, Line l) => g.DrawLine(new Pen(Color.Red), l.S.X, l.S.Y, l.E.X, l.E.Y);

    PointF rotate(PointF o, PointF p, float angle)
    {
        var sa = (float)Math.Sin(angle);
        var ca = (float)Math.Cos(angle);
        var dx = p.X - o.X;
        var dy = p.Y - o.Y;

        return new PointF((ca * dx - sa * dy + o.X), (sa * dx + ca * dy + o.Y));
    }

    float angle(PointF p1, PointF p2)
    {
        var dx = p2.X - p1.X;
        if (dx == 0)
            return 0f;
        return (float)Math.Atan((p2.Y - p1.Y) / dx);
    }

    void draw(Graphics g, Circle c)
    {
        g.DrawEllipse(new Pen(Color.Blue),
                      c.P.X - c.R,
                      c.P.Y - c.R,
                      c.R * 2,
                      c.R * 2);
    }

    float sqr(float d) => d * d;
    float sqrt(float d) => (float)Math.Sqrt(d);
}

```

All the Math involved here is based on this. The coordinates of the lines were easy to get using the formulars from the link. However they needed to be rotated by the angle between the two involved cricles centers.

To reduce the lines length i calculated their intersections. Then for that intersection i checked if the current lines end reaches into a circle that isnt the "parent of the line" and also contains the intersection itself. If that was the case, that end of the line was reduced to the location of the intersection.

The circles were simple to draw, the "notneeded" parts were difficult to remove, so i came up with a "rubber" solution, that removes the stuff that isnt needed anymore by painting it white again. Kind of brute forcing it. This is done by walking along each circles edge and checking if that pixel is within range of another circle.

Initially i wanted to roll my own circle-drawing method that only draws the circle withing specified angles but that didnt turn out well and took even more lines of code.

Really having a hard time explaining this if you havent noticed... English isnt my mother tounge so i am sorry for that.

Golfed

```
using System;using System.Collections.Generic;using System.Drawing;using System.Drawing.Imaging;using System.Linq;class P{static void Main(params string[]args)=>new P().R(args);class C{public PointF P;public float R;}class L{public PointF S;public PointF E;public C C1;public C C2;public L(C c1,C c2,PointF s,PointF e){S=s;E=e;C1=c1;C2=c2;}}List<L>_=new List<L>();List<C>c=new List<C>();void R(string[]args){for(int i=0;i<args.Length;i+=3)A(args[i],args[i+1],args[i+2]);c.Sort((c1,c2)=>c1.P.X.CompareTo(c2.P.X));int B=(int)c.Max(c=>c.P.X+c.R)+1;int e=(int)c.Max(c=>c.P.Y+c.R)+1;for(int i=0;i++<c.Count;)for(int j=i+1;j++<c.Count;){var f=c[i];var q=c[j];var d=D(f.P,q.P);var a=1/d*S((-d+f.R-q.R)*(-d-f.R+q.R)*(-d+f.R+q.R)*(d+f.R+q.R));var x=(F(d)-F(q.R)+F(f.R))/(2*d);var h=angle(f.P,q.P);var k=R(f.P,new PointF(f.P.X+x,f.P.Y+a/2),h);var m=R(f.P,new PointF(f.P.X+x,f.P.Y-a/2),h);var l=new L(f,q,k,m);_.Add(l);}foreach(L l in _)foreach(L o in _){if(l==o)continue;var n=I(l,o);if(n !=null && O(n.Value,l)&& O(n.Value,o)){foreach(C p in c){if(l.C1==p || l.C2==p)continue;if(D(n.Value,p.P)>=p.R)continue;if(D(l.E,p.P)<p.R)l.E=n.Value;if(D(l.S,p.P)<p.R)l.S=n.Value;}}}Bitmap r=new Bitmap(B,e);Graphics g=Graphics.FromImage(r);g.Clear(Color.White);foreach(var _ in c)D(g,_);for(int i=0;i++<c.Count;){var Q=c[i];var P=new PointF(Q.P.X+Q.R,Q.P.Y);for(int j=0;j++<c.Count;){if(i==j)continue;var G=c[j];for(var f=0f;f<=360f;f+=0.1f){var H=R(Q.P,P,f);if(D(H,G.P)<=G.R){g.DrawRectangle(new Pen(Color.White),(int)H.X,(int)H.Y,1,1);}}}}foreach(var l in _)D(g,l);r.Save("t.bmp");}float D(PointF p1,PointF p2)=>S(F(p1.X-p2.X)+F(p1.Y-p2.Y));bool O(PointF p,L l){var lx=l.S.X<l.E.X ? l.S.X : l.E.X;var hx=l.S.X>l.E.X ? l.S.X : l.E.X;var ly=l.S.Y<l.E.Y ? l.S.Y : l.E.Y;var hy=l.S.Y>l.E.Y ? l.S.Y : l.E.Y;return p.X>=lx && p.X<=hx && p.Y>=ly && p.Y<=hy;}static PointF? I(L l1,L l2){float a=l1.E.Y-l1.S.Y;float b=l1.S.X-l1.E.X;float d=a*l1.S.X+b*l1.S.Y;float e=l2.E.Y-l2.S.Y;float f=l2.S.X-l2.E.X;float g=e*l2.S.X+f*l2.S.Y;float h=a*f-e*b;if(h==0)return null;float x=(f*d-b*g)/h;float y=(a*g-e*d)/h;return new PointF(x,y);}void A(string x,string y,string r){var F=20f;C _=new C{P=new PointF(float.Parse(x)*F,float.Parse(y)*F),R=float.Parse(r)*F };c.Add(_);}void D(Graphics g,L l)=>g.DrawLine(new Pen(Color.Red),l.S.X,l.S.Y,l.E.X,l.E.Y);PointF R(PointF o,PointF p,float angle){var a=(float)Math.Sin(angle);var n=(float)Math.Cos(angle);var b=p.X-o.X;var x=p.Y-o.Y;return new PointF((n*b-a*x+o.X),(a*b+n*x+o.Y));}float angle(PointF p1,PointF p2){var a=p2.X-p1.X;if(a==0)return 0f;return(float)Math.Atan((p2.Y-p1.Y)/a);}void D(Graphics g,C c){g.DrawEllipse(new Pen(Color.Blue),c.P.X-c.R,c.P.Y-c.R,c.R*2,c.R*2);}float F(float d)=>d*d;float S(float d)=>(float)Math.Sqrt(d);}

```

More Complex examples (top circle gets into negative y values)

---
Tags: code-golf, graphical-output, geometry
---