From: Scott Worley Date: Sat, 2 Jan 2016 08:52:39 +0000 (-0800) Subject: Generate successor boards X-Git-Url: http://git.scottworley.com/slidingtile/commitdiff_plain/5d2f7c7cebb5423fa9618a28871a81671c380041?ds=sidebyside;hp=33bb98f505ab425f693f1e8a6a1bb694a83dff92 Generate successor boards --- diff --git a/sliding_tile_lib.cc b/sliding_tile_lib.cc index aee8380..b43cbba 100644 --- a/sliding_tile_lib.cc +++ b/sliding_tile_lib.cc @@ -2,10 +2,12 @@ #include #include +#include #include #include +#include -signed char adjacent[BOARD_SIZE][5] = { +signed char Step::adjacent[BOARD_SIZE][5] = { 1, 4, -1, -1, -1, 0, 2, 5, -1, -1, 1, 3, 6, -1, -1, @@ -106,3 +108,13 @@ int Board::distance(const InvertedBoard& invo) const { } return dist; } + +std::vector Step::successors(std::shared_ptr shared_this) { + std::vector suc; + signed char hole_pos = board.hole(); + for (int i = 0; adjacent[hole_pos][i] > 0; i++) { + suc.emplace_back(new Step{board, shared_this}); + std::swap(suc.back()->board.board[hole_pos], suc.back()->board.board[adjacent[hole_pos][i]]); + } + return suc; +} diff --git a/sliding_tile_lib.h b/sliding_tile_lib.h index c5d0a8b..0bd3da3 100644 --- a/sliding_tile_lib.h +++ b/sliding_tile_lib.h @@ -2,7 +2,9 @@ #define _SLIDING_TILE_LIB_H #include +#include #include +#include const int BOARD_DIM = 4; const int BOARD_SIZE = BOARD_DIM * BOARD_DIM; @@ -22,6 +24,12 @@ struct Board { std::istream& operator>>(std::istream& is, Board& board); std::ostream& operator<<(std::ostream& os, const Board& board); -extern signed char adjacent[BOARD_SIZE][5]; +struct Step { + Board board; + std::shared_ptr prev; + std::vector successors(std::shared_ptr shared_this); + static signed char adjacent[BOARD_SIZE][5]; +}; + #endif /* _SLIDING_TILE_LIB_H */ diff --git a/sliding_tile_lib_test.cc b/sliding_tile_lib_test.cc index f142795..aea4ab7 100644 --- a/sliding_tile_lib_test.cc +++ b/sliding_tile_lib_test.cc @@ -4,7 +4,10 @@ #include "gmock/gmock.h" #include -TEST(Adjacency, Adjacency) { +using testing::Field; +using testing::ElementsAreArray; + +TEST(Step, Adjacency) { const signed char LEFT = -1; const signed char RIGHT = +1; const signed char UP = -BOARD_DIM; @@ -26,8 +29,8 @@ TEST(Adjacency, Adjacency) { } std::vector actual; - for (int j = 0; adjacent[i][j] >= 0; j++) { - actual.push_back(adjacent[i][j]); + for (int j = 0; Step::adjacent[i][j] >= 0; j++) { + actual.push_back(Step::adjacent[i][j]); } EXPECT_THAT(actual, testing::UnorderedElementsAreArray(expected)); } @@ -39,7 +42,7 @@ TEST(Board, GoodInput) { is >> b; EXPECT_FALSE(is.fail()); EXPECT_TRUE(is.eof()); - EXPECT_THAT(b.board, testing::ElementsAreArray({15,14,9,13,3,1,12,8,0,11,6,4,7,5,2,10})); + EXPECT_THAT(b.board, ElementsAreArray({15,14,9,13,3,1,12,8,0,11,6,4,7,5,2,10})); } TEST(Board, ShortInput) { @@ -115,3 +118,21 @@ TEST(Board, MaxDistance) { Board b2{{0,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1}}; EXPECT_EQ(64, b1.distance(b2)); } + +TEST(Step, TwoSuccessors) { + auto s = std::shared_ptr(new Step{{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0}}, nullptr}); + std::vector suc = s->successors(s); + EXPECT_THAT(suc, testing::UnorderedElementsAre( + Field(&Step::board, Field(&Board::board, ElementsAreArray({1,2,3,4,5,6,7,8,9,10,11,12,13,14,0,15}))), + Field(&Step::board, Field(&Board::board, ElementsAreArray({1,2,3,4,5,6,7,8,9,10,11,0,13,14,15,12}))))); +} + +TEST(Step, FourSuccessors) { + auto s = std::shared_ptr(new Step{{{1,2,3,4,5,0,6,7,8,9,10,11,12,13,14,15}}, nullptr}); + std::vector suc = s->successors(s); + EXPECT_THAT(suc, testing::UnorderedElementsAre( + Field(&Step::board, Field(&Board::board, ElementsAreArray({1,2,3,4,0,5,6,7,8,9,10,11,12,13,14,15}))), + Field(&Step::board, Field(&Board::board, ElementsAreArray({1,2,3,4,5,6,0,7,8,9,10,11,12,13,14,15}))), + Field(&Step::board, Field(&Board::board, ElementsAreArray({1,0,3,4,5,2,6,7,8,9,10,11,12,13,14,15}))), + Field(&Step::board, Field(&Board::board, ElementsAreArray({1,2,3,4,5,9,6,7,8,0,10,11,12,13,14,15}))))); +}