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