# 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? – user16402 Aug 10 '14 at 5:54

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

# Haskell, 64 68

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

# 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

# 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')


# 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

## 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. – RageCage Aug 11 '14 at 19:43