#include "aoc.h"
#include <deque>
#include <set>

namespace aoc2022 {

struct pos {
  int x;
  int y;
  int t;

  friend bool operator<(pos p1, pos p2) {
    return p1.x < p2.x ? true : p1.x > p2.x ? false : p1.y < p2.y ? true : p1.y > p2.y ? false : p1.t < p2.t;
  }
  bool operator==(pos p) const noexcept { return x == p.x && y == p.y; }
};

bool is_valid(pos p, valley& v, std::set<pos>& visited) {
  pos px{p.x, p.y, p.t % (v.height * v.width)};

  auto pr = visited.insert(px);
  if (!pr.second) {
    return false;
  }

  auto blz = v.at(px.t);
  auto find = [&blz](blizzard b) -> bool {
    for (auto& bx : blz) {
      if (bx == b)
        return true;
    }
    return false;
  };

  auto b = p.x >= 0 && p.x < v.width && p.y >= 0 && p.y < v.height;
  return b && !find(blizzard{p.x, p.y, '.'}) && v.get(p.y, p.x) == '.';
}

// bfs
int expedition(pos p, pos target, valley& v, std::set<pos>& visited) {
  std::deque<pos> q;
  q.push_back(p);

  while (!q.empty()) {
    auto size = q.size();
    while (size-- > 0) {
      pos px = q.front();
      // printf("(%d,%d) at %d\n", px.x, px.y, px.t);
      q.pop_front();
      if (px == target) {
        return px.t;
      }
      pos ps[5] = {
          {px.x, px.y + 1, px.t + 1}, {px.x + 1, px.y, px.t + 1}, {px.x, px.y - 1, px.t + 1},
          {px.x - 1, px.y, px.t + 1}, {px.x, px.y, px.t + 1},
      };
      for (int i = 0; i < 5; i++) {
        if (is_valid(ps[i], v, visited)) {
          q.push_back(ps[i]);
        }
      }
    }
  }
  return INT32_MAX;
}

std::pair<int, int> day24(line_view file) {
  // valley v{8,6}; //sample
  valley v{152, 22};

  int height{0};
  per_line(file, [&v, &height](line_view lv) {
    v.load(height++, lv);
    return true;
  });
  std::set<pos> visited;

  int m1 = expedition({1, 0, 0}, {150, 21, INT32_MAX}, v, visited);
  visited.clear();
  int m2 = expedition({150, 21, m1}, {1, 0, INT32_MAX}, v, visited);
  visited.clear();
  int m3 = expedition({1, 0, m2}, {150, 21, INT32_MAX}, v, visited);

  // printf("%d %d %d\n", m1, m2, m3);
  return {m1, m3};
}
} // namespace aoc2022