]> git.scottworley.com Git - slidingtile/blame - sliding_tile_lib.cc
Bound the frontier. I.e., do beam search.
[slidingtile] / sliding_tile_lib.cc
CommitLineData
82d6eed5
SW
1#include "sliding_tile_lib.h"
2
9c32325f 3#include <cstdlib>
32688d85 4#include <istream>
dfc82124 5#include <map>
5d2f7c7c 6#include <memory>
cada47bf 7#include <ostream>
537a8dc7
SW
8#include <queue>
9#include <set>
10#include <sstream>
f3f55aff 11#include <stdexcept>
5d2f7c7c 12#include <vector>
32688d85 13
537a8dc7
SW
14#include <iostream>
15
1955dd8b 16int Step::count = 0;
5d2f7c7c 17signed char Step::adjacent[BOARD_SIZE][5] = {
82d6eed5
SW
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};
32688d85 35
cea272cf 36bool Board::is_valid() const {
b18667f2
SW
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
0e89d341
SW
59bool 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
68bool Board::operator!=(const Board& o) const {
69 return !operator==(o);
70}
71
310a7132
SW
72bool 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
32688d85
SW
83std::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;
19bd29f9 95 board.board[i] = numeric;
32688d85 96 }
b18667f2
SW
97 if (!board.is_valid()) {
98 is.setstate(std::istream::failbit);
99 }
32688d85
SW
100 return is;
101}
f3f55aff 102
cada47bf
SW
103std::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
cea272cf 113signed char Board::hole() const {
f3f55aff
SW
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}
9c32325f
SW
121
122InvertedBoard 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
130int Board::distance(const Board& o) const {
131 return distance(o.invert());
132}
133
134int Board::distance(const InvertedBoard& invo) const {
135 int dist = 0;
136 for (int i = 0; i < BOARD_SIZE; i++) {
ab51c07a
SW
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 }
9c32325f
SW
141 }
142 return dist;
143}
5d2f7c7c 144
1955dd8b
SW
145Step::Step(Board board, std::shared_ptr<Step> prev) : board(board), prev(prev) {
146 count++;
147}
148
149Step::~Step() {
150 count--;
151}
537a8dc7
SW
152
153std::vector<std::shared_ptr<Step>> Step::successors(std::shared_ptr<Step> shared_this) const {
154 std::vector<std::shared_ptr<Step>> suc;
5d2f7c7c 155 signed char hole_pos = board.hole();
537a8dc7
SW
156 for (int i = 0; adjacent[hole_pos][i] >= 0; i++) {
157 suc.emplace_back(std::make_shared<Step>(board, shared_this));
5d2f7c7c
SW
158 std::swap(suc.back()->board.board[hole_pos], suc.back()->board.board[adjacent[hole_pos][i]]);
159 }
160 return suc;
161}
49358f36 162
537a8dc7
SW
163int Step::length() const {
164 if (prev.get() == nullptr) {
165 return 0;
166 }
167 return 1 + prev->length();
168}
169
170int Step::cost(const InvertedBoard& invgoal) const {
171 return length() + board.distance(invgoal) / 2;
172}
173
49358f36
SW
174std::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}
537a8dc7 191
8e3c9cff 192std::shared_ptr<Step> find_path(const std::string& start, const std::string& goal, unsigned max_frontier) {
537a8dc7
SW
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 }
8e3c9cff 203 return find_path(board_start, board_goal, max_frontier);
537a8dc7
SW
204}
205
8e3c9cff 206std::shared_ptr<Step> find_path(const Board& start, const Board& goal, unsigned max_frontier) {
537a8dc7 207 InvertedBoard invgoal = goal.invert();
dfc82124 208 std::multimap<int, std::shared_ptr<Step>> todo;
537a8dc7
SW
209 std::set<Board> seen;
210
dfc82124
SW
211 seen.insert(start);
212 auto start_step = std::make_shared<Step>(start, nullptr);
213 todo.emplace(start_step->cost(invgoal), start_step);
537a8dc7 214 while (!todo.empty()) {
dfc82124
SW
215 auto cur = todo.begin()->second;
216 todo.erase(todo.begin());
217 if (cur->board == goal) {
218 return cur;
537a8dc7 219 }
dfc82124 220 std::vector<std::shared_ptr<Step>> successors = cur->successors(cur);
537a8dc7
SW
221 for (const std::shared_ptr<Step>& s : successors) {
222 if (seen.find(s->board) == seen.end()) {
dfc82124
SW
223 seen.insert(s->board);
224 todo.emplace(s->cost(invgoal), s);
537a8dc7 225 if (seen.size() % 10000 == 0) {
1955dd8b
SW
226 std::cerr << "Examined " << seen.size() << " boards. Tracking "
227 << Step::count << " steps. " << todo.size()
537a8dc7 228 << " waiting. Considering paths of length "
dfc82124 229 << cur->cost(invgoal) << std::endl;
537a8dc7
SW
230 }
231 }
232 }
8e3c9cff
SW
233 while (todo.size() > max_frontier) {
234 todo.erase(--todo.end());
235 }
537a8dc7
SW
236 }
237 throw std::runtime_error("No path from start to goal");
238}