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