part1 (8081B)
1--- Day 19: Beacon Scanner --- 2 3As your probe drifted down through this area, it released an assortment of [1m[97mbeacons[0m and 4[1m[97mscanners[0m into the water. It's difficult to navigate in the pitch black open waters of the ocean 5trench, but if you can build a map of the trench using data from the scanners, you should be able to 6safely reach the bottom. 7 8The beacons and scanners float motionless in the water; they're designed to maintain the same 9position for long periods of time. Each scanner is capable of detecting all beacons in a large cube 10centered on the scanner; beacons that are at most 1000 units away from the scanner in each of the 11three axes (x, y, and z) have their precise position determined relative to the scanner. However, 12scanners cannot detect other scanners. The submarine has automatically summarized the relative 13positions of beacons detected by each scanner (your puzzle input). 14 15For example, if a scanner is at x,y,z coordinates 500,0,-500 and there are beacons at 16-500,1000,-1500 and 1501,0,-500, the scanner could report that the first beacon is at 17-1000,1000,-1000 (relative to the scanner) but would not detect the second beacon at all. 18 19Unfortunately, while each scanner can report the positions of all detected beacons relative to 20itself, [1m[97mthe scanners do not know their own position[0m. You'll need to determine the positions of the 21beacons and scanners yourself. 22 23The scanners and beacons map a single contiguous 3d region. This region can be reconstructed by 24finding pairs of scanners that have overlapping detection regions such that there are [1m[97mat least 12 25beacons[0m that both scanners detect within the overlap. By establishing 12 common beacons, you can 26precisely determine where the scanners are relative to each other, allowing you to reconstruct the 27beacon map one scanner at a time. 28 29For a moment, consider only two dimensions. Suppose you have the following scanner reports: 30 31--- scanner 0 --- 320,2 334,1 343,3 35 36--- scanner 1 --- 37-1,-1 38-5,0 39-2,1 40 41Drawing x increasing rightward, y increasing upward, scanners as S, and beacons as B, scanner 0 42detects this: 43 44...B. 45B.... 46....B 47S.... 48 49Scanner 1 detects this: 50 51...B.. 52B....S 53....B. 54 55For this example, assume scanners only need 3 overlapping beacons. Then, the beacons visible to both 56scanners overlap to produce the following complete map: 57 58...B.. 59B....S 60....B. 61S..... 62 63Unfortunately, there's a second problem: the scanners also don't know their [1m[97mrotation or facing 64direction[0m. Due to magnetic alignment, each scanner is rotated some integer number of 90-degree turns 65around all of the x, y, and z axes. That is, one scanner might call a direction positive x, while 66another scanner might call that direction negative y. Or, two scanners might agree on which 67direction is positive x, but one scanner might be upside-down from the perspective of the other 68scanner. In total, each scanner could be in any of 24 different orientations: facing positive or 69negative x, y, or z, and considering any of four directions "up" from that facing. 70 71For example, here is an arrangement of beacons as seen from a scanner in the same position but in 72different orientations: 73 74--- scanner 0 --- 75-1,-1,1 76-2,-2,2 77-3,-3,3 78-2,-3,1 795,6,-4 808,0,7 81 82--- scanner 0 --- 831,-1,1 842,-2,2 853,-3,3 862,-1,3 87-5,4,-6 88-8,-7,0 89 90--- scanner 0 --- 91-1,-1,-1 92-2,-2,-2 93-3,-3,-3 94-1,-3,-2 954,6,5 96-7,0,8 97 98--- scanner 0 --- 991,1,-1 1002,2,-2 1013,3,-3 1021,3,-2 103-4,-6,5 1047,0,8 105 106--- scanner 0 --- 1071,1,1 1082,2,2 1093,3,3 1103,1,2 111-6,-4,-5 1120,7,-8 113 114By finding pairs of scanners that both see at least 12 of the same beacons, you can assemble the 115entire map. For example, consider the following report: 116 117--- scanner 0 --- 118404,-588,-901 119528,-643,409 120-838,591,734 121390,-675,-793 122-537,-823,-458 123-485,-357,347 124-345,-311,381 125-661,-816,-575 126-876,649,763 127-618,-824,-621 128553,345,-567 129474,580,667 130-447,-329,318 131-584,868,-557 132544,-627,-890 133564,392,-477 134455,729,728 135-892,524,684 136-689,845,-530 137423,-701,434 1387,-33,-71 139630,319,-379 140443,580,662 141-789,900,-551 142459,-707,401 143 144--- scanner 1 --- 145686,422,578 146605,423,415 147515,917,-361 148-336,658,858 14995,138,22 150-476,619,847 151-340,-569,-846 152567,-361,727 153-460,603,-452 154669,-402,600 155729,430,532 156-500,-761,534 157-322,571,750 158-466,-666,-811 159-429,-592,574 160-355,545,-477 161703,-491,-529 162-328,-685,520 163413,935,-424 164-391,539,-444 165586,-435,557 166-364,-763,-893 167807,-499,-711 168755,-354,-619 169553,889,-390 170 171--- scanner 2 --- 172649,640,665 173682,-795,504 174-784,533,-524 175-644,584,-595 176-588,-843,648 177-30,6,44 178-674,560,763 179500,723,-460 180609,671,-379 181-555,-800,653 182-675,-892,-343 183697,-426,-610 184578,704,681 185493,664,-388 186-671,-858,530 187-667,343,800 188571,-461,-707 189-138,-166,112 190-889,563,-600 191646,-828,498 192640,759,510 193-630,509,768 194-681,-892,-333 195673,-379,-804 196-742,-814,-386 197577,-820,562 198 199--- scanner 3 --- 200-589,542,597 201605,-692,669 202-500,565,-823 203-660,373,557 204-458,-679,-417 205-488,449,543 206-626,468,-788 207338,-750,-386 208528,-832,-391 209562,-778,733 210-938,-730,414 211543,643,-506 212-524,371,-870 213407,773,750 214-104,29,83 215378,-903,-323 216-778,-728,485 217426,699,580 218-438,-605,-362 219-469,-447,-387 220509,732,623 221647,635,-688 222-868,-804,481 223614,-800,639 224595,780,-596 225 226--- scanner 4 --- 227727,592,562 228-293,-554,779 229441,611,-461 230-714,465,-776 231-743,427,-804 232-660,-479,-426 233832,-632,460 234927,-485,-438 235408,393,-506 236466,436,-512 237110,16,151 238-258,-428,682 239-393,719,612 240-211,-452,876 241808,-476,-593 242-575,615,604 243-485,667,467 244-680,325,-822 245-627,-443,-432 246872,-547,-609 247833,512,582 248807,604,487 249839,-516,451 250891,-625,532 251-652,-548,-490 25230,-46,-14 253 254Because all coordinates are relative, in this example, all "absolute" positions will be expressed 255relative to scanner 0 (using the orientation of scanner 0 and as if scanner 0 is at coordinates 2560,0,0). 257 258Scanners 0 and 1 have overlapping detection cubes; the 12 beacons they both detect (relative to 259scanner 0) are at the following coordinates: 260 261-618,-824,-621 262-537,-823,-458 263-447,-329,318 264404,-588,-901 265544,-627,-890 266528,-643,409 267-661,-816,-575 268390,-675,-793 269423,-701,434 270-345,-311,381 271459,-707,401 272-485,-357,347 273 274These same 12 beacons (in the same order) but from the perspective of scanner 1 are: 275 276686,422,578 277605,423,415 278515,917,-361 279-336,658,858 280-476,619,847 281-460,603,-452 282729,430,532 283-322,571,750 284-355,545,-477 285413,935,-424 286-391,539,-444 287553,889,-390 288 289Because of this, scanner 1 must be at 68,-1246,-43 (relative to scanner 0). 290 291Scanner 4 overlaps with scanner 1; the 12 beacons they both detect (relative to scanner 0) are: 292 293459,-707,401 294-739,-1745,668 295-485,-357,347 296432,-2009,850 297528,-643,409 298423,-701,434 299-345,-311,381 300408,-1815,803 301534,-1912,768 302-687,-1600,576 303-447,-329,318 304-635,-1737,486 305 306So, scanner 4 is at -20,-1133,1061 (relative to scanner 0). 307 308Following this process, scanner 2 must be at 1105,-1205,1229 (relative to scanner 0) and scanner 3 309must be at -92,-2380,-20 (relative to scanner 0). 310 311The full list of beacons (relative to scanner 0) is: 312 313-892,524,684 314-876,649,763 315-838,591,734 316-789,900,-551 317-739,-1745,668 318-706,-3180,-659 319-697,-3072,-689 320-689,845,-530 321-687,-1600,576 322-661,-816,-575 323-654,-3158,-753 324-635,-1737,486 325-631,-672,1502 326-624,-1620,1868 327-620,-3212,371 328-618,-824,-621 329-612,-1695,1788 330-601,-1648,-643 331-584,868,-557 332-537,-823,-458 333-532,-1715,1894 334-518,-1681,-600 335-499,-1607,-770 336-485,-357,347 337-470,-3283,303 338-456,-621,1527 339-447,-329,318 340-430,-3130,366 341-413,-627,1469 342-345,-311,381 343-36,-1284,1171 344-27,-1108,-65 3457,-33,-71 34612,-2351,-103 34726,-1119,1091 348346,-2985,342 349366,-3059,397 350377,-2827,367 351390,-675,-793 352396,-1931,-563 353404,-588,-901 354408,-1815,803 355423,-701,434 356432,-2009,850 357443,580,662 358455,729,728 359456,-540,1869 360459,-707,401 361465,-695,1988 362474,580,667 363496,-1584,1900 364497,-1838,-617 365527,-524,1933 366528,-643,409 367534,-1912,768 368544,-627,-890 369553,345,-567 370564,392,-477 371568,-2007,-577 372605,-1665,1952 373612,-1593,1893 374630,319,-379 375686,-3108,-505 376776,-3184,-501 377846,-3110,-434 3781135,-1161,1235 3791243,-1093,1063 3801660,-552,429 3811693,-557,386 3821735,-437,1738 3831749,-1800,1813 3841772,-405,1572 3851776,-675,371 3861779,-442,1789 3871780,-1548,337 3881786,-1538,337 3891847,-1591,415 3901889,-1729,1762 3911994,-1805,1792 392 393In total, there are [1m[97m79[0m beacons. 394 395Assemble the full map of beacons. [1m[97mHow many beacons are there?[0m 396 397