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

Question

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!

Answer 1

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.

Answer 2

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.

Answer 3

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]

Answer 4

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);}

Answer 5

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

Answer 6

Javascript ES6 - 39 41 43

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

Answer 7

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.

Answer 8

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;
        }
    }
}

Answer 9

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)