[Tutor] Find Integer co-ordinates lying on a circle

[Dave Angel]

Shashwat Anand wrote:
>> Your "all possible results" isn't even close to all the points that match
>> the 0<= r <= 5.  And I don't know how either spec justifies the set logic
>> you quoted.
>>
>>     
>
>   
>> So I have to start over.  I think you're trying to find all integer
>> co-ordinates which lie on or within a circle of given radius (sample 5).
>>
>> No, I'm trying to find all integer co-ordinates which lies on a circle.
>>     
> Say for a circle of radius 5 the co-ordinates are [(5, 0), (0, 5), (-5, 0),
> (0, -5), (3, 4), (4,3), (3, -4), (4, -3), (-3,
> 4), (-4, 3), (-3, -4), (-4, -3)] which lies on circle x**2 + y**2 = 5**2 (as
> Origin is the centre of the circle.)
>   

In other words  r = n,   not 0 <= r <= n  as you originally said.  You 
want all points for which x*x + y*y = n*n

Upon reading your new message, it appears that you are not using r in 
the usual sense of polar coordinates
    (where r = sqrt( x*x + y*y)  and  theta = arctan(x/y)    or maybe 
it's y/x )

Instead you're using r as the radius of one circle you're trying to do, 
in a loop that is trying different radii up to n (or R)
> Now I want a table of these points for say r = 0 to upper bound.
> So for r = 0, the only point lying on it is (0,0)
> For r = 1, the points lying on them (the circle x**2 + y**2 = 1**2) is [(1,
> 0), (0, 1), (-1, 0), (0, -1)]
> And so forth.
>
> Thus the table shows the points (x,y) which are lying on the circle of
> radius 'r'.
>
> radius 'r' - (x, y)
> 0 - (0, 0)
> 1 - (1, 0), (0, 1), (-1, 0), (0, -1)
> 2 - (2, 0), (0, 2), (-2, 0), (0, -2)
> 3 - (3, 0), (0, 3), (-3, 0), (0, -3)
> 4 - (4, 0), (0, 4), (-4, 0), (0, -4)
> 5 - (5, 0), (0, 5), (-5, 0), (0, -5), (3, 4), (4,3), (3, -4), (4, -3), (-3,
> 4), (-4, 3), (-3, -4), (-4, -3)
>
> Which is correct. I'm not trying to find all integer co-ordinates within a
> circle but trying to create a table of points lying on the circle of radius
> 'r', varying the radius from '0' to upper bound 'r'.
> The bruteforce can be done as:
>
> #R = upper bound
> for r in range(0, R+1):
>     for x in range(0, R+1):
>         for y in range(0, R+1):
>             if x**2 + y**2 == r**2:
>                 #store them
>
>   
Care to define r and R ?  I think the outer loop here belongs 
elsewhere.  Let's solve it for one circle.  Then you can run that inside 
a loop which iterates through possible radii.

The outer loop isn't our concern.  And the innermost loop can be 
replaced by a calculation. Why not simply
   y = math.sqrt(r*r - x*x)

and check if y is an int. ??
> However the complexity reaches O(n**3) and it's not optimized at all. So I
> though of using pythagorean triplets.
>
> Taking only the first quadrant to keep the number of values smaller, I see:
>   
>> ( 0 , 0 ) ( 0 , 1 ) ( 0 , 2 ) ( 0 , 3 ) ( 0 , 4 ) ( 0 , 5 )
>> ( 1 , 0 ) ( 1 , 1 ) ( 1 , 2 ) ( 1 , 3 ) ( 1 , 4 )
>> ( 2 , 0 ) ( 2 , 1 ) ( 2 , 2 ) ( 2 , 3 ) ( 2 , 4 )
>> ( 3 , 0 ) ( 3 , 1 ) ( 3 , 2 ) ( 3 , 3 ) ( 3 , 4 )
>> ( 4 , 0 ) ( 4 , 1 ) ( 4 , 2 ) ( 4 , 3 )
>> ( 5 , 0 )
>>
>> To find them, just write a doubly nested loop, each with range from -radius
>> to radius, checking x*x + y*y <= radius*radius.  Add to the result set, each
>> value that meets the comparison.
>>
>>
>> There are some optimizations you can do, but first get it working in the
>> form you want.
>>
>>
>> The bruteforce code is working for me but that's an unacceptable option. So
>>     
> I tried pythagorean triplets. But I'm not sure as to where am I doing
> mistake.
>   
>>>> d = collections.defaultdict(list)
>>>>         
> I created a dictionary.
>   
>>>> s = list(set([((u*u + v*v), (v*v - u*u, 2*u*v)) for u in range(10) for v
>>>>         
> in range(u+1, 10)]))
> for u = (0,9) and v > u, the triplets are u**2+v**2, v**2 - u**2, 2*u*v. So,
> I stored them. However it looks for only half of positive quadrant. set
> logic is to remove  duplicate elements. Now for each value (p, q) there will
> be seven more possible values i.e. (q, p), (q, -p), (-q, p), (-q, -p), (p,
> -q), (-p, q), (-p, -q). In case of either of p or q value = 0, the values
> are reduced to 3.
>   
>>>> [d[k].append(v) for k,v in s]
>>>>         
> I stored all the values.
>
> Hope I did not made this post really messy. I think I'm unable to apply my
> logic. How to implement / Can there be better logic, optimizations and
> implementations ?
>
>