]> git.scottworley.com Git - slidingtile/blob - sliding_tile_lib.cc
Don't constrain the hole.
[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 if (board[i] != 0) {
137 dist += std::abs(i % BOARD_DIM - invo.pos[board[i]] % BOARD_DIM) +
138 std::abs(i / BOARD_DIM - invo.pos[board[i]] / BOARD_DIM);
139 }
140 }
141 return dist;
142 }
143
144 Step::Step(Board board, std::shared_ptr<Step> prev) : board(board), prev(prev) {
145 count++;
146 }
147
148 Step::~Step() {
149 count--;
150 }
151
152 std::vector<std::shared_ptr<Step>> Step::successors(std::shared_ptr<Step> shared_this) const {
153 std::vector<std::shared_ptr<Step>> suc;
154 signed char hole_pos = board.hole();
155 for (int i = 0; adjacent[hole_pos][i] >= 0; i++) {
156 suc.emplace_back(std::make_shared<Step>(board, shared_this));
157 std::swap(suc.back()->board.board[hole_pos], suc.back()->board.board[adjacent[hole_pos][i]]);
158 }
159 return suc;
160 }
161
162 int Step::length() const {
163 if (prev.get() == nullptr) {
164 return 0;
165 }
166 return 1 + prev->length();
167 }
168
169 int Step::cost(const InvertedBoard& invgoal) const {
170 return length() + board.distance(invgoal) / 2;
171 }
172
173 std::ostream& operator<<(std::ostream& os, const Step& step) {
174 if (step.prev != nullptr) {
175 os << *step.prev;
176 signed char this_hole = step.board.hole();
177 signed char prev_hole = step.prev->board.hole();
178 os << int(step.board.board[prev_hole]) << " ";
179 switch (this_hole - prev_hole) {
180 case -1: os << "right"; break;
181 case 1: os << "left"; break;
182 case -BOARD_DIM: os << "down"; break;
183 case BOARD_DIM: os << "up"; break;
184 default: os << "somehow!"; break;
185 }
186 os << std::endl;
187 }
188 return os;
189 }
190
191 std::shared_ptr<Step> find_path(const std::string& start, const std::string& goal) {
192 std::istringstream iss_start{start}, iss_goal{goal};
193 Board board_start, board_goal;
194 iss_start >> board_start;
195 iss_goal >> board_goal;
196 if (iss_start.fail() || !iss_start.eof()) {
197 throw std::runtime_error("Could not parse the start board: " + start);
198 }
199 if (iss_goal.fail() || !iss_goal.eof()) {
200 throw std::runtime_error("Could not parse the goal board: " + goal);
201 }
202 return find_path(board_start, board_goal);
203 }
204
205 std::shared_ptr<Step> find_path(const Board& start, const Board& goal) {
206 InvertedBoard invgoal = goal.invert();
207 auto heap_greater = [invgoal](const std::shared_ptr<Step>& a, const std::shared_ptr<Step>& b) {
208 return a->cost(invgoal) > b->cost(invgoal);
209 };
210 std::priority_queue<std::shared_ptr<Step>,
211 std::vector<std::shared_ptr<Step>>,
212 decltype(heap_greater)> todo(heap_greater);
213 std::set<Board> seen;
214
215 seen.emplace(start);
216 todo.push(std::make_shared<Step>(start, nullptr));
217 while (!todo.empty()) {
218 if (todo.top()->board == goal) {
219 return todo.top();
220 }
221 std::vector<std::shared_ptr<Step>> successors = todo.top()->successors(todo.top());
222 for (const std::shared_ptr<Step>& s : successors) {
223 if (seen.find(s->board) == seen.end()) {
224 seen.emplace(s->board);
225 todo.push(s);
226 if (seen.size() % 10000 == 0) {
227 std::cerr << "Examined " << seen.size() << " boards. Tracking "
228 << Step::count << " steps. " << todo.size()
229 << " waiting. Considering paths of length "
230 << todo.top()->cost(invgoal) << std::endl;
231 }
232 }
233 }
234 todo.pop();
235 }
236 throw std::runtime_error("No path from start to goal");
237 }