# Count the Unique Rectangles!

In my last challenge, you were asked to find all rectangles given a m x n grid of them. However, it turned out to be very trivial as there actually was a mathematical formula I did not even know about to solve the problem! So now, for a little bit more of a challenge, how about calculating the number of unique rectangles, i.e. find the number rectangles that are all of different dimensions?

For example, consider 4 horizontal, or y lines at [-250,-50,50,250] and 4 vertical, or x lines at [-250,-70,70,250]. Graphing these on a coordinate plane with infinite dimensions results in the following 500 x 500 pixel closed grid, in which the length of each segment in pixels and the lines corresponding to their respected values from the arrays are shown:

which contains the 16 unique rectangles shown in this animated GIF:

However, if the topmost line (y = 250) were to be removed, there would only be 12 unique rectangles, as the top 3 rectangles would be factored out since they each won't be fully closed without the y = 250 line.

So, as shown above, the task is counting the number of rectangles rectangles with different dimensions. In other words, given an input of 2 arrays, with the first one containing all equations of all x lines, and the latter containing those of all y lines, output the total number of rectangles of different dimensions created when the lines corresponding to those equations are graphed on a coordinate plane.

## Rules

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

• If either of the arrays have less than 2 elements, the output should be 0, since if there are less than 4 lines on the plane, there are no closed, 4 sided figures.

• The input arrays are not guaranteed to be sorted.

• You can assume that there are not any repeated values in either of the the input arrays.

• A n x m rectangle is the same as a m x n rectangle. For example, a 300 x 200 rectangle is the same as a 200 x 300 one.

• Standard loopholes are prohibited.

## Test Cases

Given in the format Comma Separated Arrays Input -> Integer output:

[],[] -> 0
[-250,-50,50,250],[-250,-70,70,250] -> 16 (Visualized above)
[-250,-50,50,250],[-250,-70,70] -> 12
[-40, 40],[-80, 50] -> 1
[10],[10] -> 0
[60, -210, -60, 180, 400, -400], [250, -150] -> 12
[0,300,500],[0,300,500] -> 6
[0,81,90],[0,90,100] -> 9


Remember, this is , so shortest code wins!

• [[0,300,500],[0,300,500]] should probably be a test case – Sp3000 Aug 3 '16 at 5:43
• @Sp3000 All right. I'll add that one as soon as possible. – R. Kap Aug 3 '16 at 5:44
• @Sp3000 It's added. – R. Kap Aug 3 '16 at 7:00
• @PeterTaylor Yeah, you're right. There are 6. I forgot to count the entire square itself! It's updated now. – R. Kap Aug 3 '16 at 7:57
• @PeterTaylor Okay. Added. – R. Kap Aug 3 '16 at 10:02

# JavaScript (ES6), 99

(X,Y,Z=new Set)=>X.map(v=>X.map(t=>t>v&&Y.map(w=>Y.map(u=>u>w&&Z.add([u-w,t-v].sort()+0)))))|Z.size


Note: sort is not numeric but lexicographic, but in this specific case I don't care

Less golfed

(X, Y, Z = new Set) =>
X.map(
v => X.map(
t => t>v && Y.map(
w => Y.map(
u => u>w && Z.add([u-w, t-v].sort() + 0)
)
)
)
) | Z.size


Test

F=(X,Y,Z=new Set)=>X.map(v=>X.map(t=>t>v&&Y.map(w=>Y.map(u=>u>w&&Z.add([u-w,t-v].sort()+0)))))|Z.size

;[
[[],[], 0]
,[[-250,-50,50,250],[-250,-70,70,250], 16]
,[[-250,-50,50,250],[-250,-70,70], 12]
,[[-40, 40],[-80, 50], 1]
,[[10],[10], 0]
,[[60, -210, -60, 180, 400, -400], [250, -150], 12]
,[[0,300,500],[0,300,500], 6]
].forEach(t=>{
var a=t[0],b=t[1],k=t[2],r=F(a,b)

console.log(r==k?'OK':'KO','['+a+']','['+b+']',r)
})

# Jelly, 13 bytes

ṢIẆS€µ€ŒpṢ€QL


Try it online!

A rectangle is uniquely defined by its height and its width.

ṢIẆS€µ€ŒpṢ€QL   Main chain, argument: z

µ€         For each subarray:
Ṣ                   sort
I                  compute consecutive increments
Ẇ                 yield all substrings
S€               compute sum of each substring
Œp       Cartesian product
Ṣ€     Sort each
Q    Remove duplicates
L   Length

• Great job! +1 from me! :) – R. Kap Aug 3 '16 at 5:20
• @PeterTaylor But it does work for that input... – Leaky Nun Aug 4 '16 at 17:52
• @R.Kap, was this just because the test case was wrong? – Peter Taylor Aug 4 '16 at 18:01
• Actually, it wasn't producing any output when I entered that test case at the time, but that was because I entered it in the wrong format. My bad. It works really well for that test case. Good job. – R. Kap Aug 4 '16 at 18:31

## CJam (22 bytes)

q~{2m*::-:z0-}/m*:$_&,  Takes input as an array of arrays. Online demo, test suite ### Dissection q~ e# Parse input { e# For each of the two elements in the top-level array 2m* e# Take its Cartesian self-product ::- e# Map fold subtraction, giving the separations between lines :z e# Map absolute value 0- e# Remove 0, since trivial rectangles don't count }/ m* e# Cartesian product of the two sets of separations :$     e# Sort so that mxn === nxm
_&     e# Deduplicate
,      e# Count


# MATL, 22 bytes

"@gd&Xfo!s|]Z*!S!Xuz2/


### Explanation

"        % Implicitly input cell array of two numerical arrays. For each cell
@g     %   Push cell contents
d      %   Difference of its two entries
&Xf    %   Cell array of all substrings
o      %   Convert to numerical array, padding with zeros
!s     %   Sum of each row. Gives a row vector
|      %   Absolute value of each entry
]        % End for
Z*       % Cartesian product
!S!      % Sort each row
Xu       % Unique rows
z2/      % Number of unique rows excluding zeros. Implicitly display


Python, 208 bytes

import itertools as i
def h(x,y):
s=[]
k=[p for p in i.product(x,y)]
for j,(v,w) in enumerate(k):
for a,b in k[j+1:]:
q=sorted([abs(a-v),abs(b-w)])
if 0not in q and q not in s:s+=[q]
return len(s)