From: Scott Worley <scottworley@scottworley.com>
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=inline

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 <cstdlib>
 #include <istream>
+#include <memory>
 #include <ostream>
 #include <stdexcept>
+#include <vector>
 
-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*> Step::successors(std::shared_ptr<Step> shared_this) {
+  std::vector<Step*> 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 <istream>
+#include <memory>
 #include <ostream>
+#include <vector>
 
 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<Step> prev;
+  std::vector<Step*> successors(std::shared_ptr<Step> 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 <vector>
 
-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<signed char> 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<Step>(new Step{{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0}}, nullptr});
+  std::vector<Step*> 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<Step>(new Step{{{1,2,3,4,5,0,6,7,8,9,10,11,12,13,14,15}}, nullptr});
+  std::vector<Step*> 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})))));
+}