117 lines
3.4 KiB
Python
117 lines
3.4 KiB
Python
import math
|
|
|
|
MAX_NUM = 9999999999999999999999999999
|
|
|
|
def parseTuples(rawInput: list[str]) -> list[tuple[int, int, int]] :
|
|
tuples: list[tuple[int, int, int]] = []
|
|
for line in rawInput :
|
|
nums = line.split(",")
|
|
tuples.append((int(nums[0]), int(nums[1]), int(nums[2])))
|
|
return tuples
|
|
|
|
def calcDistance(first: tuple[int, int, int], second: tuple[int, int, int]) -> int :
|
|
return math.sqrt((first[0] - second[0])**2 + (first[1] - second[1])**2 + (first[2] - second[2])**2)
|
|
|
|
def addToConnections(minConnection: tuple[int, int]) :
|
|
for circuitCnt in range(len(connections)) :
|
|
circuit = connections[circuitCnt]
|
|
for boxCnt in range(len(circuit)) :
|
|
box = circuit[boxCnt]
|
|
if minConnection[0] == box[0] or minConnection[1] == box[0] or minConnection[0] == box[1] or minConnection[1] == box[1]:
|
|
circuit.append(minConnection)
|
|
return (circuitCnt, len(connections[circuitCnt]) - 1)
|
|
connections.append([])
|
|
connections[-1].append(minConnection)
|
|
return (len(connections) - 1, 0)
|
|
|
|
def clearRedundantConnections(newConnectionLocation: tuple[int, int]) :
|
|
newConnection = connections[newConnectionLocation[0]][newConnectionLocation[1]]
|
|
for box in connections[newConnectionLocation[0]] :
|
|
distances[box[0]][newConnection[0]] = MAX_NUM
|
|
distances[box[0]][newConnection[1]] = MAX_NUM
|
|
distances[box[1]][newConnection[0]] = MAX_NUM
|
|
distances[box[1]][newConnection[1]] = MAX_NUM
|
|
distances[newConnection[0]][box[0]] = MAX_NUM
|
|
distances[newConnection[0]][box[1]] = MAX_NUM
|
|
distances[newConnection[1]][box[0]] = MAX_NUM
|
|
distances[newConnection[1]][box[1]] = MAX_NUM
|
|
|
|
def getUniqueBoxes(circuit: list[tuple[int, int]]) -> list[int]:
|
|
boxes: list[int] = []
|
|
boxes.append(circuit[0][0])
|
|
boxes.append(circuit[0][1])
|
|
for box in circuit :
|
|
if not box[0] in boxes :
|
|
boxes.append(box[0])
|
|
elif not box[1] in boxes :
|
|
boxes.append(box[1])
|
|
return boxes
|
|
|
|
|
|
testInput = [
|
|
"162,817,812",
|
|
"57,618,57",
|
|
"906,360,560",
|
|
"592,479,940",
|
|
"352,342,300",
|
|
"466,668,158",
|
|
"542,29,236",
|
|
"431,825,988",
|
|
"739,650,466",
|
|
"52,470,668",
|
|
"216,146,977",
|
|
"819,987,18",
|
|
"117,168,530",
|
|
"805,96,715",
|
|
"346,949,466",
|
|
"970,615,88",
|
|
"941,993,340",
|
|
"862,61,35",
|
|
"984,92,344",
|
|
"425,690,689"
|
|
]
|
|
|
|
def readFile() :
|
|
ary = []
|
|
with open("files/Problem8.txt", "r") as file :
|
|
for line in file :
|
|
ary.append(line.replace("\n", ""))
|
|
return ary
|
|
|
|
#rawInput = testInput
|
|
rawInput = readFile()
|
|
parsedInput = parseTuples(rawInput)
|
|
distances: list[list[int]] = []
|
|
for outerCnt in range(len(parsedInput)) :
|
|
distances.append([])
|
|
for innerCnt in range(len(parsedInput)) :
|
|
if innerCnt == outerCnt :
|
|
distances[-1].append(MAX_NUM)
|
|
else :
|
|
distances[-1].append(calcDistance(parsedInput[outerCnt], parsedInput[innerCnt]))
|
|
connections: list[list[tuple[int, int]]] = []
|
|
minDistance = MAX_NUM
|
|
minConnection = (MAX_NUM, MAX_NUM)
|
|
for cnt in range(1000) :
|
|
print(f"number = {cnt}")
|
|
minDistance = MAX_NUM
|
|
minConnection = (MAX_NUM, MAX_NUM)
|
|
for box1Cnt in range(len(distances)) :
|
|
for box2Cnt in range(len(distances[box1Cnt])) :
|
|
if distances[box1Cnt][box2Cnt] < minDistance :
|
|
minDistance = distances[box1Cnt][box2Cnt]
|
|
minConnection = (box1Cnt, box2Cnt)
|
|
connection = addToConnections(minConnection)
|
|
clearRedundantConnections(connection)
|
|
|
|
sizes: list[int] = []
|
|
for circuit in connections :
|
|
sizes.append(len(getUniqueBoxes(circuit)))
|
|
sizes.sort(reverse=True)
|
|
print(f"sizes = {sizes}")
|
|
|
|
print(f"minConnections = {connections}, multiplication = {sizes[0] * sizes[1] * sizes[2]}")
|
|
|
|
|
|
#Too low 6000
|