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