]> git.scottworley.com Git - slidingtile/blob - sliding_tile_lib.cc
aee8380c421fe11036f4c9bc957cca971edf6eca
[slidingtile] / sliding_tile_lib.cc
1 #include "sliding_tile_lib.h"
2
3 #include <cstdlib>
4 #include <istream>
5 #include <ostream>
6 #include <stdexcept>
7
8 signed char adjacent[BOARD_SIZE][5] = {
9 1, 4, -1, -1, -1,
10 0, 2, 5, -1, -1,
11 1, 3, 6, -1, -1,
12 2, 7, -1, -1, -1,
13 0, 5, 8, -1, -1,
14 1, 4, 6, 9, -1,
15 2, 5, 7, 10, -1,
16 3, 6, 11, -1, -1,
17 4, 9, 12, -1, -1,
18 5, 8, 10, 13, -1,
19 6, 9, 11, 14, -1,
20 7, 10, 15, -1, -1,
21 8, 13, -1, -1, -1,
22 9, 12, 14, -1, -1,
23 10, 13, 15, -1, -1,
24 11, 14, -1, -1, -1,
25 };
26
27 bool Board::is_valid() const {
28 bool seen[BOARD_SIZE];
29 for (int i = 0; i < BOARD_SIZE; i++) {
30 seen[i] = false;
31 }
32
33 for (int i = 0; i < BOARD_SIZE; i++) {
34 if (board[i] < 0 || board[i] >= BOARD_SIZE || seen[board[i]]) {
35 return false;
36 }
37 seen[board[i]] = true;
38 }
39
40 // Redundant because pigeon-hole-principle, but check anyway
41 for (int i = 0; i < BOARD_SIZE; i++) {
42 if (!seen[i]) {
43 return false;
44 }
45 }
46
47 return true;
48 }
49
50 std::istream& operator>>(std::istream& is, Board& board) {
51 for (int i = 0; i < BOARD_SIZE; i++) {
52 if (!is.good()) {
53 is.setstate(std::istream::failbit);
54 break;
55 }
56 if (i > 0 && is.get() != ',') {
57 is.setstate(std::istream::failbit);
58 break;
59 }
60 int numeric;
61 is >> numeric;
62 board.board[i] = numeric;
63 }
64 if (!board.is_valid()) {
65 is.setstate(std::istream::failbit);
66 }
67 return is;
68 }
69
70 std::ostream& operator<<(std::ostream& os, const Board& board) {
71 for (int i = 0; i < BOARD_SIZE; i++) {
72 if (i > 0) {
73 os << " ";
74 }
75 os << int(board.board[i]);
76 }
77 return os;
78 }
79
80 signed char Board::hole() const {
81 for (int i = 0; i < BOARD_SIZE; i++) {
82 if (board[i] == 0) {
83 return i;
84 }
85 }
86 throw std::runtime_error("Board with no hole");
87 }
88
89 InvertedBoard Board::invert() const {
90 InvertedBoard inv;
91 for (int i = 0; i < BOARD_SIZE; i++) {
92 inv.pos[board[i]] = i;
93 }
94 return inv;
95 }
96
97 int Board::distance(const Board& o) const {
98 return distance(o.invert());
99 }
100
101 int Board::distance(const InvertedBoard& invo) const {
102 int dist = 0;
103 for (int i = 0; i < BOARD_SIZE; i++) {
104 dist += std::abs(i % BOARD_DIM - invo.pos[board[i]] % BOARD_DIM) +
105 std::abs(i / BOARD_DIM - invo.pos[board[i]] / BOARD_DIM);
106 }
107 return dist;
108 }