git.scottworley.com Git - slidingtile/blob - sliding_tile_lib.cc

   1 #include "sliding_tile_lib.h"
   2
   3 #include <cstdlib>
   4 #include <istream>
   5 #include <map>
   6 #include <memory>
   7 #include <ostream>
   8 #include <queue>
   9 #include <set>
  10 #include <sstream>
  11 #include <stdexcept>
  12 #include <vector>
  13
  14 #include <iostream>
  15
  16 int Step::count = 0;
  17 signed char Step::adjacent[BOARD_SIZE][5] = {
  18   1,   4,   -1,  -1,  -1,
  19   0,   2,   5,   -1,  -1,
  20   1,   3,   6,   -1,  -1,
  21   2,   7,   -1,  -1,  -1,
  22   0,   5,   8,   -1,  -1,
  23   1,   4,   6,   9,   -1,
  24   2,   5,   7,   10,  -1,
  25   3,   6,   11,  -1,  -1,
  26   4,   9,   12,  -1,  -1,
  27   5,   8,   10,  13,  -1,
  28   6,   9,   11,  14,  -1,
  29   7,   10,  15,  -1,  -1,
  30   8,   13,  -1,  -1,  -1,
  31   9,   12,  14,  -1,  -1,
  32   10,  13,  15,  -1,  -1,
  33   11,  14,  -1,  -1,  -1,
  34 };
  35
  36 bool Board::is_valid() const {
  37   bool seen[BOARD_SIZE];
  38   for (int i = 0; i < BOARD_SIZE; i++) {
  39     seen[i] = false;
  40   }
  41
  42   for (int i = 0; i < BOARD_SIZE; i++) {
  43     if (board[i] < 0 || board[i] >= BOARD_SIZE || seen[board[i]]) {
  44       return false;
  45     }
  46     seen[board[i]] = true;
  47   }
  48
  49   // Redundant because pigeon-hole-principle, but check anyway
  50   for (int i = 0; i < BOARD_SIZE; i++) {
  51     if (!seen[i]) {
  52       return false;
  53     }
  54   }
  55
  56   return true;
  57 }
  58
  59 bool Board::operator==(const Board& o) const {
  60   for (int i = 0; i < BOARD_SIZE; i++) {
  61     if (board[i] != o.board[i]) {
  62       return false;
  63     }
  64   }
  65   return true;
  66 }
  67
  68 bool Board::operator!=(const Board& o) const {
  69   return !operator==(o);
  70 }
  71
  72 bool Board::operator<(const Board& o) const {
  73   for (int i = 0; i < BOARD_SIZE; i++) {
  74     if (board[i] < o.board[i]) {
  75       return true;
  76     } else if (board[i] > o.board[i]) {
  77       return false;
  78     }
  79   }
  80   return false;
  81 }
  82
  83 std::istream& operator>>(std::istream& is, Board& board) {
  84   for (int i = 0; i < BOARD_SIZE; i++) {
  85     if (!is.good()) {
  86       is.setstate(std::istream::failbit);
  87       break;
  88     }
  89     if (i > 0 && is.get() != ',') {
  90       is.setstate(std::istream::failbit);
  91       break;
  92     }
  93     int numeric;
  94     is >> numeric;
  95     board.board[i] = numeric;
  96   }
  97   if (!board.is_valid()) {
  98     is.setstate(std::istream::failbit);
  99   }
 100   return is;
 101 }
 102
 103 std::ostream& operator<<(std::ostream& os, const Board& board) {
 104   for (int i = 0; i < BOARD_SIZE; i++) {
 105     if (i > 0) {
 106       os << " ";
 107     }
 108     os << int(board.board[i]);
 109   }
 110   return os;
 111 }
 112
 113 signed char Board::hole() const {
 114   for (int i = 0; i < BOARD_SIZE; i++) {
 115     if (board[i] == 0) {
 116       return i;
 117     }
 118   }
 119   throw std::runtime_error("Board with no hole");
 120 }
 121
 122 InvertedBoard Board::invert() const {
 123   InvertedBoard inv;
 124   for (int i = 0; i < BOARD_SIZE; i++) {
 125     inv.pos[board[i]] = i;
 126   }
 127   return inv;
 128 }
 129
 130 int Board::distance(const Board& o) const {
 131   return distance(o.invert());
 132 }
 133
 134 int Board::distance(const InvertedBoard& invo) const {
 135   int dist = 0;
 136   for (int i = 0; i < BOARD_SIZE; i++) {
 137     if (board[i] != 0) {
 138       dist += std::abs(i % BOARD_DIM - invo.pos[board[i]] % BOARD_DIM) +
 139               std::abs(i / BOARD_DIM - invo.pos[board[i]] / BOARD_DIM);
 140     }
 141   }
 142   return dist;
 143 }
 144
 145 Step::Step(Board board, std::shared_ptr<Step> prev) : board(board), prev(prev) {
 146   count++;
 147 }
 148
 149 Step::~Step() {
 150   count--;
 151 }
 152
 153 std::vector<std::shared_ptr<Step>> Step::successors(std::shared_ptr<Step> shared_this) const {
 154   std::vector<std::shared_ptr<Step>> suc;
 155   signed char hole_pos = board.hole();
 156   for (int i = 0; adjacent[hole_pos][i] >= 0; i++) {
 157     suc.emplace_back(std::make_shared<Step>(board, shared_this));
 158     std::swap(suc.back()->board.board[hole_pos], suc.back()->board.board[adjacent[hole_pos][i]]);
 159   }
 160   return suc;
 161 }
 162
 163 int Step::length() const {
 164   if (prev.get() == nullptr) {
 165     return 0;
 166   }
 167   return 1 + prev->length();
 168 }
 169
 170 int Step::cost(const InvertedBoard& invgoal) const {
 171   return length() + board.distance(invgoal) / 2;
 172 }
 173
 174 std::ostream& operator<<(std::ostream& os, const Step& step) {
 175   if (step.prev != nullptr) {
 176     os << *step.prev;
 177     signed char this_hole = step.board.hole();
 178     signed char prev_hole = step.prev->board.hole();
 179     os << int(step.board.board[prev_hole]) << " ";
 180     switch (this_hole - prev_hole) {
 181       case -1:         os << "right";    break;
 182       case  1:         os << "left";     break;
 183       case -BOARD_DIM: os << "down";     break;
 184       case BOARD_DIM:  os << "up";       break;
 185       default:         os << "somehow!"; break;
 186     }
 187     os << std::endl;
 188   }
 189   return os;
 190 }
 191
 192 std::shared_ptr<Step> find_path(const std::string& start, const std::string& goal, unsigned max_frontier) {
 193   std::istringstream iss_start{start}, iss_goal{goal};
 194   Board board_start, board_goal;
 195   iss_start >> board_start;
 196   iss_goal >> board_goal;
 197   if (iss_start.fail() || !iss_start.eof()) {
 198     throw std::runtime_error("Could not parse the start board: " + start);
 199   }
 200   if (iss_goal.fail() || !iss_goal.eof()) {
 201     throw std::runtime_error("Could not parse the goal board: " + goal);
 202   }
 203   return find_path(board_start, board_goal, max_frontier);
 204 }
 205
 206 std::shared_ptr<Step> find_path(const Board& start, const Board& goal, unsigned max_frontier) {
 207   InvertedBoard invgoal = goal.invert();
 208   std::multimap<int, std::shared_ptr<Step>> todo;
 209   std::set<Board> seen;
 210
 211   seen.insert(start);
 212   auto start_step = std::make_shared<Step>(start, nullptr);
 213   todo.emplace(start_step->cost(invgoal), start_step);
 214   while (!todo.empty()) {
 215     auto cur = todo.begin()->second;
 216     todo.erase(todo.begin());
 217     if (cur->board == goal) {
 218       return cur;
 219     }
 220     std::vector<std::shared_ptr<Step>> successors = cur->successors(cur);
 221     for (const std::shared_ptr<Step>& s : successors) {
 222       if (seen.find(s->board) == seen.end()) {
 223         seen.insert(s->board);
 224         todo.emplace(s->cost(invgoal), s);
 225         if (seen.size() % 10000 == 0) {
 226           std::cerr << "Examined " << seen.size() << " boards.  Tracking "
 227                     << Step::count << " steps.  " << todo.size()
 228                     << " waiting.  Considering paths of length "
 229                     << cur->cost(invgoal) << std::endl;
 230         }
 231       }
 232     }
 233     while (todo.size() > max_frontier) {
 234       todo.erase(--todo.end());
 235     }
 236   }
 237   throw std::runtime_error("No path from start to goal");
 238 }