Stack the rocks

Question

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 code-golf, shortest wins!

Testcases

4 => 
* * * *

7 => 
 * * *
* * * *

8 =>
    *
   * *
* * * * *

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

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

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

or

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

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

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

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

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

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

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

Answer 1

Ruby, 124 117 112 110 bytes

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

Answer 2

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!

Answer 3

05AB1E, 69 60 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!

Some high-level comments:

[                   # 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

Answer 4

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!

Answer 5

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.

Answer 6

K (ngn/k), 177 bytes

g:{r:,1+&b:1+#**|x
  s:(#/:/|1(2*#*:)\)'x@&b>2*#'*:'x
  s:x@&2!b+#'*:'x:s,x
 ?x,((,!0),0^@\:[;!b]'{(&-2!x-#*y),/:y}[b]'s),\:r}
f:{*(x=+//')#({~(x=#**|:y)||/x=+//'y}[x])g/(,,,1)}

Try it online!

Recursively build up structures by placing either one or two smaller such structures on top of a base wide enough to accommodate them.

Could probably use a better heuristic for impossible answers. Currently just iterates until the base is as wide as the target.