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