From bd13e34b93d67a60012fb56a38f4319070668031 Mon Sep 17 00:00:00 2001 From: jacopograndi Date: Wed, 16 Feb 2022 14:05:06 +0100 Subject: day19 --- 2021/day19/day19 | Bin 0 -> 100832 bytes 2021/day19/day19.cpp | 272 ++++++++++++ 2021/day19/day19_input.txt | 1057 ++++++++++++++++++++++++++++++++++++++++++++ 2021/day19/makefile | 2 + 2021/day19/test0.txt | 136 ++++++ 2021/day19/test1.txt | 7 + 2021/day19/test2.txt | 53 +++ 2021/day19/test3.txt | 4 + 8 files changed, 1531 insertions(+) create mode 100755 2021/day19/day19 create mode 100644 2021/day19/day19.cpp create mode 100644 2021/day19/day19_input.txt create mode 100644 2021/day19/makefile create mode 100644 2021/day19/test0.txt create mode 100644 2021/day19/test1.txt create mode 100644 2021/day19/test2.txt create mode 100644 2021/day19/test3.txt diff --git a/2021/day19/day19 b/2021/day19/day19 new file mode 100755 index 0000000..c00434d Binary files /dev/null and b/2021/day19/day19 differ diff --git a/2021/day19/day19.cpp b/2021/day19/day19.cpp new file mode 100644 index 0000000..f45d7ca --- /dev/null +++ b/2021/day19/day19.cpp @@ -0,0 +1,272 @@ +#include +#include +#include +#include + + +class Beacon { + public: + Beacon() { x=y=z=0; } + Beacon(int x, int y, int z): x(x), y(y), z(z) { } + Beacon(const Beacon &b) { x=b.x; y=b.y; z=b.z; } + + int x,y,z; + + bool operator==(const Beacon& r) { + return x==r.x && y==r.y && z==r.z; + } + friend bool operator==(const Beacon& l, const Beacon& r) { + return l.x==r.x && l.y==r.y && l.z==r.z; + } + + std::string show () { + std::string rep = + std::to_string(x) + "," + + std::to_string(y) + "," + + std::to_string(z) + "\n"; + return rep; + } +}; + +class Scanner { + public: + Scanner() { } + Scanner(const Scanner &s) { + for (Beacon b : s.beacons) beacons.emplace_back(b); + } + + int x,y,z; + std::vector beacons; + bool fixed = false; + + bool operator==(const Scanner& r) { + return x==r.x && y==r.y && z==r.z && beacons == r.beacons; + } + + std::string show () { + std::string rep = "scanner\n"; + for (Beacon b : beacons) { + rep += " beacon at " + b.show(); + } + return rep; + } + + Scanner scale (int x, int y, int z) { + Scanner s; + for (Beacon& b : beacons) { + s.beacons.emplace_back(b.x*x, b.y*y, b.z*z); + } + return s; + } + + Scanner rotate (int axis, int pi_halves) { + Scanner s; + int sin = pi_halves < 2 ? pi_halves : -pi_halves+2; + pi_halves = (pi_halves+1) % 4; + int cos = pi_halves < 2 ? pi_halves : -pi_halves+2; + for (Beacon& b : beacons) { + if (axis == 2) + s.beacons.emplace_back( + b.x*cos - b.y*sin, + b.x*sin + b.y*cos, + b.z); + if (axis == 1) + s.beacons.emplace_back( + b.x*cos + b.z*sin, + b.y, + -b.x*sin + b.z*cos); + if (axis == 0) + s.beacons.emplace_back( + b.x, + b.y*cos - b.z*sin, + b.y*sin + b.z*cos); + } + return s; + } + + Scanner rebase (bool swapxy, bool swapyz, bool swapxz) { + Scanner s; + int tmp; + for (Beacon& b : beacons) { + Beacon a { b }; + if (swapxy) { tmp = a.x; a.x = a.y; a.y = tmp; } + if (swapyz) { tmp = a.y; a.y = a.z; a.z = tmp; } + if (swapxz) { tmp = a.x; a.x = a.z; a.z = tmp; } + s.beacons.push_back(a); + } + return s; + } + + Scanner translate (int x, int y, int z) { + Scanner s; + for (Beacon& b : beacons) { + s.beacons.emplace_back(b.x+x, b.y+y, b.z+z); + } + return s; + } + + int overlap (Scanner oth) { + int sum = 0; + for (Beacon &b : beacons) { + if (std::find(std::begin(oth.beacons), std::end(oth.beacons), b) + != std::end(oth.beacons)) { + sum++; + } + } + //std::cout << sum << " "; + return sum; + } +}; + + +std::vector orientations (Scanner source) { + std::vector orientations; + for (int i=0; i<4; i++) { + Scanner rotated = source.rotate(0, i); + for (int j=0; j<6; j++) { + Scanner based { rotated }; + if (j==1) { + based = rotated.rotate(1, 1); + } + if (j==2) { + based = rotated.rotate(1, 2); + } + if (j==3) { + based = rotated.rotate(1, 3); + } + if (j==4) { + based = rotated.rotate(2, 1); + } + if (j==5) { + based = rotated.rotate(2, 3); + } + orientations.push_back(based); + } + } + return orientations; +} + +Beacon parse_beacon (std::string raw) { + Beacon b; + + auto comma = raw.find(","); + b.x = std::stoi(raw.substr(0, comma)); + raw = raw.substr(comma+1); + + comma = raw.find(","); + b.y = std::stoi(raw.substr(0, comma)); + raw = raw.substr(comma+1); + + b.z = std::stoi(raw); + + return b; +} + +std::vector parse_scanners (std::string raw) { + std::vector scanners; + while (raw.size() > 0) { + auto newline = raw.find('\n'); + if (newline != std::string::npos) { + std::string line = raw.substr(0, newline); + raw = raw.substr(newline+1); + if (line.find("---") != std::string::npos) { + scanners.push_back(Scanner()); + } else if (line.size() > 1) { + Beacon b = parse_beacon(line); + scanners[scanners.size()-1].beacons.push_back(b); + } + } else { + Beacon b = parse_beacon(raw); + scanners[scanners.size()-1].beacons.push_back(b); + } + } + return scanners; +} + +int main (int argc, char *argv[]) { + std::string raw; std::getline(std::ifstream(argv[1]), raw, '\0'); + + std::vector scanners = parse_scanners(raw); + + std::vector cloud; + for (Beacon b : scanners[0].beacons) { + if (std::find(std::begin(cloud), std::end(cloud), b) + == std::end(cloud)) + cloud.push_back(b); + } + scanners[0].fixed = true; + scanners[0].x = 0; + scanners[0].y = 0; + scanners[0].z = 0; + + while (true) { + int fixed_count = 0; + bool overlap = false; + for (int i=0; i 2000) continue; + Scanner translated = rebased.translate(dx, dy, dz); + if (base.overlap(translated) >= 12) { + std::cout << "overlaps: " << base.overlap(translated) << std::endl; + scanners[i].x = dx; + scanners[i].y = dy; + scanners[i].z = dz; + std::cout << " at: " <