# My triangle needs more nodes

Consider the standard equilateral triangle, with nodes labeled using barycentric coordinates:

We can turn this 3 node triangle into a 6 node triangle by adding a new line of 3 vertices (one more than was present on a side of the original 3 node triangle), remove any internal edges (but not internal nodes) and re-normalize the coordinates:

Repeating the process to go from a 6 node triangle to a 10 node triangle, add a line of 4 vertices (again, one more than was present on a side of the original 6 node triangle), remove any internal edges (but not internal nodes) and re-normalize the coordinates:

This process can be repeated indefinitely. The goal of this challenge is given an integer N representing how many times this process has been performed, output all the nodes for the associated triangle in barycentric coordinates.

# Input

Your program/function should take as input a single non-negative integer N representing how many times this process has been applied. Note that for N=0, you should output the original triangle with 3 nodes.

The input may come from any source (function parameter, stdio, etc.).

# Output

Your program/function should output all the nodes in normalized barycentric coordinates. The order of the nodes does not matter. A number can be specified as a fraction (fraction reduction not required) or a floating point number. You may also output "scaled" vectors to specify a node. For example, all 3 of the following outputs are equivalent and allowed:

0.5,0.5,0

1/2,2/4,0

[1,1,0]/2


If using floating point output, your output should be accurate to within 1%. The output may be to any sink desired (stdio, return value, return parameter, etc.). Note that even though the barycentric coordinates are uniquely determined by only 2 numbers per node, you should output all 3 numbers per node.

# Examples

Example cases are formatted as:

N
x0,y0,z0
x1,y1,z1
x2,y2,z2
...


where the first line is the input N, and all following lines form a node x,y,z which should be in the output exactly once. All numbers are given as approximate floating point numbers.

0
1,0,0
0,1,0
0,0,1

1
1,0,0
0,1,0
0,0,1
0.5,0,0.5
0.5,0.5,0
0,0.5,0.5

2
1,0,0
0,1,0
0,0,1
0.667,0,0.333
0.667,0.333,0
0.333,0,0.667
0.333,0.333,0.333
0.333,0.667,0
0,0.333,0.667
0,0.667,0.333

3
1,0,0
0.75,0,0.25
0.75,0.25,0
0.5,0,0.5
0.5,0.25,0.25
0.5,0.5,0
0.25,0,0.75
0.25,0.25,0.5
0.25,0.5,0.25
0.25,0.75,0
0,0,1
0,0.25,0.75
0,0.5,0.5
0,0.75,0.25
0,1,0


# Scoring

This is code golf; shortest code in bytes wins. Standard loopholes apply. You may use any built-ins desired.

• You say "If using floating point output". What alternatives are there? Fractions? If so, do they have to be reduced? How about scaled vectors like [1,2,3]/6? – Peter Taylor Aug 23 '16 at 9:54
• Yes, all of those alternatives are allowed. I'll update the problem statement. – helloworld922 Aug 23 '16 at 9:55

## CJam (22 bytes)

{):X),3m*{:+X=},Xdff/}


This is an anonymous block (function) which takes N on the stack and leaves an array of arrays of doubles on the stack. Online demo

### Dissection

{         e# Define a block
):X     e# Let X=N+1 be the number of segments per edge
),3m*   e# Generate all triplets of integers in [0, X] (inclusive)
{:+X=}, e# Filter to those triplets which sum to X
Xdff/   e# Normalise
}


f n|m<-n+1=[map(/m)[x,y,m-x-y]|x<-[0..m],y<-[0..m-x]]


# Python 3, 87 bytes

This is actually supposed to be a comment to the solution by TheBikingViking but I don't have enough reputation for comments.

One can save a few bytes by only iterating over the variables i,j and using the fact that with the third one they add up to n+1.

def f(n):d=n+1;r=range(n+2);print([[i/d,j/d,(d-i-j)/d]for i in r for j in r if d>=i+j])


## Mathematica,  44  43 bytes

Select[Range[0,x=#+1]~Tuples~3/x,Tr@#==1&]&


This is an unnamed function taking a single integer argument. Output is a list of lists of exact (reduced) fractions.

Generates all 3-tuples of multiples of 1/(N+1) between 0 and 1, inclusive, and then selects those whose sum is 1 (as required by barycentric coordinates).

# 05AB1E, 10 bytes

ÌL<¤/3ãDOÏ


Explanation

ÌL<          # range(1,n+2)-1
¤/        # divide all by last element (n+1)
3ã      # cartesian product repeat (generate all possible triples)
DO    # make a copy and sum the triples
Ï   # keep triples with sum 1


Try it online

• Since ¤ consumes the array, why does / divide the array by that? Does it "remember" that last popped value and use it if needed? – Luis Mendo Aug 23 '16 at 13:40
• @LuisMendo: ¤ is one of the few commands that does not pop and consume from the stack. It pushes the last element of the list while leaving the list on the stack. – Emigna Aug 23 '16 at 13:47
• – Luis Mendo Aug 23 '16 at 14:04
• @LuisMendo 05AB1E only outputs the top of the stack at the end of a program. – Emigna Aug 23 '16 at 14:20
• Oh, of course! Thanks for the explanations – Luis Mendo Aug 23 '16 at 15:08

# MATL, 17 bytes

2+:qGQ/3Z^t!s1=Y)


Try it online!

### Explanation

The approach is the same as in other answers:

1. Generate the array [0, 1/(n+1), 2/(n+1), ..., 1], where n is the input;
2. Generate all 3-tuples with those values;
3. Keep only those whose sum is 1.

More specifically:

2+     % Take input and add 2: produces n+2
:q     % Range [0 1 ... n+1]
GQ/    % Divide by n+1 element-wise: gives [0, 1/(n+1), 2/(n+1)..., 1]
3Z^    % Cartesian power with exponent 3. Gives (n+1)^3 × 3 array. Each row is a 3-tuple
t      % Duplicate
!s     % Sum of each row
1=     % Logical index of entries that equal 1
Y)     % Use that index to select rows of the 2D array of 3-tuples


## Jellyfish, 37 33 bytes

Thanks to Zgarb for saving 4 bytes.

p
*%
# S

=E   S
/
1+r#>>i
3


Try it online!

Like my Mathematica and Peter's CJam answers, this generates a set of candidate tuples and then selects only those that sum to 1. I'm not entirely happy with the layout yet, and I wonder whether I can save some bytes with hooks or forks, but I'll have to look into that later.

# Perl 6: 50 40 bytes

{grep *.sum==1,[X] (0,1/($_+1)...1)xx 3}  Returns a sequence of 3-element lists of (exact) rational numbers. Explanation: • $_
Implicitly declared parameter of the lambda.
• 0, 1/(\$_ + 1) ... 1
Uses the sequence operator ... to construct the arithmetic sequence that corresponds to the possible coordinate values.
• [X] EXPR xx 3
Takes the Cartesian product of three copies of EXPR, i.e. generates all possible 3-tuples.
• grep *.sum == 1, EXPR
Filter tuples with a sum of 1.

# Ruby, 62

I'd be surprised if this can't be improved on:

->x{0.step(1,i=1.0/(x+1)){|a|0.step(1-a,i){|b|p [a,b,1-a-b]}}}


Taking the advice latent in the puzzle, this calculates the second node options based on the first, and the third node by subtracting the first two.

# Brachylog, 24 bytes

+:1f
yg:2j:eaL+?/g:Lz:*a


Try it online!

# Python 3, 106 bytes

def f(n):r=range(n+2);print([x for x in[[i/-~n,j/-~n,k/-~n]for i in r for j in r for k in r]if sum(x)==1])


A function they takes input via argument and prints a list of lists of floats to STDOUT.

Python is not good at Cartesian products...

How it works

def f(n):                         Function with input iteration number n
r=range(n+2)                      Define r as the range [0, n+1]
for i in r for j in r for k in r  Length 3 Cartesian product of r
[i/-~n,j/-~n,k/-~n]               Divide each element of each list in the product
by n+1
[x for x in ... if sum(x)==1]     Filter by summation to 1
print(...)                           Print to STDOUT


Try it on Ideone

# Actually, 15 bytes

This uses an algorithm similar to the one in TheBikingViking's Python answer. Golfing suggestions welcome. Try it online!

u;ur♀/3@∙Σ1=░


Ungolfed:

u;                Increment implicit input and duplicate.
ur              Range [0..n+1]
♀/            Divide everything in range by (input+1).
3@∙         Take the Cartesian product of 3 copies of [range divided by input+1]
Σ1=    Create function that takes a list checks if sum(list) == 1.
░   Push values of the Cartesian product where f returns a truthy value.


# Ruby, 77 74 bytes

Another answer using the algorithm in TheBikingViking's Python answer. Golfing suggestions welcome.

->n{a=[*0.step(1,i=1.0/(n+1))];a.product(a,a).reject{|j|j.reduce(&:+)!=1}}


Another 74-byte algorithm based on Not that Charles's Ruby answer.

->x{y=x+1;z=1.0/y;[*0..y].map{|a|[*0..y-a].map{|b|p [a*z,b*z,(y-a-b)*z]}}}


## JavaScript (Firefox 30-57), 88 81 bytes

n=>[for(x of a=[...Array(++n+1).keys()])for(y of a)if(x+y<=n)[x/n,y/n,(n-x-y)/n]]


Returns an array of arrays of floating-point numbers. Edit: Saved 7 bytes by computing the third coordinate directly. I tried eliminating the if by calculating the range of y directly but it cost an extra byte:

n=>[for(x of a=[...Array(++n+1).keys()])for(y of a.slice(x))[x/n,(y-x)/n,(n-y)/n]]

• At the end, you wrote [x/n,y/n/z/n], did you forget a comma? – kamoroso94 Aug 24 '16 at 3:44
• @kamoroso94 You're right, I typoed the last comma, thanks for letting me know. – Neil Aug 24 '16 at 7:28