title: Generate combinations with replacement

text:
# Question
Title: Generate combinations with replacement
List all of the combinations with replacement (or combinations with repetition) of size *k* from a set of *n* elements.

A combination with replacement is an unordered multiset that every element in it are also in the set of *n* elements. Note that:

* It is unordered. So a previously printed set with a different order shouldn't be printed again.
* It is a multiset. The same element can (but isn't required to) appear more than once. This is the only difference between a combination with replacement and a normal combination.
* The set should have exactly *k* elements.

Alternatively, it is also a size-*k* subset of the multiset which contains each of the *n* elements *k* times.

The input should be either *n* and *k*, where the elements are the first *n* positive or non-negative integers, or the *n* elements and *k*, where you can assume the *n* elements are all different from each other.

The output should be a list of all the combinations with replacement with size *k* from the given set. You can print them and the elements in each of them in any order.

You may not use builtins generating combinations with replacement. But you can use builtins to generate normal combinations, permutations, tuples, etc.

This is code-golf, shortest code wins.

## Example

```
Input: 4 2
Output: [0 0] [0 1] [0 2] [0 3] [1 1] [1 2] [1 3] [2 2] [2 3] [3 3]

```

# Answer
## Jelly, 4 bytes

*Thanks to Sp3000 for saving 2 bytes.*

```
ṗṢ€Q

```

Input is `n` and `k` as command-line arguments in that order. Uses elements `1` to `n`.

Try it online!

### Explanation

```
ṗ     # Get k-th Cartesion power of n.
 Ṣ€   # Sort each tuple.
   Q  # Remove duplicates.

```
> 8 votes

# Answer
## CJam (8 bytes)

```
{m*:$_&}

```

Online demo

### Dissection

```
{    e# Declare block (anonymous function); parameters are n k
  m* e# Cartesian product, which implicitly lifts n to [0 1 ... n-1]
  :$ e# Sort each element of the Cartesian product, to give them canonical forms
  _& e# Deduplicate
}

```
> 8 votes

# Answer
# MATL, 11 bytes

(There's a 9-byte solution based on Cartesian power, but Peter Taylor already did that. Let's try something different).

Combinations with replacement can be reduced to combinations without replacement as follows. We want `n Cr k`, for example with `n=3`, `k=2`:

```
0 0
0 1
0 2
1 1
1 2
2 2

```

We can compute `n+k-1 C k`:

```
0 1
0 2
0 3
1 2
1 3
2 3

```

and then subtract `0 1 ... k-1` from each row:

```
+q:2GXn2G:-

```

Explanation:

```
+q     % take two inputs n, k and compute n+k-1
:      % range [1,2...,n+k-1]
2G     % push second input, k
Xn     % combinations without replacement
2G:    % range [1,2,...,k]
-      % subtract with broadcast. Display

```

The code works in release 13.1.0 of the language/compiler, which is earlier than the challenge.

You can **try it online!** Note that the online compiler has been updated to release 14.0.0, so `Xn` needs to be changed to `XN`.
> 3 votes

# Answer
## Mathematica, ~~31~~ 29 bytes

*Thanks to A Simmons for saving 2 bytes.*

```
{}⋃Sort/@Range@#~Tuples~#2&

```

An unnamed function taking `n` and `k` as integer arguments in that order and returning a list of lists. The elements will be `1` to `n`. Works the same as Peter's CJam answer.
> 3 votes

# Answer
## JavaScript (Firefox 30-57), 71 bytes

```
f=(n,k)=>k?[for(m of Array(n).keys())for(a of f(m+1,k-1))[...a,m]]:[[]]

```

I get to use `keys()` for once.
> 3 votes

# Answer
## Ruby, ~~56~~ 55 bytes

Two solutions, surprisingly both the same length:

```
->n,k{[*1..n].repeated_permutation(k).map(&:sort).uniq}
->n,k{(a=[*1..n]).product(*[a]*(k-1)).map(&:sort).uniq}

```

Hey, you *did* say we could use permutation builtins...

This simply generates all repeated *permutations* (the second one generates repeated Cartesian products) and removes ones that aren't in sorted order.

Thanks to Martin for saving a byte with `0...n` -\> `1..n`!
> 2 votes

# Answer
# Dyalog APL, 22 bytes

```
{∪{⍵[⍋⍵]}¨↓⍉⍺⊥⍣¯1⍳⍺*⍵}

```

Requires `⎕IO←0`, which is default in many APL systems. Takes k as left argument, n as right argument.

`⍳⍺*⍵` 0 1 2 ... kⁿ
`⍺⊥⍣¯1` convert to base k
transpose
make matrix into list of lists
`{⍵[⍋⍵]}¨` sort each...
the unique
> 1 votes

# Answer
## Pyth, 7 bytes

```
{SM^UQE

```

Uses the same algorithm as Peter's answer.

```
    UQ   range(input())
      E  input()
   ^     repeated Cartesian product of ^^, ^ times
 SM      map(sort)
{        uniq

```
> 1 votes

# Answer
# Python 3, 81 80

Recursive solution:

```
t=lambda n,k,b=0:[[]]if k<=0 else [[i]+l for i in range(b,n)for l in t(n,k-1,i)]

```

The function `t(n, k, b)` returns the list of all `k`-element multi-subsets of the range from `b` to `n`. This list is empty if `k <= 0`. Otherwise, we break the problem down based on the smallest element of the multi-subset, which we denote by `i`.

For each `i` in the range from `b` to `n`, we generate all of the `k`-multi-subsets with smallest element `i` by starting with `[i]` and then appending each `(k-1)`-multi-subset of the range from `i` to `n`, which we obtain by recursively calling `t(n, k-1, i)`.
> 1 votes

# Answer
## Python, 63 bytes

```
f=lambda n,k:n*k and[l+[n]for l in f(n,k-1)]+f(n-1,k)or[[]][k:]

```

A recursive method. To make a multiset of `k` elements, `1` to `n`, we choose to either:

* Include another instance of `n`, and it remains to make a multiset of `k-1` elements from `1` to `n`
* Don't include another instance of `n`, and it remains to make a multiset of `k` elements from to `1` to `n-1`

We terminate when either `k` or `n` reaches `0`, and if it `k` reached `0`, we give a base case of the empty list. If not, we have the wrong number of elements, and so give the empty list.
> 1 votes

# Answer
# J, 18 bytes

```
[:~.#~<@/:~@#:i.@^

```

Similar approach used in @Adám's solution.

Another approach using Cartesian product `{` for 24 bytes. Takes `k` on the LHS and `n` on the RHS.

```
~.@:(/:~&.>)@,@{@(#<@i.)

```

## Usage

```
   f =: [:~.#~<@/:~@#:i.@^
   4 f 2
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│0 0│0 1│0 2│0 3│1 1│1 2│1 3│2 2│2 3│3 3│
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘

```

## Explanation

```
[:~.#~<@/:~@#:i.@^ Input: n on LHS and k on RHS
                 ^ Compute n^k
              i.@  Create a range [0, 1, ... n^k-1]
    #~             Create k copies on n
            #:     On each value in the range above, convert each digit to base-n
                   and take the last k digits of it
        /:~@       For each array of digits, sort it in ascending order
      <@           Box each array of digits
[:~.               Take the distinct values in the array of boxes and return it

```
> 1 votes

# Answer
## Clojure, 94 bytes

```
(defn f[k n](if(= 1 k)(for[i(range n)][i])(sort(set(for[i(f(dec k)n)j(range n)](conj i j))))))

```

Note the changed parameter order: 1st is `k` and 2nd is `n`. This saved 1 byte in `(f(dec k)n)`.
> 1 votes

# Answer
# Mathematica, 36 bytes

```
{##}&~Array~Table@##~Flatten~(#2-1)&

```

*Please* tell me there's a 1/6 bonus for using no \[\]s...Or maybe for the many uses of ##?
> 0 votes

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


title: Evaluate the aspect ratio of a triangle

text:
# Question
Title: Evaluate the aspect ratio of a triangle
Given three sidelengths of a triangle, evaluate its aspect ratio *AR* given the following formula:

where

The closer to equilaterality a triangle is, the closer to `1` its aspect ratio is. The aspect ratio is bigger or equal to `1` for valid triangles.

### Inputs

The input is three real positive numbers which can be encapsulated in a list or anything similar if need be.

Your program must output the same value no matter what the order in which the three sidelengths are inputted is.

Those three numbers will always be valid sidelengths of a triangle (degenerate triangles like one with sidelengths `1`, `1` and `2` will not be given as input). You need not worry about floating point inaccuracies when values become extremely close to a degenerate triangle (e.g. it is acceptable that your program would error `division by 0` for input `[1, 1, 1.9999999999999999]`).

The input can be given through `STDIN`, as a function argument, or anything similar.

### Outputs

The output is a real number bigger or equal to `1` with the standard accuracy that is acceptable in your language.

The output may be printed to `STDOUT`, returned from a function, or anything similar.

### Test cases

```
Inputs                   Output

  1      1      1         1
  3      4      5         1.25
 42     42   3.14         ≈ 6.9476
 14      6     12         1.575
  6     12     14         1.575
0.5    0.6    0.7         ≈ 1.09375

```

### Scoring

This is , so the shortest answer in bytes wins.

# Answer
# Jelly, 6 bytes

This answer is based on Emigna's 05AB1E answer. Many thanks to Dennis and Lynn for their help in figuring this answer out. Golfing suggestions welcome! Try it online!

```
S_Ḥ⁸÷P

```

**Ungolfing**

```
           Implicit argument [a, b, c].
S          Take the sum, a+b+c or 2*s
  Ḥ        Take the double, [2*a, 2*b, 2*c].
 _         Vectorized subtract, giving us [2*(s-a), 2*(s-b), 2*(s-c)].
   ⁸÷      Vectorized divide the initial left argument, the input [a, b, c],
             by [2*(s-a), 2*(s-b), 2*(s-c)].
     P     Take the product giving us the aspect ratio, abc/8(s-a)(s-b)(s-c).

```
> 19 votes

# Answer
# Jelly, 7 bytes

```
SH_÷@HP

```

Try it online!

## Explanation

Let’s read this chain:

* The implicit argument is a list `[a, b, c]`.
* First we read `S`. This takes the sum: `a + b + c`.
* Then, we read `H`. This halves it: `(a + b + c)/2`. (This is `s`.)
* Then, we read a dyad `_` (subtract), followed by another dyad. This is a **hook**: it lacks a right argument, so it receives the argument to this chain, `[a, b, c]`, giving us `[s-a, s-b, s-c]`. (This is the **fifth chain pattern in the table here**.)
* Then, we read the dyad-monad pair `÷@H`. This is a **fork**: `÷@` is division with the arguments flipped, and `H` is halve, so our working value gets `H`alf the argument to this chain `÷`’d by it. This vectorizes; we’re left with `[(a/2)/(s-a), (b/2)/(s-b), (c/2)/(s-c)]`. (This is the **second chain pattern in the table here**.)
* Finally, we take the product with `P`, getting us `abc/(8(s-a)(s-b)(s-c))`.

**View a tree-like graph of how the links fit together.**
> 56 votes

# Answer
# Jelly, 6 bytes

```
S÷_2Pİ

```

Try it online!

### How it works

```
S÷_2Pİ  Main link. Argument: [a, b, c]

S       Sum; compute 2s := a + b + c.
 ÷      Divide; yield [2s ÷ a, 2s ÷ b, 2s ÷ c].
  _2    Subtract 2; yield [2s ÷ a - 2, 2s ÷ b - 2, 2s ÷ c - 2].
    P   Product; yield (2s ÷ a - 2)(2s ÷ b - 2)(2s ÷ c - 2).
     İ  Invert; yield 1 ÷ (2s ÷ a - 2)(2s ÷ b - 2)(2s ÷ c - 2).

```
> 13 votes

# Answer
# JavaScript, 38 bytes

This is a (curried) lambda:

```
a=>b=>c=>a*b*c/(b+c-a)/(a+c-b)/(a+b-c)

```

(If you assign it to a variable `f` you'd need to call it like `f(3)(4)(5)`)
> 11 votes

# Answer
# 05AB1E, ~~11~~ 7 bytes

05AB1E uses CP-1252 encoding.

```
O¹·-¹/P

```

Try it online!

**Explanation**

```
O         # sum input
 ¹        # push input again
  ·       # multiply by 2
   -      # subtract from sum
    ¹/    # divide by input
      P   # product

```
> 9 votes

# Answer
# MATL, ~~8~~ 7 bytes

```
tsGE-/p

```

Try it online!

### Explanation

Let's use input `[3 4 5]` as an example

```
t    % Take input implicitly. Duplicate
     % STACK: [3 4 5], [3 4 5]
s    % Sum of array
     % STACK: [3 4 5], 12
G    % Push input again
     % STACK: [3 4 5], 12, [3 4 5]
E    % Multiply by 2, element-wise
     % STACK: [3 4 5], 12, [6 8 10]
-    % Subtract, element-wise
     % STACK: [3 4 5], [6 4 2]
/    % Divide, element-wise
     % STACK: [0.5 1 2.5]
p    % Product of array. Implicitly display
     % STACK: 1.25

```
> 8 votes

# Answer
## R, 34 29 bytes

```
x=scan();prod(x/(sum(x)-2*x))

```

Reads input from stdin and store as the R-vector `x`. Then make use of R's vectorization to form the denominator.
> 8 votes

# Answer
# Haskell, 36 bytes

This defines the function `#` which takes three arguments.

```
(a#b)c=a*b*c/(b+c-a)/(a+c-b)/(a+b-c)

```

You have to call it as follows: `(3#4)5`

A little bit longer but perhaps more golfable:

```
p=product
f v=p v/p((sum v-).(2*)<$>v)

```
> 7 votes

# Answer
# MATLAB, ~~64 38~~ 25 bytes

This is an anyonmous function that implements the formula as provided:

```
@(v)prod(v./(sum(v)-2*v))

```

It assumes the input to be a list of three values e.g. `[3,4,5]`. This example is used in following explanation:

```
             sum(v)        = 3+4+5 = 12
             sum(v)-2*v    = 12 - 2*[3,4,5] = 12 - [6,8,10] = [6,4,2]
         v./(sum(v)-2*v))  = [3,4,5] ./ [6,4,2] = [0.5,1,2.5]
    prod(v./(sum(v)-2*v))  = 0.5 * 1 * 2.5 = 1.25

```
> 6 votes

# Answer
## Mathematica, 20 bytes

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

```

Takes input as a list of three values, which is referred to as `#` inside the function. `Tr@` is the shortest way to sum a list (to get `2s`) and `1##&@@(...)` multiplies the three factors `i/(2s-2i)` for `i` in `a, b, c`.

If the inputs are integers or rational numbers, you'll get an exact result.
> 6 votes

# Answer
# Python 3, 42 bytes

```
lambda a,b,c:a*b*c/(b+c-a)/(a+c-b)/(a+b-c)

```

Try It Online!
> 6 votes

# Answer
# Minecraft 1.8, 1607 bytes + 85 blocks = 1692 blytes

**Warning: *Not* golfed. Golfed will take up to 1*/*3 less blytes.**

Here is a commented screenshot:

* The inputs are `a`, `b`, and `c`,and the output is `fin`
* `fin`, and all other variables in Minecraft are integers, so the standard Minecraft accuracy is 0 decimal points
* The green border: the command blocks on the left will activate after the ones on the right, which are just variable initializations.
* The lever (grey-brown rectangle in the down right) is the contraption trigger
* **It takes up so much because of the way Minecraft handles variables**. A very simplified overview:

+ `/scoreboard objectives add name dummy` creates a new variable named "`name`"
    + `/scoreboard players set @p name number` sets the variable `name` to `number`. Number must be a real number, not a variable.
    + `/scoreboard players operation @p name += @p name2` increments `name` by `name2`. `name2` must be a variable, not a number.

    - `-=`, `/=`, `*=`, `=` and more can be used instead `+=` to decrement, multiply, divide, etc.
* I'm not going to post all the 43 commands here. It would help golfing this, but would also help drive me crazy copypasting
* *If 1.9 command blocks would be used, the solution would (at least) use 42 blocks less. If one-letter variables would be used, almost 200 bytes would be saved.*
> 6 votes

# Answer
# OCaml, 51 bytes

```
fun a b c->a*.b*.c/.(b+.c-.a)/.(a+.c-.b)/.(a+.b-.c)

```

Yay, separate operators for floats...
> 5 votes

# Answer
# Actually, ~~10~~ 8 bytes

This answer is based on Dennis's excellent Jelly answer. Golfing suggestions welcome! Try it online!

```
;Σ♀/♂¬πì

```

**Ungolfing**

```
     Implicit input [a, b, c].
;    Duplicate [a, b, c].
Σ    sum() to get twice the semiperimeter, 2*s.
♀/   Vectorized divide 2*s by [a, b, c] to get [2*s/a, 2*s/b, 2*s/c].
♂¬   Vectorized subtract 2 to get [2*s/a-2, 2*s/b-2, 2*s/c-2].
π    Get the product of the above to get 8*(s/a-1)*(s/b-1)*(s/c-1).
     This is the same as 8(s-a)(s-b)(s-c)/abc.
ì    Invert to get the aspect ratio, abc/8(s-a)(s-b)(s-c).
     Implicit return.

```
> 5 votes

# Answer
# Wonder, 48 bytes

```
@@@prod[#0#1#2/1- +#1#0#2/1- +#2#0#1/1- +#2#1#0]

```

RIP

Usage:

```
(((@@@prod[#0#1#2/1* * - +#1#0#2- +#2#0#1- +#2#1#0])3)4)5

```

# Explanation

Function calls are costly in Wonder when compared to infix operators in other languages. Because of this, I contained all the terms in an array and got the product of the result instead of multiplying every single term. The code would be equivalent to something like:

```
(a,b,c)=>product([a,b,c,1/(b+c-a),1/(a+c-b),1/(a+b-c)])

```
> 5 votes

# Answer
# Java, 38 bytes

```
(a,b,c)->a*b*c/(b+c-a)/(a-b+c)/(a+b-c)

```

## Testing and ungolfed

```
public class Pcg101234 {
  interface F {
    double f(double a, double b, double c);
  }
  public static void main(String[] args) {
    F f = (a,b,c)->a*b*c/(b+c-a)/(a-b+c)/(a+b-c);

    System.out.println(f.f(1,1,1));
    System.out.println(f.f(3,4,5));
    System.out.println(f.f(42,42,3.14));
    System.out.println(f.f(14,6,12));
    System.out.println(f.f(6,12,14));
    System.out.println(f.f(0.5,0.6,0.7));
  }
}

```

Test it!

## Output

```
1.0
1.25
6.947606226693615
1.575
1.575
1.09375

```
> 4 votes

# Answer
## Jellyfish, ~~17~~ 16 bytes

*Thanks to Zgarb for saving 1 byte.*

```
p%/*-)/+i
    2%

```

Try it online!

### Explanation

This is based on the same reciprocal formula as Dennis's answer.

In more traditional functional notation, the above program reads as follows:

```
print(
  1 / fold(
    multiply,
    fold(add, i) / i - 2
  )
)

```

Where `i` is the input list. Note that `fold(multiply, ...)` just computes the product and `fold(add, ...)` the sum, so we can further simplify this to:

```
print(1 / product(sum(i) / i - 2))

```

The `sum(i) / i` is implemented via the hook `)/+` which defines a new unary function to do both steps at once.
> 4 votes

# Answer
# Dyalog APL, ~~10~~ 9 bytes

```
×/⊢÷+/-+⍨

```

This is an anonymous function train (an atop of a fork of a fork of a fork), meaning that every sub-function is applied to the argument, inside the following structure:

```
 ┌─┴─┐
×/ ┌─┼───┐
   ⊢ ÷ ┌─┼──┐
      +/ - +⍨

```

TryAPL online!

`×/` the product of

the arguments

`÷` divided by

`+/` the sum of the arguments

`-` minus

`+⍨` the arguments doubled (lit. added to themselves)

Mathematical background.

ngn shaved a byte.
> 4 votes

# Answer
# 2sable, 6 bytes

A port of Dennis' Jelly answer.

```
Os/ÍPz

```

Uses the **CP-1252** encoding. Try it online!
> 3 votes

# Answer
# dc, 49 bytes

```
5k?dsa?dsb?dsc++2/sslalblc**lsla-lslb-lslc-8***/p

```

A direct implementation of the formula given. Prompts for the three inputs upon invocation on three separate lines and outputs a floating-point value with 5 digits after the decimal point to the next line.

## Explanation

```
5k                                                # Set the output precision to 5 digits after the decimal
  ?dsa                                            # Prompt for first input value on first line, duplicate it, and then store it in register `a`
      ?dsb                                        # Prompt for second input, duplicate it, and store it in register `b`
          ?dsc                                    # Prompt for third input, duplicate it, and store it in register `c`
              ++2/ss                              # Sum up the 3 values on the main stack, then divide sum by 2 and store the result in register `s`
                    lalblc**                      # Copy all three values from registers `a`,`b`,`c` onto the main stack, find their product, and push result to top of main stack
                            lsla-                 # Copy value from register `s` onto main stack, subtract register `a`'s value from it, and push result to main stack
                                 lslb-            # Copy value from register `s` onto main stack, subtract register `b`'s value from it, and push result to main stack
                                      lslc-       # Copy value from register `s` onto main stack, subtract register `c`'s value from it, and push result to main stack
                                           8***   # Find the product of the top three values and 8 and then push the result to main stack
                                               /p # Divide the second to top value (a*b*c) by the top of stack value (8*(s-a)*(s-b)*(s-c)), push the result to the main stack, and then output the result to STDOUT

```
> 3 votes

# Answer
# TI-Basic, 11 bytes

Input should be in the form of a list, like `{A B C}`.

```
prod(Ans)/prod(sum(Ans)-2Ans

```

Maybe this visual will help (remember that `2s = a+b+c`):

```
      abc                    abc                   abc                prod(Ans)
---------------- = --------------------- = ------------------- = -------------------
8(s-a)(s-b)(s-c)   (2s-2a)(2s-2b)(2s-2c)   (a+b+c)(1-2{a,b,c})   prod(sum(Ans)-2Ans)

```
> 3 votes

# Answer
# Perl 6, 44 bytes

```
->\a,\b,\c{a*b*c/(b+c -a)/(a+c -b)/(a+b -c)}

```
> 2 votes

# Answer
# Python, 55 bytes

```
def f(x,y,z):s=x+y+z;return 1/((s/x-2)*(s/y-2)*(s/z-2))

```

Credit to Dennis. I just ported. In Python, a much-neglected language.
> 2 votes

# Answer
# Forth, 83 bytes

Assumes the floating point parameters start on the floating point stack. Leaves the result on the floating point stack. Using the stack for params/returning is the standard for Forth.

```
: p 3 fpick ;
: T p p p ;
: f 0 s>f T f- f+ f- T f+ f- f* T f- f- f* 1/f f* f* f* ;

```

**Try it online** \- *contains all test cases*

Uses the formula `a*b*c * 1/ ( -(a+b-c) * -(b+c-a) * (a+c-b) )`. Pretty much the entire program is using only the floating point stack. The exception is the `3` in `3 fpick`. This program requires an interpreter that supports `fpick` (Ideone works, repl.it doesn't).

**Explanation:** *slightly less golfed*

```
\ 3 fpick takes the 3rd element (0-indexed) and pushes a copy
\ Used to copy parameters on the stack over another number 'x' ( a b c x -> a b c x a b c )
: f3p 3 fpick 3 fpick 3 fpick ;

: f                     \ define a function f
0 s>f f3p f- f+ f-      \ push a zero, copy params, compute 0-(a+b-c)
                        \ the zero allows me to copy (I need an 'x' to jump over)
f3p f+ f- f*            \ copy params and compute -(b+c-a), multiply by previous result
                        \ the negatives miraculously cancel
f3p f- f- f*            \ copy and compute (a+c-b), multiply by previous result
1/f f* f* f* ;          \ take the reciprocal and multiply by a*b*c
                        \ the result is left on the floating point stack

```
> 2 votes

# Answer
# ised: 19 bytes

```
@*$1/@*{@+$1-2.*$1}

```

Call it as `ised --l 'inputfile.txt' '@*$1/@*{@+$1-2.*$1}'` where `inputfile.txt` can be a file with space separated array, or `-` to receive from pipe/stdin.

Unicode version (same bytecount but 3 chars less):

```
Π$1/Π{Σ$1-2.*$1}

```

Unfortunately, `ised` wastes a lot of chars for its input argument syntax.
> 2 votes

# Answer
# vba, 76

```
Function r(a,b,c)
s=(a+b+c)/2:r=(a*b*c)/(8*(s-a)*(s-b)*(s-c))
End Function

```

Call with

> ?r(3,4,5)

or in excel with

> =r(5,12,13)
> 2 votes

# Answer
## C#, 82 bytes

```
void ar(double a,double b,double c)=>Console.Write(a*b*c/(b+c-a)/(a+c-b)/(a+b-c));

```

Usage:

```
ar(42, 42, 3.14);

```
> 2 votes

# Answer
# Pyke, 12 bytes

```
1QFQsR/tt)B/

```

Try it here!

Well, BlueEyedBeast, you had your chance. I used a good algorithm here.
> 2 votes

# Answer
# k, 19 bytes

```
{(*/x)%8*/-x-+/x%2}

```

Evaluates right to left - Divide the list x by 2, sum the result and subtract it from original x. Neg the answer and get the product of the result and 8. The result is the denominator, the numerator is the product of the list.
> 2 votes

# Answer
# Lua, 45 bytes

```
a,b,c=...print(a*b*c/(b+c-a)/(a+c-b)/(a+b-c))

```

Heavily based on the JavaScript answer.
> 1 votes

# Answer
## Common Lisp, 70 bytes

```
(lambda(a b c &aux(s(/(+ a b c)2)))(/(* a b c)8(- s a)(- s b)(- s c)))

```
> 1 votes

# Answer
# Math++, ~~51~~ 41 bytes

```
?>a
?>b
?>c
a*b*c/(b+c-a)/(a-b+c)/(a+b-c)

```
> 1 votes

# Answer
# 05AB1E, 6 bytes

```
O¹/ÍPz

```

Try it online!

Floating point inaccuracies.

Ported.

Looks an awful lot like this answer. Gawd.
> 1 votes

# Answer
# CJam, ~~21~~ 15 bytes

```
l~_:+\f/2f-:*W#

```

`[.5 .6 .7]`

Dennis's post that I ported.

*Thanks to 8478 (Martin Ender) for saving me 6 bytes.*
> 1 votes

# Answer
# Minkolang v0.15, 34 bytes

```
$n3$D++2$:3[d5i-g-$r]x**8*r**r$:N.

```

Try it online!

### Explanation

```
$n                                     takes all numbers from input
                                       STACK: [a,b,c]
  3$D                                  duplicates stack 3 times
                                       STACK: [a,b,c,a,b,c,a,b,c]
     ++                                adds top two numbers in stack
                                       STACK: [a,b,c,a,b,c,a+b+c]
       2$:                             divides it by 2 (float division)
                                       STACK: [a,b,c,a,b,c,(a+b+c)/2]
                                        or can be restated as
                                       STACK: [a,b,c,a,b,c,s]
          3[        ]                  starts a for-loop (for 3 iterations)
            d                          duplicates top of stack
                                       STACK: [a,b,c,a,b,c,s,s]
             5i-g                      pushes 5 minus the index (0-indexed) and gets the
                                       value in the stack at that index
                                       STACK: [a,b,c,a,b,s,s,c]
                 -                     subtracts them
                                       STACK: [a,b,c,a,b,s,s-c]
                  $r                   swaps the top 2 stack values
                                       STACK: [a,b,c,a,b,s-c,s]
                                       Does this two more times
                                       STACK: [a,b,c,s-c,s-b,s-a,s]
                    x                  removes top of stack
                                       STACK: [a,b,c,s-c,s-b,s-a]
                     **8*              multiplies the top 3 values with 8 and each other
                                       STACK: [a,b,c,8(s-c)(s-b)(s-a)]
                         r             reverses stack
                                       STACK: [8(s-c)(s-b)(s-a),a,b,c]
                          **           multiplies top 3 values with each other
                                       STACK: [8(s-c)(s-b)(s-a),abc]
                            r$:        reverse stack and divide the values
                                       STACK: [abc/8(s-c)(s-b)(s-a)]
                               N.      outputs value as number and exit program

```
> 1 votes

# Answer
# PHP, ~~109~~ 97 bytes

```
<?$n=explode(',',$argv[1]);echo($a=$n[0])*($b=$n[1])*($c=$n[2])/($a+$b-$c)/($a+$c-$b)/($b+$c-$a);

```

Output:

```
php triangle-aspect.php "1,1,1"
1
php triangle-aspect.php "3,4,5"
1.25
php triangle-aspect.php "42,42,3.14"
6.9476062266936
php triangle-aspect.php "14,6,12"
1.575
php triangle-aspect.php "6,12,14"
1.575
php triangle-aspect.php ".5,.6,.7"
1.09375

```
> 1 votes

# Answer
## QBIC, 35 bytes

```
:::?(a*b*c)/(a+b-c)/(a+c-b)/(b+c-a)

```

Wrapped the shortest algorithm in a QBIC boilerplate. `:::` gets three command line parameters and makes the ints `a, b, c` out of them.
> 1 votes

# Answer
## Lithp, 71 bytes

```
#A,B,C::((/ (* A B C) (+ B C (- 0 A)) (+ A C (- 0 B)) (+ A B (- 0 C))))

```

At least it's not the longest solution. But it's not all that short either.

In Lithp, arithmatic functions such as `/ (divide)`, `* (multiply)`, `+ (plus)` and `- (subtract)` take multiple arguments, and continually applies the operation to each successive argument. Therefore we only need one `divide` call total, one `multiply` and several discrete `add` and `subtract` operations. This saves quite a few bytes.

Automatic arithmatic like `-A` does not work, so instead we subtract `A` from 0 to make it negative and save on more complex operations.

Usage and ungolfed:

```
(
    (import "lists")
    (def f #A,B,C::(
        (/ (* A B C)
           (+ B C (- 0 A))
           (+ A C (- 0 B))
           (+ A B (- 0 C))
        )
    ))
    (print (f 1   1   1))    % Output: 1
    (print (f 3   4   5))    % Output: 1.25
    (print (f 42  42  3.14)) % Output: 6.9476062266936145
    (print (f 14  6   12))   % Output: 1.575
    (print (f 6   12  14))   % Output: 1.575
    (print (f 0.5 0.6 0.7))  % Output: 1.09375
)

```
> 1 votes

# Answer
# , 10 bytes

```
*/ .%+/-+:

```

Try it online!

## Explanation

```
*/ .%+/-+:  Input: array [a b c]
        +:  Double, gets [2a, 2b, 2c]
     +/     Reduce by addition, gets the sum a+b+c
       -    Subtract, gets [-a+b+c, a-b+c, a+b-c]
   .        Inner product between [a b c] and [-a+b+c, a-b+c, a+b-c]
    %         Divide elementwise
*/            Reduce by multiplication

```
> 1 votes

# Answer
## Clojure, 53 bytes

```
#(apply /(apply * %)8(for[i %](-(*(apply + %)0.5)i)))

```

Takes numbers as a list or a vector and applies them to various basic mathematical operations. Many bytes from repeated `apply`.
> 1 votes

# Answer
## Racket 57 bytes

```
(define s(/(+ a b c)2))(/(* a b c)8(- s a)(- s b)(- s c))

```

Ungolfed:

```
(define (f a b c)
  (define s (/ (+ a b c) 2))
  (/ (* a b c)
     8
     (- s a)
     (- s b)
     (- s c)))

```

Testing:

```
(f 1 1 1)
(f 3 4 5)
(f 42 42 3.14)
(f 14 6 12)
(f 6 12 14)
(f 0.5 0.6 0.7)

```

Output:

```
1
1 1/4
6.947606226693614
1 23/40
1 23/40
1.0937499999999993

```
> 0 votes

---
Tags: code-golf, math, arithmetic, geometry
---


title: Find the Centroid of a Polygon

text:
# Question
Title: Find the Centroid of a Polygon
From Wikipedia:

> The centroid of a non-self-intersecting closed polygon defined by *n* vertices (*x0,y0*), (*x1,y1*), ..., (*xn−1,yn−1*) is the point (*Cx, Cy*), where
>
> and where *A* is the polygon's signed area,
>
> In these formulas, the vertices are assumed to be numbered in order of their occurrence along the polygon's perimeter. Furthermore, the vertex ( *xn, yn* ) is assumed to be the same as ( *x0, y0* ), meaning *i + 1* on the last case must loop around to *i = 0*. Note that if the points are numbered in clockwise order the area *A*, computed as above, will have a negative sign; but the centroid coordinates will be correct even in this case.

---

* Given a list of vertices in order (either clockwise, or counter-clockwise), find the centroid of the non-self-intersecting closed polygon represented by the vertices.
    + If it helps, you may assume input to be only CW, or only CCW. Say so in your answer if you require this.
* The coordinates are not required to be integers, and may contain negative numbers.
* Input will always be valid and contain at least three vertices.
* Inputs only need to be handled that fit in your language's native floating point data type.
* You may assume that input numbers will always contain a decimal point.
* You may assume that input integers end in `.` or `.0`.
* You may use complex numbers for input.
* Output should be accurate to the nearest thousandth.

### Examples

```
[(0.,0.), (1.,0.), (1.,1.), (0.,1.)]        -> (0.5, 0.5)
[(-15.21,0.8), (10.1,-0.3), (-0.07,23.55)]  -> -1.727 8.017
[(-39.00,-55.94), (-56.08,-4.73), (-72.64,12.12), (-31.04,53.58), (-30.36,28.29), (17.96,59.17), (0.00,0.00), (10.00,0.00), (20.00,0.00), (148.63,114.32), (8.06,-41.04), (-41.25,34.43)]   -> 5.80104769975, 15.0673812762

```

Too see each polygon on a coordinate plane, paste the coordinates without the square brackets in the "Edit" menu of this page.

I confirmed my results using this Polygon Centroid Point Calculator, which is awful. I couldn't find one that you can input all vertices at once, or that didn't try to erase your `-` sign when you type it first. I'll post my Python solution for your use after people have had a chance to answer.

# Answer
> 16 votes
# Jelly, ~~25~~ ~~24~~ ~~22~~ ~~21~~ 18 bytes

```
S×3÷@×"
ṙ-żµÆḊçS€S

```

Applies the formula shown in the problem.

Saved 3 bytes with help from @Jonathan Allan.

Try it online! or Verify all test cases.

## Explanation

```
S×3÷@×"  Helper link. Input: determinants on LHS, sum of pairs on RHS
S        Sum the determinants
 ×3      Multiply by 3
     ×"  Vectorized multiply between determinants and sums
   ÷@    Divide that by the determinant sum multipled by 3 and return

ṙ-żµÆḊçS€S  Main link. Input: 2d list of points
ṙ-          Rotate the list of points by 1 to the right
  ż         Interleave those with the original points
            This creates all overlapping slices of length 2
   µ        Start new monadic chain
    ÆḊ      Get the determinant of each slice
       S€   Get the sum of each slice (sum of pairs of points)
      ç     Call the helper link
         S  Sum and return

```

# Answer
> 17 votes
# Mathematica, 23 bytes

```
RegionCentroid@*Polygon

```

~~Take **THAT**, Jelly!~~

Edit: One does not simply beat Jelly...

# Explanation

```
Polygon

```

Generate a polygon with vertices at the points specified.

```
RegionCentroid

```

Find the centroid of the polygon.

# Answer
> 4 votes
# J, 29 bytes

```
2+/@(+/\(*%3*1#.])-/ .*\)],{.

```

Applies the formula shown in the problem.

## Usage

```
   f =: 2+/@(+/\(*%3*1#.])-/ .*\)],{.
   f 0 0 , 1 0 , 1 1 ,: 0 1
0.5 0.5
   f _15.21 0.8 , 10.1 _0.3 ,: _0.07 23.55
_1.72667 8.01667
   f _39 _55.94 , _56.08 _4.73 , _72.64 12.12 , _31.04 53.58 , _30.36 28.29 , 17.96 59.17 , 0 0 , 10 0 , 20 0 , 148.63 114.32 , 8.06 _41.04 ,: _41.25 34.43
5.80105 15.0674

```

## Explanation

```
2+/@(+/\(*%3*1#.])-/ .*\)],{.  Input: 2d array of points P [[x1 y1] [x2 y2] ...]
                           {.  Head of P
                         ]     Get P
                          ,    Join, makes the end cycle back to the front
2                              The constant 2
2                      \       For each pair of points
                  -/ .*        Take the determinant
2    +/\                       Sum each pair of points
         *                     Multiply the sum of each pair by its determinant
          %                    Divide each by
             1#.]              The sum of the determinants
           3*                  Multiplied by 3
 +/@                           Sum and return

```

# Answer
> 4 votes
## Maxima, ~~124 118 116 112~~ 106 byte

```
f(l):=(l:endcons(l[1],l),l:sum([3,l[i-1]+l[i]]*determinant(matrix(l[i-1],l[i])),i,2,length(l)),l[2]/l[1]);

```

I'm not experienced with Maxima, so any hints are welcome.

Usage:

```
(%i6) f([[-15.21,0.8], [10.1,-0.3], [-0.07,23.55]]);
(%o6)              [- 1.726666666666668, 8.016666666666668]

```

# Answer
> 3 votes
## Racket 420 bytes

```
(let*((lr list-ref)(getx(lambda(i)(lr(lr l i)0)))(gety(lambda(i)(lr(lr l i)1)))(n(length l))(j(λ(i)(if(= i(sub1 n))0(add1 i))))
(A(/(for/sum((i n))(-(*(getx i)(gety(j i)))(*(getx(j i))(gety i))))2))
(cx(/(for/sum((i n))(*(+(getx i)(getx(j i)))(-(*(getx i)(gety(j i)))(*(getx(j i))(gety i)))))(* 6 A)))
(cy(/(for/sum((i n))(*(+(gety i)(gety(j i)))(-(*(getx i)(gety(j i)))(*(getx(j i))(gety i)))))(* 6 A))))
(list cx cy))

```

Ungolfed:

```
(define(f l)
  (let* ((lr list-ref)
         (getx (lambda(i)(lr (lr l i)0)))
         (gety (lambda(i)(lr (lr l i)1)))
         (n (length l))
         (j (lambda(i) (if (= i (sub1 n)) 0 (add1 i))))
         (A (/(for/sum ((i n))
                (-(* (getx i) (gety (j i)))
                  (* (getx (j i)) (gety i))))
              2))
         (cx (/(for/sum ((i n))
                 (*(+(getx i)(getx (j i)))
                   (-(*(getx i)(gety (j i)))
                     (*(getx (j i))(gety i)))))
               (* 6 A)))
         (cy (/(for/sum ((i n))
                 (*(+(gety i)(gety (j i)))
                   (-(*(getx i)(gety (j i)))
                     (*(getx (j i))(gety i)))))
               (* 6 A))))
    (list cx cy)))

```

Testing:

```
(f '[(-15.21 0.8)  (10.1 -0.3)  (-0.07 23.55)] )
(f '[(-39.00 -55.94)  (-56.08 -4.73)  (-72.64 12.12)  (-31.04 53.58)
     (-30.36 28.29)  (17.96 59.17)  (0.00 0.00)  (10.00 0.00)
     (20.00 0.00) (148.63 114.32)  (8.06 -41.04)  (-41.25 34.43)])

```

Output:

```
'(-1.7266666666666677 8.01666666666667)
'(5.8010476997538465 15.067381276150996)

```

# Answer
> 3 votes
# R, 129 127 bytes

```
function(l){s=sapply;x=s(l,`[`,1);y=s(l,`[`,2);X=c(x[-1],x[1]);Y=c(y[-1],y[1]);p=x*Y-X*y;c(sum((x+X)*p),sum((y+Y)*p))/sum(p)/3}

```

Unnamed function that take an R-list of tuples as input. The named equivalent can be called using e.g.:

```
f(list(c(-15.21,0.8),c(10.1,-0.3),c(-0.07,23.55)))

```

**Ungolfed and explained**

```
f=function(l){s=sapply;                           # Alias for sapply
              x=s(l,`[`,1);                       # Split list of tuples into vector of first elements
              y=s(l,`[`,2);                       # =||= but for second element
              X=c(x[-1],x[1]);                    # Generate a vector for x(i+1)
              Y=c(y[-1],y[1]);                    # Generate a vector for y(i+1)
              p=x*Y-X*y;                          # Calculate the outer product used in both A, Cx and Cy
              c(sum((x+X)*p),sum((y+Y)*p))/sum(p)/3    # See post for explanation
}

```

The final step (`c(sum((x+X)*p),sum((y+Y)*p))/sum(p)*2/6`) is a vectorized way of calculating both `Cx` and `Cy`. The sum in the formulas for `Cx` and `Cy` are stored in a vector and consequently divided by the "sum in `A`" `*2/6`. E.g.:

```
(SUMinCx, SUMinCy) / SUMinA / 3

```

, and then implicitly printed.

Try it on R-fiddle

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

Straight implementation of the formula

```
l=>[...l,l[0]].map(([x,y],i)=>(i?(a+=w=t*y-x*u,X+=(t+x)*w,Y+=(u+y)*w):X=Y=a=0,t=x,u=y))&&[X/3/a,Y/3/a]

```

**Test**

```
f=
l=>[...l,l[0]].map(([x,y],i)=>(i?(a+=w=t*y-x*u,X+=(t+x)*w,Y+=(u+y)*w):X=Y=a=0,t=x,u=y))&&[X/3/a,Y/3/a]

function go()
{
  var c=[],cx,cy;
  // build coordinates array
  I.value.match(/-?[\d.]+/g).map((v,i)=>i&1?t[1]=+v:c.push(t=[+v]));
  console.log(c+''),
  [cx,cy]=f(c);
  O.textContent='CX:'+cx+' CY:'+cy;
  // try to display the polygon
  var mx=Math.max(...c.map(v=>v[0])),
    nx=Math.min(...c.map(v=>v[0])),
    my=Math.max(...c.map(v=>v[1])),
    ny=Math.min(...c.map(v=>v[1])),
    dx=mx-nx, dy=my-ny,
    ctx=C.getContext("2d"),
    cw=C.width, ch=C.height,
    fx=(mx-nx)/cw, fy=(my-ny)/ch, fs=Math.max(fx,fy)
  C.width=cw
  ctx.setTransform(1,0,0,1,0,0);
  ctx.beginPath();
  c.forEach(([x,y],i)=>ctx.lineTo((x-nx)/fs,(y-ny)/fs));
  ctx.closePath();
  ctx.stroke();
  ctx.fillStyle='#ff0000';
  ctx.fillRect((cx-nx)/fs-2,(cy-ny)/fs-2,5,5);
}
go()
```

```
#I { width:90% }
#C { width:90%; height:200px;}
```

```
<input id=I value='[[-15.21,0.8], [10.1,-0.3], [-0.07,23.55]]'>
<button onclick='go()'>GO</button>
<pre id=O></pre>
<canvas id=C></canvas>
```

# Answer
> 2 votes
# Python, ~~156~~ 127 bytes

```
def f(p):n=len(p);p=p+p[:1];i=s=0;exec'd=(p[i].conjugate()*p[i+1]).imag;s+=d;p[i]=(p[i]+p[i+1])*d;i+=1;'*n;print sum(p[:n])/s/3

```

Ungolfed:

```
def f(points):
  n = len(points)
  points = points + [points[0]]
  determinantSum = 0
  for i in range(n):
    determinant = (points[i].conjugate() * points[i+1]).imag
    determinantSum += determinant
    points[i] = (points[i] + points[i+1]) * determinant
  print sum(points[:n]) / determinantSum / 3

```

Ideone it.

This takes each pair of points `[x, y]` as a complex number `x + y*j`, and outputs the resulting centroid as a complex number in the same format.

For the pair of points `[a, b]` and `[c, d]`, the value `a*d - b*c` which is needed for each pair of points can be computed from the determinant of the matrix

```
| a b |
| c d |

```

Using complex arithmetic, the complex values `a + b*j` and `c + d*j` can be used as

```
conjugate(a + b*j) * (c + d*j)
(a - b*j) * (c + d*j)
(a*c + b*d) + (a*d - b*c)*j

```

Notice that the imaginary part is equivalent to the determinant. Also, using complex values allows the points to be easily summed component-wise in the other operations.

# Answer
> 2 votes
# R + sp (46 bytes)

Assumes `sp` package is installed (https://cran.r-project.org/web/packages/sp/)

Takes a list of vertices, (for example `list(c(0.,0.), c(1.,0.), c(1.,1.), c(0.,1.))`)

Takes advantage of the fact that the "labpt" of a Polygon is the centroid.

```
function(l)sp::Polygon(do.call(rbind,l))@labpt

```

# Answer
> 1 votes
# Actually, ~~45~~ ~~40~~ 39 bytes

This uses an algorithm similar to miles' Jelly answer. There is a shorter way to calculate determinants using a dot product, but there's currently a bug with Actually's dot product where it won't work with lists of floats. Golfing suggestions welcome. Try it online!

```
;\Z♂#;`i¥`M@`i│N@F*)F@N*-`M;Σ3*)♀*┬♂Σ♀/

```

**Ungolfing**

```
         Implicit input pts.
;\       Duplicate pts, rotate right.
Z        Zip rot_pts and pts together.
♂#       Convert the iterables inside the zip to lists
         (currently necessary due to a bug with duplicate)
;        Duplicate the zip.
`...`M   Get the sum each pair of points in the zip.
  i        Flatten the pair to the stack.
  ¥        Pairwise add the two coordinate vectors.
@        Swap with the other zip.
`...`M   Get the determinants of the zip.
  i│       Flatten to stack and duplicate entire stack.
           Stack: [a,b], [c,d], [a,b], [c,d]
  N@F*)    Push b*c and move it to BOS.
  F@N*     Push a*d.
  -        Get a*d-b*c.
;Σ3*)    Push 3 * sum(determinants) and move it to BOS.
♀*       Vector multiply the determinants and the sums.
┬        Transpose the coordinate pairs in the vector.
♂Σ       Sum the x's, then the y's.
♀/       Divide the x and y of this last coordinate pair by 3*sum(determinants).
         Implicit return.

```

**A shorter, non-competitive version**

This is another 24-byte version that uses complex numbers. It's non-competitive because it relies on bug fixes that postdate this challenge. Try it online!

```
;\│¥)Z`iá*╫@X`M;Σ3*)♀*Σ/

```

**Ungolfing**

```
         Implicit input a list of complex numbers, pts.
;\       Duplicate pts, rotate right.
│        Duplicate stack. Stack: rot_pts, pts, rot_pts, pts.
¥)       Pairwise sum the two lists of points together and rotate to BOS.
Z        Zip rot_pts and pts together.
`...`M   Map the following function over the zipped points to get our determinants.
  i        Flatten the list of [a+b*i, c+d*i].
  á        Push the complex conjugate of a+bi, i.e. a-b*i.
  *        Multiply a-b*i by c+d*i, getting (a*c+b*d)+(a*d-b*c)*i.
           Our determinant is the imaginary part of this result.
  ╫@X      Push Re(z), Im(z) to the stack, and immediately discard Re(z).
           This map returns a list of these determinants.
;        Duplicate list_determinants.
Σ3*)     Push 3 * sum(list_determinants) and rotate that to BOS.
♀*Σ      Pairwise multiply the sums of pairs of points and the determinants and sum.
/        Divide that sum by 3*sum(list_determinants).
         Implicit return.

```

# Answer
> 1 votes
# Python 2, 153 bytes

Uses no complex numbers.

```
P=input()
A=x=y=0;n=len(P)
for i in range(n):m=-~i%n;a=P[i][0];b=P[i][1];c=P[m][0];d=P[m][1];t=a*d-b*c;A+=t;x+=t*(a+c);y+=t*(b+d)
k=1/(3*A);print x*k,y*k

```

**Try it online**

### Ungolfed:

```
def centroid(P):
    A=x=y=0
    n=len(P)
    for i in range(n):
        m=-~i%n
        x0=P[i][0];y0=P[i][1]
        x1=P[m][0];y1=P[m][1]
        t = x0*y1 - y0*x1
        A += t/2.
        x += t * (x0 + x1)
        y += t * (y0 + y1)
    k = 1/(6*A)
    x *= k
    y *= k
    return x,y

```

# Answer
> 1 votes
# C++14, 241 bytes

```
struct P{float x;float y;};
#define S(N,T)auto N(P){return 0;}auto N(P a,P b,auto...V){return(T)*(a.x*b.y-b.x*a.y)+N(b,V...);}
S(A,1)S(X,a.x+b.x)S(Y,a.y+b.y)auto f(auto q,auto...p){auto a=A(q,p...,q)*3;return P{X(q,p...,q)/a,Y(q,p...,q)/a};}

```

Output is the helper struct `P`,

Ungolfed:

```
 //helper struct
struct P{float x;float y;};

//Area, Cx and Cy are quite similar
#define S(N,T)\  //N is the function name, T is the term in the sum
auto N(P){return 0;} \   //end of recursion for only 1 element
auto N(P a,P b,auto...V){ \ //extract the first two elements
  return (T)*(a.x*b.y-b.x*a.y) //compute with a and b
         + N(b,V...); \        //recursion without first element
}

//instantiate the 3 formulas
S(A,1)
S(X,a.x+b.x)
S(Y,a.y+b.y)

auto f(auto q,auto...p){
  auto a=A(q,p...,q)*3; //q,p...,q appends the first element to the end
  return P{X(q,p...,q)/a,Y(q,p...,q)/a};
}

```

Usage:

```
f(P{0.,0.}, P{1.,0.}, P{1.,1.}, P{0.,1.})
f(P{-15.21,0.8}, P{10.1,-0.3}, P{-0.07,23.55})

```

# Answer
> 1 votes
## Clojure, ~~177~~ ~~156~~ 143 bytes

Update: Instead of a callback I'm using `[a b c d 1]` as a function and the argument is just a list of indexes to this vector. `1` is used as a sentinel value when calculating `A`.

Update 2: Not precalculating `A` at `let`, using `(rest(cycle %))` to get input vectors offset by one.

```
#(let[F(fn[I](apply +(map(fn[[a b][c d]](*(apply +(map[a b c d 1]I))(-(* a d)(* c b))))%(rest(cycle %)))))](for[i[[0 2][1 3]]](/(F i)(F[4])3)))

```

Original version:

```
#(let[F(fn[L](apply +(map(fn[[a b][c d]](*(L[a b c d])(-(* a d)(* c b))))%(conj(subvec % 1)(% 0)))))A(*(F(fn[& l]1))3)](map F[(fn[v](/(+(v 0)(v 2))A))(fn[v](/(+(v 1)(v 3))A))]))

```

At less golfed stage:

```
(def f (fn[v](let[F (fn[l](apply +(map
                                    (fn[[a b][c d]](*(l a b c d)(-(* a d)(* c b))))
                                    v
                                    (conj(subvec v 1)(v 0)))))
                  A (* (F(fn[& l] 1)) 3)]
                [(F (fn[a b c d](/(+ a c)A)))
                 (F (fn[a b c d](/(+ b d)A)))])))

```

Creates a helper function `F` which implements the summation with any callback `l`. For `A` the callback returns constantly `1` whereas X and Y coordinates have their own functions. `(conj(subvec v 1)(v 0))` drops the first element and appends to the end, this way it is easy to keep track of `x_i` and `x_(i+1)`. Maybe there is still some repetition to be eliminated, especially at the last `(map F[...`.

---
Tags: code-golf, geometry
---


title: Convert a sample to an index

text:
# Question
Title: Convert a sample to an index
We are putting balls into a fixed number **a** bins. These bins begin empty.

```
Empty bin (a=4): 0 0 0 0

```

And one by one we add balls to the bins.

```
0 0 0 1  or
0 0 1 0  or
0 1 0 0  or
1 0 0 0

```

We need a quick way to loop over all the possible states the bins take, without duplicates and without missing any and we don't want to enumerate all the possible bins. So instead we assign each bin-configuration an index.

We assign the index by sorting the possible configurations in a specific way:

1. Sort ascending by sum: so first `0 0 0 0`, then the possible configurations with 1 ball added, then 2, etc.
2. Then sort within each sum in ascending order, from the first bin to the last:

```
0 0 0 2
0 0 1 1
0 0 2 0
0 1 0 1
0 1 1 0
0 2 0 0
etc

```
3. The index is then assigned ascending through this list:

```
0 0 0 0  -> 1
0 0 0 1  -> 2
0 0 1 0  -> 3
0 1 0 0  -> 4
1 0 0 0  -> 5
0 0 0 2  -> 6
0 0 1 1  -> 7
0 0 2 0  -> 8
0 1 0 1  -> 9
0 1 1 0  -> 10
0 2 0 0  -> 11

```

## Rules

Create a function or program that takes a list of any size with non-negative integers and print or output its index. You can assume **a** to be at least 2. Shortest code wins. You may use 0-indexed output or 1-indexed, but specify which you use. NB: all examples here are 1-indexed.

## Example code

Not golfed, in R:

```
nodetoindex <- function(node){
  a <- length(node)
  t <- sum(node)
  if(t == 0) return(1)

  index <- choose(t-1 + a, a)

  while(sum(node) != 0){
    x <- node[1]
    sumrest <- sum(node)
    if(x == 0){
      node <- node[-1]
      next
    }
    a <- length(node[-1])
    index <- index + choose(sumrest + a, a) - choose(sumrest - x + a, a)
    node <- node[-1]
  }
  return(index + 1)
}

```

## Test cases

```
10 10 10 10 -> 130571
3 1 4 1 5 9 -> 424407
2 9 -> 69
0 0 0 -> 1
0 0 1 -> 2
0 0 0 0 0 0 -> 1
1 0 0 0 0 1 -> 23

```

# Answer
# Jelly, 8 bytes

```
S0rṗLSÞi

```

Try it online!

Brute-force solution. The first test case is too much for TIO, but I've verified it locally on my laptop. The second test case requires too much RAM, even for my desktop computer.

### How it works

```
S0rṗLSÞi  Main link. Argument: A (array)

S         Compute the sum s of A.
 0r       Create the range [0, ..., s].
    L     Yield the length l of A.
   ṗ      Cartesian power; yield the array of all l-tuples over [0, ..., s], in
          lexicographical order.
     SÞ   Sort the l-tuples by their sums. The sorting mechanism is stable, so
          l-tuples with the same sum are still ordered lexicographically.
       i  Find the index of A in the generated array of tuples.

```
> 3 votes

# Answer
## Clojure, 152 bytes

```
#(loop[v[(vec(repeat(count %)0))]i 1](if-let[r((zipmap v(range))%)](+ r i)(recur(sort(set(for[v v i(range(count v))](update v i inc))))(+ i(count v)))))

```

Not as easy as I thought. Less golfed version:

```
(def f (fn[t](loop[v[(vec(repeat(count t)0))]i 1]
               (if-let[r((zipmap v(range))t)](+ r i)
                 (recur (sort-by (fn[v][(apply + v)v]) (set(for[v v i(range(count v))](update v i inc))))
                        (+ i(count v)))))))

```

Loops over current states `v`, creates a hash-map from elements of `v` to their rank, if the searched state is found then its rank is returned (+ the number of previously seen states). If not found then recurses with a new set of possible states.

Oh actually we don't need that custom sorting function as all states within each loop has identical sum. This isn't as slow as I expected as `[3 1 4 1 5 9]` took only 2.6 seconds.
> 1 votes

# Answer
# Mathematica, 50 bytes

A port of Dennis's Jelly answer.

```
0~Range~Tr@#~Tuples~Length@#~SortBy~Tr~Position~#&

```

Unnamed function taking a list of integers as input, and returning a depth-2 list with a single integer as output; for example, the input for the last test case is `{1,0,0,0,0,1}` and the output is `{{23}}`.

A slightly ungolfed version is:

```
Position[SortBy[Tuples[Range[0,Tr[#]],Length[#]],Tr],#]&

```

Often we can save individual bytes in Mathematica by using prefix notation (`function@n` instead of `function[n]`) and infix notation (`a~function~b` instead of `function[a,b]`). This only works, however, when the resulting code happens to mesh well with Mathematica's intrinsic precedence order for applying functions. I was kind of amazed here that, with six sets of square brackets, it actually worked to remove *all* of them and save six bytes with the (pleasantly bracketless) submitted code.
> 1 votes

---
Tags: code-golf, number, combinatorics
---


title: Shrink your language's character set

text:
# Question
Title: Shrink your language's character set
We often get questions here on PPCG that favour submitting solutions using only a subset of characters (sufficiently so that there's a tag that identifies a particular subset of those challenges). Wouldn't it be nice if we could automatically cut languages down to a subset of their normal character set?

As an example, JavaScript is sometimes translated into a subset known as JSFuck which contains only the characters `[]()!+`. In this challenge, you're aiming to write the equivalent of a JavaScript to JSFuck translator, but without the language restriction: you're compiling a language of your choice down to a subset of its characters (well, bytes, in order to avoid dubious corner cases).

## Clarifications and detailed specification

* Call the program you submit program *A*. The input to program *A* will be a string representing a program (program *B*). Its output must also be a string representing a program (program *C*). Program *B* will be in the same language as program *A* (there are no restrictions on how your program reacts to invalid input). Program *C* must also be a program in that language, and have the same behaviour in all cases as program *B* (i.e. if program *C* is given input *X*, it will produce the same probability distribution of outputs as program *A* does).
* You may assume that in the case where programs *A* and *B* are distinct, program *B* does not access any files from disk. (In particular, you may assume it does not attempt to read its own source code from disk.).
* Although part of the scoring is based on a single test case (program *A* itself), your program must *work* for any input (in the sense of complying with the specification above; that is, any valid program *B* must lead to a corresponding output for program *C*). Optimizing specifically for the test case given is allowed (and might or might not be helpful).
* A `cat` implementation is technically speaking a valid answer to this question (as the subsetting of characters is part of the scoring criterion, not the validity criterion), but the scoring is designed so that such a program is unlikely to win. Just as solutions to competitions should make at least an attempt to minimize the number of bytes, solutions to this competition should make at least an attempt to minimize score. (Note that in some languages, `cat` may genuinely work best because the character sets are already small or impossible to shave down further. These solutions are valid, but ideally wouldn't be upvoted.)
* You can accept the strings used for your input and output via any reasonable method.
* Because languages with no computational ability might potentially lead to trivial solutions due to there being few possible programs to consider, this competition is open only to entries written in programming languages.

## Victory condition

Let *S* be the set of bytes that can appear in the outputs *C* of your program (that is: for any valid input *B*, if the corresponding output *C* can potentially contain a byte, then that byte must be an element of *S*). Let *c* be the number of elements in *S*.

Now, let *Q* be the result of running your program on itself (i.e. the output *C* produced when *A* and *B* are the same program). Let *b* be the number of bytes in *Q*. (In order to minimize *b* and thus your score, you'll want to keep your program short, as in , but also the size of your program's output short, as in .)

Your score for this is:

(*b*+1000)×loge(*c*+1)

The winner is the entry with the lowest score. (If there's a tie for first place, the lowest *c* among the tied entries will win; if there's still a tie for first place, the earliest entry among the entries tied for first will win.) Even if you can't win, though, you're encouraged to show off interesting answers (perhaps answers with a particularly low *c*, or in a language other people haven't attempted yet).

# Answer
# Brainfuck, (1000 + 133) * loge(8+1) ~= 2489

Requires an interpreter that has wrapping 8-byte unsigned cells and produces 0 or doesn't change the cell on EOF.

```
,[>>>--[>-<++++++]>>->->->-------------->-->>>-[++[>]<<->+]--[<]<<<[->+>>+<<<]+>>>>[<[->+<]+>[<-]<[->>[[-]>]-[+<-]+>.>]>>>]-[[+]<-],]

```

A proper brainfuck interpreter ignores any character except `[]<>+-,.`, so we minify the character set by keeping only those characters.

For example, giving this as input to the above program produces the above program:

```
,[>>>
prepare array
--[>-<++++++]>>->->->-------------->-->>>-[++[>]<<->+]--
[<]<<<[->+>>+<<<]+>>>
while number to the right of i
>[
    <[->+<] move sum of both to the right
    +>[<-]<[ if sum == 0
        clear everything to the right
        ->>[[-]>]
        move to the left until we hit 1
        -[+<-]
        output i and move past to stop loop
        +>.>
    ]
    >>>
]
-[[+]<-]
,]

```
> 1 votes

---
Tags: code-challenge, source-layout
---


title: Clone yourself!

text:
# Question
Title: Clone yourself!
You are to create a program that creates exact clones of itself infinitely until stopped. Whatever is in the original program must be in the clones. In other words, the clones and original program are the same in every way except for that the clones don't have to be in the same type of file as the source code (they can be text files).

**Example:**

If my original program is:

```
for i in range(0, 10):
     print i

```

the clone must also be:

```
for i in range(0, 10):
     print i

```

**Rules and Clarifications:**

* Standard loopholes are forbidden
* The clones must be the exact copy of the original
* The clones must be readable files that can be run if put inside the correct interpreter
* The program can read its own source code
* All clones must be separate files
* Printing your program out is not allowed
* File names count into the number of bytes
* The clones don't have to be in the same directory as the source file nor share the same file name
* At least 1000 clones should be able to be created

**Winning:**

Least bytes wins!

# Answer
# Zsh, ~~19~~ ~~17~~ 9 bytes

```
#!/bin/zsh
<$0>$$;$0

```

Per consensus on meta, the shebang is excluded from the byte count.

Try it online!

Note that TIO's forkbomb protection will kill the process after 113 files have been generated. It can easily generate 1000 files on a system without such conservative resource limits.
> 4 votes

# Answer
## Batch, 32 bytes

```
set/an=%1+1
copy %0 %n%
%0 %n%

```

Not using `@` because there's no restriction on STDOUT. `%1` defaults to the empty string, so `n` becomes `1` the first time and increments on every pass. Alternatively, this might work for 28 bytes, but I have no idea how random `%random%` actually is when used like this:

```
copy %0 %random%%random%
%0

```
> 4 votes

# Answer
# Bash, ~~25~~, ~~16~~, ~~12~~, 11 bytes

EDITS:

* Removed the newline (-1 byte), Added "Try It Online". Thanks @Dennis !
* Use background job PID `$!` as the filename (will be reused every ~32k files, but that is now allowed), -4 bytes

**Golfed**

```
#!/bin/bash
$0&cp $0 $!

```

**Explained**

Re-spawns itself as a background job with &, before doing a copy, so each iteration will run under its own PID.

Uses the last job PID as the filename.

This can run infinitely (or until stopped) but will be reusing clone filenames approx. every ~32k iterations.

Could be a bit nasty to kill, but AFAIK is not against the rules.

Try It Online!
> 3 votes

# Answer
## Ruby, ~~78 bytes~~, ~~77~~ 43 + 4 (filename: a.rb) = 47 bytes

* Version 1.2

43 bytes + name / Thanks to @Alexis So much shorter!!!

```
loop{File.write "#{$.+=1}",open("a.rb",?r)}

```

that's about as golfed as I think it's going to get

* Version 1.1

73 bytes + name / Thanks to @Alexis Anderson

```
i=0
loop do
File.open("#{i}",?w){|b|b.puts File.read("a.rb",?r)}
i+=1
end

```
* Version 1.0

74 bytes + name

```
i=0
loop do
File.open("#{i}","w") do{|b|b.puts File.read("a.rb")}
i+=1
end

```

This is my first Ruby answer so all inprovements are welcome.
> 3 votes

# Answer
# sh, 24 bytes

```
yes cp $0 '`uuid`'|sh -s

```
> 2 votes

# Answer
# C#, ~~104~~ 102 bytes

-2 bytes thanks to berkeleybross

```
namespace System.IO{class a{static void Main(){int i=0;while(1>0){i++;File.Copy("c{i}.cs");}}}}

```

No, it's not the shortest. But it's C#. What did you expect?
> 2 votes

# Answer
## Python 2, 54 bytes

```
from shutil import*
a=__file__
while`copy(a,a*2)`:a*=2

```
> 1 votes

# Answer
# Processing, 55 + 5 (name of file) = 60 bytes

I don't know if the filename counts as extra bytes

```
for(int i=0;;)saveStrings(i+++"",loadStrings("a.pde"));

```

Pretty much a series of builtins all chained together

### Explanation

```
for(int i=0;;)           //A complex piece of code that cannot be explained in words alone
saveStrings(             //Save param2 (String[]) into file param1 (String)
 i+++"",                 // filename: the int i (and then is incremented)
 loadStrings("a.pde")    // content: load the content of file a.pde as a String[]
);

```
> 1 votes

# Answer
# ForceLang + the ForceLang-JS module, 162 bytes

```
set j require njs
j var a=function(){for(;;){var p=new java.io.PrintStream(Math.random()+".txt");p.println("set j require njs");p.print("j var a="+a+";a()")}};a()

```
> 1 votes

# Answer
# PHP, ~~91~~ 60 bytes

Saved 31 bytes thanks to manatwork

```
<?for(;;)file_put_contents(++$i,file_get_contents("f.php"));

```

Usage: `$ php f.php` clones `f.php` and its code reproducing infinitely itself in filenames like `1`, `2`, `3`... until timeout.

**Previous version:**

```
<?for($i=0;;$i++)$p=fwrite(fopen("$i.php","w"),fread(fopen($f="f.php","r"),filesize($f)));

```

Usage: `$ php f.php` clones `f.php` and its code reproducing infinitely itself like `f1.php`, `f2.php`, `f3.php` ... `f(n).php` until timeout.
> 1 votes

# Answer
# Mathematica, 41 bytes

```
For[a=0,1>0,$Input~CopyFile~ToString@a++]

```

Full program. Copies its own source file into `0`, `1`, `2`, etc. in the current directory.
> 1 votes

# Answer
***Python 2, 61 bytes (unix) 65 (cross-platform)***

**Unix** \- *61 bytes*

```
import os;i=1
while os.popen('cp %s %i.py'%(__file__,i)):i+=1

```

On unix cp is the systems copy-file - command. Using the console via **popen** allows me to copy the file by cp. new files will spawn in old-files directory.

**CrossPlatform** \- *65 bytes*

```
i=0
while 1:i+=1;open('%i.py'%i,'w').write(open(__file__).read())

```

This works, as **open** on default allows reading.

**Funfact:** replace `1:i+=1` with `i:i-=1` and it will stop at i copies.

Other than that, I see no way of making it shorter than @muddyfish did it.
> 1 votes

# Answer
## awk, 29 (21) bytes,

```
{while(close(i++)||1)print>i}

```

awk is not really the tool for this as it requires `close()` when running indefinitely. Otherwise all it produces are empty files.

If the clone count had a limit, for example 5:

```
{while(++i<5)print>i}

```

the program would be 21 bytes.

Paste the program to a file `a` and run:

```
$ awk -f a a

```
> 0 votes

# Answer
# Python, 69 bytes

```
a=open(__file__).read()
i=0
while 1:i+=1;open(`i`+'.py','w').write(a)

```

I tried using `a` for the file name, but (unsurprisingly) Windows does not like files named `a=open(__file__).read()\ni=0\nwhile 1:i+=1;open(`i`+'.py','w').write(a)`. I also tried this:

```
a=open(__file__).read()
i=''
while 1:i+='.py';open(i,'w').write(a)

```

However it gives me this error:

```
Traceback (most recent call last):
  File "C:/Python27/codeGolfCopy.py", line 3, in <module>
    while 1:i+='.py';open(i,'w').write(a)
IOError: [Errno 2] No such file or directory: '.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py.py'

```

It creates 83 files, but that is not even close to the needed 1000.

If you would like to remove these files, you can use this:

```
import os;i = 1
while 1:os.remove(`i`+'.py');i+=1

```
> 0 votes

---
Tags: code-golf, quine, file-system
---


title: Golf a Numerical Growing Braid

text:
# Question
Title: Golf a Numerical Growing Braid
## Braid Description

In this braid, when a strand crosses over the top of another strand it adds the other strand's value to itself and all other strand values pass through. The braid has three strands and each strand begins at 1. The first crossover is the leftmost strand crossing over the middle strand. The next crossover is the rightmost strand crossing over the new middle strand (previously the leftmost strand). These two steps of crossovers repeat. In other words, the first crossover is `[a, b, c] -> [b, a+b, c]` and the second is `[a, b, c] -> [a, b+c, b]`. Using these rules here are the first six levels of the braid:

```
1,1,1
1,2,1
1,3,2
3,4,2
3,6,4
6,9,4

```

## Your task

Write a golfed program or function that accepts an integer as the braid level and outputs the three values for that level of the braid. You must indicate if your levels are zero- or one-based. Input and output may come in any reasonable format and trailing white space is allowed.

## Test Cases (1-based)

```
1 -> 1,1,1

2 -> 1,2,1

5 -> 3,6,4

10 -> 28,41,19

```

# Answer
> 7 votes
# MATL, ~~18~~ ~~17~~ 16 bytes

```
7Bi:"2:4PB@EX!Y*

```

Input is 0-based.

**Try it online!** Or **verify all test cases**.

### Explanation

Given a row vector `[a b c]`, the next vector is obtained post-matrix-multiplying it by either

```
[1 0 0;
 0 1 1;
 0 1 0]

```

or

```
[0 1 0;
 1 1 0;
 0 0 1]

```

depending on whether the iteration index is odd or even. For example, the matrix product `[1 3 2]*[0 1 0; 1 1 0; 0 0 1]` gives `[3 4 2]`. Then `[3,4,2]*[1 0 0; 0 1 1; 0 1 0]` gives `[3 6 4]`, and so on.

Note also that the second matrix equals the first rotated 180 degrees, which can be exploited to save a few bytes.

```
7        % Push 7
B        % Convert to binary. Gives [1 1 1]. This is the initial level
i        % Take input n
:        % Push range [1 2 ... n]
"        % For each
  5      %   Push 5
  I:     %   Push range [1 2 3]
  -      %   Subtract, element-wise: gives [4 3 2]
  B      %   Convert to binary. This gives the matrix [1 0 0; 0 1 1; 0 1 0]
  @      %   Push current iteration index
  E      %   Multiply by 2. Gives 2 in the firt iteration, 4 in the second etc
  X!     %   Rotate matrix 90 degrees either 2 or 0 times
  Y*     %   Matrix multiply
         % End. Implicitly display

```

# Answer
> 5 votes
## Haskell, 51 bytes

```
f p@(a,b,c)=p:(b,a+b,c):f(b,a+b+c,a+b)
(f(1,1,1)!!)

```

This uses 0-based indexing. Usage example: `(f(1,1,1)!!) 10` -\> `(28,60,41)`.

`f` creates the infinite list of braid triples and `(f(1,1,1)!!)` picks the nth one. `f` itself is a simple recursion which makes a list of its argument, followed by the left crossover and a recursive call with left and right crossover.

# Answer
> 4 votes
## Ruby, ~~60~~ 57 bytes

```
->n{f=->x{x<2?1:f[x-1]+f[x-3]};[f[n-2|1],f[n],f[n-1&-2]]}

```

The levels are 1-based.

Based on the following formula:

```
f(-1) = 1
f(0)  = 1
f(1)  = 1
f(x)  = f(x-1) + f(x-3)

braid(x) = {
    [f(x-1), f(x), f(x-2)]  if x is even,
    [f(x-2), f(x), f(x-1)]  if x is odd
}

```

Thanks to Neil for 3 bytes off with some nifty bitwise shenanigans.

# Answer
> 4 votes
# Python 2, 57 bytes

```
f=lambda n,a=1,b=1,c=1:1/n*(c,b,a)or f(n-1,b,b+c,a)[::-1]

```

Try it online!

# Answer
> 3 votes
# Jelly, 14 bytes

```
Ḋ+\;Ḣ
6BÇ⁸¡Ṛ⁸¡

```

Try it online!

### How it works

```
6BÇ⁸¡Ṛ⁸¡  Main link. Argument: n (integer)

6B        Convert 6 to binary, yielding [1, 1, 0], which is the braid at index 0.
  Ç⁸¡     Call the helper link n times.
     Ṛ⁸¡  Reverse the resulting array n times.

Ḋ+\;Ḣ     Helper link. Argument: [a, b, c] (integer array)

Ḋ         Dequeue, yielding [b, c].
 +\       Cumulative sum, yielding [b, b+c].
   ;Ḣ     Concatenate with the head of [a, b, c], yielding [b, b+c, a].

```

# Answer
> 2 votes
# TI-Basic, 58 bytes

One-based.

```
Prompt N
{1,1,1
For(I,1,Ans
If fPart(I/2
Then
{Ans(2),Ans(1)+Ans(2),Ans(3
Else
{Ans(1),Ans(2)+Ans(3),Ans(2
End
End

```

# Answer
> 2 votes
# PowerShell 2+, 75 bytes

1-based index

```
$a=1,1,0;1..$args[0]|%{$d=(0,2)[$_%2];$a[1],$a[$d]=($a[1]+$a[$d]),$a[1]};$a

```

### Try it online! or Try all Test Cases!

The loop always runs once so for the case of braid level `1` I simply start with an array of `1,1,0` so the result of the algorithm with make it `1,1,1`.

`$a[1]` is always the middle, then I just determine whether the other element index (`$d`) is going to be `0` or `2` based on whether the current level is even or odd. PowerShell supports multiple assignments at once so swapping becomes as easy as `$x,$y=$y,$x` which is basically what I'm doing with the array elements, just embedding the addition within that assignment.

# Answer
> 2 votes
# Javascript (ES6), 55 bytes

```
x=>(f=y=>y<2?1:f(y-1)+f(y-3),[f(x-2|1),f(x),f(x-1&-2)])

```

repl.it

1-based

This is just a port of @Doorknob's Ruby answer with @Neil's awesome bitwise golf.

# Answer
> 1 votes
# Befunge, 64 bytes

```
110p100p1&v
01:\_v#:-1<\p00<v\+g
..g.@>_10g
\1-:!#^_\:00g+\v>10p

```

Try it online!

**Explanation**

```
110p                Initialise a to 1 (at location 1;0).
    100p            Initialise c to 1 (at location 0;0).
        1           Initialise b to 1 (on the stack, since it'll be most frequently used).
         &v         Read n from stdin and turn down.

          <         The main loop starts here, executing right to left.
        -1          Decrement n.
    _v#:            Duplicate and check if zero; if not, continue left.
   \                Swap b to the top of the stack, leaving n below it.
01:            g    Make a duplicate copy, and read a from memory (at location 1;0).
              +     Add a to b, the result becoming the new b.
            v\      Swap the original b to the top of the stack and turn down.
            >10p    Turn around and save the original b as a (at location 1;0).
\1-                 Swap n back to the top of the stack and decrement.
   :!#^_            Duplicate and check if zero; if not continue right.
        \           Swap b to the top of the stack, leaving n below it.
         :00g       Make a duplicate copy, and read c from memory (at location 0;0).
             +      Add c to b, the result becoming the new b.
              \v    Swap the original b to the top of the stack and turn down.
            p00<    Turn around and save the original b as c (at location 0;0).
           \        Swap n back to the top of the stack.
          <         And repeat the loop from the beginning.

      >             If either of the zero tests succeed, we end up on line 3 going right.
       _            This just drops the n that is now zero, and continues to the right.
        10g         Read the final value of a (at location 1;0).
..                  Output a along with the b that was already on the stack.
  g                 Read the final value of c (the 0;0 location is implied).
   .@               Output c and exit.

```

# Answer
> 1 votes
# 05AB1E, 17 bytes

```
6bSIF¬¸s¦.pOì}¹FR

```

Try it online!

# Answer
> 1 votes
# Java 8, 121

This uses one-based levels:

```
(int l)->{int a=1,b=a,c=a,i=a;while(i<l)if(i++%2>0){b^=a;a^=b;b=(a^b)+a;}else{b^=c;c^=b;b=(c^b)+c;}return a+","+b+","+c;}

```

Ungolfed, with test program:

```
import java.util.function.IntFunction;

public class GolfANumericalGrowingBraid {

  public static void main(String[] args) {
    for (int level : new int[] { 1, 2, 5, 10 }) {
      output((int l) -> {
        int a = 1, b = a, c = a, i = a;
        while (i < l) {
          if (i++ % 2 > 0) {
            b ^= a;
            a ^= b;
            b = (a ^ b) + a;
          }
          else {
            b ^= c;
            c ^= b;
            b = (c ^ b) + c;
          }
        }
        return a + "," + b + "," + c;
      } , level);
    }
  }

  private static void output(IntFunction<String> function, int level) {
    System.out.println(function.apply(level));
  }
}

```

Output:

> 1,1,1
> 1,2,1
> 3,6,4
> 28,41,19

# Answer
> 0 votes
# GameMaker Language, 113 bytes

One-indexed, based on Doorknob's recursive solution. *Please don't ask why you can't initialize a primitive array all at once in GameMaker, I really don't know...*

Main program (69 bytes):

```
a=argument0 if a mod 2c=1b[0]=a(a-c-1)b[1]=a(a)b[2]=a(a+c-2)return b

```

Subprogram `a` (46 bytes):

```
a=argument0 if a<2return 1return a(a-1)+a(a-3)

```

# Answer
> 0 votes
# Perl 6, 60 bytes

```
{(1 xx 3,->[\a,\b,\c]{$++%2??(a,b+c,b)!!(b,b+a,c)}...*)[$_]}

```

Zero-based.

Straight-forwardly generated the lazy infinite sequence, and then indexes it.
There are likely better approaches.

# Answer
> 0 votes
## Clojure, 98 bytes

```
#(ffirst(drop %(iterate(fn[[v[a b c d]]][[(v a)(+(v b)(v c))(v d)][b a d c]])[[1 1 0][0 1 2 1]])))

```

Keeps track of current value `v` and from which positions the summation should be made for next round. Starts one state before the `[1 1 1]` to have 1-based indexing.

# Answer
> 0 votes
# C# ~~88~~ 86 Bytes

```
f(int n,int a=1,int b=1,int c=1)=>n>1?n--%2>0?f(n,b,a+b,c):f(n,a,b+c,b):a+","+b+","+c;

```

## Explanation

```
f(int n,int a=1,int b=1,int c=1)=>  //Using an expression bodied function to allow for defaults and remove return statement
    n>1?                            //recurse or return result
        n--%2>0?                    //get odd or even then decrement n
            f(n,b,a+b,c)            //odd recursion
           :f(n,a,b+c,b)            //even recursion
       :a+","+b+","+c;              //build output

```

# Answer
> 0 votes
# Mathematica, 68 bytes

```
If[#<3,{1,#,1},{{#,+##2,#2}&,{#2,#+#2,#3}&}[[Mod[#,2,1]]]@@#0[#-1]]&

```

Straightforward recursive definition of an unnamed function, taking a positive integer argument and returning an ordered list of three integers.

---
Tags: code-golf, math, integer
---