3
$\begingroup$

Take this 10 by 10 grid of numbers.

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

You can place a circle centered at any of the grid points and it can have any radius.

The task is to find a center and radius for a circle placed on the grid which maximizes the sum of the values in the grid within it.

For example, this is a non optimal solution.

enter image description here

Any part outside the grid that is covered by the circle counts zero.

Extension

As the challenge was solved quite quickly by computer based methods, here is an extension that might need more thought. What if we extend the grid to be infinite but with 0 put that at all points outside the existing 10 by 10 area?

$\endgroup$
7
  • 1
    $\begingroup$ By "within the circle" you mean strictly inside the circle and not on the border of the circle? Just to clarify. $\endgroup$
    – oAlt
    Dec 30, 2023 at 11:11
  • 3
    $\begingroup$ It kinda doesn't matter, in that if you have a circle that goes through some points exactly then a tiny increase or decrease in the radius will either unambiguously include them or unambiguously exclude them, without adding or removing any other points. $\endgroup$
    – Gareth McCaughan
    Dec 30, 2023 at 12:30
  • 1
    $\begingroup$ @oAlt It doesn't matter from the point of view of getting the best score but to be concrete let's say it includes the border of the circle. $\endgroup$
    – Simd
    Dec 30, 2023 at 13:00
  • 1
    $\begingroup$ So the circle center is not allowed to be farther away on the infinite square grid? Without that requirement I can get 29. $\endgroup$ Dec 30, 2023 at 18:03
  • 5
    $\begingroup$ Can't see how one would go ahead and conclusively solve this without a (more or less brute force) full search of the solution space, so I'm voting to close this as "Nifty exercise, but not really a puzzle". (Will of course retract my vote if someone shows a clever and/or insightful way to approach this. So far there are two answers, both offering "I wrote a program" as the only solution method.) $\endgroup$
    – Bass
    Dec 30, 2023 at 21:56

2 Answers 2

5
$\begingroup$

The maximum sum is

23,

achieved, for example, by

enter image description here

I solved the problem via integer linear programming as follows. Let $a_{ij}$ be the given value in cell $(i,j)$. Let binary decision variable $x_{ij}$ indicate whether cell $(i,j)$ is selected. Let binary decision variable $y_{ij}$ indicate whether cell $(i,j)$ is the center. Let $R$ be the (finite) set of radii, say $R=\{\sqrt k: k\in\{0,\dots,19\}\}$. For $r\in R$, let binary decision variable $z_r$ indicate whether the radius is $r$. The problem is to maximize $\sum_{i,j} a_{ij} x_{ij}$ subject to linear constraints \begin{align} \sum_{i,j} y_{ij} &= 1 \tag1\label1 \\ \sum_r z_r &= 1 \tag2\label2 \\ y_{i_0 j_0} + z_r - 1 &\le \begin{cases} x_{ij} & \text{if $(i-i_0)^2+(j-j_0)^2 \le r^2$} \\ 1 - x_{ij} &\text{otherwise} \end{cases} &&\text{for all $(i_0,j_0)$, $r$, and $(i,j)$} \tag3\label3 \end{align}

Constraint \eqref{1} selects one center. Constraint \eqref{2} selects one radius. Constraint \eqref{3} selects the cells that are within the circle.

$\endgroup$
6
  • $\begingroup$ I am not sure that is enough radii in principle although your answer looks good. $\endgroup$
    – Simd
    Dec 30, 2023 at 17:01
  • 2
    $\begingroup$ @simd The center is one of the grid points, and you can assume that at least one grid point is on the border, so you can restrict the radius to be one of the distances between grid points. $\endgroup$
    – RobPratt
    Dec 30, 2023 at 17:14
  • $\begingroup$ How long does tree optimzer take to find the maximum? $\endgroup$
    – Simd
    Dec 30, 2023 at 17:26
  • 1
    $\begingroup$ It solved in a few seconds. $\endgroup$
    – RobPratt
    Dec 30, 2023 at 17:27
  • $\begingroup$ Very cool indeed. $\endgroup$
    – Simd
    Dec 30, 2023 at 17:30
5
$\begingroup$

An optimal solution:

The sum of the numbers within this circle is 23.
enter image description here
Two cells in the first column can also be the center of a circle containing numbers with this same sum. If the center need not be on a lattice point, the circle shown can be shifted slightly and expanded to include the 2 and 1 just to the left for a sum of 26. The red line is part of a larger circle center off the grid containing a maximal sum of 29, as suggested by Pontus von Brömssen in a comment.

$\endgroup$
7
  • $\begingroup$ Very impressive! How did you do it? $\endgroup$
    – Simd
    Dec 30, 2023 at 16:48
  • $\begingroup$ This was found with a programmed search. $\endgroup$ Dec 30, 2023 at 16:55
  • $\begingroup$ Could you describe how you did it? It's not obvious $\endgroup$
    – Simd
    Dec 30, 2023 at 17:00
  • 2
    $\begingroup$ @Simd For each cell in the array, sort the array by distance from that cell, then take the sum of all cells starting with the nearest (when distance is equal, cells of lesser value are added first). The maximum partial sum attained in this process is the optimal solution. $\endgroup$ Dec 30, 2023 at 17:10
  • 1
    $\begingroup$ @Simd For the unrestricted center, i used discrete steps of 0.1 units, with the center at a distance up to 100 units. At that distance, the portion of the circle crossing the grid is essentially a straight line. $\endgroup$ Jan 10 at 15:15

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