Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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!

share|improve this question
    
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.) –  steveverrill Aug 10 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 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 at 0:10
    
@Geobits That's precisely it. –  Brandon Anzaldi Aug 10 at 0:12
2  
What's the winning criterion? code-golf? –  professorfish Aug 10 at 5:54

9 Answers 9

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.

share|improve this answer
    
+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 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.

share|improve this answer
    
This is really cool! –  Brandon Anzaldi Aug 10 at 5:24
1  
Not bad golfing for a language invented almost 50 years ago! –  DigitalTrauma Aug 10 at 21:23
2  
I like the method of explaining how the code works. –  hsl Aug 10 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]
share|improve this answer
1  
~- is nice, but >>1 is shorter than /2|0 –  edc65 Aug 11 at 5:10
1  
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 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);}
share|improve this answer
    
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 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 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 at 6:32

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
share|improve this answer
    
41 if you remove the parentheses around n>b. –  core1024 Aug 11 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.

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

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;
        }
    }
}
share|improve this answer

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)
share|improve this answer
    
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 at 19:42
    
Whoops, never thought of that. –  Batman Aug 11 at 19:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.