-
-
Save maksverver/c734acd0bbd173e818d3c5190a6e811b to your computer and use it in GitHub Desktop.
Solution for Infi.nl Advent of Code 2023
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Infi.nl Advent of Code | |
# https://aoc.infi.nl/2023 | |
from math import hypot, inf | |
def Calc1(polygon): | |
# Minimum radius of a circle centered at the origin that includes the entire | |
# polygon. This is simply the maximum distance from any vertex to the origin. | |
return max(hypot(x, y) for (x, y) in polygon) | |
def Part1(polygons): | |
return sum(Calc1(polygon) for polygon in polygons) | |
def CenterOfCircumCircle(x1, y1, x2, y2, x3, y3) : | |
'''Returns the center of the circumcircle of the given triangle, i.e., the | |
circle that passes through all three points. The points may not be colinear.''' | |
# Logic adapted from: | |
# https://www.geeksforgeeks.org/equation-of-circle-when-three-points-on-the-circle-are-given/ | |
x12 = x1 - x2 | |
y12 = y1 - y2 | |
x13 = x1 - x3 | |
y13 = y1 - y3 | |
x21 = x2 - x1 | |
y21 = y2 - y1 | |
x31 = x3 - x1 | |
y31 = y3 - y1 | |
sx13 = x1**2 - x3**2 | |
sy13 = y1**2 - y3**2 | |
sx21 = x2**2 - x1**2 | |
sy21 = y2**2 - y1**2 | |
cx = (sx13*y12 + sy13*y12 + sx21*y13 + sy21*y13) / (x21*y13 - x31*y12) / 2 | |
cy = (sx13*x12 + sy13*x12 + sx21*x13 + sy21*x13) / (y21*x13 - y31*x12) / 2 | |
return (cx, cy) | |
def Calc2(polygon): | |
# Returns the minimum circle that includes the entire polygon, if we can | |
# choose the center freely. The minimal circle will either touch exactly two | |
# points (then the center lies on the midpoint) or (at least) three points. | |
# We can consider all the cases. | |
best = (inf, 0, 0) | |
def CalcRadius(cx, cy): | |
return max(hypot(x - cx, y - cy) for (x, y) in polygon) | |
for i in range(len(polygon)): | |
x1, y1 = polygon[i] | |
for j in range(i + 1, len(polygon)): | |
x2, y2 = polygon[j] | |
cx = (x1 + x2)/2 | |
cy = (y1 + y2)/2 | |
best = min(best, (CalcRadius(cx, cy), cx, cy)) | |
for k in range(j + 1, len(polygon)): | |
x3, y3 = polygon[k] | |
cx, cy = CenterOfCircumCircle(x1, y1, x2, y2, x3, y3) | |
best = min(best, (CalcRadius(cx, cy), cx, cy)) | |
return best | |
def Part2(polygons): | |
answer = 0 | |
for caseNo, polygon in enumerate(polygons): | |
r, cx, cy = Calc2(polygon) | |
answer += r | |
if False: | |
# For debugging: generate SVG to illustrate solution. | |
with open('case-%d.svg' % caseNo, 'wt') as f: | |
f.write(f'''\ | |
<svg viewBox="-150 -150 300 300" xmlns="http://www.w3.org/2000/svg"> | |
<circle cx="{cx}" cy="{cy}" r="{r}" fill="none" stroke="blue" /> | |
<polygon points="{' '.join(f'{x},{y}' for (x, y) in polygon)}" fill="none" stroke="black" stroke-linejoin="round" /> | |
</svg>''') | |
return answer | |
testdata = [ | |
[(10, -39), (35, -86), (-89, 13), (70, -100), (-27, -37), (97, 25), (89, -24)], | |
[(88, 33), (79, 23), (7, -95), (-92, -9), (-60, -72), (18, 58)], | |
[(93, -38), (62, -49), (59, -77), (-66, -50), (55, -59)], | |
[(19, -20), (6, -50), (18, -85), (6, 69), (-82, 62), (45, 91)], | |
[(-97, -27), (73, 1), (70, -5), (85, -7), (55, -38)], | |
[(-89, 1), (45, 65), (65, -58)], | |
[(-68, -9), (-54, -96), (-74, -1), (57, 73), (-76, 22)], | |
[(40, 45), (-53, -30), (-44, -52), (-15, -50), (32, -20), (-40, -45)], | |
[(64, -82), (-2, -61), (-84, -31)], | |
[(-97, 76), (-42, 13), (0, -41), (99, -53), (-26, 43), (96, -30)], | |
[(44, -86), (16, 59), (41, -55), (-3, -21)], | |
[(10, -78), (71, -65), (-94, -61), (-92, -100), (18, 56)], | |
[(81, 45), (64, -14), (33, 69), (96, -52), (-62, 75), (88, -16)], | |
[(92, -5), (49, 1), (39, -2), (71, 71), (-40, -13), (-35, -64), (41, -36)], | |
[(59, -62), (-26, -75), (-61, 14), (-19, 99)], | |
[(-71, -75), (71, -52), (-51, -60), (40, 21)], | |
[(81, -57), (11, -10), (6, -40), (-81, 85), (84, 20), (-43, -2)], | |
[(92, 5), (44, -11), (-100, 0), (62, -56)], | |
[(10, -5), (-1, -28), (13, 27), (22, 22)], | |
[(47, 44), (-2, 60), (-80, 40)], | |
[(31, -87), (-95, -46), (29, 61), (42, 52)], | |
[(-67, -35), (4, 60), (-60, -61), (59, -7), (5, 33), (-84, 91), (-66, 47)], | |
[(-38, -38), (0, 9), (54, 52), (-69, -15), (-97, -81)], | |
[(-13, 56), (89, 46), (49, 53), (46, -7)], | |
[(-38, -82), (62, 80), (8, 84), (-96, -45), (-14, 24)], | |
] | |
print(Part1(testdata)) # 2561.8898615822372 | |
print(Part2(testdata)) # 2158.892834786057 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment