from collections import defaultdict

class Scanner:
    def __init__(self, id_):
        self.points = []
        self.distances = []
        self.id_ = id_
        self.offset = [0, 0, 0]
        self.axis_sign = [1, 1, 1]
        self.axis_map = [0, 1, 2]

    def calculate_distances(self):
        """Create a sorted list of distances to other points for each point.

        This will help us identify common points.
        """
        self.distances = []
        # Create a matrix of distances
        for i in range(len(self.points)):
            p1 = self.points[i]
            distances = []

            for j in range(len(self.points)):
                if i == j:
                    continue
                p2 = self.points[j]
                dist = (p2[0] - p1[0])**2 + (p2[1] - p1[1])**2 + (p2[2] - p1[2])**2
                distances.append(dist)

            distances.sort()
            self.distances.append(distances)

    def find_overlapping(self, other: 'Scanner'):
        """By comparing distances point by point, for all the common points we
        can find out the correct sign and rotation of the axis.
        """
        common_points = {}

        def def_alignment():
            return 0

        same_point_alignment = defaultdict(def_alignment)
        for i in range(len(self.distances)):
            for j in range(len(other.distances)):
                if self.distances[i][0] != other.distances[j][0]:
                    # Dangerous, but ignore points for which first distances
                    # do not match. Since with each scanner there is an
                    # overlap of points, then these points have to be closer
                    # between each other, meaning the first distances of the
                    # same points should match. Also this lowers the runtime
                    # by 1x order of magnitude.
                    continue
                i2, j2 = 0, 0
                n1, n2 = len(self.distances[i]), len(other.distances[j])
                _c = 0
                while i2 < n1 and j2 < n2:
                    if self.distances[i][i2] == other.distances[j][j2]:
                        _c += 1
                        i2 += 1
                        j2 += 1
                    elif self.distances[i][i2] < other.distances[j][j2]:
                        i2 += 1
                    else:
                        j2 += 1

                if _c > same_point_alignment[j]:
                    # If the current pair is more aligned, then choose this.
                    same_point_alignment[j] = _c
                    common_points[j] = i

        # Reverse
        common_points = {v: k for k, v in common_points.items()}
        if len(common_points) < 12:
            # Apparently 12 points are always shared.
            return False

        # Determine axis switch. By default we assume complete alignment
        axis_map = [0, 1, 2]
        axis_sign = [1, 1, 1]
        offset = [None, None, None]

        keys = list(common_points.keys())
        for i in range(3):
            # i - axis rotation
            for j in [1, -1]:

                crash_x = False
                crash_y = False
                crash_z = False
                _offset_x = self.points[keys[0]][0] - j * other.points[common_points[keys[0]]][i]
                _offset_y = self.points[keys[0]][1] - j * other.points[common_points[keys[0]]][i]
                _offset_z = self.points[keys[0]][2] - j * other.points[common_points[keys[0]]][i]

                for key in keys[1:]:
                    p1 = self.points[key]
                    p2 = other.points[common_points[key]]
                    if not crash_x:
                        _of1 = p1[0] - j * p2[i]
                        if _of1 != _offset_x:
                            crash_x = True
                    if not crash_y:
                        _of2 = p1[1] - j * p2[i]
                        if _of2 != _offset_y:
                            crash_y = True
                    if not crash_z:
                        _of3 = p1[2] - j * p2[i]
                        if _of3 != _offset_z:
                            crash_z = True

                if not crash_x:
                    axis_map[0] = i
                    axis_sign[0] = j
                    offset[0] = _offset_x
                if not crash_y:
                    axis_map[1] = i
                    axis_sign[1] = j
                    offset[1] = _offset_y
                if not crash_z:
                    axis_map[2] = i
                    axis_sign[2] = j
                    offset[2] = _offset_z
        if not all(offset):
            return False

        other.offset = offset
        other.axis_map = axis_map
        other.axis_sign = axis_sign

        other.align_points()
        return True

    def align_points(self):
        """Function that aligns the offset with the root scanner.
        """
        for i in range(len(self.points)):
            x, y, z = self.axis_map
            sx, sy, sz = self.axis_sign

            new_x = self.offset[0] + sx * self.points[i][x]
            new_y = self.offset[1] + sy * self.points[i][y]
            new_z = self.offset[2] + sz * self.points[i][z]

            self.points[i][0] = new_x
            self.points[i][1] = new_y
            self.points[i][2] = new_z


scanners = []
file = "day_19.dat"
with open(file, 'r') as f:
    current = None
    _c = 0
    for line in f:
        if line.startswith('---'):
            if current:
                current.points = points
                current.calculate_distances()
            current = Scanner(_c)
            _c += 1
            scanners.append(current)
            points = []
            continue
        if not line.strip():
            continue

        points.append([int(_) for _ in line.split(',')])

    current.points = points
    current.calculate_distances()

to_process = scanners[:]
processed = [to_process.pop(0)]

while to_process:
    scanner = to_process.pop(0)

    for i, aligned in enumerate(processed):
        ok = aligned.find_overlapping(scanner)
        if ok:
            break
    if ok:
        processed.append(scanner)
    else:
        to_process.append(scanner)

# Gather all the points and return the number of beacons
points = []
for scanner in processed:
    for point in scanner.points:
        if point in points:
            continue
        else:
            points.append(point)
print("Part 1. Number of beacons:", len(points))


max_distance_between_2scanners = 0
for i in range(len(processed)):
    for j in range(i, len(processed)):
        s1 = processed[i]
        s2 = processed[j]

        dist = abs(s1.offset[0] - s2.offset[0]) + abs(s1.offset[1] - s2.offset[1]) + abs(s1.offset[2] - s2.offset[2])

        if dist > max_distance_between_2scanners:
            max_distance_between_2scanners = dist
print("Part 2. Max manhattan distance between two scanners: ", max_distance_between_2scanners)