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