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 ?
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
