#!/usr/bin/env python3
#
# --- Day 19: Beacon Scanner ---
#
# As your probe drifted down through this area, it released an assortment
# of beacons and scanners into the water. It's difficult to navigate in the
# pitch black open waters of the ocean trench, but if you can build a map
# of the trench using data from the scanners, you should be able to safely
# reach the bottom.
#
# The beacons and scanners float motionless in the water; they're designed
# to maintain the same position for long periods of time. Each scanner is
# capable of detecting all beacons in a large cube centered on the scanner;
# beacons that are at most 1000 units away from the scanner in each of the
# three axes (x, y, and z) have their precise position determined relative
# to the scanner. However, scanners cannot detect other scanners. The submarin
# has automatically summarized the relative positions of beacons detected
# by each scanner (your puzzle input).
#
# For example, if a scanner is at x,y,z coordinates 500,0,-500 and there are
# beacons at -500,1000,-1500 and 1501,0,-500, the scanner could report that
# the first beacon is at -1000,1000,-1000 (relative to the scanner) but would
# not detect the second beacon at all.
#
# Unfortunately, while each scanner can report the positions of all detected
# beacons relative to itself, the scanners do not know their own position.
# You'll need to determine the positions of the beacons and scanners yourself.
#
# The scanners and beacons map a single contiguous 3d region. This region can
# be reconstructed by finding pairs of scanners that have overlapping detection
# regions such that there are at least 12 beacons that both scanners detect
# within the overlap. By establishing 12 common beacons, you can precisely
# determine where the scanners are relative to each other, allowing you
# to reconstruct the beacon map one scanner at a time.
#
# For a moment, consider only two dimensions. Suppose you have the following
# scanner reports:
#   --- scanner 0 ---
#   0,2
#   4,1
#   3,3
#
#   --- scanner 1 ---
#   -1,-1
#   -5,0
#   -2,1
#
# Drawing x increasing rightward, y increasing upward, scanners as S,
# and beacons as B, scanner 0 detects this:
#   ...B.
#   B....
#   ....B
#   S....
#
# Scanner 1 detects this:
#   ...B..
#   B....S
#   ....B.
#
# For this example, assume scanners only need 3 overlapping beacons. Then,
# the beacons visible to both scanners overlap to produce the following
# complete map:
#   ...B..
#   B....S
#   ....B.
#   S.....
#
# Unfortunately, there's a second problem: the scanners also don't know their
# rotation or facing direction. Due to magnetic alignment, each scanner is
# rotated some integer number of 90-degree turns around all of the x, y, and z
# axes. That is, one scanner might call a direction positive x, while another
# scanner might call that direction negative y. Or, two scanners might agree
# on which direction is positive x, but one scanner might be upside-down from
# the perspective of the other scanner. In total, each scanner could be in any
# of 24 different orientations: facing positive or negative x, y, or z, and
# considering any of four directions "up" from that facing.
#
# For example, here is an arrangement of beacons as seen from a scanner in the
# same position but in different orientations:
#   --- scanner 0 ---
#   -1,-1,1
#   -2,-2,2
#   -3,-3,3
#   -2,-3,1
#   5,6,-4
#   8,0,7
#
#   --- scanner 0 ---
#   1,-1,1
#   2,-2,2
#   3,-3,3
#   2,-1,3
#   -5,4,-6
#   -8,-7,0
#
#   --- scanner 0 ---
#   -1,-1,-1
#   -2,-2,-2
#   -3,-3,-3
#   -1,-3,-2
#   4,6,5
#   -7,0,8
#
#   --- scanner 0 ---
#   1,1,-1
#   2,2,-2
#   3,3,-3
#   1,3,-2
#   -4,-6,5
#   7,0,8
#
#   --- scanner 0 ---
#   1,1,1
#   2,2,2
#   3,3,3
#   3,1,2
#   -6,-4,-5
#   0,7,-8
#
# By finding pairs of scanners that both see at least 12 of the same beacons,
# you can assemble the entire map. For example, consider the following report:
#   --- scanner 0 ---
#   404,-588,-901
#   528,-643,409
#   -838,591,734
#   390,-675,-793
#   -537,-823,-458
#   -485,-357,347
#   -345,-311,381
#   -661,-816,-575
#   -876,649,763
#   -618,-824,-621
#   553,345,-567
#   474,580,667
#   -447,-329,318
#   -584,868,-557
#   544,-627,-890
#   564,392,-477
#   455,729,728
#   -892,524,684
#   -689,845,-530
#   423,-701,434
#   7,-33,-71
#   630,319,-379
#   443,580,662
#   -789,900,-551
#   459,-707,401
#
#   --- scanner 1 ---
#   686,422,578
#   605,423,415
#   515,917,-361
#   -336,658,858
#   95,138,22
#   -476,619,847
#   -340,-569,-846
#   567,-361,727
#   -460,603,-452
#   669,-402,600
#   729,430,532
#   -500,-761,534
#   -322,571,750
#   -466,-666,-811
#   -429,-592,574
#   -355,545,-477
#   703,-491,-529
#   -328,-685,520
#   413,935,-424
#   -391,539,-444
#   586,-435,557
#   -364,-763,-893
#   807,-499,-711
#   755,-354,-619
#   553,889,-390
#
#   --- scanner 2 ---
#   649,640,665
#   682,-795,504
#   -784,533,-524
#   -644,584,-595
#   -588,-843,648
#   -30,6,44
#   -674,560,763
#   500,723,-460
#   609,671,-379
#   -555,-800,653
#   -675,-892,-343
#   697,-426,-610
#   578,704,681
#   493,664,-388
#   -671,-858,530
#   -667,343,800
#   571,-461,-707
#   -138,-166,112
#   -889,563,-600
#   646,-828,498
#   640,759,510
#   -630,509,768
#   -681,-892,-333
#   673,-379,-804
#   -742,-814,-386
#   577,-820,562
#
#   --- scanner 3 ---
#   -589,542,597
#   605,-692,669
#   -500,565,-823
#   -660,373,557
#   -458,-679,-417
#   -488,449,543
#   -626,468,-788
#   338,-750,-386
#   528,-832,-391
#   562,-778,733
#   -938,-730,414
#   543,643,-506
#   -524,371,-870
#   407,773,750
#   -104,29,83
#   378,-903,-323
#   -778,-728,485
#   426,699,580
#   -438,-605,-362
#   -469,-447,-387
#   509,732,623
#   647,635,-688
#   -868,-804,481
#   614,-800,639
#   595,780,-596
#
#   --- scanner 4 ---
#   727,592,562
#   -293,-554,779
#   441,611,-461
#   -714,465,-776
#   -743,427,-804
#   -660,-479,-426
#   832,-632,460
#   927,-485,-438
#   408,393,-506
#   466,436,-512
#   110,16,151
#   -258,-428,682
#   -393,719,612
#   -211,-452,876
#   808,-476,-593
#   -575,615,604
#   -485,667,467
#   -680,325,-822
#   -627,-443,-432
#   872,-547,-609
#   833,512,582
#   807,604,487
#   839,-516,451
#   891,-625,532
#   -652,-548,-490
#   30,-46,-14
#
# Because all coordinates are relative, in this example, all "absolute"
# positions will be expressed relative to scanner 0 (using the orientation
# of scanner 0 and as if scanner 0 is at coordinates 0,0,0).
#
# Scanners 0 and 1 have overlapping detection cubes; the 12 beacons they both
# detect (relative to scanner 0) are at the following coordinates:
#   -618,-824,-621
#   -537,-823,-458
#   -447,-329,318
#   404,-588,-901
#   544,-627,-890
#   528,-643,409
#   -661,-816,-575
#   390,-675,-793
#   423,-701,434
#   -345,-311,381
#   459,-707,401
#   -485,-357,347
#
# These same 12 beacons (in the same order) but from the perspective
# of scanner 1 are:
#   686,422,578
#   605,423,415
#   515,917,-361
#   -336,658,858
#   -476,619,847
#   -460,603,-452
#   729,430,532
#   -322,571,750
#   -355,545,-477
#   413,935,-424
#   -391,539,-444
#   553,889,-390
#
# Because of this, scanner 1 must be at 68,-1246,-43 (relative to scanner 0).
#
# Scanner 4 overlaps with scanner 1; the 12 beacons they both detect
# (relative to scanner 0) are:
#   459,-707,401
#   -739,-1745,668
#   -485,-357,347
#   432,-2009,850
#   528,-643,409
#   423,-701,434
#   -345,-311,381
#   408,-1815,803
#   534,-1912,768
#   -687,-1600,576
#   -447,-329,318
#   -635,-1737,486
#
# So, scanner 4 is at -20,-1133,1061 (relative to scanner 0).
#
# Following this process, scanner 2 must be at 1105,-1205,1229 (relative
# to scanner 0) and scanner 3 must be at -92,-2380,-20 (relative to scanner 0).
#
# The full list of beacons (relative to scanner 0) is:
#   -892,524,684
#   -876,649,763
#   -838,591,734
#   -789,900,-551
#   -739,-1745,668
#   -706,-3180,-659
#   -697,-3072,-689
#   -689,845,-530
#   -687,-1600,576
#   -661,-816,-575
#   -654,-3158,-753
#   -635,-1737,486
#   -631,-672,1502
#   -624,-1620,1868
#   -620,-3212,371
#   -618,-824,-621
#   -612,-1695,1788
#   -601,-1648,-643
#   -584,868,-557
#   -537,-823,-458
#   -532,-1715,1894
#   -518,-1681,-600
#   -499,-1607,-770
#   -485,-357,347
#   -470,-3283,303
#   -456,-621,1527
#   -447,-329,318
#   -430,-3130,366
#   -413,-627,1469
#   -345,-311,381
#   -36,-1284,1171
#   -27,-1108,-65
#   7,-33,-71
#   12,-2351,-103
#   26,-1119,1091
#   346,-2985,342
#   366,-3059,397
#   377,-2827,367
#   390,-675,-793
#   396,-1931,-563
#   404,-588,-901
#   408,-1815,803
#   423,-701,434
#   432,-2009,850
#   443,580,662
#   455,729,728
#   456,-540,1869
#   459,-707,401
#   465,-695,1988
#   474,580,667
#   496,-1584,1900
#   497,-1838,-617
#   527,-524,1933
#   528,-643,409
#   534,-1912,768
#   544,-627,-890
#   553,345,-567
#   564,392,-477
#   568,-2007,-577
#   605,-1665,1952
#   612,-1593,1893
#   630,319,-379
#   686,-3108,-505
#   776,-3184,-501
#   846,-3110,-434
#   1135,-1161,1235
#   1243,-1093,1063
#   1660,-552,429
#   1693,-557,386
#   1735,-437,1738
#   1749,-1800,1813
#   1772,-405,1572
#   1776,-675,371
#   1779,-442,1789
#   1780,-1548,337
#   1786,-1538,337
#   1847,-1591,415
#   1889,-1729,1762
#   1994,-1805,1792
#
# In total, there are 79 beacons.
#
# Assemble the full map of beacons. How many beacons are there?
#
#
# --- Solution ---
#
# We start by reading the input file and splitting it by single empty line.
# Then for each entry we drop the first line (header with scanner identifier)
# and map remaining to list of integers (the coordinates). Then we produce
# a set of all possible rotations about X, Y and Z axes – for this we implement
# the rotation equations from the matrix forms and other helper functions.
# Ultimately this set gives us all unique transformations we can perform:
# how to remap the indexes and flip the axes. For example a tuple: ((1, 0, 2),
# (-1, 1, -1)) describes we should put Y (1) as first index, X (0) as second,
# Z (2) as third and invert the first and last element in final vector.
# Next we take a single set of readings from scanners and we treat it as our
# base with origin/reference point (0, 0, 0). Then in a loop, as long as there
# are some unmapped scanners, we attempt to find a transformations that will
# cause some readings to overlap in at least 12 points. To find a mapping for
# a given scanner, we consider all possible rotations of a scanner beacon
# readings and then we compute the translation vectors between each rotated
# beacon position and each already mapped (known/recognized/unique) beacon.
# Finally for each of translations we produce a set of translated beacons
# positions and we get an intersection of this set and our set of already
# mapped beacons (i.e. we find a list of all common elements between two sets)
# – if there are at least 12 common elements, we found the proper translation
# that allows us to join the sets and recognize new beacons positions by simply
# adding two sets (an union operation). In the end we remove the just mapped
# scanner from the list and start this procedure again for all remaining
# scanners, every time with a bigger set of identified unique beacons.
# As an answer, we print the length of generated set after there are no more
# unmapped scanners.
#

INPUT_FILE = 'input.txt'


def sin(angle):
    angle %= 360
    if angle == 0 or angle == 180:
        return 0
    elif angle == 90:
        return 1
    elif angle == 270:
        return -1
    raise ValueError('Only the multiples of the right angle are supported.')


def cos(angle):
    return sin(angle + 90)


def rotation_x(angle, vec):
    return [
        vec[0],
        cos(angle) * vec[1] + -sin(angle) * vec[2],
        sin(angle) * vec[1] + cos(angle) * vec[2],
    ]


def rotation_y(angle, vec):
    return [
        cos(angle) * vec[0] + sin(angle) * vec[2],
        vec[1],
        -sin(angle) * vec[0] + cos(angle) * vec[2],
    ]


def rotation_z(angle, vec):
    return [
        cos(angle) * vec[0] + -sin(angle) * vec[1],
        sin(angle) * vec[0] + cos(angle) * vec[1],
        vec[2],
    ]


def rotation_xyz(angle_x, angle_y, angle_z, vec):
    return rotation_z(angle_z, rotation_y(angle_y, rotation_x(angle_x, vec)))


def abs(value):
    if value >= 0:
        return value
    else:
        return -value


def sign(value):
    if value >= 0:
        return 1
    elif value < 0:
        return -1


def main():
    with open(INPUT_FILE, 'r') as file:
        scanners = file.read().strip().split('\n\n')

    for i, scanner in enumerate(scanners):
        scanners[i] = [tuple(map(int, line.split(',')))
                       for line in scanner.split('\n')[1:]]

    rotations = set()
    transformations = set()

    for angle1 in [0, 90, 180, 270]:
        for angle2 in [0, 90, 180, 270]:
            for angle3 in [0, 90, 180, 270]:
                vec = rotation_xyz(angle1, angle2, angle3, [1, 2, 3])
                rotations.add(tuple(vec))

    for transformation in rotations:
        indexes = tuple([abs(component) - 1 for component in transformation])
        signs = tuple([sign(component) for component in transformation])
        transformations.add((indexes, signs))

    known = set(scanners.pop(0))  # first scanner is our origin point (0, 0, 0)

    while scanners:
        matched = False
        for scanner in scanners:
            for transformation in transformations:
                indexes, signs = transformation
                nx, ny, nz = indexes
                s1, s2, s3 = signs
                rotated = [(s1 * beacon[nx], s2 * beacon[ny], s3 * beacon[nz])
                           for beacon in scanner]

                for reading in known:
                    for beacon in rotated:
                        dx, dy, dz = [b_i - r_i
                                      for b_i, r_i in zip(beacon, reading)]

                        translated = set([(x - dx, y - dy, z - dz)
                                          for candidate in rotated
                                          for x, y, z in [candidate]])

                        common_points = known.intersection(translated)

                        if len(common_points) >= 12:
                            known = known.union(translated)
                            matched = True
                            break

                    if matched:
                        break

                if matched:
                    break

            if matched:
                break

        if matched:
            scanners.remove(scanner)
        else:
            print('Went through all, no match – something is wrong!')
            break

    print(len(known))


if __name__ == '__main__':
    main()
