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 
 * *
 * * *
 * * * * * *
 * * * * * * *
 * * * * * * * *
 * * * * * * * * *
 * * * * * * * * * *
* * * * * * * * * * *

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

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

• Dingus: A very elegant solution! Couple of small saves: n{a=[]; -> n,*a{, and the first pair of parentheses isn't needed.
• Level River St: @Dingus Thanks! Down to 124 now.
• G B: 120 bytes
• Dingus: 119 bytes based on GB's golf.
• Level River St: @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.

Answer 2

Jelly, (削除) 53 (削除ここまで) 43 bytes

ŒṗQƑƇḂ9ƤḄ_’ʋⱮ3Ȧ$ƇṀÞḢμạṀIḂ’+Ʋ6ẋ;"b1KḣƊ€z6ZŒ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{o6

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

NθW∨›θ0=θ±2≧−L⊞Oυωθ↘Eυ⭆−Lυκ§ *⎇∧κλ∨%θ2¬∧θ=2+κλ›⊕⊗+κλ±θ

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

Nθ

Input n.

W∨›θ0=θ±2≧−L⊞Oυωθ

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.

↘Eυ⭆−Lυκ§ *⎇∧κλ∨%θ2¬∧θ=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), ¹⁷⁶ 170 bytes

g:{r:,1+&b:1+#**|x
 s:(,'/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!

-6 bytes : @Adám

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.

• doug: This has a performance enhancement to stop as soon as a solution exists. Could save quite a few bytes if I'm willing to do blindly do as many iterations as the target.