6
\$\begingroup\$

Make an upside down triangle of positive integers. Every number in the triangle must be distinct. Each number is the summation of its two parents (similar to how Pascal's triangle is constructed, but upside-down). Construct it in such a way that the bottom number is minimized.

For example, for input n = 4, here is a possible solution:

4 1 2 7 5 3 9 8 12 20

A reversal of the top numbers, such as 7 2 1 4, would also work.

For input n = 5, here is a possible solution:

7 2 1 4 6 9 3 5 10 12 8 15 20 23 43

The solution for n = 2 is rather boring:

1 2 3

The sequence of bottom numbers is described in OEIS A028307.

Challenge

Given an input integer n > 0 describing how many elements are in the first row, output the corresponding minimal triangle as explained above. Output can be as ASCII-art of the triangle, a list-of-lists or matrix, to STDOUT as one row per line, etc.

Rules

  • If applicable, you can assume that the input/output will fit in your language's native Integer type.
  • The input and output can be given by any convenient method.
  • Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
  • Standard loopholes are forbidden.
  • This is so all usual golfing rules apply, and the shortest code (in bytes) wins.
Improve this question
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Is padding between numbers specified? \$\endgroup\$ Commented Apr 26, 2018 at 15:07
  • 1
    \$\begingroup\$ @DeadPossum Up to you, so long as it's unambiguous (e.g., don't use 1 as your padding). The I/O isn't the interesting part of this challenge. \$\endgroup\$ Commented Apr 26, 2018 at 15:09

2 Answers 2

Reset to default
4
\$\begingroup\$

Jelly, 20 bytes

!*ṗµ+ƝÐĿ€FQƑ$Ðf-ị$ÞḢ

Try it online!

It's trivial to prove that there exists a solution which all elements on the first row are in range [1,n!n].

Be careful as this computes an array of 10'077'696 3-element arrays for n=3.

Proof:

Let x be on the kth layer (1 ≤ k ≤ n, and there are a numbers to the left of x. Let b0, b1, ..., bn-1 be the numbers on the first line.

Then:

x = ba × (k-1 choose 0) + ba+1 × (k-1 choose 1) + ... + ba+k-1 × (k-1 choose k-1)

It can be proven that all of the coefficients are non-negative and less than n! (except when n=1, in that case the algorithm gives correct result anyway), and two different numbers have two different set of coefficients.

So if the first line are chosen to be the powers of n! with exponent 0,1,2,...,n-1, the value of each cell uniquely determines the set of coefficients, and thus is unique.

Jelly, 19 bytes

!*r1œcµ_ƝÐĿ€FQƑ$ÐfṪ

Try it online!

Output format: Columns, upside down.

Improve this answer
\$\endgroup\$
0
1
\$\begingroup\$

Python 2, 251 239 230 bytes

-9 bytes thanks to @Mr.Xcoder

Outputs list of lines of triangle, bottom to top. 

def F(s,d): if-~d==len(s): 	u=sum(s,[]) 	if len(u)==len(set(u)):print s;g else: 	for j in range(s[d][0]): 	 s[d+1]=[j] 	 for i in s[d]:j=i-j;s[d+1]+=j, 	 if min(s[d+1])>=0:F(s,d+1) i,I=1,input() while i:F(eval(`[[i]]*I`),0);i+=1

Try it online!

Bruteforce-ish solution.
For all i in [1 .. ] generate all possbile triangles starting from the bottom, until one with all different numbers is found.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Yeah, that output is fine. \$\endgroup\$ Commented Apr 26, 2018 at 15:59
  • \$\begingroup\$ 230 bytes \$\endgroup\$ Commented Apr 26, 2018 at 16:58

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.