AOC 2023 Day 25

25.cpp

#include "common.h"

struct Node {
  std::string name;
  std::unordered_map<std::string, bool> edges;
};

struct Edge {
  std::string first, second, origFirst, origSecond;
};
int main(int argc, char **argv) {
  std::string path(argv[argc - 1]);
  std::string content = file_to_string(path);
  std::vector<std::string> lines = split(content, "\n");
  std::unordered_map<std::string, Node> origNodes;
  for (auto line : lines) {
    auto parts = split(line, " ");
    parts[0] = parts[0].substr(0, parts[0].find(":"));
    for (auto entry : parts) {
      if (!origNodes.count(entry)) {
        Node n;
        n.name = entry;
        origNodes[entry] = n;
      }
    }
  }
  std::vector<Edge> pp;
  for (auto line : lines) {
    auto parts = split(line, " ");
    parts[0] = parts[0].substr(0, parts[0].find(":"));
    Node &left = origNodes[parts[0]];
    if (parts.size() > 1)
      for (size_t i = 1; i < parts.size(); i++) {
        Node &right = origNodes[parts[i]];
        left.edges[parts[i]] = true;
        right.edges[parts[0]] = true;
        pp.push_back({parts[0], parts[i], parts[0], parts[i]});
      }
  }
  std::vector<std::pair<std::string, std::string>> found;
  for (size_t it = 0; it < 50000; it++) {
    auto pairs = pp;
    auto nodes = origNodes;
    while (pairs.size() > 3) {
      auto index = randInt(0, pairs.size() - 1);
      auto rr = pairs[index];
      std::pair<Node &, Node &> entry(nodes[rr.first], nodes[rr.second]);
      pairs.erase(pairs.begin() + index);
      entry.first.edges.erase(entry.second.name);
      entry.second.edges.erase(entry.first.name);

      std::vector<size_t> indexes;
      for (size_t i = 0; i < pairs.size(); i++) {
        auto p = pairs[i];
        if ((p.first == rr.first || p.second == rr.first) &&
            (p.first == rr.second || p.second == rr.second)) {
          indexes.push_back(i);
        }
      }
      for (int64_t i = indexes.size() - 1; i >= 0; i--)
        pairs.erase(pairs.begin() + indexes[i]);

      for (auto &other : entry.second.edges) {
        Node &otherNode = nodes[other.first];
        otherNode.edges.erase(entry.second.name);
        otherNode.edges[entry.first.name] = true;
        entry.first.edges[other.first] = true;
      }
      for (auto &p : pairs) {
        if (p.first == entry.second.name) {
          p.first = entry.first.name;
        } else if (p.second == entry.second.name) {
          p.second = entry.first.name;
        }
      }
    }
    if (pairs.size() != 3)
      continue;
    for (auto edge : pairs)
      found.push_back(std::pair(edge.origFirst, edge.origSecond));
    std::cout << "found after: " << it << "\n";
    break;
  }
  {
    auto nodes = origNodes;
    for (auto p : found) {
      Node &left = nodes[p.first];
      Node &right = nodes[p.second];
      left.edges.erase(p.second);
      right.edges.erase(p.first);
    }
    std::deque<std::string> q;
    std::set<std::string> left, right;
    {
      auto start = nodes.begin();
      q.push_back(start->first);
      while (q.size()) {
        auto elem = q.front();
        q.pop_front();
        if (left.count(elem))
          continue;
        left.insert(elem);
        Node node = nodes[elem];
        for (auto entry : node.edges)
          q.push_back(entry.first);
      }
    }

    {
      auto start = nodes.begin();
      while (left.count(start->first))
        start++;
      q.clear();
      q.push_back(start->first);
      while (q.size()) {
        auto elem = q.front();
        q.pop_front();
        if (right.count(elem))
          continue;
        right.insert(elem);
        Node node = nodes[elem];
        for (auto entry : node.edges)
          q.push_back(entry.first);
      }
    }
    std::cout << left.size() * right.size() << "\n";
  }
  return 0;
}

common.h

#ifndef COMMON_H
#define COMMON_H
#include <iostream>
#include <assert.h>
#include <string>
#include <limits>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <utility>
#include <sstream>
#include <fstream>
#include <deque>
#include <sstream>
#include <random>
struct MapSize {
  size_t x, y;
};
int64_t randInt(int64_t min, int64_t max) {
   std::random_device rd; // obtain a random number from hardware
    std::mt19937 gen(rd()); // seed the generator
    std::uniform_int_distribution<> distr(min, max); // define the range
    return distr(gen);
}
MapSize getGridSize(std::vector<std::string> &vec) {
  return {vec.size() == 0 ? 0 : vec[0].size(), vec.size()};
}
std::string file_to_string(std::string path) {
  std::ifstream stream(path);
  std::stringstream ss;
  ss << stream.rdbuf();
  stream.close();
  return ss.str();
};
std::string gridToStr(std::vector<std::string> &vec) {
  std::stringstream stream;
  for (auto &line : vec) {
    for (const char e : line)
      stream << e;
    stream << "\n";
  }
  return stream.str();
}
std::string hashKey(std::vector<int64_t> v) {
  std::stringstream stream;
  for (auto n : v)
    stream << n << "x";
  return stream.str();
}
bool inBounds(const std::vector<std::string> &map, int64_t x, int64_t y) {
  if (x < 0 || x >= map[0].size() || y < 0 || y >= map.size())
    return false;
  return true;
}
std::vector<std::string> flipClockwise(std::vector<std::string> &in) {
  std::vector<std::string> out;
  out.reserve(in[0].size());
  for (int64_t l = 0; l < in[0].size(); l++) {
    std::string r;
    for (int64_t y = in.size() - 1; y >= 0; y--)
      r += (in[y][l]);
    out.push_back(r);
  }
  return out;
}
std::vector<std::string> flipCounterClockwise(std::vector<std::string> &in) {
  std::vector<std::string> out;
  out.reserve(in[0].size());
  for (int64_t l = in[0].size() - 1; l >= 0; l--) {
    std::string r;
    for (size_t y = 0; y < in.size(); y++)
      r += (in[y][l]);
    out.push_back(r);
  }
  return out;
}

std::vector<std::string> split(std::string base, std::string delimiter) {
  std::vector<std::string> final;
  final.reserve(base.length() / 76);
  size_t pos = 0;
  std::string token;
  while ((pos = base.find(delimiter)) != std::string::npos) {
    token = base.substr(0, pos);
    final.push_back(token);
    base.erase(0, pos + delimiter.length());
  }
  final.push_back(base);
  return final;
};
#define assertm(exp, msg) assert(((void)msg, exp))
#endif