File size: 2,850 Bytes
14c9c2b | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 | # EVOLVE-BLOCK-START
"""Constructor-based circle packing for n=26 circles"""
import numpy as np
def construct_packing():
"""
Construct a specific arrangement of 26 circles in a unit square
that attempts to maximize the sum of their radii.
Returns:
Tuple of (centers, radii, sum_of_radii)
centers: np.array of shape (26, 2) with (x, y) coordinates
radii: np.array of shape (26) with radius of each circle
sum_of_radii: Sum of all radii
"""
# Initialize arrays for 26 circles
n = 26
centers = np.zeros((n, 2))
# Place circles in a structured pattern
# This is a simple pattern - evolution will improve this
# First, place a large circle in the center
centers[0] = [0.5, 0.5]
# Place 8 circles around it in a ring
for i in range(8):
angle = 2 * np.pi * i / 8
centers[i + 1] = [0.5 + 0.3 * np.cos(angle), 0.5 + 0.3 * np.sin(angle)]
# Place 16 more circles in an outer ring
for i in range(16):
angle = 2 * np.pi * i / 16
centers[i + 9] = [0.5 + 0.7 * np.cos(angle), 0.5 + 0.7 * np.sin(angle)]
# Additional positioning adjustment to make sure all circles
# are inside the square and don't overlap
# Clip to ensure everything is inside the unit square
centers = np.clip(centers, 0.01, 0.99)
# Compute maximum valid radii for this configuration
radii = compute_max_radii(centers)
return centers, radii
def compute_max_radii(centers):
"""
Compute the maximum possible radii for each circle position
such that they don't overlap and stay within the unit square.
Args:
centers: np.array of shape (n, 2) with (x, y) coordinates
Returns:
np.array of shape (n) with radius of each circle
"""
n = centers.shape[0]
radii = np.ones(n)
# First, limit by distance to square borders
for i in range(n):
x, y = centers[i]
# Distance to borders
radii[i] = min(x, y, 1 - x, 1 - y)
# Then, limit by distance to other circles
# Each pair of circles with centers at distance d can have
# sum of radii at most d to avoid overlap
for i in range(n):
for j in range(i + 1, n):
dist = np.sqrt(np.sum((centers[i] - centers[j]) ** 2))
# If current radii would cause overlap
if radii[i] + radii[j] > dist:
# Scale both radii proportionally
scale = dist / (radii[i] + radii[j])
radii[i] *= scale
radii[j] *= scale
return radii
# EVOLVE-BLOCK-END
# This part remains fixed (not evolved)
def run_packing():
"""Run the circle packing constructor for n=26"""
centers, radii = construct_packing()
# Calculate the sum of radii
sum_radii = np.sum(radii)
return centers, radii, sum_radii
|