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.
\$\endgroup\$
  • 1
    \$\begingroup\$ Is padding between numbers specified? \$\endgroup\$ – Dead Possum Apr 26 '18 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\$ – AdmBorkBork Apr 26 '18 at 15:09
3
\$\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.

\$\endgroup\$
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.

\$\endgroup\$
  • \$\begingroup\$ Yeah, that output is fine. \$\endgroup\$ – AdmBorkBork Apr 26 '18 at 15:59
  • \$\begingroup\$ 230 bytes \$\endgroup\$ – Mr. Xcoder Apr 26 '18 at 16:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.