# Stack a random number of cups into a perfect two dimensional pyramid (triangle)

You are given a certain number of cups (`n`). You are tasked with stacking these cups into a pyramid, with each row having one more cup than the row above it. The number you are given may or may not be able to be perfectly stacked. You must write a function that takes the total number of cups (`n`), and returns the following values. `t`, which is the total number of cups in the pyramid, and `b`, which is the number of cups on the bottom row. Your answer must be returned in the format of a string, as `b,t`.

• `n` is a randomly generated, positive, finite, whole number.
• `b` and `t` must also be positive, finite, and whole.
• You may not use any libraries that aren't already built into your language of choice.
• The pyramid is two dimensional, so instead of expanding out, it is linear, with each row adding only a single cup more than the last, instead of one with a square or triangular base.

In some potential cases:

• If `n=4`, `b=2` and `t=3`.
• If `n=13`, `b=4` and `t=10`.
• If `n=5000`, `b=99` and `t=4950`.

A verbose example in JavaScript:

``````var pyramid = function(n){
var i;
var t = 0;
var b;
for(i=0;i<=(n-t);i++){
t += i;
b = i;
}
console.log(b + ',' + t);
}
``````

And a tiny example too:

`p=function(n){for(t=i=0;i<=(n-t);i++){t+=i;b=i}return b+','+t}`

Good luck!

-
um... what shape is the base of the pyramid? is it an equilateral triangle (1,4,10,20...) a square (1,5,14,30..) or a rectangle (yes this is possible, the pyramid has a ridge on top.) – Level River St Aug 10 '14 at 0:07
@steveverrill I should have clarified that it's supposed to be a 2 dimensional shape, so a triangle is a more appropriate definition. So row 1 would have 1 cup, 2 would have 2, 3 would have 3, and so on. I apologize for the lack of clarity. I'm editing the question now. – Brandon Anzaldi Aug 10 '14 at 0:10
@steveverrill From the examples given, it's not a pyramid at all, but a triangle, so {1,3,6,10...} or `t=(b*b+b)/2` – Geobits Aug 10 '14 at 0:10
@Geobits That's precisely it. – Brandon Anzaldi Aug 10 '14 at 0:12
What's the winning criterion? code-golf? – professorfish Aug 10 '14 at 5:54

This works out the base directly by inverting the triangular number formula, `t = (b^2+b)/2`, and calculating `b = (sqrt(8*t+1) - 1) / 2`.

``````f n=init.tail\$show(b,div(b^2+b)2)where b=floor\$(sqrt(8*n+1)-1)/2
``````

And rather than constructing the string-based answer as `show b++","++show t`, it simply chops the brackets off the shown tuple.

Edit: calculating the new triangular number in place instead of declaring a new variable, `t`, saves 4 characters.

-
+1 for a better formula than mine uses. I can save 11 chars that way by eliminating the ugly checks in the return. – Geobits Aug 10 '14 at 3:27

# GNU dc, 25 bytes

dc does not really have functions, but the closest thing is a macro. This defines a macro which is stored in register `m`. This pops the input `n` from the top of the stack (idiomatic for dc), and prints `b,t` to stdout as per the spec:

``````# 25 byte macro definition
[8*1+v1-2/ddn44P1+*2/p]sm

# Some test cases
4 lmx
9 lmx
10 lmx
11 lmx
13 lmx
5000 lmx
``````

### Output:

``````\$ dc 2dpyr.dc
2,3
3,6
4,10
4,10
4,10
99,4950
\$
``````

### Explanation:

This uses the same inverse of the triangle function used in some of the other numbers. The triangle number `n` for base length `b` is given by:

``````n = b(b+1)/2
``````

Rearranging into a quadratic in terms of `b`:

``````b² + b - 2n = 0
``````

Plugging the coefficients {A=1, B=1, C=-2} into the quadratic formula gives:

``````b = (-(1) ± sqrt((1)²-4(1)(-2n))) / 2(1)

b = (-(1) ± sqrt(1+8n)) / 2
``````

This translates to `dc` as follows:

``````[                         # Start a macro definition
8*                       # Push 8 to the stack and multiply by n
#     (n is assumed to be next value on the stack)
1+                     # Push 1 to the stack and add to 8n
v                    # Take the square root
1-                  # Push 1 to the stack and subtract from the square root
2/                # Push 2 to the stack and divide to get the value of `b`
dd              # Duplicate top of stack twice (value of `b`)
n             # Pop top of stack and print value of with no newline
44P          # Push ASCII value of ',' (comma) and print with no newline
1+        # Push 1 to the stack and add 1 to `b`
*       # Multiply b by (b+1)
2/     # Push 2 the stack and divide to get the value of `t`
p    # Print value of `t` with a newline
]   # End macro definition
sm # Store macro in `m` register
``````

Note the quadratic formula introduces a ±, but the + root always gives us the answer we need.

Note also that `dc`'s default precision is 0 decimal places, and positive numbers are always rounded down to the nearest whole number, which is exactly the rounding we need.

-
This is really cool! – Brandon Anzaldi Aug 10 '14 at 5:24
Not bad golfing for a language invented almost 50 years ago! – Digital Trauma Aug 10 '14 at 21:23
I like the method of explaining how the code works. – NinjaBearMonkey Aug 10 '14 at 22:02

# ES6 41

This is based on the comperendinous' formula:

Edit: Thanks to edc65's suggestions:

``````p=n=>''+[b=~-Math.sqrt(8*n+1)>>1,b++*b/2]
``````
-
`~-` is nice, but `>>1` is shorter than `/2|0` – edc65 Aug 11 '14 at 5:10
Really, I hate the 'right' answer beeing surpassed by a loop (that could be a lot slower for big numbers). 41: `p=n=>''+[b=~-Math.sqrt(8*n+1)>>1,b++*b/2]` – edc65 Aug 11 '14 at 18:24

# Java

It's pretty simple to find triangle numbers. Here are three ways in Java, all under 90 chars, including a loopless version:

### 67

``````String x(int n){int t=0,b=0;for(;b<=n-t;t+=b++);return(b-1)+","+t;}
``````

### 78

``````String y(int n){int b=1,t=1;for(;t<=n*2;t=b*b+b++);return(--b-1)+","+(t/2-b);}
``````

### 89

``````String z(int n){int b=(int)Math.sqrt(n*2),t=(b*b+b)/2;return(t>n?b-1:b)+","+(t>n?t-b:t);}
``````
-
Bravo. I tried using the Math.sqrt(n*2) in my own solution before, but ran into some rounding issues in JS because I didn't implement the final checks as you did. Nor did I correctly get the (b*b+b)/2 down. – Brandon Anzaldi Aug 10 '14 at 0:30
I don't follow your math. Knowing that the number of items in a triangle of base b is (b*b+b)/2, you just have to solve a quadratic equation (best explained in the `dc` answer) – edc65 Aug 11 '14 at 5:19
@edc65 It's how I reverse triangle numbers in my head. Knowing `2t=b*b+b`, it's easy to show that `floor(sqrt(2t))=b`, since `b*b+b` lies between `b*b` and `(b+1)*(b+1)` (assuming b is positive, which it is). What screws it up is that `n!=t`, and this method doesn't work unless the number is actually triangular. As a result, I just kludged through an off-by-one check instead of doing it the other way. I thought about changing it later, but even with that change, it's not as short as the simple loop method in Java. – Geobits Aug 11 '14 at 6:32

# Javascript ES6 - 39 4143

Thought I'd try some recursion in hopes that it'd be smaller than the for loop.

``````f=(n,b=0,t=0)=>(n>b)?f(n-++b,b,t+b):b+','+t
``````

Tried to shrink it by calculating the total rather than passing it but ended up the same length

``````f=(n,b=0)=>(n>b)?f(n-++b,b):b+','+(b+b*b)/2
``````

Edit: Dropped another 2 with core1024's suggestion

``````f=(n,b=0,t=0)=>n>b?f(n-++b,b,t+b):b+','+t
``````

Edit: In principal, I agree with edc65 about the 'right' answer and almost didn't try to a recursive loop assuming it would be have to be longer. So I hate to take his improvement, but I will :) Nice spy there!

``````f=(n,b=0)=>n>b?f(n-++b,b):b+','+b++*b/2
``````
-
41 if you remove the parentheses around `n>b`. – core1024 Aug 11 '14 at 5:45

# JavaScript (ES6) – 47

``````p=n=>{for(t=i=0;i+t<n;)t+=i++;return i-1+','+t}
``````

For now only works on Firefox. The following works on any recent browser at 55 bytes:

``````p=function(n){for(t=i=0;i+t<n;)t+=i++;return i-1+','+t}
``````

This is derived from the example provided by the OP.

-
Wrong output format - "Your answer must be returned in the format of a string, as b,t." – isaacg Aug 10 '14 at 3:27
@isaacg I was testing it with `alert()`, which automatically converts the array to a string. I've changed it. – NinjaBearMonkey Aug 10 '14 at 3:34
You can pre-increment `i`, so it will be the correct value when the loop is done. – core1024 Aug 10 '14 at 10:39

# Pyth, 29

``````DAbKJ0W>b+JK~K1~JK)R++`K","`J
``````

If the output format `b, t` instead of `b,t` is OK, then it's 28 characters:

``````DAbKJ0W>b+JK~K1~JK)R:`,KJ1_1
``````

If `(b, t)` is OK, it's 23 characters:

``````DAbKJ0W>b+JK~K1~JK)R,KJ
``````

Explanation:

``````def A(b):
K=J=0
while gt(b,plus(J,K)):
K+=1
J+=K
return plus(plus(repr(K),","),repr(J))
``````

Test run - (input, output):

``````DAbKJ0W>b+JK~K1~JK)R++`K","`Jj"\n"m,dAdL11

(0, '0,0')
(1, '1,1')
(2, '1,1')
(3, '2,3')
(4, '2,3')
(5, '2,3')
(6, '3,6')
(7, '3,6')
(8, '3,6')
(9, '3,6')
(10, '4,10')
``````
-

## PHP 145

``````<?\$n=\$argv[1];for(\$b=ceil(\$n/2);\$b>0;\$b--){for(\$k=\$b-1;\$k>0;\$k--){\$v=array_sum(range(\$k,\$b));if(\$v>\$n)continue 2;if(\$v==\$n){echo "\$b,\$k";exit;}}}
``````

Expanded:

``````<?
\$n=\$argv[1];
for(\$b=ceil(\$n/2);\$b>0;\$b--){
for(\$k=\$b-1;\$k>0;\$k--){
\$v=array_sum(range(\$k,\$b));
if(\$v>\$n)continue 2;
if(\$v==\$n){
echo "\$b,\$k";
exit;
}
}
}
``````
-

PYTHON: 76

``````def r(x,b,t):
x-=b+1
return r(x,b+1,t+b) if x>=0 else str(b)+','+str(t+b)
``````
-
`x-(b+1)` can be shortened to `x-b-1`, or since you're not using `x` again, maybe `x-=b+1` and use `x` instead of `c`. – Geobits Aug 11 '14 at 19:42
Whoops, never thought of that. – Batman Aug 11 '14 at 19:43