]> git.scottworley.com Git - slidingtile/blob - sliding_tile_lib.cc
Board equality operator
[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 std::istream& operator>>(std::istream& is, Board& board) {
66 for (int i = 0; i < BOARD_SIZE; i++) {
67 if (!is.good()) {
68 is.setstate(std::istream::failbit);
69 break;
70 }
71 if (i > 0 && is.get() != ',') {
72 is.setstate(std::istream::failbit);
73 break;
74 }
75 int numeric;
76 is >> numeric;
77 board.board[i] = numeric;
78 }
79 if (!board.is_valid()) {
80 is.setstate(std::istream::failbit);
81 }
82 return is;
83 }
84
85 std::ostream& operator<<(std::ostream& os, const Board& board) {
86 for (int i = 0; i < BOARD_SIZE; i++) {
87 if (i > 0) {
88 os << " ";
89 }
90 os << int(board.board[i]);
91 }
92 return os;
93 }
94
95 signed char Board::hole() const {
96 for (int i = 0; i < BOARD_SIZE; i++) {
97 if (board[i] == 0) {
98 return i;
99 }
100 }
101 throw std::runtime_error("Board with no hole");
102 }
103
104 InvertedBoard Board::invert() const {
105 InvertedBoard inv;
106 for (int i = 0; i < BOARD_SIZE; i++) {
107 inv.pos[board[i]] = i;
108 }
109 return inv;
110 }
111
112 int Board::distance(const Board& o) const {
113 return distance(o.invert());
114 }
115
116 int Board::distance(const InvertedBoard& invo) const {
117 int dist = 0;
118 for (int i = 0; i < BOARD_SIZE; i++) {
119 dist += std::abs(i % BOARD_DIM - invo.pos[board[i]] % BOARD_DIM) +
120 std::abs(i / BOARD_DIM - invo.pos[board[i]] / BOARD_DIM);
121 }
122 return dist;
123 }
124
125 std::vector<Step*> Step::successors(std::shared_ptr<Step> shared_this) {
126 std::vector<Step*> suc;
127 signed char hole_pos = board.hole();
128 for (int i = 0; adjacent[hole_pos][i] > 0; i++) {
129 suc.emplace_back(new Step{board, shared_this});
130 std::swap(suc.back()->board.board[hole_pos], suc.back()->board.board[adjacent[hole_pos][i]]);
131 }
132 return suc;
133 }
134
135 std::ostream& operator<<(std::ostream& os, const Step& step) {
136 if (step.prev != nullptr) {
137 os << *step.prev;
138 signed char this_hole = step.board.hole();
139 signed char prev_hole = step.prev->board.hole();
140 os << int(step.board.board[prev_hole]) << " ";
141 switch (this_hole - prev_hole) {
142 case -1: os << "right"; break;
143 case 1: os << "left"; break;
144 case -BOARD_DIM: os << "down"; break;
145 case BOARD_DIM: os << "up"; break;
146 default: os << "somehow!"; break;
147 }
148 os << std::endl;
149 }
150 return os;
151 }