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]

I'm still having difficulty cross referencing. I can confirm that all 8755 of X=7 Y=9 are duplicates but I can't confirm as yet that they are duplicates of a single other list (but it looks likely)

There are quite a few of the duplicates that come from the X=7 family. I'm still working on it but the way I have my data organised is not condusive to this type of comparison.

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

 

[kwbMitel]

Here are some more chord lengths that can be eliminated
[tt]
X=11 Y=13 5836 Circles Contained entirely in X=1 X=17
X=09 y=19 4736 Circles Contained entirely in X=1 X=21
X=13 y=19 4309 Circles Contained entirely in X=1 X=23
X=17 y=21 3635 Circles Contained entirely in X=1 X=27
X=11 y=29 3128 Circles Contained entirely in X=1 X=31[/tt]

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

 

[kwbMitel]

More eliminations - Chords defined by:[tt]
Duplicate Original
X Y X Y
19 27 1 33
23 29 1 37
13 41 1 43
19 43 1 47
31 43 1 53
25 49 1 55
21 53 1 57
37 51 1 63
41 53 1 67
17 71 1 73
51 55 1 75
47 61 1 77
39 71 1 81
31 77 1 83
[/tt]

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

 

[kwbMitel]

I'm starting to find chord lengths where all but a few a completely cancelled out. 3334 of 3337 for example. I've found 10 of these so far. I've also found 13 more completely cancelled out. I think I'll work though finding all of the complete eliminations before moving on to the partials.

So far I've eliminated in excess of 50,000 circles.

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

 

[kwbMitel]

Interesting development. I'm now finding complete chord lengths that are eliminated by higher Y Offset values.

Example X=11 Y =47 is contained within X=31 Y=37.

Not sure what this might mean to your method but I thought I'd give you a heads up.

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

 

[jges]

I found 240 lists that could be completely eliminated (using the grouping method I've described earlier in the thread).

I let it run over the weekend, it ran for 10 hours most of which was just comparing lists but it did complete.

 

[jges]

Success!!

 

[IPGuru]

Congratulations, I have been following this thread with mild interest, but never actualy tried to produce any code myself
all you need to do now is speed the process up to fit the 3 minute expectation
good luck


I do not Have A.D.D. im just easily, Hey look a Squirrel!

 

[kwbMitel]

jgres - Success? Does this mean you've submitted your answer and it is correct? If so Congrats.

I've eliminated over 100 lists so far but my process is manual so I expect it to take much longer.

Olaf - I think the 3 minute expectation in this case is out to lunch. The description was probably written before this puzzle was added. I suspect many of the newer puzzles cannot be solved in 3 minutes or less.

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

 

[jges]

I had a quick look at the project euler forum to see what others had to say and a number post code that claims to solve the problem in less than 1 minute (I have not taken a good look or run any of the code, so I have to take their word at this point). The creator of the problem posted and claims to be able to solve the L(1,000,000) case in less than 8 seconds, L(100,000) in less than 1 second. When I have time, I'm going to look more closely at what they did as I'm sure I'll learn something that will help in the future (both project euler problems and more importantly, real world problems).

 

[jges]

...Congrats

Thank you for your help. I'm not sure I would have got there without the exchange of ideas in this thread. And keep at it, now you know you are on the right track, you will be the next one submitting an answer!

 

[kwbMitel]

Jgres - I can probably go a little faster now as I was recording all the eliminated lists and where they were found in case you needed them. Now I'll just concentrate on eliminating and not cross referencing. It also helps to know how many to expect, thanks for that.

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

 

[kwbMitel]

Jges Please confirm 240 Chords eliminated.

I only found 239.

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

 

[jges]

In my bookkeeping method there were 240 chords with unique dx, dy that were subsets of other chords.

I can compile a list if you like, but it will take some cross referencing so it wouldn't be until tomorrow afternoon at best.

 

[kwbMitel]

Don't put yourself out yet. Let me double Check some things first.

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

 

[jges]

I don't think this is really a spoiler, but if you don't want a hint it I'll put it in a spoiler tag:

Spoiler

focus your search on chords that are the same length but have different dx dy values

 

[kwbMitel]

Thanks for the hint. That will actually be very helpful. I had not yet tried to figure out what the common factor was for these chords. I had been assuming it was some multiple but hadn't gotten around to checking. At this point where I've already discovered 239 (possibly 240 if I miscounted), its more a method of verification. Actually, if you had given it to me earlier, I might have saved me about 6 hours work.

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