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

Jelly, 4 bytes

RS€P

Try it online!

Alternatively, also 4 bytes

pP€S

Try it online!

\$\endgroup\$
5
  • \$\begingroup\$ Good job. Thumbs up. :) \$\endgroup\$
    – R. Kap
    Aug 1, 2016 at 5:31
  • 24
    \$\begingroup\$ Care to explain? \$\endgroup\$ Aug 1, 2016 at 9:11
  • \$\begingroup\$ There's also בHP and ‘c2P and maybe other 4 byte alternatives. \$\endgroup\$
    – miles
    Aug 1, 2016 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\$ Aug 2, 2016 at 20:00
  • 1
    \$\begingroup\$ @FryAmTheEggman so what your saying is.... Magic \$\endgroup\$ Aug 3, 2016 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\$
2
  • \$\begingroup\$ I'm not sure, is currying OK in languages that don't do this by default? \$\endgroup\$ Aug 2, 2016 at 10:23
  • 1
    \$\begingroup\$ @JanDvorak Meta post. \$\endgroup\$
    – Leaky Nun
    Aug 2, 2016 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\$
0
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\$
1
  • \$\begingroup\$ Which version do you think is best? \$\endgroup\$ Aug 1, 2016 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\$
1
  • \$\begingroup\$ I could've sworn I read something in the docs about integer division... \$\endgroup\$ Aug 3, 2016 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\$
1
  • \$\begingroup\$ cat(prod(choose(scan()+1,2))) is 29 bytes. \$\endgroup\$
    – Giuseppe
    Dec 27, 2017 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
  • 2
    \$\begingroup\$ I think this works for 10 if you make input a list of two elements? {_:~+:*4/} \$\endgroup\$ Aug 1, 2016 at 14:07
  • \$\begingroup\$ Actually, there's no need to use ~ at all in CJam. Just use ). \$\endgroup\$ Aug 1, 2016 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\$
1
  • \$\begingroup\$ This conversation has been moved to chat. \$\endgroup\$
    – Dennis
    Aug 3, 2016 at 7:41
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\$
6
  • 1
    \$\begingroup\$ You don't need that return and a->b-> is one byte shorter than (a,b)->. \$\endgroup\$ Aug 1, 2016 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\$ Aug 1, 2016 at 15:56
  • 2
    \$\begingroup\$ I agree with @DavidConrad : I don't count the ending ; on single statement J8 lambdas. \$\endgroup\$
    – CAD97
    Aug 1, 2016 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\$ Sep 21, 2016 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\$ Oct 6, 2016 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\$
1
  • \$\begingroup\$ You don't need to name it—anonymous functions are okay as per site convention \$\endgroup\$ Aug 3, 2016 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\$
1
  • \$\begingroup\$ This could use a breakdown, but I find it to be a work of art, personally. \$\endgroup\$
    – corsiKa
    Aug 2, 2016 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\$
2
  • 1
    \$\begingroup\$ You can use F instead of .* and remove the Q since it is added implictly. \$\endgroup\$
    – Denker
    Aug 1, 2016 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, 2016 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\$
5
  • 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, 2016 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, 2016 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, 2016 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, 2016 at 11:43
  • \$\begingroup\$ Oh, I forgot that lua works like that. My bad! \$\endgroup\$
    – Zwei
    Aug 2, 2016 at 11:44
1
\$\begingroup\$

Cheddar, 23 bytes

m->n->m*(m+1)*n*(n+1)/4
\$\endgroup\$
4
  • \$\begingroup\$ n*(n+1) can be golfed to n^2+n \$\endgroup\$
    – Downgoat
    Aug 3, 2016 at 19:57
  • \$\begingroup\$ @Downgoat What about the parentheses? \$\endgroup\$
    – Leaky Nun
    Aug 3, 2016 at 20:03
  • \$\begingroup\$ oh >_> yeah. sorry, nvm, wasn't thinking \$\endgroup\$
    – Downgoat
    Aug 3, 2016 at 20:04
  • \$\begingroup\$ try currying the function. m->n->... \$\endgroup\$ Aug 3, 2016 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 and acknowledge you have read our privacy policy.

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