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 bool Board::operator<(const Board& o) const {
  66   for (int i = 0; i < BOARD_SIZE; i++) {
  67     if (board[i] < o.board[i]) {
  68       return true;
  69     } else if (board[i] > o.board[i]) {
  70       return false;
  71     }
  72   }
  73   return false;
  74 }
  75
  76 std::istream& operator>>(std::istream& is, Board& board) {
  77   for (int i = 0; i < BOARD_SIZE; i++) {
  78     if (!is.good()) {
  79       is.setstate(std::istream::failbit);
  80       break;
  81     }
  82     if (i > 0 && is.get() != ',') {
  83       is.setstate(std::istream::failbit);
  84       break;
  85     }
  86     int numeric;
  87     is >> numeric;
  88     board.board[i] = numeric;
  89   }
  90   if (!board.is_valid()) {
  91     is.setstate(std::istream::failbit);
  92   }
  93   return is;
  94 }
  95
  96 std::ostream& operator<<(std::ostream& os, const Board& board) {
  97   for (int i = 0; i < BOARD_SIZE; i++) {
  98     if (i > 0) {
  99       os << " ";
 100     }
 101     os << int(board.board[i]);
 102   }
 103   return os;
 104 }
 105
 106 signed char Board::hole() const {
 107   for (int i = 0; i < BOARD_SIZE; i++) {
 108     if (board[i] == 0) {
 109       return i;
 110     }
 111   }
 112   throw std::runtime_error("Board with no hole");
 113 }
 114
 115 InvertedBoard Board::invert() const {
 116   InvertedBoard inv;
 117   for (int i = 0; i < BOARD_SIZE; i++) {
 118     inv.pos[board[i]] = i;
 119   }
 120   return inv;
 121 }
 122
 123 int Board::distance(const Board& o) const {
 124   return distance(o.invert());
 125 }
 126
 127 int Board::distance(const InvertedBoard& invo) const {
 128   int dist = 0;
 129   for (int i = 0; i < BOARD_SIZE; i++) {
 130     dist += std::abs(i % BOARD_DIM - invo.pos[board[i]] % BOARD_DIM) +
 131             std::abs(i / BOARD_DIM - invo.pos[board[i]] / BOARD_DIM);
 132   }
 133   return dist;
 134 }
 135
 136 std::vector<Step*> Step::successors(std::shared_ptr<Step> shared_this) {
 137   std::vector<Step*> suc;
 138   signed char hole_pos = board.hole();
 139   for (int i = 0; adjacent[hole_pos][i] > 0; i++) {
 140     suc.emplace_back(new Step{board, shared_this});
 141     std::swap(suc.back()->board.board[hole_pos], suc.back()->board.board[adjacent[hole_pos][i]]);
 142   }
 143   return suc;
 144 }
 145
 146 std::ostream& operator<<(std::ostream& os, const Step& step) {
 147   if (step.prev != nullptr) {
 148     os << *step.prev;
 149     signed char this_hole = step.board.hole();
 150     signed char prev_hole = step.prev->board.hole();
 151     os << int(step.board.board[prev_hole]) << " ";
 152     switch (this_hole - prev_hole) {
 153       case -1:         os << "right";    break;
 154       case  1:         os << "left";     break;
 155       case -BOARD_DIM: os << "down";     break;
 156       case BOARD_DIM:  os << "up";       break;
 157       default:         os << "somehow!"; break;
 158     }
 159     os << std::endl;
 160   }
 161   return os;
 162 }