Lenticular Circles

[CajunCenturion]

Problem link:

http://projecteuler.net/index.php?section=problems&id=295

Circle one is centered on (0, 0) with radius r[sub]1[/sub]
Circle two is centered on (x[sub]2[/sub], y[sub]2[/sub]) with radius r[sub]2[/sub]
The equations of our two circles are:
x[sup]2[/sup] + y[sup]2[/sup] = r[sub]1[/sub][sup]2[/sup]
(x - x[sub]2[/sub])[sup]2[/sup] + (y - y[sub]2[/sub])[sup]2[/sup] = r[sub]2[/sub][sup]2[/sup]

The distance between (x[sub]1[/sub], y[sub]1[/sub]) and (x[sub]2[/sub], y[sub]2[/sub]) is
D = SQR( (x[sub]2[/sub] - x[sub]1[/sub])[sup]2[/sup] + (y[sub]2[/sub] - y[sub]1[/sub])[sup]2[/sup] )
There are no solutions if
[li]D = 0 - the circles are coincident[/li]
[li]D > r[sub]1[/sub] + r[sub]2[/sub] - the circles do not intersect.[/li]
[li]D < ABS( r[sub]1[/sub] + r[sub]2[/sub]) - one circle is inside of the other and they do not intersect.[/li]

Next step is to find the two intersection of the two circles. We have the two circle equations and two unknowns, and this is going to get messy, but we can solve them simultaneously and we'll get out two intersection points
(x[sub]3[/sub], y[sub]3[/sub])
(x[sub]4[/sub], y[sub]4[/sub])

Once we have those two pairs, we know that either
ABS(x[sub]3[/sub] - x[sub]4[/sub]) = 1
or
ABS(y[sub]3[/sub] - y[sub]4[/sub]) = 1

And of course, all point coordinates are integers.
It's a start.




--------------
Good Luck
To get the most from your Tek-Tips experience, please read
FAQ181-2886
As a circle of light increases so does the circumference of darkness around it. - Albert Einstein

 

[Olaf Doschke]

What I did was simply using SQL, creating the circles by scanning lattice points:

#Define N 10
Ns=N^2

Create Table LatticePoints (Rs Int, X Int, Y Int)

For j=0 to N
  For i=Max(1,j) to N
    rs = i^2+j^2
    If rs<=Ns
       Insert Into LatticePoints Values (rs, i, j)
    EndIf
  EndFor
EndFor

Each record then stands for up to 8 coordinates (i,j),(i,-j),(-i,j) and (-i,-j), (j,i).... intersection points of the circle. There can of course be more than one record per radius.

I then determine chords by matching records with same rs and computing variants of dx,dy via x and y of both records (including self matches), only storing chords with dx>0 and dy>=x.

That brute force way I don't miss anything. In fact I limit the usage of the stored i,j to compute positve dx and dy, which reduces computing time, but that's not so important. This results in a table Chords with R,dx,dy,x,y, which are radius, dx and dy of the chord and starting point x,y of the chord.

Chords define half lenticlar hole areas between the chords themselve and the circle arc. These are then filtered by checking lattice points along the chord line on the side towards the arc in a "line draw" algorithm. If any of those lattice points other than start and end point has a distance < r towards the center (0,0), the chord disqualifies.

I then match two circles by their chords by matching equal dx and dy via

Select c1.R as R1, c2.*
  from Chords c1 
  left join Chords c2 on c1.R<=c2.R 
  and c1.dx=c2.dx and c1.dy=c2.dy

And afterwards Select distinct r1,r to determine the number of lenticular holes.

All this takes 0.3 seconds for N=100. But for N=100000 I fail due to table size limits, I'll change towards MySQL or SQL Server and then should be good.

Bye, Olaf.

 

[Olaf Doschke]

Olaf, I feel you have already eliminated some circles by some process.

Yes, indeed those chords are what remains after eliminating chords belonging to lenticular holes enclosing lattice points.

In conjunction with the radius of the circle a chord belongs to, you can eliminate a chord without knowing the second circle in advance, as you can split a lenticular whole in it's two halves, but you need the combination of chord length and radius, with chords alone you can only eliminate those having a lattice point on them.

Before the elimination I get 794 chord lengths of which many eliminate fully. root106 for example has 9 circles, but does only work within one radius, I assume the largest one.

Bye, Olaf.

 

[kwbMitel]

L(100,000) is not being as difficult as I thought. Much fewer valid chord lengths than I first thought.

I'm Grouping my Chord Lengths by family according to the difference in coordinates on the Y (Horizontal) Axis

The X and Y axis coordinates are always odd integers in separation from 1 another.

Family 1 (Y+1) is root(2,10,26,50,82,122,170,226,290,362,442,530,626)
These circles all combine with each other and have no minimum size.
Total Combinations = 34204

Family 2 (Y+3) is root (34,58,130,178)
Minimum size applies
Total combinations = 2098

I haven't yet checked for duplicates between these.

More to come.

**********************************************
What's most important is that you realise ... There is no spoon.

 

[kwbMitel]

[tt]Family 1 = 34204 Holes From 552 Circles
Family 2 = 2098 Holes From 110 Circles
Family 3 = 954 Holes From 74 Circles

More details as follows:

Family 1 breakdown on request

Family 2 (Y+3) is root (34,58,130,178)
Minimum Radius size applies (root of)
34 = 697 (50 Circles, 1275 Holes)
58 = 2465 (36 Circles, 666 Holes)
130 = 31265 (13 Circles, 91 Holes)
178 = 31432 (11 Circles, 66 Holes)
Total Holes = 2098

Family 3 (Y+5) is root (74,106,146,194)
Minimum Radius size applies (root of)
74 = 2257 (32 circles, 528 Holes)
106 = 5989 (24 Circles, 300 Holes)
146 = 19345 (15 Circles, 120 Holes)
194 = 81040 ( 3 Circles, 6 Holes)
Total Holes = 954

Total Holes so far = 37256
Total Duplicate Circles = 34

Grand total so far = 37222

Unfortunately, got to call it a day, work to do[/tt]

**********************************************
What's most important is that you realise ... There is no spoon.

 

[kwbMitel]

Going faster now, less to check

Family 4 (Y+7) is root (130,170,218,274)
Minimum Radius size applies (root of)
130 = 12 (32 circles, 78 Holes)
170 = 7 (24 Circles, 28 Holes)
218 = 7 (15 Circles, 28 Holes)
274 = 3 ( 3 Circles, 6 Holes)
Total Holes = 140

20 More duplicate circles (54 duplicates total)

Total holes now:34150

**********************************************
What's most important is that you realise ... There is no spoon.

 

[kwbMitel]

Sorry for wasting space. I just realized I set my limit at R = Root(100000) not R = 100000

%#&!#$&#$&^#%!!!!

**********************************************
What's most important is that you realise ... There is no spoon.

 

[kwbMitel]

Reset -

Now set my limit correctly.

Family 1 = 3087148000 Holes
The longest Chord is 199810 (447 X 1)
Total Circles = 312060

Without having a way to calculate the minimum radius for the other chord length families, I think I'm back to observation.

I can provide the chord lengths, any takers?

**********************************************
What's most important is that you realise ... There is no spoon.

 

[kwbMitel]

I'm still working on this but at the rate I'm going I'm 1 to 2 weeks away from completing.

I'm noticing some unusual patterns in the minimum radius length as my chord length and angle increases.

For example.
- Chord length 99 X 17
- Smallest R = root 125126
- Minimum R = 13425375625 (too big)

The next increment is 101 X 17
- Smallest R = Root 131125
- Minimum R = 903634825 (an order of magnitude smaller)

Just a heads up, If your using chord lengths as your guide, don't stop incrementing when you reach the first circle length that fails.

97 X 17 is the first one that fails
137 X 17 is the last one that succeeds.

The difference between the 2 is how far from the chord end points is the nearest lattice point proximity to the chord. If it is near the center of the chord the circle needs to be bigger than if it is nearer 1 end.

**********************************************
What's most important is that you realise ... There is no spoon.

 

[jges]

I'm glad you posted yesterday, I was afraid everyone had cracked this nut and moved on except me! I haven't had much spare time to give this problem, I'm slowly catching up to you guys. One thing I have found is an equation to find the minimum radius circle for a chord length of the form sqrt(k^2 + 1^2) where k can be an odd integer >= 1. These are the chords of the form delta x = 1 (the ones we know contain no lattice points).

The equation is: r = (k^2 + 1)/2

So instead of finding chord lengths, I'm asserting a chord length and finding circles. For example, if k = 3 (chord length sqrt(10)) the minimum radius = 5. This circle (centered at (0,0) passes through point (5,0). To find the next circle with the same chord length add k to the x coordinate and 1 to the y coordinate. So the next circles that have the same chord length pass through (8,1), (11,2), (14,3), etc
If k = 5 (chord length sqrt(26)), the minimum radius is 13 and the circle passes through (13,0). The next circles pass through (18,1), (23,2), (28,3), etc. You can keep incrementing the circle size until the radius is larger than the specified maximum.

I'm looking for a general form of the chord length / minimum radius equation, but no luck so far. But if you know a circle a chord passes through you can add the chord delta x, delta y to get the next circle. For instance: the chord with length sqrt(7^2 + 3^2) passes through the circle (centered at (0,0)) that passes through (12,1) (not useful since it contains lattice points). The next circles with the same chord length passes through (19,4) [(12+7, 1+3)], (26,7), etc. The first one that doesn't contain lattice points passes through (47,16).

I still don't have a way to calculate if the chord contains lattice points.

 

[Olaf Doschke]

I'm also not finished with this. Had little time to optimize my approach. I needed to stop my brute force approach as the initial collection of (i,j,radius^2) with j<i<N would grow to about 200 GB. Doable, but would take some time, while many of the circles will not work anyway.

Bye, Olaf.

 

[kwbMitel]

Jgres - Definitely still working on it. Getting more efficient but still way too much manual work.

With respect to the minimum circle size. For all chords where the y axis offset is 1, All circles that can contain that chord can be counted (no minimum). I am not looking for the "Smallest" circle but I am looking for the minimum circle from all valid circles that will not contain a lattice point. This is very hard for me without a formula.

So far I've calculated all of the circles for Y offset of 1, 3, 5, 7...23.

It appears that the upper cutoff for Y offset is around 130's (139 is the highest X value found so far) It may actually be much less than the X value (Around 100) but I won't know until I get there.

I can provide my values for minimum circle sizes for each Chord length if anyone want to help me find a formula. In the mean time, the patterns I'm finding are self correcting and I need to spot check less and less the further I go Hopefully I'll have a breakthru soon.

I figure I have about 20 hours before I'll have a number

**********************************************
What's most important is that you realise ... There is no spoon.

 

[kwbMitel]

Got 25, 27 and 29 done.

And I finally have the beginnings of a pattern in determining the Minimum Circle size within a range.

Should start going faster again.

Largest X Axis offset so far is 173

**********************************************
What's most important is that you realise ... There is no spoon.

 

[jges]

I have some code that will determine the minimum radius for a given chord length. It is by no means elegant but seems to work. My method is to determine the closest lattice point to the chord (brute force loop, could be optimized a bit), then calculate the circle that passes through the chord end points and the closest point. Note that this minimum radius circle returned is most likely not a candidate for a solution since it's center point will most likely not coincide with a lattice point (the next candidate circle larger than this one will not contain any lattice points). Here is the code for those interested (in VBScript form so anyone on Windows XP or later can run it; copy it to notepad, save it and change the extension from .txt to .vbs). You will need to enter chordX and chordY (near the top of the file) for your chord of interest.

Set objFSO = CreateObject("scripting.filesystemobject")
'Set objDistances = objFSO.CreateTextFile("distances.log", True)

''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
' enter values for chord length. Length = sqrt(chordX^2 + chordY^2)
' for chord length sqrt(106) chordX = 5, chordY = 9
chordX = 5
chordY = 9
''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''

minX = 1000
minY = 1000
minDistance = 1000

For i = 0 to chordX
	For j = 0 to chordY
		distance = DistToSegment(i, j, chordX, 0, 0, chordY)
		'objDistances.WriteLine(i & "," & j & vbtab & distance)
		if distance < minDistance and distance <> 0 then
			minX = i
			minY = j
			minDistance = distance
		end if
	next
next
'objDistances.WriteLine()
'objDistances.WriteLine(chordX & ",0" & vbtab & "0," & chordY & vbtab & minX & "," & minY)
'objDistances.close
'wscript.echo("minX: " & minX & vbcrlf & "minY: " & minY)

p1X = chordX
p1Y = 0
p2X = 0
p2Y = chordY
p3X = minX
p3Y = minY

ma = (p2Y - p1Y)/(p2X - p1X)
mb = (p3Y - p2Y)/(p3X - p2X)
centerX = (ma * mb * (p1Y - p3Y) + mb * (p1X + p2X) - ma * (p2X + p3X))/(2 * (mb - ma))
centerY = - (1/ma)*(centerX - (p1X + p2X)/2)+(p1Y + p2Y)/2
radius = sqr((p1X - centerX)^2 + (p1Y - centerY)^2)

wscript.echo("minimum radius: " & radius)

'**************************************************************************************************
Function DistToSegment(px, py, X1, Y1, X2, Y2)
Dim dx
Dim dy
Dim t

    dx = X2 - X1
    dy = Y2 - Y1
    If dx = 0 And dy = 0 Then
        ' It's a point not a line segment.
        dx = px - X1
        dy = py - Y1
        near_x = X1
        near_y = Y1
        DistToSegment = Sqr(dx * dx + dy * dy)
        Exit Function
    End If

    ' Calculate the t that minimizes the distance.
    t = ((px - X1) * dx + (py - Y1) * dy) / (dx * dx + dy * dy)

    ' See if this represents one of the segment's
    ' end points or a point in the middle.
    If t < 0 Then
        dx = px - X1
        dy = py - Y1
        near_x = X1
        near_y = Y1
    ElseIf t > 1 Then
        dx = px - X2
        dy = py - Y2
        near_x = X2
        near_y = Y2
    Else
        near_x = X1 + t * dx
        near_y = Y1 + t * dy
        dx = px - near_x
        dy = py - near_y
    End If

    DistToSegment = Sqr(dx * dx + dy * dy)
End Function

 

[kwbMitel]

jgres - Very good. That helps a bit. Now, if it could output a range of numbers based on incementing either the x or y axis in a format that I can cut and paste then we might have something really useful.

One problem. It outputs values for chord lengths that do not work. E.g. X= 5, Y = 25. This is a multiple of X=1, Y=5 and as such cannot have a valid Circle as the chord passes directly thru multiple lattice points.

**********************************************
What's most important is that you realise ... There is no spoon.

 

[Olaf Doschke]

I have done another approach on finding lattice points within half lenticular holes. Taking a circle with center (0,0) and two intersection points.

Let (sx,sy) be one of the intersection points, dx and dy the difference so that (sx+dx,sy+dy) is the endpoint of the chord. Of course sx[sup]2[/sup]+sy[sup]2[/sup] = r[sup]2[/sup] and (sx+dx)[sup]2[/sup]+(sy+dy)[sup]2[/sup] = r[sup]2[/sup].

Because of the symmetry you can always rotate the points, so that dy>0 and dx>=dy, so the slope 0<dy/dx<1 is between 0 and 1 and also the arc of the circle is below the chord.

The starting point is below and left of the end point and more left than below. Because the arc should be below the chord interesting lattice points to check are also below the chord, at extreme they could be exactly on the chord line. If that's the case or those lattice points are within the circle radius the half lenticular hole is not a lenticular hole.

I compute these lattice points by a very simplistic line algorithm:

Rsquare = sx^2+sy^2
slope = dy/dx
For x=1 to dx-1
   y = Floor(x*slope)
   If (sx+x)^2+(sy+y)^2<Rsquare
      ' latice point found within area
      ' exit loop, chord is no candidate
   End If 
Next

Bye, Olaf.

 

[kwbMitel]

I've now completed all the chord lengths up to X=63 and Y=157

It's starting to go much faster as most circles are only valid if the closest approach of a lattice point is within 5 of each end. I feel I very close to the end of calulating and will soon be sorting, comparing and adding.

**********************************************
What's most important is that you realise ... There is no spoon.

 

[jges]

Thanks Olaf, that looks like a much simpler approach!

 

[Olaf Doschke]

Yes, it is very simple, but needs a little preprocessing, as it has some prerequisites (as said dx>=dy>0) If I imagine this correctly the sx,sy for which this works will rather be in the 4th quadrant (sy<0,sx>0).

Even though the code is short it's not an anylytical approach but an algorithmic. It needs to loop all lattice points along the chord before confirming it to be a half of a lenticular hole, it's faster for detecting nonlenticualar holes and chords not working than chords working.

You may modify it to rather determine the minimum R or R[super]2[/super], for which some dx,dy would work and go the route of kwbMitel solving the problem from the point of view of chords instead of checking all sx,sy.

Bye, Olaf.

 

[kwbMitel]

I'm burning out on this one. I've got my Y axis offset into the 90's with no clear end in site. I'm starting to make mistakes that are consuming hugh amounts of time to correct. I need a program that will return the x/y coordinates of the nearest lattice point to a chord defined by two other coordinates. I lack the skill. I can no longer plot the coordinates manually for those I cannot predict as it is starting to exceed the resolution of my monitor.

I can predict about 80% but a pattern eludes me for the rest which is why things are taking so long.

**********************************************
What's most important is that you realise ... There is no spoon.

 

[kwbMitel]

About 10 minutes after I wrote the last I took another shot at spotting the pattern and got it. I can now predict 100% of the lattice points closest approach to the chord. Don't ask me how I spotted it, I'm kindof crazy that way.

I don't know if I'm just tired but I can't even explain it it terms I understand. I just know it works as it is giving me the same values I have manually plotted.

**********************************************
What's most important is that you realise ... There is no spoon.