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\$
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 '20 at 21:43
  • \$\begingroup\$ @ovs—thanks for catching this! The table is updated now. \$\endgroup\$ – Peter Kagey Oct 17 '20 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 '20 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
\$\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) $$

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

\$\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!

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

\$\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!

\$\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 '20 at 22:20
  • \$\begingroup\$ I think (n,y=x=0)=>g=k=> ... +g(k) works for 56 bytes: tio.run/… \$\endgroup\$ – ovs Oct 18 '20 at 13:31
  • \$\begingroup\$ @ovs It sure does. Thank you! \$\endgroup\$ – Arnauld Oct 18 '20 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
\$\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.

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

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

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

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