git.scottworley.com Git - slidingtile/blob - sliding_tile_lib.cc

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