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