20
\$\begingroup\$

This problem will have you analyzing circles drawn on the grid, with the gridlines drawn at integer values of \$x\$ and \$y\$.

Let \$\varepsilon\$ be a very small number (think, \$\varepsilon = 0.0001\$). If we paint a filled-in circle of radius \$\varepsilon\$ centered at the origin, it will require paint to be in \$4\$ boxes; painting a circle of radius \$1 + \varepsilon\$ will send the paintbrush to \$12\$ different boxes (second, red circle); painting a circle of radius \$\sqrt 2 + \varepsilon\$ will send the paintbrush to \$16\$ different boxes (third, green circle).

There's no way to draw a circle based at the origin that lives in exactly \$13\$ or \$14\$ or \$15\$ boxes, so the possible number of boxes that a circle can live in is given by [4, 12, 16, ...].

Circles based at the origin containing 4, 12, 16, ... boxes

Rules

This challenge will give you a point \$(x,y)\$ on the plane consisting of two rational numbers \$x\$ and \$y\$. Your job is to output the first sixteen (or more!) terms of the sequence consisting of all numbers \$b\$ such that there is a way to draw a circle centered at \$(x,y)\$ that contains a part of exactly \$b\$ boxes.

Any reasonable input is allowed: you can take the center point as a pair of floats, a complex number, a list containing numerators and denominators in some order, etc.

This is a challenge, so the shortest code wins.

Examples

In my example, the inputs are written as pairs of rational numbers. The first entry in the table is illustrated above.

[input]    | [output]
(x, y)     | sequence
-----------+----------------------------------------------------------------------
(0/1, 0/1) | 4, 12, 16, 24, 32, 36, 44, 52, 60, 68, 76, 80, 88, 104, 112, 120, ...
(5/1, 5/2) | 2,  6,  8, 12, 16, 20, 22, 26, 34, 38, 40, 44, 48,  52,  56,  60, ...
(1/3, 8/1) | 2,  4,  6,  8, 10, 12, 14, 18, 20, 22, 24, 26, 28,  30,  32,  34, ...
(1/2, 3/2) | 1,  5,  9, 13, 21, 25, 29, 37, 45, 49, 61, 69, 77,  81,  89,  97, ...
(1/3,-1/3) | 1,  3,  4,  6,  8,  9, 11, 13, 15, 17, 19, 21, 22,  24,  26,  29, ...
(1/9, 8/7) | 1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13,  14,  15,  16, ...

(If it helps, the first example is given by \$4\$ times A000592.)

\$\endgroup\$
8
  • 2
    \$\begingroup\$ May \$x\$ or \$y\$ be negative? (If yes, it may be worth adding a test case.) \$\endgroup\$ – Arnauld Jan 8 at 9:14
  • 4
    \$\begingroup\$ As a follow up to my previous comment: it might be easier to just have both x and y in [0,1), as it doesn't change anything to the box counting as far as I can tell. \$\endgroup\$ – Arnauld Jan 8 at 14:08
  • \$\begingroup\$ @Arnauld, \$x\$ and \$y\$ can be negative, and I've added a test case. Your observation is correct, so a program could transform \$x\$ and \$y\$ "mod \$1\$" without any change in output. \$\endgroup\$ – Peter Kagey Jan 8 at 19:07
  • \$\begingroup\$ A big part of me wants to golf this; a bigger part of me can't even remotely fathom where to go after figuring out how to generate A000592 \$\endgroup\$ – Zaelin Goodman Jan 8 at 19:12
  • 2
    \$\begingroup\$ @Xcali Borders don't need to be defined. Suppose we have a circle which is tangent to some border(s). If borders are excluded, when we increase the radius of the circle by a small amount, it still intersects all squares which it already intersected, but also intersects all other squares which share one of those borders (and no more). If borders are included, when we decrease the radius the circle can still intersect all squares which it already intersects, but without touching any of those borders. \$\endgroup\$ – att Jan 8 at 21:08
4
\$\begingroup\$

MATL, 51 50 bytes

p-9:9*tJ*!+1ei1GP*1Gp\tFF5Mth3$v-!Z}J*!+u-|X<S&Y'Ys

The input consists of an array containing the denominators followed by an array containing the numerators. The output may contain more than 16 terms.

Try it online! Or verify all test cases (with output trimmed to 16 terms for convenience)

Explanation

Let (x, y) be the input values modulo 1. The code checks the distance from the (x, y) to each square with lower left corner (a, b), where a and b are integers. To do that, 9 points of the square are tested: (a+m,b+n) with m = 0, x, 1 and n = 0, y, 1, and the minimum of the 9 distances is kept.

A grid of 19×19 squares with a, b = −9, −8, ..., 9 is generated. The distance from (x, y) to each square is computed as described in the preceding paragraph. The 361 distances are sorted and run-length encoded, and the cumulative sum of the run lengths is the desired output.

To keep floating-point issues as controlled as possible, instead of using the actual values for x, y, a, b, m, n, the code uses those values multiplied by the product of the two input denominators.

p       % Implicit input: array with the denominators. Product
-9:9    % Push [-9, -8, ... 9]
*       % Multiply, element-wise
tJ*     % Duplicate, multiply by j (imaginary unit) element-wise
!+      % Transpose, add with broadcast. This generates the 19×19 grid of
        % complex values
1e      % Linearize into a row vector
i       % Input: array with the numerators
1GP     % Push first input again. Flip it
*       % Multiply, element-wise
1Gp     % Push first input again. Product (*)
\       % Modulo, element-wise (**)
t       % Duplicate
FF      % Push [0 0]
5Mth    % Push (*) again. Duplicate, concatenate with itself horizontally
3$v     % Concatenate three elements vertically. Gives a 3×2 matrix
-       % Subtract (*) with broadcast
!       % Transpose. The result is a 2×3 matrix
Z}      % Split into two rows with 3 elements
J*      % Multiply by j (imaginary unit) element-wise
!+      % Transpose, add with broadcast. This gives a 3×3 matrix with the
        % 9 points to be considered in each square
u       % Unique. This gives a column vector with the (unique) values
-|      % Subtract with broadcast, absolute value. Gives a 9×361 matrix
X<      % Minimum of each column. This gives the 361 distances
S       % Sort
&Y'     % Run-length encoding, producing only the run lengths
Ys      % Cumulative sum. Implicit display
\$\endgroup\$
7
\$\begingroup\$

PowerShell, 317 313 305 298 281 274 231 221 210 207 195 181 136 126 111 109 108 bytes

-an enormous 94 bytes thanks to mazzy!

I must say, I never expected to beat Charcoal in this challenge; and when I posted that 317 byte answer, I certainly never expected to get it all the way down to the low 100s. I'm hopeful I can shave those final 10 to get to sub-100, but this feels so very optimized!

Takes the x and y offsets (center of the circle) as inputs. Generates all points in the range (-9..9,-9..9), then adds points for potential border intersections, which handles offset circles, and handles doubling point values on x,0 or 0,y coordinates when the circle is centered on the origin. Groups all of those points by their squared distance from the origin, then for each group outputs the sum of the group's count and the counts of all groups with distance smaller than that group. Multiplies all of the squared distances by 1e7 then casts to Integer to avoid issues with floating points.

Because it groups the distances, it does output more than the first 16 terms, but as the challenger stated that this is acceptable, the TIO link truncates the output to the first 16 terms to make it more clear which tests succeed.

$x,$y=$args|%{,(-9..9+($p=$_%1)|%{($t=$_-$p)*$t*1e7})}
$x|%{$n=$_;$y|%{[Int]($n+$_)}}|group|% c*|%{($s+=$_)}

Try it online!

Ungolfed

At this point, the ungolfed solution is more a representation of the logic behind my solution than it is an ungolfed version of the solution - as the iterations have been made, I haven't been able to keep up with the changes on the ungolfed version. I am leaving it in here, despite the discrepancy, in hopes that it will inspires to answer in their language of choice (or port it to their language)


#Take the x-offset, y-offset, and starting radius as a parameter
#radius starts at 0, so that the first element will be the count of points on the origin of the circle
param($xOffset,$yOffset,$radius=0)
#set the x and y offsets to be in the range [0,1)
$xOffset=$xOffset % 1
$yOffset=$yOffset % 1
#do 16 times (for the required 16 elements)
1..16|%{
	#make an array of points
	$points = @()
	#set our limits to the edge of the bounding box of the circle
	#this will normally be within 1 of the actual circle, but offsets of .5
	#will increase the search space due to .NET's banker's rounding
	$upperSearchLimitX = [Int]($xOffset+$radius+1)
	$lowerSearchLimitX = -$upperSearchLimitX 
	$upperSearchLimitY = [Int]($yOffset+$radius+1)
	$lowerSearchLimitY = -$upperSearchLimitY 
	#generate x and y for every combination of values in those ranges
	$lowerSearchLimitX..$upperSearchLimitX | %{
		$x = $_
		$lowerSearchLimitY..$upperSearchLimitY | %{
			$y = $_
			#add the point to our list
			$points+=@{x=$x;y=$y}
			#If x is zero, also add a special point that represents a border intersection to the list
			#this will also make x,0 points count for two when the center is at 0,0
			if (!$x) {
				$points+=@{x=$x+$xOffset;y=$y}
			}
			#If y is zero, also add a special point that represents a border intersection to the list
			#this will also make 0,y points count for two when the center is at 0,0
			if (!$y) {
				$points+=@{x=$x;y=$y+$yOffset}
			}
		}
	}
	#add the center point to the list
	$points += @{x=$xOffset;y=$yOffset}
	#set the minimum point as the closest point to our current circle that's outside of the bounds of the circle
	$minimum =	$points|?{ 
				($_.distance=[Math]::Sqrt(($_.x-$xOffset)*($_.x-$xOffset)+($_.y-$yOffset)*($_.y-$yOffset))) -gt $radius
			}|sort distance -t 1
	#set our new radius to be that point's distance from the x offset
	$radius = $minimum.distance
	#count the number of points that lie inside (but not on the boundary of) this new circle, output implicitly
	@($points|?{$_.distance -lt $radius}).Count
}

Try it online!

I'm not the best at making images; if anyone can recommend a good tool for things like these, let me know. But here's a rough sketch of all the points that get checked along with the order we iterate to them in for x=3/8, y=1/4

First 9 iterations

\$\endgroup\$
7
  • 1
    \$\begingroup\$ @mazzy not sure about getting rid of the double loop, having trouble getting it to generate the right point set in as few bytes as I do here; that bit of wizardry might just be outside my skill set, but you always surprise me with your iterations on my golfs! Unfortunately, for replacing the -1 and +1 with r =1; that will work for the first iteration, but kind of breaks down after that from my testing. Always happy to be proved wrong with both of those ideas though! :) I've been staring at this so long, I might just be too stuck on the current method to figure out those changes \$\endgroup\$ – Zaelin Goodman Jan 9 at 3:40
  • 1
    \$\begingroup\$ @mazzy thanks! And thanks again for all your saves! Reusing $a was something I had done very early on, but it didn't work on that particular version of the code; now that I've eliminated [Math]::Floor and [Math]::Ceil in favor of integer casts it finally works! \$\endgroup\$ – Zaelin Goodman Jan 9 at 7:23
  • \$\begingroup\$ Awesome! \(^-^)/ \$\endgroup\$ – mazzy Jan 10 at 6:08
  • 1
    \$\begingroup\$ @mazzy very, very nice! But there was room for improvement yet ;) \$\endgroup\$ – Zaelin Goodman Jan 13 at 21:59
  • \$\begingroup\$ 97 bytes!, sqrt->[double] \$\endgroup\$ – mazzy Jan 14 at 14:34
6
\$\begingroup\$

Charcoal, 117 bytes

NθNηNζNε≧×εθ≧×ηζ≧×ηε≔⁰ηW‹Lυ¹⁶«≔⟦⟧δF…·±ηηF…·±ηηF¬›ΣX⟦κλ⟧²ηF…·÷⁺θκε±÷⁺θκ±εF…·÷⁺ζλε±÷⁺ζλ±εF¬№δ⟦νξ⟧⊞δ⟦νξ⟧F¬№υLδ⊞υLδ≦⊕η»Iυ

Try it online! Link is to verbose version of code. Takes input as numerator denominator numerator denominator. Explanation:

NθNηNζNε

Input the co-ordinates.

≧×εθ≧×ηζ≧×ηε

Increase the scale of the grid so that the gridlines are drawn at intervals given by the product of the denominators.

≔⁰η

Start enumerating circles with radius \$ \sqrt h + ε \$.

W‹Lυ¹⁶«

Repeat until 16 box counts have been found.

≔⟦⟧δ

Start with an empty list of boxes.

F…·±ηηF…·±ηη

Search points with a distance of up to and including \$ h \$ both horizontally and vertically.

F¬›ΣX⟦κλ⟧²η

Skip points whose distance from the desired point is greater than \$ h \$.

F…·÷⁺θκε±÷⁺θκ±εF…·÷⁺ζλε±÷⁺ζλ±ε

Consider all boxes touching this point.

F¬№δ⟦νξ⟧⊞δ⟦νξ⟧

Add the box to the list of boxes if it's not already present.

F¬№υLδ⊞υLδ

Add the count of boxes to the list of box counts if it's not already present.

≦⊕η

Move on to the next radius.

»Iυ

Print all of the box counts found.

\$\endgroup\$
2
\$\begingroup\$

Perl 5, 225 bytes

sub f{my($x,$y,@a,@r,%b,$n,$i)=(@_,map{[cos,sin],[-cos,sin],[cos,-sin],[-cos,-sin]}map$_/12.566,0..720);while(@r<16){$n+=2e-3;$b{int$x+$n*$$_[0]+1e4,int$y+$n*$$_[1]+1e4}++for@a;$b=keys%b;$i=0,push@r,$b if$b>$r[-1]&&$i++>1}@r}

Try it online!

All brawn and no brain, but the 5 given tests passes in about 11 seconds at link above. It's easy to find new tests that will fail. The function f starts at the given input (x,y) and circles around in ever wider circles counting boxes it falls into. To be (almost) sure it found all boxes it needs two rounds for a new number of boxes to be registered into the return array @r. This solution is bound to have floating point "rounding errors" and "over- or understepping" when the radius is increased. To solve this properly I'd try to sort the distances of the edges of the close by boxes, but I'm too lazy to even think about that now.

sub f{
  my($x,$y,@a,@r,%b,$n,$i)=
    ( @_, map {[cos,sin],[-cos,sin],
               [cos,-sin],[-cos,-sin]}
          map $_/12.566, 0..720 );     #12.566 ~ 4*π
  while(@r<16){                        #repeat until 16 elems found
    $n+=2e-3;                          #increase radius
    $b{ int$x+$n*$$_[0]+1e4,           #keys of dict b contains found boxes
        int$y+$n*$$_[1]+1e4 }++        #+1e4 to avoid rounding up for x<0 or y<0
      for @a;                          #for all angles tested
    $b=keys%b;                         #b = number of boxes so far
    $i=0, push@r,$b                    #register b in solution if
      if !@r || $b > $r[-1] && $i++ > 1#it's > last number and if it's
                                       #found at least twice
  }
  @r                                   #return the 16 counts found
}
\$\endgroup\$
3
  • \$\begingroup\$ This solution looks cool, but I don't get any of it! Would you mind adding a bit of explanation for the less Perl-minded? \$\endgroup\$ – Zaelin Goodman Jan 9 at 4:35
  • \$\begingroup\$ @ZaelinGoodman – thx, added some text now \$\endgroup\$ – Kjetil S. Jan 9 at 4:58
  • \$\begingroup\$ Thanks! Great solution! I couldn't get brute force to work, myself, but I was hoping somebody would find a good way to do it! \$\endgroup\$ – Zaelin Goodman Jan 9 at 8:01
2
\$\begingroup\$

Javascript, 199 bytes

My first code golf in a long time!

I originally started with a brute force solution, but couldn't get the step sizes small enough to have it produce the correct answers in a timely manner. So here's a more elegant solution that iterates points in a similar fashion to Zaelin's answer.

(x,y)=>{b={0:1};g=w=>b[d=parseInt(w*1e7)]=1+(b[d]|0);for(u=x%1-9;++u<9;){g(u*u);for(v=y%1-9;++v<9;)g(u*u+v*v)||u+1<9||g(v*v)}s=0;return Object.keys(b).sort((a,b)=>a-b).map(v=>(s+=b[v])).slice(0,16)}

Try it online!

Ungolfed

(x, y) => {
  b = { 0: 1 };             // initialize a map for the lengths
  g = (w) => {              // function g is used to add to the map
    d = parseInt(w * 1e7);  // avoid floating point rounding errors
    b[d] = 1 + (b[d] | 0);  // increment point with length d
  }
  for (u = (x % 1) - 9; ++u < 9; ) {    //loop over "u" coordinates
    g(u * u);                           // add horizontal line
    for (v = (y % 1) - 9; ++v < 9; )    // loop over "v" coords
      g(u * u + v * v);                 // add corner
      (u + 1 < 9) || g(v * v);          // add vertical line (but only once per above for loop)
  }
  s = 0;                        // sum of circles up to this point
  return Object.keys(b)
    .sort((a, b) => a - b)
    .map((v) => (s += b[v]))    // aggregate number of circles visited
    .slice(0, 16);        // first 16 terms only
};

It relies on the fact that every new vertical, horizontal and corner node found represents exactly one new grid square found. Note that the x=0 or y=0 cases do not have to be treated specially, it just means that we hit a node and a vertical/horizontal line at the same time, which represents the multiple new grid squares hit.

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