CodeWars/4kyu/shortest_knight_path/solution.cpp

#include <cassert>
#include <deque>
#include <iostream>
#include <string>
#include <vector>

namespace {

int convert_column(char x) { return x - 'a'; }
int convert_row(char y) { return y - '1'; }

template <typename T> bool in_range(const T &x, const T &min, const T &max) {
  return min <= x && x < max;
}

template <typename T> using table_t = std::vector<std::vector<T>>;

static const std::vector<std::pair<int, int>> dpos{
    {-2, 1}, {-2, -1}, {-1, 2}, {-1, -2}, {1, 2}, {1, -2}, {2, 1}, {2, -1}};
static const int dpos_size = static_cast<int>(dpos.size());

class position_t;
std::ostream &operator<<(std::ostream &stream, const position_t &pos);

class position_t {
  int _x, _y;

public:
  position_t(int x, int y) : _x(x), _y(y) {}
  position_t(const std::pair<int, int> &coords)
      : _x(coords.first), _y(coords.second) {}
  position_t(const std::string &position)
      : _x(convert_column(position[0])), _y(convert_row(position[1])) {}

  int x() const { return _x; }
  int y() const { return _y; }
  bool in_bounds() const { return in_range(_x, 0, 8) && in_range(_y, 0, 8); }

  template <typename T> T &in(table_t<T> &table) const { return table[_y][_x]; }

  bool operator==(const position_t &other) const {
    return _x == other._x && _y == other._y;
  }
  bool operator!=(const position_t &other) const {
    return _x != other._x || _y != other._y;
  }
  position_t operator+(const position_t &other) const {
    return {_x + other._x, _y + other._y};
  }
};

std::ostream &operator<<(std::ostream &stream, const position_t &pos) {
  stream << static_cast<char>('a' + pos.x())
         << static_cast<char>('1' + pos.y());
  return stream;
}

class adjacent_iterator {
  const position_t pos;
  int i;

  position_t position() const { return pos + position_t(dpos[i]); }

  adjacent_iterator &next() {
    do {
      i++;
    } while (i < dpos_size && !position().in_bounds());
    return *this;
  }

public:
  adjacent_iterator(position_t pos) : pos(pos), i(-1) { next(); }
  adjacent_iterator(position_t pos, int i) : pos(pos), i(i) {}

  bool operator!=(const adjacent_iterator &other) const {
    return pos != other.pos || i != other.i;
  }
  adjacent_iterator &operator++() { return next(); }
  position_t operator*() const { return position(); }
};

class adjacent {
  const position_t &pos;

public:
  adjacent(const position_t &pos) : pos(pos) {}

  adjacent_iterator begin() const { return {pos}; }
  adjacent_iterator end() const { return {pos, dpos_size}; }
};

} // namespace

int knight(std::string start, std::string finish) {
  position_t src(start);
  position_t dst(finish);

  // construct table
  table_t<int> distances(8, std::vector<int>(8, -1));
  src.in(distances) = 0;

  // run BFS and break once ‹finish› is found
  std::deque<position_t> queue{src};
  while (!queue.empty()) {
    position_t pos = queue.front();
    queue.pop_front();

    int current_distance = pos.in(distances);
    for (const auto &next_pos : adjacent(pos)) {
      next_pos.in(distances) = current_distance + 1;
      queue.push_back(next_pos);

      if (next_pos == dst) {
        // We have just set distance to the seeked position
        queue.clear();
        break;
      }
    }
  }

  // return the distance to ‹finish›
  return dst.in(distances);
}

int main() {
  // position_t p("b8");
  // std::cout << "Constructed from string: " << p << "\n";

  // std::cout << "===adjacent===\n";
  // for (auto pos : adjacent(p)) {
  //   std::cout << pos << "\n";
  // }

  assert(knight("a1", "c1") == 2);
  assert(knight("a1", "f1") == 3);
  assert(knight("a1", "f3") == 3);
  assert(knight("a1", "f4") == 4);
  assert(knight("a1", "f7") == 5);

  return 0;
}