29
\$\begingroup\$

Well, although this challenge turned out to be a huge success, it also turned out to be very trivial to solve. Therefore, for those of looking for more of a challenge, I created a sequel to this challenge in which you must now count the number of unique rectangles. Check it out!

Now, for those of you looking to solve this challenge, here it comes.


Well, we don't really have a challenge like this yet, so here we go.

Consider this 3 x 3 grid of rectangles:

Example

How many rectangles are there? Well, counting visually, we can see that there are actually 36 rectangles, including the entire plane itself, which are all shown in the animated GIF below:

Rectangles in Example

The Task

The counting of rectangles as shown above is the task. In other words, given 2 integers greater than or equal to 0, m and n, where m represents the width and n represents the height, output the total number of rectangles in that m x n grid of rectangles.

Rules

  • The use of any built-ins that directly solve this problem is explicitly disallowed.

  • This challenge is not about finding the shortest answer, but finding the shortest answer in every language. Therefore, no answer will be accepted.

  • Standard loopholes are prohibited.

Test Cases

Presented in the format Array of Integers Input -> Integer Output:

[0,0] -> 0
[1,1] -> 1
[3,3] -> 36 (Visualized above)
[4,4] -> 100
[6,7] -> 588

References

Remember, this is , so shortest code wins!

\$\endgroup\$
  • \$\begingroup\$ I calculated 588 for the last test-case. \$\endgroup\$ – Leaky Nun Aug 1 '16 at 5:31
  • \$\begingroup\$ @LeakyNun Well then, I guess I missed some while counting them. It's fixed. \$\endgroup\$ – R. Kap Aug 1 '16 at 5:32
  • \$\begingroup\$ What is the maximum value of the input? \$\endgroup\$ – Erik the Outgolfer Aug 1 '16 at 10:06
  • \$\begingroup\$ Relevant \$\endgroup\$ – shooqie Aug 1 '16 at 11:09

24 Answers 24

34
\$\begingroup\$

Python, 22 bytes

lambda m,n:m*~m*n*~n/4

The formula m*n*(m+1)*(n+1)/4 is shortened using the bit-complement ~m=-(m+1), expressing (m+1)*(n+1) as ~m*~n.

Why is the number of rectangles m*n*(m+1)*(n+1)/4? Each rectangle is specified by the choice of two horizontal lines (top and bottom) and two vertical lines (left and right). There are m+1 horizontal lines, of which we choose a subset of two distinct ones. So the number of choices is choose(m+1,2), which is m*(m+1)/2. Multiplying by the n*(n+1)/2 choices for vertical lines gives the result.

\$\endgroup\$
  • \$\begingroup\$ That +1 trick is brilliant. \$\endgroup\$ – David Ljung Madison Aug 2 '16 at 6:14
11
\$\begingroup\$

Jelly, 4 bytes

RS€P

Try it online!

Alternatively, also 4 bytes

pP€S

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Good job. Thumbs up. :) \$\endgroup\$ – R. Kap Aug 1 '16 at 5:31
  • 24
    \$\begingroup\$ Care to explain? \$\endgroup\$ – Pureferret Aug 1 '16 at 9:11
  • \$\begingroup\$ There's also בHP and ‘c2P and maybe other 4 byte alternatives. \$\endgroup\$ – miles Aug 1 '16 at 21:59
  • 1
    \$\begingroup\$ @Pureferret This uses the formula from OEIS about this being the product of the nth and mth triangular number. R converts each number into the 1 based index: [1, 2, ..., n]. S is sum and means 'each' so each list is summed, giving a list like: [nth triangle number, mth triangle number]. Then P takes the product of that list, which gives the desired result. \$\endgroup\$ – FryAmTheEggman Aug 2 '16 at 20:00
  • 1
    \$\begingroup\$ @FryAmTheEggman so what your saying is.... Magic \$\endgroup\$ – Pureferret Aug 3 '16 at 6:49
9
\$\begingroup\$

Javascript (ES6), 17 bytes

m=>n=>m*n*~m*~n/4

A fork of this answer.

f=m=>n=>m*n*~m*~n/4
alert(f(prompt())(prompt()))

\$\endgroup\$
  • \$\begingroup\$ I'm not sure, is currying OK in languages that don't do this by default? \$\endgroup\$ – John Dvorak Aug 2 '16 at 10:23
  • 1
    \$\begingroup\$ @JanDvorak Meta post. \$\endgroup\$ – Leaky Nun Aug 2 '16 at 12:04
9
\$\begingroup\$

Mathematica, 15 bytes

##(1##+##+1)/4&

This is an unnamed function taking two integer arguments and returning the number of rectangles.

Explanation

The implementation is basically a very golfy form of the product of the two triangular numbers. It might be worth reading the section "Sequences of arguments" in this post for the details, but I'll try to summarise the gist here.

## expands to a sequence of all arguments. This is similar to splatting in other languages. For instance, if the arguments are 3 and 4, then {1, 2, ##, 5} will give you {1, 2, 3, 4, 5}. But this doesn't just work in lists, but in any expression whatsoever, e.g. f[1, 2, ##, 5] would also be f[1, 2, 3, 4, 5].

This gets interesting when you combine ## with operators. All operators in Mathematica are just short-hands for some f[...]-like expression (possibly nested). E.g. a+b is Plus[a, b] and a-b actually represents Plus[a, Times[-1, b]]. Now when you combine ## with operators, what Mathematica does is to expand the operators first, treating ## like a single operand, and expand them only at the end. By inserting ## in the right places, we can therefore use it both to multiply and to add the operands.

Let's do this for the code above:

##(1##+##+1)/4

Expanding it to its full form, we get this:

Times[##, Plus[Times[1, ##], ##, 1], Rational[1/4]]

Let's insert the function arguments a and b:

Times[a, b, Plus[Times[1, a, b], a, b, 1], Rational[1/4]]

And now we convert it back into standard mathematical notation:

a * b * (a * b + a + b + 1) / 4

A little rearranging shows that this is the product of the triangular numbers:

a * b * (a + 1) * (b + 1) / 4
(a * (a + 1) / 2) * (b * (b + 1) / 2)
T(a) * T(b)

Fun fact: this implementation is so golfy, it's the same length as the built-in for computing a single triangular number, PolygonalNumber.

\$\endgroup\$
8
\$\begingroup\$

C, 25 bytes

#define r(x,y)x*y*~x*~y/4

Purist version (27):

r(x,y){return x*y*~x*~y/4;}

ISO-er version (35):

#define r(x,y)((x)*(y)*~(x)*~(y)/4)
\$\endgroup\$
  • \$\begingroup\$ Which version do you think is best? \$\endgroup\$ – Erik the Outgolfer Aug 1 '16 at 10:09
8
\$\begingroup\$

Jellyfish, 16 bytes

p|%/**+1
  4  Ei

Input format is [x y], output is just the result.

Try it online!

Alternative solution, same byte count:

pm%/*[*i
  4  +1

Explanation

Time to give Jellyfish the introduction it deserves! :)

Jellyfish is Zgarb's language based on his 2D syntax challenge. The semantics are largely inspired by J, but the syntax is a work of art. All functions are single characters and laid out on a grid. Functions take their arguments from the next token south and east of them and return the result north and west. This let's you create an interesting web of function calls where you reuse values by passing them into several functions from multiple directions.

If we ignore the fact that some of tokens in the above program are special operators (higher-level functions), the above program would be written something like this in a sane language:

p(|( /*(i*(i+1)) % 4 ))

Let's go through the code bottom-up. Input gets fed in by the i, which therefore evaluates to [x y].

The + on top of it receives this input together with the literal 1 and therefore increments both elements to give [(x+1) (y+1)] (most operations are threaded automatically over lists).

The other value of i is sent left, but the E splits is eastern argument north and west. That means the inputs to the right * are actually [x y] and [(x+1) (y+1)] so this computes [x*(x+1) y*(y+1)].

The next * up is actually modified by the preceding / which turns it into a fold operation. Folding * over a pair simply multiplies it, so that we get x*(x+1)*y*(y+1).

Now % is just division so it computes x*(x+1)*y*(y+1)/4. Unfortunately, this results in a float so we need to round it with the unary |. Finally, this value is fed to p which prints the final result.

\$\endgroup\$
  • \$\begingroup\$ I could've sworn I read something in the docs about integer division... \$\endgroup\$ – Conor O'Brien Aug 3 '16 at 4:43
7
\$\begingroup\$

R, 40 35 bytes

Well, time to jump in at the deep end ! Here is my R code, inspired from @xnor answer :

a=scan();(n=a[1])*(m=a[2])*(n+1)*(m+1)/4 

EDIT : In this version, R will ask twice for inputs.

(n=scan())*(m=scan())*(n+1)*(m+1)/4
\$\endgroup\$
  • \$\begingroup\$ cat(prod(choose(scan()+1,2))) is 29 bytes. \$\endgroup\$ – Giuseppe Dec 27 '17 at 23:54
6
\$\begingroup\$

CJam, 12 10 Bytes

2 bytes saved thanks to Martin.

{_:)+:*4/}

Try it online!

This is a block that takes a list of 2 elements from the stack and leaves the solution on the stack. Usable full program for testing: riari+{_:)+:*4/}~.

Based off of xnor's outstanding python solution.

Explanation:

{_:)+:*4/}
{        } -- Define a block
 _:)       -- Duplicate list, increment all values in new list
    +      -- Join the two lists
     :*    -- Fold multiply over all 4 elements
       4/  -- Divide by 4
\$\endgroup\$
  • 2
    \$\begingroup\$ I think this works for 10 if you make input a list of two elements? {_:~+:*4/} \$\endgroup\$ – Martin Ender Aug 1 '16 at 14:07
  • \$\begingroup\$ Actually, there's no need to use ~ at all in CJam. Just use ). \$\endgroup\$ – Martin Ender Aug 1 '16 at 14:53
5
\$\begingroup\$

Matlab, 23 19 bytes

@(x)prod([x/2,x+1])

Implementation of the formula m*n*(m+1)*(n+1)/4
Usage: ans([m,n])

\$\endgroup\$
4
\$\begingroup\$

MATL, 6 bytes

tQ*2/p

Input is an array of the form [m,n].

Try it online!

Explanation

Direct computation based on the formula m*(m+1)*n*(n+1)/4.

t     % Input array [m,n] implicitly. Duplicate
Q     % Add 1 to each entry of the copy: gives [m+1,n+1]
*     % Multiply element-wise: gives [m*(m+1),n*(n+1)]
2/    % Divide each entry by 2: [m*(m+1)/2,n*(n+1)/2]
p     % Product of the two entries: m*(m+1)*n*(n+1)/4. Display implicitly
\$\endgroup\$
4
\$\begingroup\$

J, 8 bytes

2*/@:!>:

Usage:

   f =: 2*/@:!>:
   f 0 0
0
   f 3 3
36
\$\endgroup\$
4
\$\begingroup\$

Java 7, 39 38 bytes

int c(int a,int b){return~a*a*b*~b/4;}

Java 8, 26 25 19 18 17 bytes

a->b->a*~a*b*~b/4

Based on @xnor's excellent answer. Multiple bytes saved thanks to @DavidConrad. Try it here.

Test code (Java 7):

Try it here.

class M{
  static int c(int a,int b){return~a*a*b*~b/4;}

  public static void main(String[] a){
    System.out.println(c(0, 0));
    System.out.println(c(1, 1));
    System.out.println(c(3, 3));
    System.out.println(c(4, 4));
    System.out.println(c(6, 7));
  }
}

Output:

0
1
36
100
588
\$\endgroup\$
  • 1
    \$\begingroup\$ You don't need that return and a->b-> is one byte shorter than (a,b)->. \$\endgroup\$ – David Conrad Aug 1 '16 at 15:53
  • 2
    \$\begingroup\$ I don't think you need the semicolon, either, since if you were passing the lambda into a method that took a Function<Integer, Function<Integer, Integer>> as a parameter, it wouldn't be followed by a semicolon. \$\endgroup\$ – David Conrad Aug 1 '16 at 15:56
  • 2
    \$\begingroup\$ I agree with @DavidConrad : I don't count the ending ; on single statement J8 lambdas. \$\endgroup\$ – CAD97 Aug 1 '16 at 17:14
  • \$\begingroup\$ @DavidConrad Sorry for the very late edit, but I only now noticed I read past your comment to remove the return .. Also, I almost never program in Java 8 (hence all my Java 7 answers), but how do I get a->b-> to work? Here is the ideone for the current case. \$\endgroup\$ – Kevin Cruijssen Sep 21 '16 at 7:27
  • 1
    \$\begingroup\$ Sorry for the very late reply! You need to curry the function, so you need to change MathOperation.operation to take only one int, return a Function<Integer, Integer>, and when you call it, you initially pass only the first parameter, a, and then call .apply(b) on the Function. You also need to import java.util.function.Function. Here is an ideone with the changes. \$\endgroup\$ – David Conrad Oct 6 '16 at 21:14
3
\$\begingroup\$

Ruby, 22 bytes

Stealing @xnor's trick and making a stabby-lambda:

r=->(m,n){m*n*~m*~n/4}

Example call:

r[6,7]     # => 588

Or as a proc, also 22 bytes:

proc{|m,n|m*n*~m*~n/4}

Which we could then call:

proc{|m,n|m*n*~m*~n/4}.call(6,7)     # => 588
\$\endgroup\$
  • \$\begingroup\$ You don't need to name it—anonymous functions are okay as per site convention \$\endgroup\$ – Conor O'Brien Aug 3 '16 at 4:51
3
\$\begingroup\$

Labyrinth, 13 11 bytes

*?;*_4/!
):

Try it online!

Explanation

This also computes the product of the triangular numbers like most answers. The leading 2x2 block is a small loop:

*?
):

On the first iteration * doesn't do anything, so that the real loop order is this:

?   Read integer N from STDIN or 0 at EOF and push onto stack. If 0, exit the loop.
:   Duplicate N.
)   Increment.
*   Multiply to get N*(N+1).

The remaining code is just linear:

;   Discard the zero that terminated the loop.
*   Multiply the other two values.
_4  Push a 4.
/   Divide.
!   Print.

Labyrinth then tries to execute / again, which terminates the program due to a division by zero.

\$\endgroup\$
2
\$\begingroup\$

Pyke, 6 bytes

mh+Bee

Try it here!

mh     -    map(increment, input)
  +    -   ^ + input
   B   -  product(^)
    ee - ^ \ 4
\$\endgroup\$
  • \$\begingroup\$ This could use a breakdown, but I find it to be a work of art, personally. \$\endgroup\$ – corsiKa Aug 2 '16 at 22:03
2
\$\begingroup\$

05AB1E, 4 bytes

€LOP

Explanation

Uses the formula described at A096948

      # Implicit input, ex: [7,6]
€L    # Enumerate each, [[1,2,3,4,5,6,7],[1,2,3,4,5,6]]
  O   # Sum, [28,21]
   P  # Product, 588
      # Implicit display

Takes input as [n,m].

Try it online

\$\endgroup\$
1
\$\begingroup\$

Pyth, 8 6 bytes

Two bytes saved thanks to @DenkerAffe.

*FmsSd

Input is expected as a list like [m,n]. Try it out here.

Explanation:

          Implicit assignment of Q to eval(input).
*         Multiplication.
 F        Splat the following sequence onto the arguments of the previous function.
  m       Map the following function of d over Q (Q is implicitly added to the end).
   s      Reduce the following list with addition, initial value of 0.
    Sd    Return range(1,d+1).
\$\endgroup\$
  • 1
    \$\begingroup\$ You can use F instead of .* and remove the Q since it is added implictly. \$\endgroup\$ – Denker Aug 1 '16 at 10:52
  • \$\begingroup\$ I knew about F but I couldn't figure out how to use it and figured I needed to use .* instead... Thanks! \$\endgroup\$ – Rhyzomatic Aug 1 '16 at 19:42
1
\$\begingroup\$

C#, 19 bytes

(n,m)=>m*n*~m*~n/4;

An anonymous function based off of @xnor's answer.

\$\endgroup\$
1
\$\begingroup\$

Lua, 74 63 bytes

x,y=...n=0 for i=1,y do for j=i,i*x,i do n=n+j end end print(n)

Function takes input as number parameters.

Because of the way Lua is implemented, this is technically a function, with variable args, which can be called by wrapping it in a "function" statement, or loading it from source code using "loadstring"

\$\endgroup\$
  • 1
    \$\begingroup\$ I see that you have quite a lot of code there just for I/O. Perhaps it would be shorter to simply make a function that takes the two numbers and returns the answer, and remove all this unnecessary I/O code? \$\endgroup\$ – Zwei Aug 1 '16 at 17:45
  • \$\begingroup\$ @Zwei I forgot that functions are allowed to take input by parameters. Thanks for pointing that out. \$\endgroup\$ – brianush1 Aug 2 '16 at 9:51
  • \$\begingroup\$ The function could be named something like "f" instead of the whole name "function" to save 7 more bytes \$\endgroup\$ – Zwei Aug 2 '16 at 11:28
  • \$\begingroup\$ In Lua, the keyword "function" is required to declare a function. If no name is specified (ex: "function f()"), it's an anonymous function. (ex: "function()"). Therefore, the "function" is required for the code to work. \$\endgroup\$ – brianush1 Aug 2 '16 at 11:43
  • \$\begingroup\$ Oh, I forgot that lua works like that. My bad! \$\endgroup\$ – Zwei Aug 2 '16 at 11:44
1
\$\begingroup\$

Cheddar, 23 bytes

m->n->m*(m+1)*n*(n+1)/4
\$\endgroup\$
  • \$\begingroup\$ n*(n+1) can be golfed to n^2+n \$\endgroup\$ – Downgoat Aug 3 '16 at 19:57
  • \$\begingroup\$ @Downgoat What about the parentheses? \$\endgroup\$ – Leaky Nun Aug 3 '16 at 20:03
  • \$\begingroup\$ oh >_> yeah. sorry, nvm, wasn't thinking \$\endgroup\$ – Downgoat Aug 3 '16 at 20:04
  • \$\begingroup\$ try currying the function. m->n->... \$\endgroup\$ – Conor O'Brien Aug 3 '16 at 20:04
1
\$\begingroup\$

Brain-Flak, 84 80 bytes

({}<>)({({})<({}[()])>}{})<>({({})<({}[()])>}{}[()]){<>(({}))<>({}[()])}<>({{}})

Try it online!

Probably very sub-optimal, especially because of the code reuse regarding triangle numbers, but at least we have a Brain-Flak solution that works.

Sadly it seems to fail by looping infinitely with the 0 0 testcase but all others work fine.

\$\endgroup\$
0
\$\begingroup\$

Convex, 7 bytes

I know that this can be smaller, I just can't figure out how yet...

_:)+×½½

Try it online!. Uses the CP-1252 encoding.

\$\endgroup\$
0
\$\begingroup\$

APL (Dyalog), 9 bytes

×/+/∘⍳¨∘⊢

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Pyt, 3 bytes

←△Π

Explanation:

←       Get input
 △      Get triangle numbers
  Π     Array product
        Implicit output

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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