16
\$\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.

Improve this question
\$\endgroup\$
3
  • \$\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, 2020 at 21:43
  • \$\begingroup\$ @ovs—thanks for catching this! The table is updated now. \$\endgroup\$
    – Peter Kagey
    Oct 17, 2020 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, 2020 at 5:12

12 Answers 12

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

Charcoal, 21 bytes

ＮθＮηＩΣＥθ№Ｅη×λ⁻ηλ×ι⁻θι

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:

ＮθＮη

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

ＩΣ

Output the total sum of all matches found.

Ｅη×λ⁻ηλ

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

Ｅθ№...×ι⁻θι

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\$
3
  • 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, 2020 at 22:20
  • \$\begingroup\$ I think (n,y=x=0)=>g=k=> ... +g(k) works for 56 bytes: tio.run/… \$\endgroup\$
    – ovs
    Oct 18, 2020 at 13:31
  • \$\begingroup\$ @ovs It sure does. Thank you! \$\endgroup\$
    – Arnauld
    Oct 18, 2020 at 13:35
3
\$\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 occurrences (of v in A)
       S - sum
Improve this answer
\$\endgroup\$
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\$
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
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\$
1
\$\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\$
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\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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