]> git.scottworley.com Git - slidingtile/blame - sliding_tile_lib.cc
successors is const
[slidingtile] / sliding_tile_lib.cc
CommitLineData
82d6eed5
SW
1#include "sliding_tile_lib.h"
2
9c32325f 3#include <cstdlib>
32688d85 4#include <istream>
5d2f7c7c 5#include <memory>
cada47bf 6#include <ostream>
f3f55aff 7#include <stdexcept>
5d2f7c7c 8#include <vector>
32688d85 9
5d2f7c7c 10signed char Step::adjacent[BOARD_SIZE][5] = {
82d6eed5
SW
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};
32688d85 28
cea272cf 29bool Board::is_valid() const {
b18667f2
SW
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
0e89d341
SW
52bool 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
61bool Board::operator!=(const Board& o) const {
62 return !operator==(o);
63}
64
310a7132
SW
65bool 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
32688d85
SW
76std::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;
19bd29f9 88 board.board[i] = numeric;
32688d85 89 }
b18667f2
SW
90 if (!board.is_valid()) {
91 is.setstate(std::istream::failbit);
92 }
32688d85
SW
93 return is;
94}
f3f55aff 95
cada47bf
SW
96std::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
cea272cf 106signed char Board::hole() const {
f3f55aff
SW
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}
9c32325f
SW
114
115InvertedBoard 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
123int Board::distance(const Board& o) const {
124 return distance(o.invert());
125}
126
127int 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}
5d2f7c7c 135
f92e9dca 136std::vector<Step*> Step::successors(std::shared_ptr<Step> shared_this) const {
5d2f7c7c
SW
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}
49358f36
SW
145
146std::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}