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

 

[kwbMitel]

What a difference a formula makes!

I've found what I believe to be the upper limit for L(100,000)

The Chord Length is Root(88978)

The chord end points are at (267,0) and (0,133)

The nearest Lattice point to the chord is at (265,1)

The minimum valid Circle size is the first of the following 4
R = Root(9778014865)
R = Root(9837096257)
R = Root(9896355605)
R = Root(9955792909)

Now that I have all the circles, I need to compare for duplicates.

This may take more time than it sounds. I currently have them stored in 65 separate spreadsheets and they total by my estimate around 500,000.

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

 

[kwbMitel]

So here I am, I have all the circles plotted and all of their combinations calculated.

The last element is to look for duplicate circles that appear in more than 1 family of chord lengths.

Currently I have about 67 separate excel spreadsheets that contain these circles.

Every 3rd column contains the valid circle radii.

there are approximately 500,000 circles.

I am more than a little intimidated about manually copting and pasting these circles to another spreadsheet for comparison purposes.

Any direction anyone can give me would be appreciated.

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

 

[kwbMitel]

Counting away. My estimate of 500,000 circles seems to have been a little low. Well above 600,000 and still counting. Should have an answer tomorrow I think.

Whether or not it is the right one is another question altogether.

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

 

[Olaf Doschke]

Well, you'll see when submitting your answer to project euler, if it's correct or not.

I'm still with you, but have to pause on the Euler Project until October.

Bye, Olaf.

 

[jges]

I'm also in pause mode, but still thinking about it.

 

[kwbMitel]

I think my chances are about 50/50. Too many areas in my method where a mistake can be made. We'll see soon enough I suppose.

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

 

[kwbMitel]

Answer by today was overly optimistic.

I've found some errors in my spreadsheets that needed correcting before proceeding.

I'm now at 1.1 million circles, but I am nearing the point where there is a large drop off due to the length of the chords.

Still working.

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

 

[kwbMitel]

Well I've finally got an answer. Not the right one apparently but an answer none the less.

I've got all my data stored and when you guys get going maybe we can compare results and I'll see where I went wrong.

I have a simple method for calculating the smallest R of a circle that will pass thru a chord of defined size AND not contain a lattice point between the arc and the chord.

I'm not sure how to express it mathematically as it requires repeating functions until an integer result is found. Maybe someone can help me with how to express it clearly.



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

 

[jges]

I have an important deadline on the 28th, after which I can spend more time on this. If you can describe your method, I'd be glad to try to help.

 

[kwbMitel]

Here are some of my assumptions that I have used for this puzzle. Does anyone see any issues with these?

List of assumptions that have yet to be disproven.
1) - All valid circles than contain a specific chord length will combine with all other circles with the same chord length. 10 circles will combine 55 times using X * (X+1)/2 formula

2) - Valid chord lengths when the end points are plotted on the X=0 and y=0 axis will always have an odd 2nd coordinate of a larger value. If x = 5, the smallest Y value for the other end point will be 7. the end points in this example would be at (5,0) and (0,7)

3) - Some circles will be found with more than 1 chord length. R=5 being an example of a root(2) and Root(10) chord length. These circles must only be counted once for combining with the same size circle. The count determined by #1 assumption above must be reduced by 1 for every duplicate circle found.

4) - For Y axis offset 3 or greater, there will be some valid circles that will contain lattice points. I am assuming that the lattice point that is found nearest the chord will determine the minimum radius that must be used from the set of valid circles. This is my biggest assumption and has had the least scrutiny.

My biggest concern is with #4. My confidence level in the others is quite high as they were used to determine the L(100) solution of 3442.

Any feedback on the above?

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

 

[jges]

Ok, I've picked this back up. When I left off, I was working on generating circles based on valid chord lengths. This looks like it has some promise.

kwbMitel,
1) agree
2) agree. My working theory is both chord length X and Y components must be odd and coprime.
3) mostly agree. What you wrote is true, but to generalize further you have to reduce count for each duplicate combination of circles.
4) agree

 

[kwbMitel]

Jgres

Re: 3) Mostly agree.
I may have been unclear in what I meant. To use the L(100) as an example. There were 13 circles that appeared in more than 1 category. 1 circle r=root(1105) appeared in 3. These circles would only be counted once for combining with themselves and reduce the calculated values from step 1 by 14.

Re: 4) I am not comfortable with this one at all. Especially when the closest point is near one end or the other. My gut says this one is OK but your agreement helps.

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

 

[jges]

Ok, I get correct answers for the L(10) and L(100) cases. I can generate what I think are all the circles for the L(100,000) case in a little over 3 minutes, but I don't think my counting technique is up to the task of L(100,000). It ran for hours and gave an incorrect result. Looks like some brainstorming and bug hunting is in order.

 

[jges]

I think I found my error.

Here's my overall strategy that seems to work: divide each family of circles into its own list (chord length = sqrt(2) in a list, chord length = sqrt(10) in a list, etc etc).

function ASum(x)
ASum = (x * (x+1))/2
End Function

For 1 list, the total number of combinations are ASum(ListCount). For the 2nd list add ASum(List#2Count) and subtract ASum(#Duplicates between list 1 and 2). List 3 and above get a bit trickier as I have to keep track of which duplicates I have already seen.

Here's some test code:

http://www.box.net/shared/pu1djau5tb

If you run the script, it will create a text file in the folder the script is in named: DictionaryTest.log that steps through what happens.

It works well for a small number of lists, it only takes a few seconds for the L(100) case. But it is a brute force type approach that doesn't scale up well. Any suggestions for improvement are welcome!

 

[kwbMitel]

jgres - Care to share your incorrect answer? I would like to see how close we are to each other. No need to hide the answer as it is incorrect.

P.S. I can provide total circles for each Chord Length.
P.P.S. I can provide every single circle as well.

I'll post my answer tomorrow when I have access to my home PC

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

 

[jges]

For what it's worth: 4850255504.

 

[jges]

Also, I ended up with 922 families of circles.

 

[kwbMitel]

So my totals are not as high as yours but are still in the same region.

Total Combinations = 4582451728

Total Circles = 1454232

Total Duplicate circles = 279433

Total Holes = Combinations - Duplicates = 4582172295

I grouped my circles differently than you so I don't immediately have a total of all the different chord lengths (What you call families I assume) 922 sounds about right but I'll count them shortly and post again.


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

 

[jges]

Yes, by families I meant chord lengths.

I had another run at it today. Another number in the same ballpark, but still incorrect. I have a feeling that I'm not catching all the chord lengths for the 100,000 case. Also, I'm still suspicious of my counting technique.

I'm curious of your counting technique, but it's getting late here. I'll post a more specific question/example tomorrow if I find time.

 

[kwbMitel]

I tallied my Chord Lengths and it is much higher than yours.

1302

My technique is very basic (And unusual). I have 67 excel spreadsheets grouping the chord lengths by the Y axis offset.

The smallest y axis offset is 1 and this yields 224 chord lengths from X=1 to X=447. This grouping does not have any minimum circle sizes.

Y Axis offset = 3 by comparison only has 31 Chord Lengths starting with X = 5 and maxing out at X = 101. Every 3rd one in this group is a multiple of Y=1 and is invalid. Also this group has minimims for circle radius within each length as some combinations of smaller circles contain lattice points.

The largest y offset is 133 and only yields 2 chord lengths and 12 circles that combine for 46 holes

I can provide complete data on each and every chord length that I consider valid. Obviously I've missed something but by comparing data maybe we can come to a concensus

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