A distance metric

diff --git a/sliding_tile_lib.cc b/sliding_tile_lib.cc
index 5037c8edbda5877b2ab2d0d2e6ac37d7cd981461..aee8380c421fe11036f4c9bc957cca971edf6eca 100644 (file)
--- a/sliding_tile_lib.cc
+++ b/sliding_tile_lib.cc
@@ -1,5 +1,6 @@
 #include "sliding_tile_lib.h"
 
+#include <cstdlib>
 #include <istream>
 #include <ostream>
 #include <stdexcept>
@@ -84,3 +85,24 @@ signed char Board::hole() const {
   }
   throw std::runtime_error("Board with no hole");
 }
+
+InvertedBoard Board::invert() const {
+  InvertedBoard inv;
+  for (int i = 0; i < BOARD_SIZE; i++) {
+    inv.pos[board[i]] = i;
+  }
+  return inv;
+}
+
+int Board::distance(const Board& o) const {
+  return distance(o.invert());
+}
+
+int Board::distance(const InvertedBoard& invo) const {
+  int dist = 0;
+  for (int i = 0; i < BOARD_SIZE; i++) {
+    dist += std::abs(i % BOARD_DIM - invo.pos[board[i]] % BOARD_DIM) +
+            std::abs(i / BOARD_DIM - invo.pos[board[i]] / BOARD_DIM);
+  }
+  return dist;
+}

diff --git a/sliding_tile_lib.h b/sliding_tile_lib.h
index d144789187c7e91170b46658e37c72a53c01c5e4..c5d0a8bc66c99b7480d06a1c2b96811de9bbe6b6 100644 (file)
--- a/sliding_tile_lib.h
+++ b/sliding_tile_lib.h
@@ -7,10 +7,17 @@
 const int BOARD_DIM = 4;
 const int BOARD_SIZE = BOARD_DIM * BOARD_DIM;
 
+struct InvertedBoard {
+  signed char pos[BOARD_SIZE];
+};
+
 struct Board {
   signed char board[BOARD_SIZE];
   bool is_valid() const;
   signed char hole() const;
+  InvertedBoard invert() const;
+  int distance(const Board& o) const;
+  int distance(const InvertedBoard& invo) const;
 };
 std::istream& operator>>(std::istream& is, Board& board);
 std::ostream& operator<<(std::ostream& os, const Board& board);

diff --git a/sliding_tile_lib_test.cc b/sliding_tile_lib_test.cc
index 12cc46b8a051394b03d7fd93b7d724a25917c92c..f1427950c4bbb982d5d2b9ceb1bae8968dee8e2e 100644 (file)
--- a/sliding_tile_lib_test.cc
+++ b/sliding_tile_lib_test.cc
@@ -86,3 +86,32 @@ TEST(Board, NoHole) {
   Board b{{16,14,9,13,3,1,12,8,16,11,6,4,7,5,2,10}};
   EXPECT_THROW(b.hole(), std::runtime_error);
 }
+
+TEST(Board, ZeroDistance) {
+  Board b{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0}};
+  EXPECT_EQ(0, b.distance(b));
+}
+
+TEST(Board, DistanceAdjacentTilesFlipped) {
+  Board b1{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0}};
+  Board b2{{2,1,3,4,5,6,7,8,9,10,11,12,13,14,15,0}};
+  EXPECT_EQ(2, b1.distance(b2));
+}
+
+TEST(Board, DistanceOneMoveRemaining) {
+  Board b1{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0}};
+  Board b2{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,0,15}};
+  EXPECT_EQ(2, b1.distance(b2));
+}
+
+TEST(Board, DistanceCornersSwapped) {
+  Board b1{{0,2,3,13,5,6,7,8,9,10,11,12,4,14,15,1}};
+  Board b2{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0}};
+  EXPECT_EQ(24, b1.distance(b2));
+}
+
+TEST(Board, MaxDistance) {
+  Board b1{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0}};
+  Board b2{{0,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1}};
+  EXPECT_EQ(64, b1.distance(b2));
+}