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     dist += std::abs(i % BOARD_DIM - invo.pos[board[i]] % BOARD_DIM) +
 137             std::abs(i / BOARD_DIM - invo.pos[board[i]] / BOARD_DIM);
 138   }
 139   return dist;
 140 }
 141
 142 Step::Step(Board board, std::shared_ptr<Step> prev) : board(board), prev(prev) {
 143   count++;
 144 }
 145
 146 Step::~Step() {
 147   count--;
 148 }
 149
 150 std::vector<std::shared_ptr<Step>> Step::successors(std::shared_ptr<Step> shared_this) const {
 151   std::vector<std::shared_ptr<Step>> suc;
 152   signed char hole_pos = board.hole();
 153   for (int i = 0; adjacent[hole_pos][i] >= 0; i++) {
 154     suc.emplace_back(std::make_shared<Step>(board, shared_this));
 155     std::swap(suc.back()->board.board[hole_pos], suc.back()->board.board[adjacent[hole_pos][i]]);
 156   }
 157   return suc;
 158 }
 159
 160 int Step::length() const {
 161   if (prev.get() == nullptr) {
 162     return 0;
 163   }
 164   return 1 + prev->length();
 165 }
 166
 167 int Step::cost(const InvertedBoard& invgoal) const {
 168   return length() + board.distance(invgoal) / 2;
 169 }
 170
 171 std::ostream& operator<<(std::ostream& os, const Step& step) {
 172   if (step.prev != nullptr) {
 173     os << *step.prev;
 174     signed char this_hole = step.board.hole();
 175     signed char prev_hole = step.prev->board.hole();
 176     os << int(step.board.board[prev_hole]) << " ";
 177     switch (this_hole - prev_hole) {
 178       case -1:         os << "right";    break;
 179       case  1:         os << "left";     break;
 180       case -BOARD_DIM: os << "down";     break;
 181       case BOARD_DIM:  os << "up";       break;
 182       default:         os << "somehow!"; break;
 183     }
 184     os << std::endl;
 185   }
 186   return os;
 187 }
 188
 189 std::shared_ptr<Step> find_path(const std::string& start, const std::string& goal) {
 190   std::istringstream iss_start{start}, iss_goal{goal};
 191   Board board_start, board_goal;
 192   iss_start >> board_start;
 193   iss_goal >> board_goal;
 194   if (iss_start.fail() || !iss_start.eof()) {
 195     throw std::runtime_error("Could not parse the start board: " + start);
 196   }
 197   if (iss_goal.fail() || !iss_goal.eof()) {
 198     throw std::runtime_error("Could not parse the goal board: " + goal);
 199   }
 200   return find_path(board_start, board_goal);
 201 }
 202
 203 std::shared_ptr<Step> find_path(const Board& start, const Board& goal) {
 204   InvertedBoard invgoal = goal.invert();
 205   auto heap_greater = [invgoal](const std::shared_ptr<Step>& a, const std::shared_ptr<Step>& b) {
 206     return a->cost(invgoal) > b->cost(invgoal);
 207   };
 208   std::priority_queue<std::shared_ptr<Step>,
 209                       std::vector<std::shared_ptr<Step>>,
 210                       decltype(heap_greater)> todo(heap_greater);
 211   std::set<Board> seen;
 212
 213   seen.emplace(start);
 214   todo.push(std::make_shared<Step>(start, nullptr));
 215   while (!todo.empty()) {
 216     if (todo.top()->board == goal) {
 217       return todo.top();
 218     }
 219     std::vector<std::shared_ptr<Step>> successors = todo.top()->successors(todo.top());
 220     for (const std::shared_ptr<Step>& s : successors) {
 221       if (seen.find(s->board) == seen.end()) {
 222         seen.emplace(s->board);
 223         todo.push(s);
 224         if (seen.size() % 10000 == 0) {
 225           std::cerr << "Examined " << seen.size() << " boards.  Tracking "
 226                     << Step::count << " steps.  " << todo.size()
 227                     << " waiting.  Considering paths of length "
 228                     << todo.top()->cost(invgoal) << std::endl;
 229         }
 230       }
 231     }
 232     todo.pop();
 233   }
 234   throw std::runtime_error("No path from start to goal");
 235 }