title: Whole Number Groups

text:
# Question
Title: Whole Number Groups
Given a list of fractions, group them so that each group sums to a whole number. This should be done in such a way to maximize the number of non-empty groups.

You may assume a solution exists. Order does not matter, both for the groups and their contents. You may output in any order.

## Test Cases

| Fractions | Groups |
| --- | --- |
| `1/2, 1/2, 1/2, 1/2` | `(1/2, 1/2), (1/2, 1/2)` |
| `1/2, 1/3, 1/6, 6/7, 8/7` | `(1/2, 1/3, 1/6), (8/7, 6/7)` |
| `5/3, 2/3, 2/3, 1/3, 1/3, 1/3` | `(1/3, 5/3), (1/3, 2/3), (1/3, 2/3)` |
| `9/2, 3/4, 1/12, 7/4, 2/3, 2/3, 7/12` | `(9/2, 3/4, 1/12, 2/3), (7/4, 2/3, 7/12)` |
| `1/10, 1/5, 1/2, 7/10, 1/2` | `(1/10, 1/5, 7/10), (1/2, 1/2)` |

## IO

You may take fractions as a tuple or list of `[numerator, denominator]`, and output in the same format. You can also use your language's built-in fraction type if it exists.

If there are multiple optimal solutions you may output any of them, some of them, or all of them. Do not output any non-optimal solutions.

# Answer
# JavaScript (ES7), 176 bytes

Expects a list of `[numerator, denominator]` pairs.

```
a=>eval("for(o=n=a.length,q=n**n;q--;)o[(p=a.map((_,j)=>a.filter((_,i)=>!(q/n**i%n^j))).filter(a=>a+a)).length]||p.some(b=>b.map(([p,q])=>[P=P*q+p*Q,Q*=q],P=0,Q=1)|P%Q)?o:o=p")

```

Try it online!

### Commented

This is a version without `eval()` for readability.

```
a => {                     // a[] = input list of fractions
  for(                     // main loop:
    o =                    //   o[] = output, initially not an array
    n = a.length,          //   n = length of a[]
    q = n ** n;            //   q = counter, initialized to n ** n
    q--;                   //   stop once q = 0 has been processed
  )                        //
  o[                       // test o[], using the length of p[]:
    ( p =                  //   p[] = partition
      a.map((_, j) =>      //   for each element at index j in a[]:
        a.filter((_, i) => //     for each element at index i in a[]:
          !(               //       keep this entry if
            q / n ** i % n //       floor(q / n ** i) mod n
            ^ j            //       is equal to j
          )                //
        )                  //     end of filter()
      ).filter(a => a + a) //   end of map(); remove empty slots
    ).length               //   get the final length of p[]
  ] ||                     // abort if p[] is longer than o[]
  p.some(b =>              // for each list of fractions b[] in p[]:
    b.map(([p, q]) =>      //   for each fraction [p, q] in b[]:
      [                    //     we add p/q to P/Q by:
        P = P * q + p * Q, //       updating the numerator P
        Q *= q             //       updating the denominator Q
      ],                   //
      P = 0, Q = 1         //     start with P/Q = 0/1
    )                      //   end of map()
    | P % Q                //   trigger some() if Q is not a divisor of P
  ) ? 0                    // end of some(); do nothing if truthy
    : o = p;               // otherwise, update o[] to p[]
                           // (implicit end of for)
  return o                 // return o[]
}                          //

```
> 6 votes

# Answer
# Vyxal, 14 bytes

```
ṖvøṖÞf'Ṡ¨=⌊;ÞG

```

Try it Online!

Times out for anything more than 5 fractions if you're lucky. Don't even bother giving it the third and fourth test case.

Inputs as a list of fraction objects. Due to technical limitations, this is done with the `a` flag for convenience.

## Explained

```
ṖvøṖÞf'Ṡ¨=⌊;ÞG # We'll call the length of the list N so we can see why this takes so long
Ṗ              # Permutations of the input - returns a list of N! items
 vøṖ           # To each of the N! permutations, get all possible partitions. Each permutation has 2^(N-1) partitions, so there are now N! * 2^(N-1) sublists but still N! items
    Þf         # Flatten the entire thing by one level. This iterates over each of those N! * 2^(N-1) sublists.
      '    ;   # From those partitions of permutations, keep only those where: (also iterating over each of those N! * 2^(N-1) items)
       Ṡ       #   Summating each partition
        ¨=⌊    #   is invariant under flooring
            ÞG # Get the longest remaining item.

```
> 5 votes

# Answer
# Wolfram Language (Mathematica), 148 bytes

```
Last@Sort@(y=Flatten)[(a=#;(x=Select)[a~TakeList~#&/@x[Range@n~Tuples~#&~Array~(n=Length@a)~y~1,Tr@#==n&],Tr@Mod[Tr/@#,1]==0&])&/@Permutations@#,1]&

```

Try it online!
> 5 votes

# Answer
# 05AB1E, ~~24~~ 22 bytes

```
œ€.œ€`éʒε.EOT.òDïQ}P}θ

```

-2 bytes by taking the input as a list of strings `"a/b"` instead of list of pairs `[a,b]`.

Try it online or verify all test cases.

**Explanation:**

```
œ            # Get all permutations of the (implicit) input-list
 €.œ         # Get all partitions of each permutation
    €`       # Flatten it one level down to a single list of partitions
      é      # Sort it by length (shortest to longest)
ʒ            # Filter this list of partitions by:
 ε           #  Map over each part of this partition:
  .E         #   Evaluate each inner string as Elixir to get the decimals
    O        #   Sum them together
     T.ò     #   Round it to 10 decimal values to fix floating point errors
        DïQ  #   Check that it's an integer:
        D    #    Duplicate
         ï   #    Cast the copy to an integer (floor for positive integers)
          Q  #    Check if the two are equal
 }P          #  After the map: check if all parts in this partition were truthy
}θ           # After the filter: pop and leave the last/longest valid partition
             # (which is output implicitly as result)

```
> 3 votes

# Answer
# Charcoal, 92 bytes

```
≔Ｅ⪪Ｓ,⁺⟦ικ⟧Ｉ⪪ι/θ≔ΠＥθ§ι³ηＦθ⊞ι×÷η⊟ι⊟ιＷθ«≔ΦＥＸ²ＬθΦθ﹪÷κＸ²ν²∧κ¬﹪ΣＥκ§μ²ηι≔§ι⌕ＥιＬκ⌊ＥιＬκι≔⁻θιθ⟦⪫Ｅι§κ⁰,

```

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

```
≔Ｅ⪪Ｓ,⁺⟦ικ⟧Ｉ⪪ι/θ

```

Input the fractions and split them into numerator and denominator.

```
≔ΠＥθ§ι³η

```

Calculate a common denominator that will work for all of the fractions.

```
Ｆθ⊞ι×÷η⊟ι⊟ι

```

Calculate the equivalent numerator for each fraction.

```
Ｗθ«

```

Repeat until there are no more fractions to process.

```
≔ΦＥＸ²ＬθΦθ﹪÷κＸ²ν²∧κ¬﹪ΣＥκ§μ²ηι

```

Get all of the subsets of the fractions but filter out the empty set and any set whose sum of numerators isn't a multiple of the common denominator.

```
≔§ι⌕ＥιＬκ⌊ＥιＬκι

```

Find the shortest such subset.

```
≔⁻θιθ

```

Remove the shortest subset from the remaining fractions.

```
⟦⪫Ｅι§κ⁰,

```

Output the original fractions from the shortest subset.
> 2 votes

---
Tags: code-golf, number, rational-numbers
---


title: (A[l(t[e(r)n]e)s]t) a string!

text:
# Question
Title: (A[l(t[e(r)n]e)s]t) a string!
*Alternesting*, is the act of taking a string and nesting it in alternating brackets. Here is how you *alternest* a string.

* For a string of length **N**, take the center **N** characters, and surround them in parenthesis. So if our string was `Hello world!` (12 characters), we'll end up with

```
(Hello world!)

```
* Then, take the remaining center `n-2` characters, and surround them in square brackets. In this case, the center 10 characters are `ello world`, so the next iteration is:

```
(H[ello world]!)

```
* As long as there are more than two characters left in the middle of the string, repeat the last two steps, alternating between `()` and `[]`. Here are the last steps:

```
(Hello world!)
(H[ello world]!)
(H[e(llo worl)d]!)
(H[e(l[l(o[ w]o)r]l)d]!)

```

Since there are only two characters left in the middle on the last iteration, we stop. Our final string is

```
(H[e(l[l(o[ w]o)r]l)d]!)

```

Note how there are two characters in the middle brackets. This happens when the input is an even length. If the input was an odd length (for example, `Hello, world!` with a comma added), we would have only one character in the middle:

```
(H[e(l[l(o[,( )w]o)r]l)d]!)

```

For today's challenge, you must write a program or function that takes a string as input, and alternests it, outputting the new string. You can take input and output in any reasonable format you like. The input will always be at least one character long, and will only contain printable ASCII. You can also assume that the input will *not* contain any parenthesis or square brackets. For traditional languages, this shouldn't matter too much, but it might make it easier for some esoteric languages.

As usual, this is a competition, so try to make the shortest possible answer in the language of your choice. Have fun!

## Test IO

```
#Input                      #Output

"Alternesting is fun!"  --> (A[l(t[e(r[n(e[s(t[in]g) ]i)s] )f]u)n]!)
"PPCG"                  --> (P[PC]G)
"Code-golf"             --> (C[o(d[e(-)g]o)l]f)
"4 8 15 16 23 42"       --> (4[ (8[ (1[5( [1]6) ]2)3] )4]2)
"a"                     --> (a)
"ab"                    --> (ab)
"abc"                   --> (a[b]c)

```

# Answer
> 25 votes
# Python 3, ~~70~~ ~~69~~ 65 bytes

*-1 byte thanks to @Uriel*
*-4 bytes thanks to @xnor*

```
f=lambda s,b=0:s and'(['[b]+s[0]+f(s[1:-1],~b)+s[1:][-1:]+')]'[b]

```

Try it online!

# Answer
> 10 votes
# C, ~~143~~ ~~137~~ 135 bytes

```
i,l,k;f(char*s){for(k=i=0,l=strlen(s);*s;printf("%c%c","([])"[i++%2+2*(i>l/2+!k)],*s++))i>l/2-1&&l&1^1&&putchar(*s++,k=++l);puts(")");}

```

Try it online!

**Explanation:**

```
// Function (and variable) declaration.
i,l,k;f(char*s){

// Start the loop and initialize the variables. The loop terminates
// when the NUL-terminator of the string is reached.
for(k=i=0,l=strlen(s);*s;<this part saved for later>)

// Check if we have reached the middle of the string. Because of the
// short-circuiting of the conditions, we don't need to use an 'if'
// statement here; if a condition is false, no further conditions
// are evaluated.
i>l/2-1&&

// Equivalent to '!(l%2)', but one byte shorter. Checks if the length
// of the string is even.
l&1^1

// If we have reached the middle and the length of the string is even,
// we'll need to skip one bracket, so we'll print the current character
// of the string and increment the pointer. Also we increment 'l' to
// avoid this getting done more than once, and give 'k' a non-zero
// value.
&&putchar(*s++,k=++l);

// The following is inside the 'increment' part of the 'for' loop.
// We print two characters. The first one is a bracket and the second
// one is the current character in the string.
printf("%c%c","([])"[i++%2+2*(i>l/2+!k)],*s++)

// The type of bracket is  chosen depending on the value of 'i'. A
// character from the string "([])" is selected with the index 'i%2 + 2',
// if we have reached the  middle of the string, and with index 'i%2', if
// we haven't.

// The exact part where this change happens depends on the parity of
// the string length, so we use 'k' to signal if the length is even or
// odd. If the length is odd, 'k==0', so '+!k' is the same as '+1'.
// Otherwise 'k' is non-zero, so '+!k' is the same as '+0'.

// Output the final ')'.
puts(")");}

```

# Answer
> 8 votes
# Retina, 52 bytes

```
+`(?<!\()[^()]+(?!\))
($&)
(\(.)\(
$1[
r`\)(.\))
]$1

```

Try it online! The first stage inserts pairs of parentheses between each pair of input characters, while the second and third stages correct alternate parentheses to brackets.

# Answer
> 7 votes
# JavaScript (ES6), ~~69 68~~ 62 bytes

*-6 thanks to @Shaggy*

```
f=([c,...s],i,l=s.pop()||s)=>c?'[('[i^=1]+c+f(s,i)+l+'])'[i]:s

```

Try it online!

# Answer
> 6 votes
# Sed, 78

Score includes +1 for `-r` option passed to sed.

```
s/.*/(&)/
:
s/(\(.)([^][]+)(.\))/\1[\2]\3/
t
s/(\[.)([^)(]+)(.\])/\1(\2)\3/
t

```

Try it online.

# Answer
> 5 votes
# , ~~25~~ ~~26~~ 25 bytes

~~1~~ 2 bytes off thanks to @DJMcMayhem

```
òC()Pé
%llòÍî
òF)%r[r];

```

Try it online!

Borrowed some of @udioca's ideas. ~~Also finally used the surround plugin included in V for an answer, although it may not have been the best way, who knows.~~ The plugin does NOT want to be used.

Hexdump:

```
00000000: e3e1 0a6b f2e9 286c 6ce9 5b6c 6cf2 6af2  ...k..(ll.[ll.j.
00000010: e129 6868 e15d 6868 f2cd ce              .)hh.]hh...

```

Explanation:

```
-> |abcdefg      (the input, where | is the cursor)
ò              ' recursively
 C()           ' (C)hange from the cursor to the end of the line to '()'
-> (|)    (where | is the cursor)
     P         ' (P)aste the changed bit (what was there) left of the cursor
-> (abcdef|g)
      é        ' nsert a newline
-> (abcdef
   |g)
%              ' Goto the previous matching parenthese
-> |(abcdef
   g)
 ll            ' Move two characters right
-> (a|bcdef
   g)
   ò           ' End recursive loop (it will break on ll when there are no characters left
-> (a(b(c
   d)
   e)
   f)
    Íî         ' Remove all newlines
-> (a(b(cd)e)f|)
ò              ' Recursively
 F)            ' Go backwards to the next )
-> (a(b(cd)e|)f)
   %r[         ' Go to the matching paren and (r)eplace it with [
-> (a|[b(cd)e)f)
               ' Go back to the previous cursor location
-> (a[b(cd)e|)f)
       r]      ' (r)eplace this paren with ]
-> (a[b(cd)e|]f)
         ;     ' repeat F)
-> (a[b(cd|)e]f)
               ' implicitly end recursion

```

# Answer
> 5 votes
# Haskell, 96 91 81 79 77 bytes

```
(cycle"()[]"!)
(l:r:a)!k|[x]<-k=[l,x,r]|x:y<-k=l:x:a!init y++[last y,r]|2>1=k

```

Try it online!

# Answer
> 2 votes
# Javascript(ES6) 110 105 bytes

Thanks to @powelles for reminding me about `x%y<1`.

Thanks @Luke for `a-b?y:x`

```
i=>'('+[...i].map((a,b,c,d=i.length/2-1,e=b%2<1)=>a+(d>b?e?'[':'(':d-b?(d%1==0?!e:e)?')':']'):'').join``

```

```
let f=i=>'('+[...i].map((a,b,c,d=i.length/2-1,e=b%2<1)=>a+(d>b?e?'[':'(':d==b?'':(d%1==0?!e:e)?')':']')).join``
```

```
<input onkeyup="result.textContent = f(this.value)"/>
<p id="result"></p>
```

---

The first thing in understanding this beast is ungolfing it:

```
function alternest(input) { //input is i in the original
  let inputArray = Array.from(input); //the [...i] section
  let result = inputArray.map((item, index, baseArray) => { //result is an added helper variable
    let middle = input.length / 2 - 1, //the middle of the string
        alternate = index % 2 == 0; //should you alternate from '(' and '[' or ')' and ']'

    let symbol; //the alternating symbol

    if(middle > index) { //if its opening braces
      symbol = alternate ? '[' : '(';
    } else if(middle < index) {
      if(middle % 1 === 0) //if middle is a whole number
        alternate = !alternate; //reverse alternate
      symbol = alternate ? ')' : ']';
    } else { //if middle === index
      symbol = ''; //there's no symbol in the center for even alternests
    }
    return item + symbol; //convert the array item into the item and symbol
  }).join('');

  return '(' + result; //add the first symbol.
}

```

Almost every line is a part of the golfed version, so stepping through:

**Line 1:** The function statement becomes an arrow function, renaming `input` to `i`. Becomes `i=>`.

**Line 2:** `Array.from` is the new, proper way of converting a string into an array, and what we use in on this line. However along with it, the spread operator is a cheaper way than the old `.split('')` way, to do it, which is what is used in the golfed version. Ends up as `[...i]`.

**Line 3:** `.map` loops through an array, giving you three arguments: `item`(`a` in the golfed), `index`; golfed as `b`, and `baseArray` or `c`. While we only care about `item` and `index`, we kept `baseArray`(see line 4 for why). Golfs to `.map((a,b,c,...)=>...`.

**Line 4:** The variable `middle`, the or the argument `d` in the golfed version is created to save a few bytes when it is repeated. The argument `c` had to be kept for argument `d` to be created. Is converted to `(...,d=i.length/2-1,...)`.

**Line 5**: The variable `alternate`, or argument `e` is used to check what character it was on "(" or "\[" or if it was past the middle, ")" and "\]". `b%2<1` is equal to `b%2==0` because it can't be anything less than 1, but 0 in this case. Equals `(...,e=b%2<1)`.

**Line 6:** A helper variable to allow me to convert the `ternary operators` to `if` statements. Isn't anything in the actual codegolf.

**Lines 7-8**: If the index is less than the middle of the string set the symbol to an alternation of "\[" and "(". Equates to `d>b?e?'[':'(':...`.

**Lines 9-12**: Else (if index is greater than middle), check if middle is a whole number, if so switch the alternation. Then set the symbol to an alternation of ')' and '\]'. Obfuscated to `(d%1==0?!e:e)?')':']'`.

**Lines 13-15**:If the in the middle set the symbol to an empty string. This doesn't apply to odd alternesters, because middle has a decimal. Becomes: `d==b?'':...`.

**Line 16**: Joins the character array back into a string. Equates to `.join```.

**Line 17**: Returns the starting symbol "(" and the result. Correlates to `'('+...`.

# Answer
> 2 votes
# Ruby, 79 77 bytes

-2 bytes thanks to @Value Ink

```
->s{z=s.size
(z/2+z%2).times{|i|s.insert k=i*2,'(['[i%2]
s[~k]+=')]'[i%2]}
s}

```

Try it online!

# Answer
> 2 votes
# Jelly, ~~23~~ 21 bytes

```
LHĊRị
ç⁾)]żUFUż@ç⁾([$

```

Try it online!

```
LHĊRị           - helper function. Takes inputs of the input string and list of brace types
L                 - length of the input string
 HĊ               - number of parenthesis/brackets facing a single direction
   R              - range
    ị             - indexed into right argument: list of brace types ')]' or '(['

ç⁾)]żUFUż@ç⁾([$ - main function
ç⁾)]              - get list of left-facing parentheses/brackets
    żU            - zip to the end (U) of the input string
      FU          - move the beginning of the string back to the beginning
        ż@        - zip with (to the start of the string):
          ç⁾([$   -the list of right-facing parentheses/brackets to the beginning

```

*-2 bytes thanks to @EricTheOutgolfer*

# Answer
> 1 votes
# SCALA, ~~140~~ 138 chars, ~~140~~ 138 bytes

I'm sorry I couldn't do better ... I'm sure there are many ways to improve it. Still:

```
val n=s.length-1
var l=""
var r=""
for(i<-0 to n/2){l+=(if(i%2<1)"("else"[")
if(i!=n-i)l+=""+s(i)
r=""+s(n-i)+(if(i%2<1)")"else"]")+r}
l+r

```

Try it online!

Thanks for this challenge, that was quite hard for me.

EDIT : -2 bytes thanks to Mar Dev.

PS : I will ask something though. I understand why THIS CODE keeps duplicating the central char of my string if I have an odd length (I just don't check and add it twice, in both `l` and `r` strings). But why do I get a pair of parenthesis when I try correcting it like THAT? I don't understand at all.

# Answer
> 1 votes
# C++ 14, ~~154~~ ~~145~~ 134 bytes

(Thanks to ideas by ceilingcat for extra bytes 145-\>134)

\[Recursive\]

```
#include <regex>
using S=std::string;S L(S i,int b=1){int l=i.size();return"(["[b]+(l<3?i:i[0]+L(i.substr(1,l-2),!b)+i[l-1])+"])"[b];}

```

# C++ 14, 177 bytes

\[Iterative\]

```
auto l(string s){int z=s.length();string r(z*2+z%2,'-');int i=0;for(;i<z;i+=2)r[i]=i/2%2?'[':'(',r[i+1]=s[i/2];for(i=z;i<2*z;i+=2)r[i]=s[i/2],r[i+1]=(i+1)/2%2?')':']';return r;}

```

# Answer
> 1 votes
# Perl, ~~77~~ 74 (73 + 1) bytes

Regular expressions are glorious things. Run with the `-p` command line flag.

```
$x=qr/[^]()[]/;$z=qr/(^|$x)\K($x+)($|$x)/;s/$z/[$2]$3/ while s/$z/($2)$3/

```

# Answer
> 1 votes
# 05AB1E, 31 bytes

```
2ä`Rð«„)]Ig©×øRJ®Èƒ¦}s„([®×søJì

```

Try it online!

**Explanation**

With examples for input: `abcd` / `abcde`

```
2ä`                              # split input to 2 separate parts on stack
                                 # RESULT: 'ab','cd' / 'abc', 'de'
   R                             # reverse the second part
    ð«                           # append a space
      „)]                        # push the string ")]"
         Ig©×                    # repeat it len(input) times
             ø                   # zip with the second part of the input string
              RJ                 # reverse and join to string
                                 # RESULT:  ' )c]d)' /  ' )d]e)'
                ®Èƒ¦}            # remove the first (1,2) chars for (odd,even) length input
                                 # RESULT: 'c]d)' / ')d]e)'
                     s           # swap the first part of the input string to top of stack
                      „([®×      # repeat the string "([" len(input) times
                           sø    # zip with first part of input string
                                 # RESULT: ['(a', '[b'] / ['(a', '[b', '(c']
                             Jì  # join to string and prepend to the second part

```

# Answer
> 1 votes
# Ruby, 57 bytes

```
f=->s,i=0{a,*b,c=s;a ?["(["[i],a,*f[b,~i],*c,")]"[i]]:''}

```

Try it online!

Recursive function similar in spirit to ovs's Python answer. Inputs and outputs arrays of characters.

Note that we could shave off 3 more bytes, and in the test suite on TIO, where we join the arrays back to strings, the visible result would look unchanged:

```
f=->s,i=0{a,*b,c=s;a ?["(["[i],a,f[b,~i],c,")]"[i]]:p}

```

However, this would produce nested arrays and nils in the raw output, which is probably too weird for a "reasonable" output format.

# Answer
> 0 votes
## PowerShell, 125 119 111 bytes

```
{param($s)for($p='()[]';($f,$s,$g=$s-split'(?<=.)(.+)(?=.)')[0]){$l+=$p[$i++]+$f;$r=$g+$p[$i++]+$r;$i%=4}$l+$r}

```

Try it online!

Previous version\*

```
{for($s="($args)";$s-ne($t=$s-replace'(\(.)([^][]+)(.\))','$1[$2]$3'-replace'(\[.)([^)(]+)(.\])','$1($2)$3')){$s=$t}$s}

```

\*Thanks @Digital Trauma.

# Answer
> 0 votes
# Pyth, 42 (!) bytes

```
M?!lHH+@,\[\(G++hHg!GPtH+?qlH1keH@,\]\)Gg1

```

Test it online! The input must be quoted.

**Explanations**

```
M                                             # Define a function g with arguments G and H
 ?!lHH                                        # If len(H) == 0, return H. Otherwise...
      +@,\[\(G                                # Concatenate [ or ( to...
               +hHg!GPtH                      # ...to H[0] concatenated to g(not(G), H[1:-1]), itself concatenated...
              +          ?qlH1keH             # ...to H[-1] if len(H) != 1, otherwise to "" (that's for odd length input strings)...
                        +        @,\]\)G      # ...and to that concatenate ] or ).
                                        g1    # Call g(True, Q). Q is implicit input

```

So basically I progressively remove the head and end of H (being the input string in the beginning) while concatenating the parentheses/brackets. G is just a boolean which remembers if I must use brackets or parentheses.

# Answer
> 0 votes
# 05AB1E, ~~49~~ 42 bytes

```
g;îD„([×s£©"s‚.Bøvy¬ðQi¦}}JR"DU.V®D∞sKRX.V

```

Try it online!

# Answer
> 0 votes
# QuadR, 82 bytes

(81 bytes +1 for  flag)

```
(\(.)([^[])(.+?)([^\]])(.\))
(\(.)(..?)(.\))
^[^\(].*
\1[\2(\3)\4]\5
\1[\2]\3
(&)

```

Try it online!

# Answer
> 0 votes
# AWK, 118 bytes

```
{b=")";for(j=l=length(c=$0);j>0;){x=substr(c,j--,1);b=(j>l/2?(((d=!d)?"]":")")x):j==l/2?x:((d=!d)?"(":"[")x)b}print b}

```

Tested with gawk, but it should work with any compliant awk interpreters

```
$ awk -f alternesting.awk <<< 'abc'
(a[b]c)

```

# Answer
> 0 votes
# Java (OpenJDK 8), 124 bytes

```
c->{String s="";for(int l=c.length-1,a=l/2;a>=0;)s=(a%2<1?"(":"[")+(a<-~l/2?c[a]+s+c[l-a]:c[a])+(a--%2<1?")":"]");return s;}

```

Try it online!

## Credits

# Answer
> 0 votes
# JavaScript, 101 bytes

Not a winner, but it was interesting to try the `replace` approach. This could definitely be improved, but it got out of hand quick...

```
s=>"("+s.replace(/./g,(a,b)=>a+(l%2|b*2+2!=l?")][("[3*(c=l>(b+=l%2-1)*2+2)+(b-c*l)%2]:""),l=s.length)

```

# Answer
> 0 votes
# Stax, 25 bytes

```
ò≥◘■O║£/öτt≈K↔ì♂≈-⌂6=═°!b

```

Run and debug it

# Answer
> 0 votes
# Japt, 28 bytes

Initially inspired by Arnauld's solution.

```
V°g"()[]"ò)i1¢?UÌiUÎ+ßUs1J:U

```

Try it

```
V°g"()[]"ò)i1¢?UÌiUÎ+ßUs1J:U     :Implicit input of string U
V                                :Second input variable, defaulting to 0
 °                               :Postfix increment
  g                              :Index, 0-based & modular, into
   "()[]"ò                       :  Length 2 partitions of string "()[]"
          )                      :End indexing
           i1                    :Insert at 0-based index 1
             ¢                   :  Slice first 2 characters off U
              ?                  :  If truthy (non-empty string) return
               UÌ                :    Last character of U
                 i               :    Prepend
                  UÎ             :      First character of U
                    +            :      Append
                     ß           :        Recursive call with argument (V is passed automatically)
                      Us1        :          U sliced from index 1 to index
                         J       :          -1
                          :U     :  Else return U

```

# Answer
> 0 votes
# JavaScript (Node.js), 77 bytes

Not the best JS solution, but it could interest some people : this solution uses recursive calls with inversion of the 2 optional parameters at each step to alternate between `()` and `[]`

```
f=(s,a="()",b="[]")=>a[0]+(s[2]?s[0]+f(s.slice(1,-1),b,a)+s.slice(-1):s)+a[1]

```

Try it online!

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


title: Arbitrary Apple Dilemma

text:
# Question
Title: Arbitrary Apple Dilemma
I have encountered this type of puzzle, that usually involves apples, several times. It goes as follows:

> There is a certain number of apples in a basket. Ava takes a third of the apples. Bob takes a quarter of the apples that are left. Finally, Dennis takes one-sixth of the apples left. In the end, there are 10 leftover apples. How many apples were in the basket?

The answer to the above task is 24.

## Task

Given a list of positive integers and an integer representing the apples left in the end, return the number of apples originally in the basket.

## Specs

* The \\$n\\$th element of the list represents the \\$\frac 1 k\\$ share of apples the \\$n\\$th person took in the apples left over.
* There will always exist one integer solution, but the step calculations might result in rational numbers
* This is , so the shortest answer wins.

## Test cases

```
[3, 4, 6], 10    -> 24
[2], 14          -> 28
[6], 30          -> 36
[4, 3], 20       -> 40
[5, 8, 7], 9     -> 15
[2, 9, 4, 8], 7  -> 24

```

# Answer
# Vyxal, ~~5~~ 4 bytes

```
Ė⌐Π/

```

Try it Online!

Based on @Sean's Raku answer. I feel stupid for not seeing this 4 byte solution sooner.

```
Ė     reciprocal (1/x)
 ⌐    complement (1-x)
  Π   product
   /  divide

```
> 9 votes

# Answer
# Raku, 23 bytes

```
{$^n/[*] 1 X-(1 X/@^a)}

```

Try it online!

* The number of apples is passed as the parameter `$^n`, and the list of integers as the parameter `@^a`.
* `1 X/ @^a` produces the list of reciprocals of the integers.
* `1 X- (1 X/ @^a)` subtracts each reciprocal from 1.
* `[*]` multiples together all of those fractions.
> 7 votes

# Answer
# , 21 bytes

```
\(x,n)prod(x/(x-1),n)

```

Attempt This Online!

Uses the fact that \\$\frac{1}{1-\frac{1}{x}} = \frac{x}{x-1}\\$ and then multiplies everything together using `prod`.
> 5 votes

# Answer
# Wolfram Language (Mathematica), ~~17~~ 16 bytes

```
##&@@(#/--+#)#2&

```

Try it online!

```
        --+#    {3,4,6}-1
      #/        {3,4,6}/{2,3,5}
##&@@(      )   Sequence[3/2,4/3,6/5]
             #2 Sequence[3/2,4/3,6/5]*10
                Times[3/2,4/3,6/5,10] (=24)

```
> 5 votes

# Answer
# TI-Basic, ~~15~~ 13 bytes

```
Prompt A,B
B/prod(1-ʟA⁻¹

```
> 4 votes

# Answer
# , 8 bytes

```
%[:*/1-%

```

Try it online!

Takes the number of remaining apples as left argument and the list as right argument.

* The first `%` (division) forms a dyadic hook, and divides the left argument by the result of applying `[:*/1-%` to the right argument (monadically).
    + The second `%` takes the reciprocals of the numbers in the list.
    + `1` `-` subtracts each reciprocal from 1.
    + `*/` takes the product; a cap (`[:`) is used to do so monadically.
> 4 votes

# Answer
# MATL, 5 bytes

```
tq/hp

```

Try it out at MATL Online

```
        % Implicitly retrieve the first input, an array
t       % Duplicate the first input (x)
q       % Subtract 1 (x - 1)
/       % Divide (element-wise) the two values on the stack (x / (x - 1))
h       % Implicitly retrieve the second input and append to the array
p       % Compute the product of all elements
        % Implicitly display the result

```
> 4 votes

# Answer
# Desmos, ~~39~~ 28 bytes

*-11 bytes thanks to @Greg Martin with an amazing insight!*

```
f(l,k)=k/e^{ln(1-1/l).total}

```

Port of most of the other answers here. ~~Taking the product of a list in Desmos is super annoying; there should be an equivalent of `total` for products lol.~~ Thanks to Greg Martin, `total` can be used in a very creative way to take the product of a list!

Try It On Desmos!

Try It On Desmos! - Prettified
> 3 votes

# Answer
# Python, 45 bytes

*-9 bytes thanks to `att`*

Avoids the use of `math.prod`; utilises the walrus `:=` operator instead.

```
lambda l,n:round([n:=n*x/~-x for x in l][-1])

```

Attempt This Online!
> 3 votes

# Answer
# 05AB1E, 5 bytes

```
D</P*

```

Try it online!

Port of AndrovT's Vyxal answer.

#### Explanation

```
D</P*  # Implicit input
D      # Duplicate
 <     # Decrement
  /    # Divide
   P   # Product
    *  # Multiply
       # Implicit output

```
> 2 votes

# Answer
# Arturo, ~~29~~ 24 bytes

```
$=>[&*∏map&'x->x//x-1]

```

Try it

This answer assumes potential floating point issues are okay. Let me know if that is a bad assumption. This uses a new feature in 0.9.82 that was released today. Function arguments no longer need to be named. The first instance of `&` is the first argument and the second instance of `&` is the second.
> 2 votes

# Answer
# JavaScript, 27 bytes

```
(x,n)=>x.map(c=>n*=c/~-c)|n // 27

(x,n)=>x.map(c=>n+=n/~-c)|n // 27

```

The first formula is obvious: if we get \\$\frac{1}{x}\\$ so there left \\$\frac{x-1}{x}\\$ and we need to divide reminder to \\$\frac{x-1}{x}\\$ and it is the same to multiply reminder to \\$\frac{x}{x-1}\\$

The second formula is the same as first just in another format:

\\$ n * \frac{x}{x - 1} = n * (\frac{x - 1 + 1}{x - 1}) = n * (1 + \frac{1}{x - 1}) = n + \frac{n}{x-1} \\$

Try it:

```
f1=(x,n)=>x.map(c=>n*=c/~-c)|n

;f2=(x,n)=>x.map(c=>n+=n/~-c)|n

;[
    [[3, 4, 6], 10],    // 24
    [[2], 14],          // 28
    [[6], 30],          // 36
    [[4, 3], 20],       // 40
    [[5, 8, 7], 9],     // 15
    [[2, 9, 4, 8], 7],  // 24
].map(([a,b]) => console.log(f1(a,b), f2(a,b)))
```

## UPD 31 -\> 29

Thanks to AZTECCO for the tip to reduce bytes count

## UPD 29 -\> 27

Thanks to Shaggy for the tip to reduce bytes count
> 2 votes

# Answer
# Wolfram Language (Mathematica), 18 bytes

```
#2/Times@@(1-1/#)&

```

Try it online!

Unnamed function that takes the list as its first input and the final number of applies as its second input. Same formula as most other answers here. One trivium: unless I'm overlooking some possibility, it's shorter to use `Times` here than its abbreviation `1##&` because the precedence of `/` would require extra parentheses in the second case.
> 2 votes

# Answer
# Jelly, 5 bytes

```
İCP÷@

```

Try it online!

Port of Sean's Raku answer.

#### Explanation

```
İCP÷@  # Implicit input
İ      # Reciprocal (1 / z)
 C     # Complement (1 - z)
  P    # Product
   ÷@  # Divide
       # Implicit output

```
> 2 votes

# Answer
# Python NumPy, 35 bytes

```
lambda l,n:n*l.prod()//(l-1).prod()

```

Attempt This Online!

Takes a numpy vector and a number.

A bit uninspired. On the plus side: has no accuracy issues.
> 2 votes

# Answer
# K (ngn/k), 10 bytes

```
{x+x%y-1}/

```

Try it online!

* `{...}/` set up an implicitly seeded reduce, seeded with `x` (the number of remaining apples) and run over `y` (the list of integers)
    + `x%y-1` divide `x` by `y` minus one
    + `x+` add this to the above, and pass into the next iteration of the reduce

An alternative answer that is also 10 bytes is:

```
{x%/1-1%y}

```
* `1-1%y` subtract the reciprocals of `y` from one
* `x%/` beginning with `x`, do a divide-reduce over the above
> 2 votes

# Answer
# Japt, 8 bytes

```
*VË/ÓDÃ×

```

Try it
> 1 votes

# Answer
# Factor \+ `math.unicode`, ~~24~~ 21 bytes

```
[ dup 1 v-n v/ Π * ]

```

Try it online!

Port of @pajonk's R answer.

```
      ! 10 { 3 4 6 }
dup   ! 10 { 3 4 6 } { 3 4 6 }
1     ! 10 { 3 4 6 } { 3 4 6 } 1
v-n   ! 10 { 3 4 6 } { 2 3 5 }
v/    ! 10 { 1+1/2 1+1/3 1+1/5 }
Π     ! 10 2+2/5    (product)
*     ! 24

```
> 1 votes

# Answer
# Charcoal, 9 bytes

```
Ｉ÷×ηΠθΠ⊖θ

```

Try it online! Link is to verbose version of code. Explanation: Variant of @pajonk's answer that doesn't suffer from floating-point errors.

```
   η        Second input
  ×         Multiplied by
     θ      First input
    Π       Product
 ÷          Integer divided by
        θ   First input
       ⊖    Vectorised decrement
      Π     Product
Ｉ           Implicitly print

```
> 1 votes

# Answer
# JavaScript (Node.js), 40 bytes

```
x=>n=>n*eval([x.join`*`,...x].join`/~-`)

```

Try it online!

37 with small error
> 1 votes

# Answer
# Perl 5, 33 bytes

```
sub{$a=pop;$a*=$_/($_-1)for@_;$a}

```

Try it online!
> 1 votes

# Answer
# Pip, ~~18~~ 9 bytes

```
q*$*Yg/Dg

```

Attempt This Online!

Takes the list on the command line and the number on STDIN.

*-9 thanks to @DLosc*

#### Explanation

```
q*$*Yg/Dg  # Implicit input
q          # The number
 *         # multiplied by
  $*Y      # the product of
     g/    # the list divided by
       Dg  # the list minus one
           # Implicit output

```

Old:

```
Fig/BN-g{o:o*i}o*q  # Implicit input
Fi                  # for i in ...
  g/                # ... the list divided by ...
    BN-g            # ... the list minus one ...
        {     }     # ... do:
         o:         #  set o to ...
           o*i      #  ... o times i
               o*q  # output o times the number

```

(`o` is automatically initialised to 1)
> 1 votes

# Answer
# F#, 39 bytes

```
let i=Seq.foldBack(fun n c->c*n/(n-1.))

```

Try it online!

A partial-application solution. The function `i` takes two parameters and applies them directly to `Seq.foldBack` \- the source, and the initial state. In this case, the source is the collection of divisions made on the apples (eg. `[4, 3]`), and the initial state is the remaining apples (eg. `20`).

`Seq.foldBack` threads an accumulator through the collection, starting with an initial state, then applying the function specified using the next value in the sequence to that state (in this case, calculating the apple count from the next division), and so on until the sequence is finished. Because it's `Seq.foldBack`, it goes through the collection in reverse order. It returns the result of the accumulator: the initial number of apples.

For those who are curious, the reason for the `1.` instead of just plain `1` is that F# is very very strongly typed. You cannot subtract an integer from an float. Both have to be the same type. `1` is an integer, and `1.` is a float.
> 1 votes

# Answer
# Haskell, ~~33~~ 31 bytes

*-2 bytes thanks to @Lynn*

```
p=product
x#n=p x/p(pred<$>x)*n

```

Attempt This Online!
> 1 votes

# Answer
# Haskell, 22 bytes

```
foldr(\k a->k*a/(k-1))

```

Accepts the number, and then the list: `foldr(\k a->k*a/(k-1)) 10 [3, 4, 6]` is 24.

Attempt This Online!
> 1 votes

# Answer
# Nibbles, ~~6.5~~ 6 bytes

```
/*`*$@`*+-1

```

Attempt This Online!

```
/  Divide
*   multiply
`*   product
$     the list
@    the number
`*  product
+    add
-1    -1
      the list [vectorized]

```
> 0 votes

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


title: Fibonacci Binary Squares

text:
# Question
Title: Fibonacci Binary Squares
I was playing with the Fibonacci sequence in binary like so (note that the binary representations are written here from smallest bit to largest bit):

```
1                          1
1                          1
01                         2
11                         3
101                        5
0001                       8
1011                       13
10101                      21
010001                     34
111011                     55
1001101                    89
00001001                   144
10010111                   233
...

```

and I noticed that it took until the 11th Fibonacci number (1-indexed) to find a 2-by-2 square of the same bit:

```
1 00 1101
0 00 01001

```

I then wondered: in what row does the first *n*-by-*n* square filled with the same bit start?

## Task

Given an integer *n*, what is the index of the first Fibonacci number that contains part of an *n*-by-*n* square filled with the same bit?

## Rules

* You can have the Fibonacci sequence be either 0- or 1-indexed
* You do not have to worry about invalid input
* You may use any standard I/O method
* Standard loopholes are forbidden
* This is `code-golf`, so the shortest code in bytes per language wins

## Test cases:

```
Input (1-indexed) -> Output (0-indexed/1-indexed)
1 -> 0/1
2 -> 10/11
3 -> 22/23
6 -> 382/383
8 -> 4570/4571

```

## Format:

The answers can use one of the following input/output methods, and can be 0- or 1-indexed:

* Given some index *n* it can return the *n*-th entry of the list.
* Given some index *n* it can return all entries up to the *n*-th one in the sequence.
* Without taking any index, it can output *all* entries by e.g. ...
    + ...printing them one by one (potentially infinitely) or...
    + ...returning a list (lazy if the sequence is infinite) or...
    + ...returning a generator that represents the whole sequence.

# Answer
> 5 votes
# Wolfram Language (Mathematica), 124 bytes

```
(n=k=#;While[!Or@@(!FreeQ[Split@Total@PadLeft@IntegerDigits[Fibonacci@t[n-1+b,{b,k}],2],#]&/@{0~(t=Table)~k,k~t~k}),n++];n)&

```

Try it online!

# Answer
> 4 votes
# JavaScript (Node.js), 143 bytes

Expects a BigInt. The output is 0-indexed.

```
n=>eval("for(i=a=[],g=(p,q=a.reduce((q,v,i)=>i<n?p?q&v:q|v:q))=>q?(p?~q:q)&~-(1n<<n)&&g(p,q/2n):1n;g(a=[++i>2?a[0]+a[1]:1n,...a])&g(););i-[n]")

```

Try it online!

### Commented

This is a version without `eval()` for readability.

```
n => {              // n = input
for(                // main loop:
  i =               //   i = iteration counter
  a = [],           //   a[] = Fibonacci sequence in reverse order
  g = (             //   g is a helper function taking:
    p,              //     p = flag (false: test 0s, true: test 1s)
    q = a.reduce(   //     q = bitmask to be tested
      (q, v, i) =>  //     for each value v at index i in a[]:
      i < n ?       //       if i is less than n:
        p ? q & v   //         if p is set, update q to q AND v
          : q | v   //         otherwise, update it to q OR v
      :             //       else:
        q           //         leave q unchanged
    )               //     end of reduce()
  ) =>              //
  q ?               //   if q is not 0:
    (p ? ~q : q)    //     take either q or NOT(q) depending on p
    & ~-(1n << n)   //     isolate the n least significant bits
    &&              //     if the result is not 0 ...
      g(p, q / 2n)  //     ... try again with q right-shifted by 1
  :                 //   else:
    1n;             //     stop with a truthy value
  g(                //   first call to g with a truthy flag:
    a = [           //     update a[]:
      ++i > 2 ?     //       increment i; if it's greater than 2:
        a[0] + a[1] //         append the sum of the first 2 terms
      :             //       else:
        1n,         //         append 1
      ...a          //       followed by the existing terms
    ]               //
  ) & g();          //   second call to g with a falsy flag
);                  // end of for
return i - [n] }    // return the final position

```

# Answer
> 4 votes
# Raku, ~~105~~ 101 bytes

```
->\n{(1,1,*+*...{@_.tail(n)».base(2).flip~~/^(\d*)((\d)$0**:{n-1})\d*[' '\d**{$0.chars}$1\d*]*$/})-n}

```

Try it online!

*Edit:* I had to use a workaround for an apparent Raku bug. Later I found that the bug has already been reported, and the bug report suggested a different workaround, four bytes shorter than mine.

This is an anonymous function that takes a single argument `n`. The body is just a lazy Fabonacci generator with a complicated ending condition between the braces:

```
(1, 1, * + * ... { ... }) - n

```

Subtracting `n` from the sequence coerces it to a number, its length; the difference is returned.

Anyway, as for the ending condition:

* `@_.tail(n)` looks at just the last `n` elements of the Fibonacci sequence.
* `».base(2)` converts each number to its binary representation.
* `.flip` coerces that sequence of strings to a single string, joining the individual elements with spaces, then reverses the entire string.
* `~~ / ... /` matches that space-delimited string of bit strings against the slash-delimited regex.
* `^` is the beginning of the string.
* `(\d*)` is zero or more digits. This is the part that comes before the square of identical bits. It's captured in group 0 so that we can check for prefixes of the same length on the following lines.
* `((\d) $0 **: {n-1})` is a sequence of `n` of the same digit, captured in group 1.
* `\d*` matches zero or more digits to the right of the square of bits.
* `[' ' \d ** {$0.chars} $1 \d* ]*` matches, zero or more times, a space, then a digit prefix consisting of the same number of characters as the prefix on the first row, then the row of identical digits in group 1, then zero or more other digits.
* `$` is the end of the string.

# Answer
> 3 votes
# 05AB1E, ~~38~~ 35 bytes

```
∞<.ΔIÝ+Åf2вí2FøI"üÿ"δ.V}Aδ.ý˜ÅγIn@à

```

Given \\$n\\$, it'll output the 0-based value.

Try it online or verify the first 5 test cases.

Pretty slow. Can barely output \\$n=6\\$ in about 55 seconds on TIO.

**Explanation:**

```
∞                # Push an infinite positive list: [1,2,3,4,5,...]
 <               # Decrease it to a non-negative list: [0,1,2,3,4,...]
  .Δ             # Pop and find the first value that's truthy for:
    IL           #  Push a list in the range [1,input]
      +          #  Add the current value to each in this list
       Åf        #  For each of these values, get their 0-based Fibonacci number
         2в      #  Convert each inner Fibonacci number to a binary-list
           í     #  Reverse each inner list
    2FøI"üÿ"δ.V} #  Create overlapping input by input blocks:
    2F         } #   Loop 2 times:
      ø          #    Zip/transpose; swapping rows/columns
       I         #    Push the input-integer
        "üÿ"     #    Push this string, replacing `ÿ` with the input
            δ    #    Map over each inner row with this string as argument:
             .V  #     Evaluate the string as 05AB1E code,
                 #     where `ü#` creates overlapping items of size `#`
     δ           #  Map over each row of input by input sized blocks:
    A .ý         #   Intersperse it with the lowercase alphabet (or any rubbish value)
        ˜        #  Then flatten it to a single list
         Åγ      #  Run-length encode it; pushing the list of values and list of lengths
           In    #  Push the squared input
             @   #  Check for each value whether it's >= this squared input
              à  #  Get the flattened maximum to check if any is truthy
                 #  (which means there was an input by input sized block consisting of
                 #  the same bit)
                 # (after which the found index is output implicitly as result)

```

Minor note: `Aδ.ý˜ÅγIn@à` instead of just `εε˜Ë}}à` (nested map over the blocks `εε...}}`; flatten `˜`; check if all bits are the same (`Ë`); any `à`) is for the first few binary representations of Fibonacci numbers, which are smaller than an \\$n\times n\\$ block. The `2FøI"üÿ"δ.V}` will in those cases result in an empty (nested) list, which is unfortunately truthy for the `Ë` check.

# Answer
> 2 votes
# Python 3.8, ~~262~~ ~~260~~ 205 bytes

Function `s` that accepts `n` as input (1-indexed) and returns the index 1-indexed. Quite slow, but in theory it works!

*Edit*:

* *-2 bytes thanks @The Thonnu*
* *-54 bytes thanks @Neil*
* *-1 byte: moved `i` as optional function argument*

```
f=lambda x:x>1and f(x-1)+f(x-2)or x
def s(n,i=0):
 while 1:
  i+=1;b=[bin(f(i+_))[::-1]for _ in range(n)]
  for d in'01':
   for p in range(i):
    for k in b:
     if k[p:p+n]!=d*n:break
    else:return i

```

Try it online!

---

Commented code *(original version)*:

```
# lambda function that computes the Fibonacci numbers
f=lambda x: x>1 and f(x-1) + f(x-2) or x

# main function
def s(n):

 # index of the i-th Fibonacci number that is evaluated
 i = 0

 while 1:

  i + =1

  # list of binary representations of n Fibonacci numbers
  b = [bin(f(i+_-1))[2:][::-1] for _ in range(n)]

  # check both digits
  for d in '01':

   # find digit at each position in binary repr
   for p in range(len(b[0])):

    # find if repeated digit is substring of binary repr
    if b[0][p:].find(d*n) >= 0:

     # search in following Fibonacci numbers
     for k in b[1:]:

      # if substring found at different position break loop
      if k[p:].find(d*n) != 0: break

     # for loop is terminated, found all substrings at same positions
     else: return i

```

# Answer
> 2 votes
# Python, 182 bytes

```
def e(n,*l):
 r=[*zip(*[bin(i)[:1:-1]for i in l[:n]])]
 if len(r)>n>=1==min(len({*sum(r[i:i+n],())})for i in range(len(r)-n)):print((len(l)-n)*(n>1));n+=1
 e(n,l[0]+l[1],*l)
e(1,1,1)

```

Attempt This Online!

Prints the 0-based indices infinitely. (Contains a particularly horrible kludge to deal with `n=1`; let me know if you have a better solution.)

# Answer
> 2 votes
# Charcoal, 43 bytes

```
Ｎθ⊞υ¹Ｗ¬⊙01⊙υ⬤…⮌υθ№⌕Ａ⮌⍘ξ²×κθν⊞υΣ✂υ±²Ｌυ¹Ｉ⁻Ｌυθ

```

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

```
Ｎθ

```

Input the desired number of bits.

```
⊞υ¹

```

Start with `F(1)=1`.

```
Ｗ¬⊙01⊙υ⬤…⮌υθ№⌕Ａ⮌⍘ξ²×κθν

```

Check the last `n` Fibonacci numbers to see whether there is an index where they all share an overlapping match of a string of either all `n` `0`s or all `n` `1`s in their binary representations.

```
⊞υΣ✂υ±²Ｌυ¹

```

Calculate the next Fibonacci number. Unfortunately I have to start with just one Fibonacci number which makes the formula much longer than normal.

```
Ｉ⁻Ｌυθ

```

Calculate the 0-based index of the first of the last `n` Fibonacci numbers.

Bit twiddling is faster but longer at 65 bytes:

```
Ｎθ⊞υ¹≔⁰η≔⁰ζＷ¬∨№⍘η²×1θ№⍘ζ²×0θ«⊞υΣ✂υ±²≔↨υ⁰η≔ηζＦ…⮌υθ«≧＆κη≧｜κζ»»Ｉ⁻Ｌυθ

```

Try it online! Link is to verbose version of code. Explanation: Calculates Fibonacci numbers, taking both the logical Or and logical And of the last `n` Fibonacci numbers, until either the logical Or contains `n` `0`s or the logical And contains `n` `1`s in their binary representation. Somewhat verbose because I can't take the logical Or or And of a list.

---
Tags: code-golf, sequence, fibonacci
---


title: Sample integers that sum to one hundred

text:
# Question
Title: Sample integers that sum to one hundred
Given a positive integer n, randomly output n non negative integers that sum to one hundred. n will be at most 200. The output should be present as a list of integers (not sorted).

Your random sample should be uniformly sampled from all lists of n non negative integers that sum to one hundred.

Your code should run in a reasonable amount of time (e.g. should terminate on TIO) for n less than a 200 . This is just to prevent brute force solutions.

# Examples

If n=1 the code should always output 100

If n=2 the code should output 100,0 or 99,1 or 98,2 or 97,3 ... or 2,98 or 1,99 or 0,100 with equal probability. There are 101 different possible outputs in this case.

If n\>100 then some of the values in the output will necessarily be 0.

# Answer
> 7 votes
# , 64 bytes

```
\(n,m=rle(c(1,sample(!c(1:99,!1:n-1)),1)))c(m$l[!m$v],!1:n)[1:n]
```

Attempt This Online!

Implementation of 'sticks-and-stones' as suggested by xnor.

**Ungolfed**

```
function(n){
    w=rep(0:1,times=c(n-1,100)) # n-1 zeros, followed by 100 ones
    x=sample(w)                 # randomly shuffle it
    y=c(0,x,0)                  # and add zeros at the start & the end
    m=rle(y)                    # get the lengths of runs of 1s and 0s
    o=m$lengths[m$values==1]    # lengths of the runs of ones
    p=m$lengths[m$values==0]-1  # lengths of the runs of zeros, minus 1
    q=sum(p)                    # so q is the number of zero-length runs of 1s
    z=rep(0,q)                  # repeat zero that many times
    return(c(o,z))              # and return the concatenation of the runlengths of 1s and the zero-length runs
}

```

**Golfing tricks**
`rep(0:1,times=c(n-1,100))` -\> `!c(1:99,!1:n-1)`
`c(m$lengths[m$values==1],rep(0,sum(m$lengths[m$values==0]-1)))` -\> `c(m$l[!m$v],!1:n)[1:n]`

# Answer
> 6 votes
# Octave, 46 bytes

```
@(n)diff([0,sort(randperm(n+99,n-1)),n+100])-1

```

Try it online!

Based on @xnor's comment. But instead of shuffling a list of zeros and ones, here I generate a random permutation of `1:n+99`, and see the first `n-1` terms as the positions of zeros.

# Answer
> 4 votes
# Pyth, 16 bytes

```
lMc.S+*100N*tQdd

```

Try it online!

Based on xnor's comment.

* `*100N`: 100 `"` characters
* `*tQd`: n-1 space characters
* `.S+`: Concatenate, shuffle
* `c ... d`: Split on spaces
* `lM`: Map to lengths of remaining pieces

# Answer
> 3 votes
# , 27 bytes

```
0+/;.1@,1 0({~#?#)@#~100,<:

```

Try it online!

Sticks and stones method thanks to xnor's idea from the comments.

# Answer
> 3 votes
# C (clang), ~~125~~ ~~120~~ 115 bytes

* *-5 bytes thanks to @ceilingcat*

```
i=99,j,a[];main(n){scanf("%d",&n);n+=i;for(srand(&n);a[rand()%n]++||i--;);for(;i<n;)j=a[++i]?j+1:!printf("%d ",j);}

```

An implementation of xnor's suggestion in C.

Try it online!

# Answer
> 2 votes
# Desmos, 77 bytes

```
l=[2...n]
L=join(0,[1...99+n].shuffle[l[l0+n>1]].sort,100+n)
f(n)=L[2...]-L-1

```

Uses xnor's Stars and Bars idea.

Try It On Desmos!

Try It On Desmos! - Prettified

# Answer
> 2 votes
# 05AB1E, 9 bytes

```
т∍ú¦.r#€g

```

Inspired by *@isaacg*'s Pyth answer, using *@xnor*'s approach.

Try it online or verify a few random outputs at once.

**Explanation:**

```
 ∍         # Extend the (implicit) input
т          # to length 100
           # (resulting in a string - e.g. n=50 becomes "505050...50")
  ú        # Pad this string with the (implicit) input amount of leading spaces
           # (it's important to note that `∍` results in a string instead of integer,
           # otherwise this would have resulted in "50" with 505050...50 amount of
           # leading spaces instead)
   ¦       # Remove the first space, so there are input-1 amount of spaces
    .r     # Randomly shuffle the characters in this string
      #    # Split it on spaces
       €g  # Get the length of each inner string
           # (after which the result is output implicitly)

```

# Answer
> 1 votes
# PARI/GP, 82 bytes

```
n->Vec(Ser(concat([Set(numtoperm(m=n+99,random(m!))[1..n-1]),m+1]))*(y=1-x)-1/y,n)
```

Attempt This Online!

Based on @xnor's comment:

> It doesn't look like anyone has done this yet, but a slick approach is to make a list of 100 ones and n-1 zeros, shuffle it, and list off the lengths of the n runs of ones separated by zeroes. – xnor

PARI/GP doesn't have a built-in for shuffling, but we can generate a random permutation of `[1..n+100-1]` using `numtoperm` and `random`, and see the first `n-1` terms as the positions of zeros.

---

# PARI/GP, 94 bytes

```
n->b=binomial;r=random(b(n+99,k=100));[while(r>=s=b(n-l+k-1,k),r-=s;i++;k--)+i|l<-[1..n],!i=0]
```

Attempt This Online!

The number of possible outputs is `binomial(n+100-1,100)`. Here I first generate a random number `r` in the range `[0..binomial(n+100-1,100)-1]`, and then find the `r`th result. So this is guaranteed to be uniform.

# Answer
> 1 votes
# Python 3, 88 bytes

```
lambda n:[*map(len,bytes(sample([0]*100+[9]*~-n,n+99)).split(b'	'))]
from random import*

```

Try it online!

Also uses the "sticks and stones" method.

This creates a list of 100 0s and n−1 9s, then `sample` gives n+99 elements (which is all of them) in a random order. The result is then converted to `bytes` in order to use `split`; 9 was chosen because it corresponds to the tab character (which is placed in the `bytes` literal for the argument to `split`). Finally, use `map` to take the `len`gth of each piece, and `[*…]` makes it into a list.

# Answer
> 1 votes
# APL(Dyalog Unicode), 28 bytes SBCS

```
-↑∘{+/¨⍵⊂⍨1@1~⍵}{100≥?⍨⍵+99}

```

Try it on APLgolf!

A train which takes a single integer. Uses the sticks and stones method, since it translates quite well to APL.

-6 from ovs.

# Answer
> 1 votes
# Retina, 43 bytes

```
.+
*
_$
100*@¶
+@v`(.)(.*¶)
$2$1
¶

S`_
%`@

```

Try it online! Explanation:

```
.+
*

```

Convert to unary (using `_`).

```
_$
100*@¶

```

Decrement the input, append 100 `@`s, and create a work area for the shuffle.

```
+@v`(.)(.*¶)
$2$1

```

Repeatedly select a character randomly from the first line and move it to the start of the second line. (The `+` indicates to repeat, the `@` selects randomly, and the `v` allows the matches to overlap, which doesn't matter here since we're only replacing one at a time.)

Delete the input area.

```
S`_

```

Split the working area on `_`s. Since there were `n-1` of them, there are now `n` lines.

```
%`@

```

Count the number of `@`s on each line.

# Answer
> 1 votes
# Wolfram Language (Mathematica), 41 bytes

Edit: I have made my code much simpler and shorter.

```
Values[Counts[RandomInteger[{1,#},100]]]&

```

RandomInteger creates a random number between 1 and the given input integer, with uniform probability. This is done 100 times, and Counts tallies up the number of appearances of each number.

Try it online!

Old code from my previous submission is below.

```
Length/@Select[Flatten[Split[RandomChoice[Join[Riffle[Table[1,{#}]&/@#,0]]&/@Flatten[Permutations/@IntegerPartitions[100+#,{#}]-1,1]]],1],Length[#]>1&]&

```

# Answer
> 1 votes
# JavaScript (Node.js), 99 bytes

```
f=(n,a=[100])=>--n?f(n,a.flatMap(v=>(s||s++)<p&&(s+=v)>p?[d=s-p|0,v-d]:v,p=Math.random(s=0)*101)):a

```

Attempt This Online!

A recursive approach that starts with the array `[100]`, and 'splits' it randomly `n` times.
eg. `[27, 51, 22]` -\> `[27, 11, 40, 22]`

The hardest (and most costly) part is making sure `[0, 100]` is a possible output.

There is an extremely slim chance (at most approx. 1 in 253, source) of the function producing invalid output, when `Math.random()` returns exactly `0`.

# Answer
> 1 votes
# GolfScript, 42 bytes

```
100\(:a+,{;9.?rand}${a<}%1+{.1?.@@)>n\.}do

```

Try it online!

For some reason I just *had* to use GolfScript for this. No idea why though, I've never used this language before. Anyways, this is yet another implementation of xnor's idea.

```
100         # push 100 onto the stack
\(:a        # store n-1 in variable a
+,          # create array of ints from 0 to (100 + n-1) - 1
{;9.?rand}$ # shuffle array, method taken from GS tips page
{a<}%       # map items to 0 if they are >=a and to 1 if they are <1
1+          # append 1 to list.
            # This is done so that ? always finds a 1 later
{
  .1?       # find position of first 1 in array
  .@@       # move a copy of that position to the back of the stack
  )>        # discard all elements with an index < (position - 1)
  n\        # push a newline onto the stack, flip array back to the top
            # The implicit output concats all stack values together :(
.}do        # repeat until array is empty

```

The program expects n to be at to top of the stack. TIO's input field does ...unexpected things, so the header field is used to provide input instead.

# Answer
> 1 votes
# Vyxal `W`, 13 bytes

```
‹(₁ʀ℅)₁Ws₍h¯f

```

choose cut positions and sort them, append 100 at the end, calculate the difference

=\>`first number, differences...`

Try it Online!

# Answer
> 1 votes
# Ly, 22 bytes

```
'dspn,[r0l?:lf-spr,]pl

```

Try it online!

This meets the requirements in that all possible combinations of numbers that sum to 100 could be returned, but I don't think all of them have an equal chance. But someone with better understanding of statistics would have to weigh in to be sure... If that's a disqualification, I'll remove the answer. But from what I can tell, the approach is different from the other algorithms used so it might be interesting?

At a high level, the code loops `N-1` times where `N` is the count requested on STDIN. Each time through the loop it generates a random number in `0-X` where `X` starts at 100 and is decremented by the number added to the list each time. Once the loop is exhausted, it finds the number requires to get the sum to 100 and uses that as the last entry.

```
'dsp                   - Load "100", save to backup cell and pop from stack
    n,                 - Read list size "N" requested from STDIN, decrement
      [r         r,]p  - Loop once for "N-1" times
        0l?            - Load backup cell, generate random number in "0-X"
           :           - Duplicate random pick
            lf-        - Sub random pick from previous "left to sum" number
               sp      - Save new "left to sum" to backup cell and pop from stack
                     l - Load "left to sum" from backup cell
                       - Stack prints as numbers by default on exit

```

# Answer
> 0 votes
# Python 3.9, 233 226 224 211 Bytes

```
import random
from functools import*
r,p=range,cache(lambda n,s:s<1 if n<1 else sum(p(n-1,k)for k in r(s+1)))
def f(n,s):
    k=random.choices(r(s+1),[p(n-1,k)for k in r(s+1)])[0]
    return[]if n<1 else[s-k]+f(n-1,k)

```

TIO link. Slightly longer as the cache decorator is only available in Python 3.9.

# Answer
> 0 votes
# Burlesque, 49 bytes

```
s10 100rn1bx100.*FL{jg_x/0x/ia}{g1-.Js1}w!q0;;)++

```

Try it online!

Inputs are random seed and count.

```
s1         # Save count
0 100rn    # Random numbers 0..100 (seeded by second input)
1bx100.*FL # 100 1s
{
  j        # Reorder stack
  g_       # Get head of random number
  x/0x/ia  # Insert a 0 at that position
 }{
  g1-.Js1  # Decrement count and check
 }w!       # While
 q0;;      # Split on 0s
 )++       # Sum each block

```

# Answer
> 0 votes
# Charcoal, 34 bytes

```
≔Ｅ⊖Ｎ⁰θ≔Ｅ×χχ¹η⊞υ⁰Ｗ⁺θη⊞υ⎇‽ι⁺⊟υ⊟η⊟θＩυ

```

Try it online! Link is to verbose version of code. Explanation: Uses @xnor's method.

```
≔Ｅ⊖Ｎ⁰θ

```

Create a list of `n-1` `0`s.

```
≔Ｅ×χχ¹η

```

Create a list of `100` `1`s.

```
⊞υ⁰

```

Start the output list with one `0` for now.

```
Ｗ⁺θη

```

Repeat until all of the `0`s and `1`s have been popped.

```
⊞υ⎇‽ι⁺⊟υ⊟η⊟θ

```

Select one of them at random. If it's a `1`, then increment the latest number in the output list, otherwise push one of the `0`s to the output list, all while removing the `1` or `0` from its list as appropriate.

```
Ｉυ

```

Output all of the integers.

# Answer
> 0 votes
# JavaScript (Node.js), 94 bytes

```
f=(n,s=100,g=Math.random,i=g()*-~s|0)=>--n?g()*s**n<(i+1)**n-i**n?[...f(n,i),s-i]:f(n+1,s):[s]

```

Try it online!

Probable ret\[0\]==s-i is `((i+1)**n-i**n)/s**n`

# Answer
> 0 votes
# Japt, 13 bytes

```
î ÅiLî¬ ö¬¸mÊ

```

Try it

---
Tags: code-golf, probability-theory
---