6
\$\begingroup\$

Consider an \$n \times n\$ grid and a circle of radius \$r \leq \sqrt{2} n\$ with its center in the top left. In each square there is an integer from the range -3 to 3, inclusive. For a given radius, there is a set of squares in the grid which are not at least half covered by a circle of radius \$r\$ but are at least half covered by a circle of larger radius. Your task to output the sum of the integers in those squares.

Takes this example:

enter image description here

The smaller circle has radius \$3.5 \cdot \sqrt{2}\$ and the larger circle has radius \$4.5 \cdot \sqrt{2}\$. The numbers for squares that are at least half covered by the larger circle but not the smaller one are \$1, -1, 3, 3, 2, -1, -1, 1, -3, -1, 1\$. These sum to \$4\$.

You might be wondering why the \$-1\$ number in square (4,4) is not included. If we zoom in we can see why. The blue dots are the center of the squares.

enter image description here

If we had chosen the smaller radius to be \$2.5 \cdot \sqrt{2}\$ and the larger circle has radius \$3.5 \cdot \sqrt{2}\$ then we get the sum of the values we need is \$-1\$.

enter image description here

Here is the matrix from the examples given:

  [[ 3,  0,  1,  3, -1,  1,  1,  3, -2, -1],
   [ 3, -1, -1,  1,  0, -1,  2,  1, -2,  0],
   [ 2,  2, -2,  0,  1, -3,  0, -2,  2,  1],
   [ 0, -3, -3, -1, -1,  3, -2,  0,  0,  3],
   [ 2,  2,  3,  2, -1,  0,  3,  0, -3, -1],
   [ 1, -1,  3,  1, -3,  3, -2,  0, -3,  0],
   [ 2, -2, -2, -3, -2,  1, -2,  0,  0,  3],
   [ 0,  3,  0,  1,  3, -1,  2, -3,  0, -2],
   [ 0, -2,  2,  2,  2, -2,  0,  2,  1,  3],
   [-2, -2,  0, -2, -2,  2,  0,  2,  3,  3]]

Input

A 10 by 10 matrix of integers in the range -3 to 3, inclusive and a radius \$r=\sqrt{2} (a+1/2)\$ where \$a\$ is a non negative integer. The radius input will be the integer \$a\$.

Output

The sum of the numbers in the squares in the matrix which are not at least half covered by a circle of radius \$r\$ but are at least half covered by a circle of radius \$r + \sqrt{2}\$.

These are the outputs for some different values of \$a\$ using the example matrix.

a = 0 gives output 6  ( 0 + 3 + 3)
a = 1 gives output 3  (1 + -1 + -1 + 2 + 2)
a = 2 gives output -1 (3 + -1 + 1 + 0 + -2 + -3 + -3 + +0 + 2 + 2)
a = 3 gives output 4  (1 + -1 + -3 + 1 + -1 + -1 + 2 + 3 + 3 + -1 + 1)

Accuracy

Your answer should be exactly correct. The question of which squares to include can be resolved exactly mathematically.

\$\endgroup\$
14
  • \$\begingroup\$ Is d guaranteed to be an integer, or can it be any real number? Also, what is the margin of error? is it acceptable to incorrectly include a square with 49% or 51%? That will make a huge difference to the length of the code. It would be much easier if we could include all squares that have any part of the circle in them. \$\endgroup\$ Dec 16, 2023 at 10:43
  • \$\begingroup\$ @LevelRiverSt I have made the input clear I hope. I'll add a comment about numerical accuracy m \$\endgroup\$
    – Simd
    Dec 16, 2023 at 11:28
  • 1
    \$\begingroup\$ Following my previous comment about symmetry and given your explanation why square 4,4 should not be included should square 3,3 on the grid diagonal be included to give us 11 squares with the answer dropping back to 4 \$\endgroup\$
    – Graham
    Dec 16, 2023 at 16:42
  • 2
    \$\begingroup\$ The result for a=0 should be 6; the 0.5 diameter circle only fills about 39% of the top-left grid square \$\endgroup\$ Dec 16, 2023 at 19:52
  • 1
    \$\begingroup\$ @NickKennedy Thank you. Fixed. \$\endgroup\$
    – Simd
    Dec 16, 2023 at 20:33

3 Answers 3

4
\$\begingroup\$

Jelly, 22 bytes

ŒJ_.²§<Ɱ+.+Ø.²ḤƲ}^/ḋF{

Try it online!

A dyadic link taking a 10x10 integer matrix as its first argument and an integer as its second argument and returning an integer. Doesn’t use any fractions other than halves and quarters so should not lose anything to floating point accuracy.

Uses the same methodology as @Ajax1234’s Python answer so be sure to upvote that one too!

Explanation

ŒJ_.²§<Ɱ+.+Ø.²ḤƲ}^/ḋF{­⁡​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁣‏⁠‎⁡⁠⁤‏‏​⁡⁠⁡‌⁣​‎⁠‎⁡⁠⁢⁡‏‏​⁡⁠⁡‌⁤​‎⁠‎⁡⁠⁢⁢‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁢⁣‏⁠‎⁡⁠⁢⁤‏⁠‎⁡⁠⁤⁤‏⁠‎⁡⁠⁢⁡⁡‏‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁣⁡‏⁠‎⁡⁠⁣⁢‏‏​⁡⁠⁡‌⁢⁣​‎‎⁡⁠⁣⁣‏⁠‎⁡⁠⁣⁤‏⁠‎⁡⁠⁤⁡‏‏​⁡⁠⁡‌⁢⁤​‎‎⁡⁠⁤⁢‏‏​⁡⁠⁡‌⁣⁡​‎‎⁡⁠⁤⁣‏‏​⁡⁠⁡‌⁣⁢​‎‎⁡⁠⁢⁡⁢‏⁠‎⁡⁠⁢⁡⁣‏‏​⁡⁠⁡‌⁣⁣​‎‎⁡⁠⁢⁡⁤‏⁠‎⁡⁠⁢⁢⁡‏⁠‎⁡⁠⁢⁢⁢‏‏​⁡⁠⁡‌­
ŒJ                      # ‎⁡Indices along matrix
  _.                    # ‎⁢Subtract 0.5
    ²                   # ‎⁣Square
     §                  # ‎⁤Sum inner lists
      <Ɱ       Ʋ}       # ‎⁢⁡Less than each of the following applied to the right argument as a monad:
        +.              # ‎⁢⁢Add 0.5
          +Ø.           # ‎⁢⁣Add zero and one
             ²          # ‎⁢⁤Square
              Ḥ         # ‎⁣⁡Double
                 ^/     # ‎⁣⁢Reduce using xor
                   ḋF{  # ‎⁣⁣Dot product with the flattened matrix
💎

Created with the help of Luminespire.

Alternative approach Jelly, 47 45 bytes

+1.,.²Ḥµæ._²}½÷@ÆṬ,×ʋʋ¥Ɱ⁵ŻHI+.ḞḞRŒṪfU$)ḟ/œị⁹S

Try it online!

This is a dyadic link that takes the integer a as its first argument and the 10x10 matrix as its second and returns an integer. This uses the integral of the circle equation to calculate the area in each column. This is useful on the left hand part of the quarter circle but not on the right when it’s harder to calculate which squares are partially filled. My code therefore uses symmetry to control for this. There could be floating point error, but it’s not apparent in the example used here.

The formula used for the integral of \$\sqrt{r^2 - x^2}\$ is:

\$\frac{1}{2} (x \sqrt{r^2 - x^2} + r^2 \arctan{\frac{x}{\sqrt{r^2 - x^2}}})\$

This was generated using Wolfram Alpha.

Explanation

+1.,.²Ḥµæ._²}½÷@ÆṬ,×ʋʋ¥Ɱ⁵ŻHI+.ḞḞRŒṪfU$)ḟ/œị⁹S­⁡​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏⁠‎⁡⁠⁣‏⁠‎⁡⁠⁤‏⁠‎⁡⁠⁢⁡‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁢⁢‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁢⁣‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁢⁤‏⁠‎⁡⁠⁣⁢⁣‏⁠⁠‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁢⁢⁣‏⁠‎⁡⁠⁢⁢⁤‏⁠‎⁡⁠⁢⁣⁡‏‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁣⁡‏⁠‎⁡⁠⁣⁢‏⁠‎⁡⁠⁢⁢⁢‏‏​⁡⁠⁡‌⁢⁣​‎‎⁡⁠⁣⁣‏⁠‎⁡⁠⁣⁤‏⁠‎⁡⁠⁤⁡‏‏​⁡⁠⁡‌⁢⁤​‎‎⁡⁠⁤⁢‏‏​⁡⁠⁡‌⁣⁡​‎⁠‎⁡⁠⁢⁢⁡‏‏​⁡⁠⁡‌⁣⁢​‎‎⁡⁠⁤⁣‏⁠‎⁡⁠⁤⁤‏‏​⁡⁠⁡‌⁣⁣​‎‎⁡⁠⁢⁡⁡‏⁠‎⁡⁠⁢⁡⁢‏‏​⁡⁠⁡‌⁣⁤​‎‎⁡⁠⁢⁡⁣‏⁠‎⁡⁠⁢⁡⁤‏‏​⁡⁠⁡‌⁤⁡​‎‎⁡⁠⁢⁣⁢‏‏​⁡⁠⁡‌⁤⁢​‎‎⁡⁠⁢⁣⁣‏‏​⁡⁠⁡‌⁤⁣​‎‎⁡⁠⁢⁣⁤‏‏​⁡⁠⁡‌⁤⁤​‎‎⁡⁠⁢⁤⁡‏⁠‎⁡⁠⁢⁤⁢‏‏​⁡⁠⁡‌⁢⁡⁡​‎‎⁡⁠⁢⁤⁣‏‏​⁡⁠⁡‌⁢⁡⁢​‎‎⁡⁠⁢⁤⁤‏‏​⁡⁠⁡‌⁢⁡⁣​‎‎⁡⁠⁣⁡⁡‏⁠⁠‏​⁡⁠⁡‌⁢⁡⁤​‎‎⁡⁠⁣⁡⁢‏⁠‎⁡⁠⁣⁡⁣‏⁠‏​⁡⁠⁡‌⁢⁢⁡​‎‎⁡⁠⁣⁡⁤‏⁠‎⁡⁠⁣⁢⁡‏⁠‎⁡⁠⁣⁢⁢‏‏​⁡⁠⁡‌⁢⁢⁢​‎‎⁡⁠⁣⁢⁤‏⁠‎⁡⁠⁣⁣⁡‏‏​⁡⁠⁡‌⁢⁢⁣​‎‎⁡⁠⁣⁣⁢‏⁠‎⁡⁠⁣⁣⁣‏⁠‎⁡⁠⁣⁣⁤‏‏​⁡⁠⁡‌⁢⁢⁤​‎‎⁡⁠⁣⁤⁡‏‏​⁡⁠⁡‌­
+1.,.                                          # ‎⁡Add [1.5, 0.5]
     ²                                         # ‎⁢Squared
      Ḥ                                        # ‎⁣Doubled
       µ                              )        # ‎⁤For each of these squared radii:
                      ¥Ɱ⁵                      # ‎⁢⁡- Following as a dyad using the squared radius as the left argument and each integer from 1 to 10 inclusive as the right (referred to as x below)
        æ.           ʋ                         # ‎⁢⁢  - Dot product of [the squared radius, 1] with the result of the following:
          _²}                                  # ‎⁢⁣    - Subtract x squared from the squared radius
             ½                                 # ‎⁢⁤    - Square root
                    ʋ                          # ‎⁣⁡    - Following as a dyad using the above as the left argument (called z below) and x as the right argument
              ÷@                               # ‎⁣⁢      - Divide x by z
                ÆṬ                             # ‎⁣⁣      - Arctan
                  ,×                           # ‎⁣⁤      - Paired with z multiplied by x
                         Ż                     # ‎⁤⁡- Prepend zero
                          H                    # ‎⁤⁢- Half
                           I                   # ‎⁤⁣- Increments
                            +.                 # ‎⁤⁤- Add 0.5
                              Ḟ                # ‎⁢⁡⁡- Real part of complex values; floor real values
                               Ḟ               # ‎⁢⁡⁢- Floor the real values generated from the complex values above
                                R              # ‎⁢⁡⁣- Range from 1 to each of these
                                 ŒṪ            # ‎⁢⁡⁤- Two-dimensional indices of truthy values
                                   fU$         # ‎⁢⁢⁡- Keep only those which also exist in their reversed form
                                       ḟ/      # ‎⁢⁢⁢Remove the squares captured by the smaller circle from those captured by the larger one
                                         œị⁹   # ‎⁢⁢⁣Multidimensional index into the matrix
                                            S  # ‎⁢⁢⁤Sum
💎

Created with the help of Luminespire.

\$\endgroup\$
3
  • \$\begingroup\$ +1 for using the correct integral formula. I was concerned when OP insisted on accuracy that answers would appear that didn't! An alternative to using the formula would be the following algorithm: (1) find the points where the circle cuts the square (2) calculate the area of the sector bounded by the circle perimeter and 2 lines to the origin (3) subtract the triangular areas not contained within the square. Step 2 clearly requires some kind of inverse trig operation, no matter how you do it. \$\endgroup\$ Dec 17, 2023 at 1:15
  • \$\begingroup\$ @LevelRiverSt good spot - I just put the closing parenthesis in the wrong place. The formula in the code doesn’t have that problem though! \$\endgroup\$ Dec 17, 2023 at 8:36
  • \$\begingroup\$ Very glad to see an integration based solution. \$\endgroup\$
    – Simd
    Dec 17, 2023 at 8:56
4
\$\begingroup\$

Python3, 105 bytes:

E=enumerate
f=lambda m,d:sum(v for x,r in E(m)for y,v in E(r)if(U:=x*x+x+y*y+y+1)>d*d*2 and U<(d+1)**2*2)

Try it online!

\$\endgroup\$
11
  • \$\begingroup\$ What answer are you getting for my second example? \$\endgroup\$
    – Simd
    Dec 16, 2023 at 16:17
  • \$\begingroup\$ d<dist((.5,.5),(-x,-y))<=d+2**.5. Although there should be a way of avoiding dist. \$\endgroup\$
    – Neil
    Dec 16, 2023 at 17:34
  • \$\begingroup\$ The square (3,0) should be included. The area covered is approx 0.51223. \$\endgroup\$
    – Simd
    Dec 16, 2023 at 17:34
  • \$\begingroup\$ The second example should be 3, -1, 1, 0, -2, 0, -3, -3, 2, 2 \$\endgroup\$
    – Simd
    Dec 16, 2023 at 17:39
  • 1
    \$\begingroup\$ @solid.py d*d*2<x*x+x+y*y+y+1<(d+1)**2*2. \$\endgroup\$
    – Neil
    Dec 17, 2023 at 16:23
3
\$\begingroup\$

Google Sheets, 104 bytes

=sum(makearray(10,10,lambda(x,y,isbetween(((x-0.5)^2+(y-0.5)^2)^0.5,K4,K4+2^0.5,1,)*index(A1:J10,x,y))))

Put the matrix in cells A1:J10, the integer \$a\$ in cell K4, the formula for \$r\$ =2 ^ 0.5 * (K2 + 0.5) in cell K4 and the formula in cell K7.

sum circle

The input is the matrix A1:J10 and the value \$r\$ in K4. Uses the same approximation as the Python and Jelly answers.

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