# Stack the rocks

This is a rock:

*


Rocks can be stacked. Apart from the bottom-most layer, each rock must rest on two other rocks, like this:

 *
* *


You have a pile of rocks, and your boss wants you to pile them symmetrically, taking up the least horizontal space possible.

Your challenge is to take a number of rocks as input, and output that many rocks stacked symmetrically, on as small a base as possible.

For example, with input 4:

You can't fit a pile of 4 rocks on a base of 2. With a base of 3, you can, but you can't make it symmetrical - you end up with something like


*
* * *


So you need a base size of 4, which uses up all your rocks, so the result is:



* * * *


Any trailing or leading whitespace is allowed in the output, and you may use any two distinct characters instead of * and  . If there are multiple ways to stack the inputted number of rocks symmetrically with the same base, any of them are valid.

# Scoring

This is , shortest wins!

# Testcases

4 =>
* * * *

7 =>
* * *
* * * *

8 =>
*
* *
* * * * *

9 =>
* *
* * *
* * * *

12 =>
* * *
* * * *
* * * * *

13 =>
* *
* * * * *
* * * * * *

or

*     *
* * * * *
* * * * * *

17 =>
*   *
* * * *
* * * * *
* * * * * *

19 =>
*     *
* *   * *
* * * * * *
* * * * * * *

Or
*
* *
* * *
* * * * * *
* * * * * * *

20 =>
* *
* * *
* * * *
* * * * *
* * * * * *

56 =>
* * * * *
* * * * * *
* * * * * * *
* * * * * * * *
* * * * * * * * *
* * * * * * * * * *
* * * * * * * * * * *

or
* *
* * *
* * * * * *
* * * * * * *
* * * * * * * *
* * * * * * * * *
* * * * * * * * * *
* * * * * * * * * * *

• Minimum width for each n can be found with this script. It's not on OEIS, but has a clear pattern as n increases. Aug 17 at 5:22
• @Bubbler Thanks, and I'm glad I didn't make it minimum-base. Aug 17 at 5:37
• @AviFS Wdym? They both have base=11. Aug 17 at 9:15
• @AviFS Algorithmically, that shouldn't work, and I've already posted the question. Aug 17 at 9:51
• This seems to be another valid solution for n=13. Aug 17 at 22:28

# Ruby, 124 117 bytes

->n{b=0
a=*a,"* "*b+=1while(n-=b)>0||n==-2
~n%2*n<0&&a[2][2]=' '
(0...b).map{|j|q=-j>n/2?2:0;a[j][q..~q].center b*2}}


Try it online!

Incorporated ideas from dingus and G B, and also removed the deletion loop completely by using the output loop to perform its function (it truncates the first and last * rather than overwriting them).

# Ruby, 163 137 bytes

->n{a=[];b=x=0
(a<<"* "*b+=1)while(x+=b)<n||2==c=x-n
(-~c/2).times{|i|a[i][0]=a[i][-2]=' '}
~c%2*c>0&&a[2][2]=' '
a.map{|j|j.center b*2}}


Try it online!

This is a fast algorithm with no searching.

Explanation

Where T is a triangular number greater than the input, the only solution for T-1 is to delete the top * and the only solution for T-4 is to delete the top two rows and the * from the middle of the next row, forming a diamond shape.

For T-1-2n or T-4-2n a possible solution is to also delete the * at the beginning and the end of each row. In practice there are always enough asterisks to delete; If you run out it means that there is a triangular number smaller than T which would give a smaller base (This is fairly easy to prove so I'll not explain here.)

For T-2 there is no solution and we are forced to use a triangle with the next larger base.

See examples below for odd and even numbers of deletions (numbers represent the number of deletions O not the number of *).

            1                  3                  7
O                  O                  O
* *                O O                O O
* * *              * * *              O * O
* * * *            * * * *            O * * O
* * * * *          * * * * *          * * * * *

4                  6                  8
O                  O                  O
O O                O O                O O
* O *              O O O              O O O
* * * *            * * * *            O * * O
* * * * *          * * * * *          * * * * *


Commented code

->n{a=[];b=x=0                         #a[] = empty array for solution;b = base size; x = asterisk count
(a<<"* "*b+=1)while(x+=b)<n||2==c=x-n  #Add rows to a while asterisk count is below n, or the count is exactly 2 above n. Save the difference between the count and the required in c
(-~c/2).times{|i|a[i][0]=a[i][-2]=' '} #Overwrite the excess asterisks with spaces by looping (c+1)/2 times. An odd number of asterisks is deleted because there is only one on the 1st row.
~c%2*c>0&&a[2][2]=' '                  #If there was a positive even number of excess asterisks, we still need to delete the middle asterisk on row 2.
a.map{|j|j.center b*2}}                #Return an array of strings, each centred to width b*2

• A very elegant solution! Couple of small saves: n{a=[]; -> n,*a{, and the first pair of parentheses isn't needed. Aug 18 at 1:43
• @Dingus Thanks! Down to 124 now. Aug 18 at 20:08
• 120 bytes
– G B
Aug 19 at 21:28
• 119 bytes based on GB's golf. Aug 20 at 3:40
• @GB Wow that's clever, I never thought of counting down with n. If n is negative it can be divided by 2 directly (Ruby rounds to minus infinity so we get the right even-odd behaviour.) Just compare with -j and saves an additional 2 bytes. Aug 20 at 9:13

# 05AB1E, 6960 56 bytes

Very slow bruteforcing approach. Generates all triangles of with the right number of stars in increasing size.

[N>L©ODULI.ÆεXLå}vy®£0δ.ýJ.c0ð:D.BÐíQs…1 1ƵA:€Sø€ü@PP*iq


Try it online!

If we sacrifice the performance, two more bytes can be saved: Try it online!

[                   # for N in 0, 1, ...
N>L©O             # K = (N+1-th triangular number)
DULI.ÆεXLå}       # all length K lists of 0's and 1's that sum to the input
vy                # for each list y
®£0δ.ýJ.c0ð:D.B # format as a pyramid with 1's and spaces
ÐíQ             # is it symmetric?
…1 1ƵA:         # make the pyramid "dense", fill the gaps between 1's
€Sø€ü@PP*       # check if each column is supported
iq              # if so, exit and implicitly print


# Jelly, 53 43 bytes

ŒṗQƑƇḂ⁹ƤḄ_’ʋⱮ3Ȧ\$ƇṀÞḢµạṀIḂ’+Ʋ⁶ẋ;"b1KḣƊ€z⁶ZŒB


Try it online!

A monadic link taking an integer and returning a list of lists. >50% of the code is focused on the ASCII art aspect. If a list of integers indicating row sizes were permissible, this would be 20 bytes.

In brief, this is the algorithm:

1. Generate all integer partitions of n
2. Keep only those made of distinct integers
3. Keep only those where there is no length 2 subsequence of odd numbers and no length 3 subsequence that is odd, even, even.
4. Keep one of the lists with the smallest maximum integer
5. Left pad the list of integers with spaces; in general, this is max integer minus current integer, but where there are two even numbers in a row, there is one less space.
6. Half the integer, rounding up, convert to unary and separate with spaces, with an extra space if the integer is even
7. Right pad with spaces to make each line the same length.
8. Palindromise each line

Full explanation to follow.

As an alternative, here’s a translation of @LevelRiverSts clever Ruby solution:

# Jelly, 49 bytes

ŻÄ_=2o<ʋ0Tðb1K€a3¦€3¦S_Ḃo¬Ɗɗ^Ø.¦"S_HĊʋb1ɗŻṛ¡"U{o⁶


Try it online!

# JavaScript (ES7), 186 bytes

A rather naive search, but reasonably fast.

f=(n,W)=>(g=(w,x=2**w-1,o='',t=n,p=o,X=x)=>x?(i=t,s='',h=k=>k--&&(q=(x&X)>>k&1)|2*h(k,i-=q,s+=' X'[q]+' '))(w)==x&&g(w-1,x&x/2,p+s+
+o,i,p+' ')||o&&g(w,x-1,o,t,p,X):!t&&o)(W)||f(n,-~W)


Try it online!

# Charcoal, 54 bytes

ＮθＷ∨›θ⁰⁼θ±²≧⁻Ｌ⊞Ｏυωθ↘Ｅυ⭆⁻Ｌυκ§ *⎇∧κλ∨﹪θ²¬∧θ⁼²⁺κλ›⊕⊗⁺κλ±θ


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

Ｎθ


Input n.

Ｗ∨›θ⁰⁼θ±²≧⁻Ｌ⊞Ｏυωθ


Subtract increasing number of rocks from n until the result is no longer positive, but subtract the next number if the result is exactly -2.

↘Ｅυ⭆⁻Ｌυκ§ *⎇∧κλ∨﹪θ²¬∧θ⁼²⁺κλ›⊕⊗⁺κλ±θ


Print a triangle of rocks, but remove rocks symmetrically from both sides as necessary, and also the rock directly below the topmost rock if necessary.