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