sol1.py

"""
Project Euler Problem 587: https://projecteuler.net/problem=587

A square is drawn around a circle as shown in the diagram below on the left.
We shall call the blue shaded region the L-section.
A line is drawn from the bottom left of the square to the top right
as shown in the diagram on the right.
We shall call the orange shaded region a concave triangle.

It should be clear that the concave triangle occupies exactly half of the L-section.

Two circles are placed next to each other horizontally,
a rectangle is drawn around both circles, and
a line is drawn from the bottom left to the top right as shown in the diagram below.

This time the concave triangle occupies approximately 36.46% of the L-section.

If n circles are placed next to each other horizontally,
a rectangle is drawn around the n circles, and
a line is drawn from the bottom left to the top right,
then it can be shown that the least value of n
for which the concave triangle occupies less than 10% of the L-section is n = 15.

What is the least value of n
for which the concave triangle occupies less than 0.1% of the L-section?
"""

fromitertoolsimportcount
frommathimportasin, pi, sqrt


defcircle_bottom_arc_integral(point: float) ->float:
"""
 Returns integral of circle bottom arc y = 1 / 2 - sqrt(1 / 4 - (x - 1 / 2) ^ 2)

 >>> circle_bottom_arc_integral(0)
 0.39269908169872414

 >>> circle_bottom_arc_integral(1 / 2)
 0.44634954084936207

 >>> circle_bottom_arc_integral(1)
 0.5
 """

return (
 (1-2*point) *sqrt(point-point**2) +2*point+asin(sqrt(1-point))
 ) /4


defconcave_triangle_area(circles_number: int) ->float:
"""
 Returns area of concave triangle

 >>> concave_triangle_area(1)
 0.026825229575318944

 >>> concave_triangle_area(2)
 0.01956236140083944
 """

intersection_y= (circles_number+1-sqrt(2*circles_number)) / (
2* (circles_number**2+1)
 )
intersection_x=circles_number*intersection_y

triangle_area=intersection_x*intersection_y/2
concave_region_area=circle_bottom_arc_integral(
1/2
 ) -circle_bottom_arc_integral(intersection_x)

returntriangle_area+concave_region_area


defsolution(fraction: float=1/1000) ->int:
"""
 Returns least value of n
 for which the concave triangle occupies less than fraction of the L-section

 >>> solution(1 / 10)
 15
 """

l_section_area= (1-pi/4) /4

fornincount(1):
ifconcave_triangle_area(n) /l_section_area<fraction:
returnn

return-1


if__name__=="__main__":
print(f"{solution() =}")