]> git.scottworley.com Git - slidingtile/blob - sliding_tile_lib.cc
successors is const
[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 <stdexcept>
8 #include <vector>
9
10 signed char Step::adjacent[BOARD_SIZE][5] = {
11 1, 4, -1, -1, -1,
12 0, 2, 5, -1, -1,
13 1, 3, 6, -1, -1,
14 2, 7, -1, -1, -1,
15 0, 5, 8, -1, -1,
16 1, 4, 6, 9, -1,
17 2, 5, 7, 10, -1,
18 3, 6, 11, -1, -1,
19 4, 9, 12, -1, -1,
20 5, 8, 10, 13, -1,
21 6, 9, 11, 14, -1,
22 7, 10, 15, -1, -1,
23 8, 13, -1, -1, -1,
24 9, 12, 14, -1, -1,
25 10, 13, 15, -1, -1,
26 11, 14, -1, -1, -1,
27 };
28
29 bool Board::is_valid() const {
30 bool seen[BOARD_SIZE];
31 for (int i = 0; i < BOARD_SIZE; i++) {
32 seen[i] = false;
33 }
34
35 for (int i = 0; i < BOARD_SIZE; i++) {
36 if (board[i] < 0 || board[i] >= BOARD_SIZE || seen[board[i]]) {
37 return false;
38 }
39 seen[board[i]] = true;
40 }
41
42 // Redundant because pigeon-hole-principle, but check anyway
43 for (int i = 0; i < BOARD_SIZE; i++) {
44 if (!seen[i]) {
45 return false;
46 }
47 }
48
49 return true;
50 }
51
52 bool Board::operator==(const Board& o) const {
53 for (int i = 0; i < BOARD_SIZE; i++) {
54 if (board[i] != o.board[i]) {
55 return false;
56 }
57 }
58 return true;
59 }
60
61 bool Board::operator!=(const Board& o) const {
62 return !operator==(o);
63 }
64
65 bool Board::operator<(const Board& o) const {
66 for (int i = 0; i < BOARD_SIZE; i++) {
67 if (board[i] < o.board[i]) {
68 return true;
69 } else if (board[i] > o.board[i]) {
70 return false;
71 }
72 }
73 return false;
74 }
75
76 std::istream& operator>>(std::istream& is, Board& board) {
77 for (int i = 0; i < BOARD_SIZE; i++) {
78 if (!is.good()) {
79 is.setstate(std::istream::failbit);
80 break;
81 }
82 if (i > 0 && is.get() != ',') {
83 is.setstate(std::istream::failbit);
84 break;
85 }
86 int numeric;
87 is >> numeric;
88 board.board[i] = numeric;
89 }
90 if (!board.is_valid()) {
91 is.setstate(std::istream::failbit);
92 }
93 return is;
94 }
95
96 std::ostream& operator<<(std::ostream& os, const Board& board) {
97 for (int i = 0; i < BOARD_SIZE; i++) {
98 if (i > 0) {
99 os << " ";
100 }
101 os << int(board.board[i]);
102 }
103 return os;
104 }
105
106 signed char Board::hole() const {
107 for (int i = 0; i < BOARD_SIZE; i++) {
108 if (board[i] == 0) {
109 return i;
110 }
111 }
112 throw std::runtime_error("Board with no hole");
113 }
114
115 InvertedBoard Board::invert() const {
116 InvertedBoard inv;
117 for (int i = 0; i < BOARD_SIZE; i++) {
118 inv.pos[board[i]] = i;
119 }
120 return inv;
121 }
122
123 int Board::distance(const Board& o) const {
124 return distance(o.invert());
125 }
126
127 int Board::distance(const InvertedBoard& invo) const {
128 int dist = 0;
129 for (int i = 0; i < BOARD_SIZE; i++) {
130 dist += std::abs(i % BOARD_DIM - invo.pos[board[i]] % BOARD_DIM) +
131 std::abs(i / BOARD_DIM - invo.pos[board[i]] / BOARD_DIM);
132 }
133 return dist;
134 }
135
136 std::vector<Step*> Step::successors(std::shared_ptr<Step> shared_this) const {
137 std::vector<Step*> suc;
138 signed char hole_pos = board.hole();
139 for (int i = 0; adjacent[hole_pos][i] > 0; i++) {
140 suc.emplace_back(new Step{board, shared_this});
141 std::swap(suc.back()->board.board[hole_pos], suc.back()->board.board[adjacent[hole_pos][i]]);
142 }
143 return suc;
144 }
145
146 std::ostream& operator<<(std::ostream& os, const Step& step) {
147 if (step.prev != nullptr) {
148 os << *step.prev;
149 signed char this_hole = step.board.hole();
150 signed char prev_hole = step.prev->board.hole();
151 os << int(step.board.board[prev_hole]) << " ";
152 switch (this_hole - prev_hole) {
153 case -1: os << "right"; break;
154 case 1: os << "left"; break;
155 case -BOARD_DIM: os << "down"; break;
156 case BOARD_DIM: os << "up"; break;
157 default: os << "somehow!"; break;
158 }
159 os << std::endl;
160 }
161 return os;
162 }