15
\$\begingroup\$

This challenge will give you two positive integers n and k as inputs and have you count the number of rectangles with integer coordinates that can be drawn with vertices touching all four sides of the \$n \times k\$ rectangle $$ \{(x,y) : 0 \leq x \leq n, 0 \leq y \leq k\}. $$ That is, there should be:

  • at least one vertex with an \$x\$-coordinate of \$0\$,
  • at least one vertex with an \$x\$-coordinate of \$n\$,
  • at least one vertex with an \$y\$-coordinate of \$0\$, and
  • at least one vertex with an \$y\$-coordinate of \$k\$.

Example

There are \$a(5,7) = 5\$ rectangles with integer coordinates touching all four sides of a \$5 \times 7\$ rectangle:

Five examples of rectangles embedded in the 5 by 7 rectangle.

Table

The lower triangle of the (symmetric) table of \$a(n,k)\$ for \$n,k \leq 12\$ is

n\k| 1  2  3  4  5   6   7   8   9  10  11  12
---+----------------------------------------------
 1 | 1  .  .  .  .   .   .   .   .   .   .   .
 2 | 1  2  .  .  .   .   .   .   .   .   .   .
 3 | 1  1  5  .  .   .   .   .   .   .   .   .
 4 | 1  1  1  6  .   .   .   .   .   .   .   .
 5 | 1  1  1  3  9   .   .   .   .   .   .   .
 6 | 1  1  1  1  1  10   .   .   .   .   .   .
 7 | 1  1  1  1  5   1  13   .   .   .   .   .
 8 | 1  1  1  1  1   1   5  14   .   .   .   .
 9 | 1  1  1  1  1   5   1   1  17   .   .   .
10 | 1  1  1  1  1   3   1   3   1  18   .   .
11 | 1  1  1  1  1   1   5   1   5   5  21   .
12 | 1  1  1  1  1   1   1   1   5   1   1  22

This is a challenge, so the shortest code wins.

\$\endgroup\$
  • \$\begingroup\$ I get 9 distinct rectangles for n=k=5: https://ibb.co/p49WdTc. Am I missing something? I also have larger results on other (bigger) test cases, here is my result for the table. \$\endgroup\$ – ovs Oct 17 at 21:43
  • \$\begingroup\$ @ovs—thanks for catching this! The table is updated now. \$\endgroup\$ – Peter Kagey Oct 17 at 22:04
  • 1
    \$\begingroup\$ I took a shot at finding a combinatorial expression, but the best I got is: for \$k<n\$, the output is \$2C-3\$, where \$C\$ is the number of positive divisor pairs \$pq=n^2-k^2\$ with \$p\$ and \$q\$ having the same parity and both lying in the interval \$[n-k,n+k]\$. Unfortunately, the last interval condition seems to prevent a characterization in just terms of the factorization of \$n^2-k^2\$ without enumerating divisors. The condition corresponds to the inner rectangle fitting inside the outer one, rather than lying on its edges extended infinitely, a generalization that's easier to count. \$\endgroup\$ – xnor Oct 18 at 5:12

12 Answers 12

6
\$\begingroup\$

05AB1E, 10 8 bytes

LDI-*`¢O

Try it online!

Commented:

          # implicit input: [n, k]
L         # for both values take the [1..x] range
          #   [[1,...,n], [1,...,k]]
 D        # duplicate this list
  I       # push the input [n,k]
   -      # subtract this from the ranges
          #   [[1-n,...,n-n], [1-k,...,k-k]]
          #  =[[-n+1,...,0], [-k+1,...,0]]
    *     # multiply with the ranges
          #   [[1*(-n+1),...,n*0], [1*(-k+1),...,k*0]]
     `    # push all lists of this list on the stack
      ¢   # count the occurences of each value of one list in the other
       O  # sum those counts
| improve this answer | |
\$\endgroup\$
14
\$\begingroup\$

Python 2, 66 59 bytes

lambda n,k:sum(a%n*(n-a%n)==a/n*(k-a/n)for a in range(n*k))

Try it online!

Each possible rectangle inside the \$n \times k\$-rectangle can be specified by two integers, \$0 \le a \lt n\$ and \$0 \le b \lt k\$:

enter image description here enter image description here

To verify a rectangle given \$a\$ and \$b\$, it suffices to check if one angle is a right angle. To do this I take the dot product of \$\binom{b}{0}-\binom{0}{a}=\binom{-b}{a}\$ and \$\binom{k-b}{n}-\binom{0}{a}=\binom{k-b}{n-a}\$ to check whether the angle at \$\binom{0}{a}\$ is a right angle:

$$ \langle \left( \begin{matrix} -b \\ a \\ \end{matrix}\right), \left(\begin{matrix} k-b \\ n-a \\ \end{matrix} \right) \rangle = 0 \\\Leftrightarrow a\cdot(n-a)-b\cdot(k-b)=0 \\\Leftrightarrow a\cdot(n-a)=b\cdot(k-b) $$

| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

C (gcc), 63 61 bytes

Saved 2 thanks to ceilingcat!!!

s;a;f(n,k){for(s=a=n*k;a--;)s-=a%n*(n-a%n)!=a/n*(k-a/n);a=s;}

Try it online!

Port of ovs's Python answer.

| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

Scala, 65 64 60 51 bytes

n=>k=>0 to n*k-1 count(a=>a%n*(n-a%n)==a/n*(k-a/n))

Try it online!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ You can save a byte by currying (n=>k=>) \$\endgroup\$ – user Oct 18 at 19:04
  • \$\begingroup\$ You can use 1.to(n) and 1.to(k) for -2 bytes each. \$\endgroup\$ – ovs Oct 18 at 21:22
  • \$\begingroup\$ Save 9 bytes with Try it online! I just translated the python answer from @ovs. \$\endgroup\$ – Kjetil S. Oct 20 at 0:42
3
\$\begingroup\$

Charcoal, 21 bytes

NθNηIΣEθ№Eη×λ⁻ηλ×ι⁻θι

Try it online! Link is to verbose version of code. Explanation: Calculates \$ x(n-x) \$ for \$ 0 \le x < n \$ and \$ y(n-y) \$ for \$ 0 \le y < k \$ and counts the number of times an integer appears in both lists, which corresponds to the parallelogram with coordinates \$ (x, 0), (0, y), (n - x, 0), (0, k - y) \$ having 90 degree angles:

NθNη

Input \$ n \$ and \$ k \$.

IΣ

Output the total sum of all matches found.

Eη×λ⁻ηλ

Calculate \$ y(n-y) \$ for \$ 0 \le y < k \$.

Eθ№...×ι⁻θι

Calculate \$ x(n-x) \$ for \$ 0 \le x < n \$ and count how many times each integer appears in the other list.

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6),  63 58  56 bytes

Saved 2 bytes thanks to @ovs

(n,y=x=0)=>g=k=>(x=x||++y*k--&&n)&&(y*k==--x*(n-x))+g(k)

Try it online!

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Since y<k and x<n the formula is slightly more readable if you write k*y-y*y and n*x-x*x. \$\endgroup\$ – Neil Oct 17 at 22:20
  • \$\begingroup\$ I think (n,y=x=0)=>g=k=> ... +g(k) works for 56 bytes: tio.run/… \$\endgroup\$ – ovs Oct 18 at 13:31
  • \$\begingroup\$ @ovs It sure does. Thank you! \$\endgroup\$ – Arnauld Oct 18 at 13:35
2
\$\begingroup\$

Retina, 45 bytes

\d+
*
L$w`(_+) (_+)
$.`*$1=$.2*$'
m`^(.*)=\1$

Try it online! Link includes test suite. Takes space-separated inputs. Explanation:

\d+
*

Convert the inputs to unary.

L$w`(_+) (_+)

Match all substrings that contain _ _. This corresponds to all pairs of \$ 0 \le x < n \$ and \$ 0 \le y < k \$ which are represented by the unmatched parts at the beginning and end of the string $` and $' respectively while \$ n - x \$ and \$ k - y \$ are represented by $1 and $2 respectively.

$.`*$1=$.2*$'

For each pair, list the (unary) products \$ x (n - x) \$ and \$ y (k - y) \$.

m`^(.*)=\1$

Count the number of times that they are equal.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Jelly, 8 bytes

r1×ḶċⱮ/S

A monadic Link accepting a pair of integers which yields the count.

Try it online! Or see the test-suite.

How?

r1×ḶċⱮ/S - Link [n,k]
r1       - ([n,k]) inclusive range to 1 = [[n,n-1,...,1],[k,k-1,...,1]]
   Ḷ     - lowered range ([n,k]) = [[0,1,...,n-1],[0,1,...,k-1]]
  ×      - multiply = [[n×0,(n-1)×1,...,1×(n-1)],[k×0,(k-1)×1,...,1×(k-1)]]
      /  - reduce by - i.e.: f(A=[n×0,(n-1)×1,...,1×(n-1)], B=[k×0,(k-1)×1,...,1×(k-1)])
     Ɱ   -   map with - i.e.: [f(A,v) for v in B]
    ċ    -     count occurrenes (of v in A)
       S - sum
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Haskell,53 47 bytes

a#b=sum[1|x<-[1..a],y<-[1..b],x*(a-x)==y*(b-y)]

Try it online!

  • Saved 6 thanks to @ovs

We use the expression x/(b-y)==y/(a-x) which is converted to x*(a-x)==y*(b-y) to avoid modulo checks.

The expression computes the ratio between sides(the second inverted) which has to be the same to be a valid rectangle.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Perl 5, (-p -Minteger) 54 bytes

/ /;$_=grep$_%$'*($'-$_%$')==$_/$'*($`-$_/$'),1..$`*$'

Try it online! Using the same formula, and range product as ovs except the range starts from 1

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Java 8, 75 bytes

n->k->{int r=0,a=n*k;for(;a-->0;)if(a%n*(n-a%n)==a/n*(k-a/n))r++;return r;}

Port of @ovs' Python 2 answer, so make sure to upvote him!

Try it online.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Forth (gforth), 72 bytes

: f 0e over 0 do dup 0 do
2dup i - i * swap j - j * = s>f f- loop loop ;

Try it online!

Yet another port of ovs's Python 2 answer, except that it uses nested loops. Direct loop counters are much cheaper when multiple copies are needed.

Takes n k from the main stack and returns the count via the FP stack.

: f ( n k -- f:cnt )
  0e               \ setup the initial count
  over 0 do        \ outer loop (j): 0 to n-1
    dup 0 do       \ inner loop (i): 0 to k-1
      2dup         \ ( n k n k )
      i - i * swap \ ( n k i*[k-i] n )
      j - j * =    \ ( n k i*[k-i]==j*[n-j] ) Forth boolean is 0/-1
      s>f f-       \ increment count if equal
    loop
  loop
;
| improve this answer | |
\$\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.