From: Scott Worley Date: Sat, 2 Jan 2016 05:53:05 +0000 (-0800) Subject: A distance metric X-Git-Url: http://git.scottworley.com/slidingtile/commitdiff_plain/9c32325fbc48baf135d0d7840e99ded70cb738f5?ds=sidebyside A distance metric --- diff --git a/sliding_tile_lib.cc b/sliding_tile_lib.cc index 5037c8e..aee8380 100644 --- a/sliding_tile_lib.cc +++ b/sliding_tile_lib.cc @@ -1,5 +1,6 @@ #include "sliding_tile_lib.h" +#include #include #include #include @@ -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 d144789..c5d0a8b 100644 --- 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 12cc46b..f142795 100644 --- 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)); +}