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 <ostream>
   6 #include <stdexcept>
   7
   8 signed char adjacent[BOARD_SIZE][5] = {
   9   1,   4,   -1,  -1,  -1,
  10   0,   2,   5,   -1,  -1,
  11   1,   3,   6,   -1,  -1,
  12   2,   7,   -1,  -1,  -1,
  13   0,   5,   8,   -1,  -1,
  14   1,   4,   6,   9,   -1,
  15   2,   5,   7,   10,  -1,
  16   3,   6,   11,  -1,  -1,
  17   4,   9,   12,  -1,  -1,
  18   5,   8,   10,  13,  -1,
  19   6,   9,   11,  14,  -1,
  20   7,   10,  15,  -1,  -1,
  21   8,   13,  -1,  -1,  -1,
  22   9,   12,  14,  -1,  -1,
  23   10,  13,  15,  -1,  -1,
  24   11,  14,  -1,  -1,  -1,
  25 };
  26
  27 bool Board::is_valid() const {
  28   bool seen[BOARD_SIZE];
  29   for (int i = 0; i < BOARD_SIZE; i++) {
  30     seen[i] = false;
  31   }
  32
  33   for (int i = 0; i < BOARD_SIZE; i++) {
  34     if (board[i] < 0 || board[i] >= BOARD_SIZE || seen[board[i]]) {
  35       return false;
  36     }
  37     seen[board[i]] = true;
  38   }
  39
  40   // Redundant because pigeon-hole-principle, but check anyway
  41   for (int i = 0; i < BOARD_SIZE; i++) {
  42     if (!seen[i]) {
  43       return false;
  44     }
  45   }
  46
  47   return true;
  48 }
  49
  50 std::istream& operator>>(std::istream& is, Board& board) {
  51   for (int i = 0; i < BOARD_SIZE; i++) {
  52     if (!is.good()) {
  53       is.setstate(std::istream::failbit);
  54       break;
  55     }
  56     if (i > 0 && is.get() != ',') {
  57       is.setstate(std::istream::failbit);
  58       break;
  59     }
  60     int numeric;
  61     is >> numeric;
  62     board.board[i] = numeric;
  63   }
  64   if (!board.is_valid()) {
  65     is.setstate(std::istream::failbit);
  66   }
  67   return is;
  68 }
  69
  70 std::ostream& operator<<(std::ostream& os, const Board& board) {
  71   for (int i = 0; i < BOARD_SIZE; i++) {
  72     if (i > 0) {
  73       os << " ";
  74     }
  75     os << int(board.board[i]);
  76   }
  77   return os;
  78 }
  79
  80 signed char Board::hole() const {
  81   for (int i = 0; i < BOARD_SIZE; i++) {
  82     if (board[i] == 0) {
  83       return i;
  84     }
  85   }
  86   throw std::runtime_error("Board with no hole");
  87 }
  88
  89 InvertedBoard Board::invert() const {
  90   InvertedBoard inv;
  91   for (int i = 0; i < BOARD_SIZE; i++) {
  92     inv.pos[board[i]] = i;
  93   }
  94   return inv;
  95 }
  96
  97 int Board::distance(const Board& o) const {
  98   return distance(o.invert());
  99 }
 100
 101 int Board::distance(const InvertedBoard& invo) const {
 102   int dist = 0;
 103   for (int i = 0; i < BOARD_SIZE; i++) {
 104     dist += std::abs(i % BOARD_DIM - invo.pos[board[i]] % BOARD_DIM) +
 105             std::abs(i / BOARD_DIM - invo.pos[board[i]] / BOARD_DIM);
 106   }
 107   return dist;
 108 }