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 <stdexcept>
   8 #include <vector>
   9
  10 signed char Step::adjacent[BOARD_SIZE][5] = {
  11   1,   4,   -1,  -1,  -1,
  12   0,   2,   5,   -1,  -1,
  13   1,   3,   6,   -1,  -1,
  14   2,   7,   -1,  -1,  -1,
  15   0,   5,   8,   -1,  -1,
  16   1,   4,   6,   9,   -1,
  17   2,   5,   7,   10,  -1,
  18   3,   6,   11,  -1,  -1,
  19   4,   9,   12,  -1,  -1,
  20   5,   8,   10,  13,  -1,
  21   6,   9,   11,  14,  -1,
  22   7,   10,  15,  -1,  -1,
  23   8,   13,  -1,  -1,  -1,
  24   9,   12,  14,  -1,  -1,
  25   10,  13,  15,  -1,  -1,
  26   11,  14,  -1,  -1,  -1,
  27 };
  28
  29 bool Board::is_valid() const {
  30   bool seen[BOARD_SIZE];
  31   for (int i = 0; i < BOARD_SIZE; i++) {
  32     seen[i] = false;
  33   }
  34
  35   for (int i = 0; i < BOARD_SIZE; i++) {
  36     if (board[i] < 0 || board[i] >= BOARD_SIZE || seen[board[i]]) {
  37       return false;
  38     }
  39     seen[board[i]] = true;
  40   }
  41
  42   // Redundant because pigeon-hole-principle, but check anyway
  43   for (int i = 0; i < BOARD_SIZE; i++) {
  44     if (!seen[i]) {
  45       return false;
  46     }
  47   }
  48
  49   return true;
  50 }
  51
  52 bool Board::operator==(const Board& o) const {
  53   for (int i = 0; i < BOARD_SIZE; i++) {
  54     if (board[i] != o.board[i]) {
  55       return false;
  56     }
  57   }
  58   return true;
  59 }
  60
  61 bool Board::operator!=(const Board& o) const {
  62   return !operator==(o);
  63 }
  64
  65 std::istream& operator>>(std::istream& is, Board& board) {
  66   for (int i = 0; i < BOARD_SIZE; i++) {
  67     if (!is.good()) {
  68       is.setstate(std::istream::failbit);
  69       break;
  70     }
  71     if (i > 0 && is.get() != ',') {
  72       is.setstate(std::istream::failbit);
  73       break;
  74     }
  75     int numeric;
  76     is >> numeric;
  77     board.board[i] = numeric;
  78   }
  79   if (!board.is_valid()) {
  80     is.setstate(std::istream::failbit);
  81   }
  82   return is;
  83 }
  84
  85 std::ostream& operator<<(std::ostream& os, const Board& board) {
  86   for (int i = 0; i < BOARD_SIZE; i++) {
  87     if (i > 0) {
  88       os << " ";
  89     }
  90     os << int(board.board[i]);
  91   }
  92   return os;
  93 }
  94
  95 signed char Board::hole() const {
  96   for (int i = 0; i < BOARD_SIZE; i++) {
  97     if (board[i] == 0) {
  98       return i;
  99     }
 100   }
 101   throw std::runtime_error("Board with no hole");
 102 }
 103
 104 InvertedBoard Board::invert() const {
 105   InvertedBoard inv;
 106   for (int i = 0; i < BOARD_SIZE; i++) {
 107     inv.pos[board[i]] = i;
 108   }
 109   return inv;
 110 }
 111
 112 int Board::distance(const Board& o) const {
 113   return distance(o.invert());
 114 }
 115
 116 int Board::distance(const InvertedBoard& invo) const {
 117   int dist = 0;
 118   for (int i = 0; i < BOARD_SIZE; i++) {
 119     dist += std::abs(i % BOARD_DIM - invo.pos[board[i]] % BOARD_DIM) +
 120             std::abs(i / BOARD_DIM - invo.pos[board[i]] / BOARD_DIM);
 121   }
 122   return dist;
 123 }
 124
 125 std::vector<Step*> Step::successors(std::shared_ptr<Step> shared_this) {
 126   std::vector<Step*> suc;
 127   signed char hole_pos = board.hole();
 128   for (int i = 0; adjacent[hole_pos][i] > 0; i++) {
 129     suc.emplace_back(new Step{board, shared_this});
 130     std::swap(suc.back()->board.board[hole_pos], suc.back()->board.board[adjacent[hole_pos][i]]);
 131   }
 132   return suc;
 133 }
 134
 135 std::ostream& operator<<(std::ostream& os, const Step& step) {
 136   if (step.prev != nullptr) {
 137     os << *step.prev;
 138     signed char this_hole = step.board.hole();
 139     signed char prev_hole = step.prev->board.hole();
 140     os << int(step.board.board[prev_hole]) << " ";
 141     switch (this_hole - prev_hole) {
 142       case -1:         os << "right";    break;
 143       case  1:         os << "left";     break;
 144       case -BOARD_DIM: os << "down";     break;
 145       case BOARD_DIM:  os << "up";       break;
 146       default:         os << "somehow!"; break;
 147     }
 148     os << std::endl;
 149   }
 150   return os;
 151 }