Algorithm for stacking objects?

In other words, if you are given  a number k, you need to solve

n * (n+1)/2 <= k

n is the number of elements you would have at the base of your pyramid.

sorry, swap floor and ceil in the previous answer

@sunnycoder:
Uhm, he cannot start from the top, because for n=3, for example, he will have the base with only 1 element,which contradics the basic requirement.

@ozo:
Your alghorithm is good for calculating the base, but it wrong for calculating stack hight.
For example, for n=11, base has ceil(4,21)=5, which is good, but height is floor(4,21)=4, which is wrong, because a stack with 11 elements will be like this:
oo
oooo
ooooo
therefore height is only 3.

I will supply you with a pseudo-code algorithm later today (in 7-8 hours)

In my alghoritm, I will use ozo's formula for calculating the base dimension, and I'll give him full credit for his formula.
I will build your stack in a square matrix with ceil(sqrt(8*n + 1)-1)/2) lines and colums.
I will initialize all matrix elements with 0;
Knowing the base dimension, I will build the stack by writing 1 until I finish all the given elements.
I will build the stack by using line_dim to know the current line lenght (starting from known base dimension and decreasing by 1 as I go up).
The output will be a matrix looking like that:
1111
1110
1100
1000
for n=10
and looking like that:
11111
11110
11000
00000
00000
for n=11
where 1 represents the stack elements.
I know that your stack will be upside down, but you can correct that by the way you display it. I made it like this to keep a clean alghoritm.

BEGIN algorithm;
read n;
initialise dim with ceil(sqrt(8*n + 1)-1)/2);
initialize a matrix will all elements 0;
initialize counter_elements with n;
initialize i with 0;
initialize line_dim with dim;
 while counter_elements>0
   begin
    i++;
    For j=1 to line_dim
     begin
      a[i,j]=1;
      line_dim--;
      end;
    end;
 display matrix a; {careful that your stack is stored upside down in the matrix}
END algorithm.

If I get this right, you cannot reach 3 layers with n=5.
You get at most

OO
OOO

or

O
OOOO

The attached code prints such a stack with maximal height and lowest baryenter (i.e. for n=5 it will produce the second variant).

void PrintRow(int k) {
   for (int i=0; i<k; ++i)
      printf("O");
   printf("\n");
}
 
void PrintPyramid(int n) {
   for (int rowlen=1; rowlen*2 < n; ++rowlen) {
       PrintRow(rowlen);
       n -= rowlen;
   }
   // Now n is either =0 or greater than the last printed rowlen
   if (n>0) 
      PrintRow(n);
}

                                              

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:

I forgot to decrement the counter_elements counter. Of course you need to decrement it by 1 before the end of the while.

>he cannot start from the top, because for n=3, for example, he will have the base with only 1 element,which
>contradics the basic requirement.

n(n+1)/2 <= 3

solves to n = 2
i.e. base would have 2 elements.

The following alternative code produces maximum height and highest barycenter.

Alternatively to the iterative method below (complexity O(sqrt(n)), you could calculate "base" using ozo's formula (but with ceiling) and calculating atLeast from that.
However, the output is at least as complex anyway :)

void PrintPyramid(int n) {
   int base = 0;
   int atLeast = 0;
   while (atLeast < n) {
      ++base;
      atLeast += base;
   }
   // If we had "atLeast" objects, we could make a 
   // perfect pyramid with base "base".
   int skip= atLeast -n;
   // by skipping one row of suitable length, 
   // we get the desired result.
   for (int row = 1; row<=base; ++row)
      if (row != skip)
         PrintRow(row);
}

                                              

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:

sunnycoder:My bad, I ment for n=4 :)
For n=4, he would have his stack like this:
o
oo
o

What was my point.

for n =4, you would still have a two level pyramid with one element left out.


n * (n+1)/2 <= k

would still solve to n = 2

sunnycoder:
So, let's just leave elements out because is convenient?
...

or we can try to fit them in even if it means that we dont get the kind of pyramid that we were asked to build?

Fitting in extra elements is no sweat ... add them all to the base level or one by one from base level upwards (you would need to add 2 to base in worst case)

> For example, for n=11, base has ceil(4,21)=5, which is good, but height is floor(4,21)=4, which is wrong, > because a stack with 11 elements will be like this:
> oo
> oooo
> ooooo
> therefore height is only 3.

Why is the height for 11 less than the height for 10?
o
oo
ooo
ooooo

> Fitting in extra elements is no sweat ... add them all to the base level or one by one from base level upwards (you would need to add 2 to base in worst case)

Well, these two methods of flling in extra are comprised by my codes in #23411668 and #23411861, but of course one has many choices inbetween. In fact, if you are left with k objects after building a maximal perfect pyramid, you have p(k) options to add these without breaking the stacking property, wher p(k) denotes the number of partitions of k; "one by one from base level upwards" corresponds to the partition "1+1+...+1", "add them all to the base" corresponds to "k".

ozo:
I wasn't careful that he wants the highest stack possible, and I assumed that he wants "the most stable" stack, starting from base, with minimum elements on the base.
Indeed, your formula for height is good too.
I apologize :(

sunnycoder:
You just supplied the idea for the quickest algorithm.
Make the perfect stack, and distribute the leftovers one by one, from base up. This actually guarantees the highest stack.
1. Calculate the biggest perfect stack with your number of elements.
read n;
i=1;
while i*(i+1)/2 <=n
m=i*(i+1)/2;
i++
end while;
2. At this point, n-m will be the leftovers to distribute, i-1 will be the base of the perfect stack. I will assume you want your stack stored (and not just displayed), and I will store your stack in a matrix, just as in my first algorithm. It will be a (i-1) X (i-1) matrix (i calculated above) if your n is the sum of first i numbers, and will be a i X i matrix if there are leftovers to complete. The matrix will have 1 where you have a stack element. (careful that the stack will be upside down in the matrix).
3. Treating the lucky case when n is a sum of first i numbers (perfect stack)
if m==n
for j=1 to i-1
 for k=1 to i-1
  a(j,k)=1
end algorithm
4. Building perfect stack and completing the stack
for j=1 to i-1
 for k=1 to i-1
  a(j,k)=1
k=1;
while m<n
   a(k,i)=1;
   k++;
end while;
5. You will have your stack in the a matrix like this:
for n=10
1111
1110
1100
1000
for n=18
111111
111110
111100
110000
100000
And so on.

This is the quickest and the most "clean" algorithm.
Of course I give a lot of credit to sunnycoder for the idea (in his second post he said that the base will have n elements - well, it will have n elements *only* if your number of elements builds a perfect stack.) Also, I must say that you will never have to add 2 elements to the base, not even in the worst case.
Apologize again for not paying fully attention to your requirements, and apologize to ozo, because his formulas were both good.

One thing remains to be proven, that this guarantees the highest stack.
Well, highest stack is guaranteed, because the perfect stack is the highest stack possible with a given number of elements, and the leftovers are too few to build a higher perfect stack. So if you complete with all the leftovers  by 1 per level starting from the base and going up, you are sure you have the higher stack, with the least number of elements possible on the base.

Ignore my first algorithm, it doesn't build you the highest stack. It builds you the lowest stack with the least number of elements on the base.