From 537a8dc7ce26e6ab5cf3c82ecce388d08566a8b8 Mon Sep 17 00:00:00 2001 From: Scott Worley Date: Sat, 9 Jan 2016 11:44:08 -0800 Subject: [PATCH] find_path --- sliding_tile.cc | 3 ++ sliding_tile_lib.cc | 73 +++++++++++++++++++++++++++++++++++++--- sliding_tile_lib.h | 11 +++++- sliding_tile_lib_test.cc | 17 +++++----- 4 files changed, 91 insertions(+), 13 deletions(-) diff --git a/sliding_tile.cc b/sliding_tile.cc index 572a6e3..cfa7425 100644 --- a/sliding_tile.cc +++ b/sliding_tile.cc @@ -1,9 +1,12 @@ #include "sliding_tile_lib.h" #include "gflags/gflags.h" +#include + DEFINE_string(start, "", "The starting tile positions. 0 is the hole."); DEFINE_string(goal, "1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0", "The desired tile positions. 0 is the hole."); int main(int argc, char** argv) { gflags::ParseCommandLineFlags(&argc, &argv, false); + std::cout << *find_path(FLAGS_start, FLAGS_goal); } diff --git a/sliding_tile_lib.cc b/sliding_tile_lib.cc index 5284dab..9f6bfc9 100644 --- a/sliding_tile_lib.cc +++ b/sliding_tile_lib.cc @@ -4,9 +4,14 @@ #include #include #include +#include +#include +#include #include #include +#include + signed char Step::adjacent[BOARD_SIZE][5] = { 1, 4, -1, -1, -1, 0, 2, 5, -1, -1, @@ -133,16 +138,29 @@ int Board::distance(const InvertedBoard& invo) const { return dist; } -std::vector Step::successors(std::shared_ptr shared_this) const { - std::vector suc; +Step::Step(Board board, std::shared_ptr prev) : board(board), prev(prev) {} + +std::vector> Step::successors(std::shared_ptr shared_this) const { + 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}); + for (int i = 0; adjacent[hole_pos][i] >= 0; i++) { + suc.emplace_back(std::make_shared(board, shared_this)); std::swap(suc.back()->board.board[hole_pos], suc.back()->board.board[adjacent[hole_pos][i]]); } return suc; } +int Step::length() const { + if (prev.get() == nullptr) { + return 0; + } + return 1 + prev->length(); +} + +int Step::cost(const InvertedBoard& invgoal) const { + return length() + board.distance(invgoal) / 2; +} + std::ostream& operator<<(std::ostream& os, const Step& step) { if (step.prev != nullptr) { os << *step.prev; @@ -160,3 +178,50 @@ std::ostream& operator<<(std::ostream& os, const Step& step) { } return os; } + +std::shared_ptr find_path(const std::string& start, const std::string& goal) { + std::istringstream iss_start{start}, iss_goal{goal}; + Board board_start, board_goal; + iss_start >> board_start; + iss_goal >> board_goal; + if (iss_start.fail() || !iss_start.eof()) { + throw std::runtime_error("Could not parse the start board: " + start); + } + if (iss_goal.fail() || !iss_goal.eof()) { + throw std::runtime_error("Could not parse the goal board: " + goal); + } + return find_path(board_start, board_goal); +} + +std::shared_ptr find_path(const Board& start, const Board& goal) { + InvertedBoard invgoal = goal.invert(); + auto heap_greater = [invgoal](const std::shared_ptr& a, const std::shared_ptr& b) { + return a->cost(invgoal) > b->cost(invgoal); + }; + std::priority_queue, + std::vector>, + decltype(heap_greater)> todo(heap_greater); + std::set seen; + + seen.emplace(start); + todo.push(std::make_shared(start, nullptr)); + while (!todo.empty()) { + if (todo.top()->board == goal) { + return todo.top(); + } + std::vector> successors = todo.top()->successors(todo.top()); + for (const std::shared_ptr& s : successors) { + if (seen.find(s->board) == seen.end()) { + seen.emplace(s->board); + todo.push(s); + if (seen.size() % 10000 == 0) { + std::cerr << "Examined " << seen.size() << " boards. " << todo.size() + << " waiting. Considering paths of length " + << todo.top()->cost(invgoal) << std::endl; + } + } + } + todo.pop(); + } + throw std::runtime_error("No path from start to goal"); +} diff --git a/sliding_tile_lib.h b/sliding_tile_lib.h index 1b56da4..de2ca1f 100644 --- a/sliding_tile_lib.h +++ b/sliding_tile_lib.h @@ -4,6 +4,7 @@ #include #include #include +#include #include const int BOARD_DIM = 4; @@ -28,12 +29,20 @@ std::istream& operator>>(std::istream& is, Board& board); std::ostream& operator<<(std::ostream& os, const Board& board); struct Step { + Step(Board board, std::shared_ptr prev); + Board board; std::shared_ptr prev; - std::vector successors(std::shared_ptr shared_this) const; + + std::vector> successors(std::shared_ptr shared_this) const; + int length() const; + int cost(const InvertedBoard& invgoal) const; + static signed char adjacent[BOARD_SIZE][5]; }; std::ostream& operator<<(std::ostream& os, const Step& step); +std::shared_ptr find_path(const std::string& start, const std::string& goal); +std::shared_ptr find_path(const Board& start, const Board& goal); #endif /* _SLIDING_TILE_LIB_H */ diff --git a/sliding_tile_lib_test.cc b/sliding_tile_lib_test.cc index 5597a1b..25b0e76 100644 --- a/sliding_tile_lib_test.cc +++ b/sliding_tile_lib_test.cc @@ -6,6 +6,7 @@ #include using testing::Field; +using testing::Pointee; TEST(Step, Adjacency) { const signed char LEFT = -1; @@ -141,20 +142,20 @@ TEST(Board, MaxDistance) { TEST(Step, TwoSuccessors) { auto s = std::make_shared(Step{{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0}}, nullptr}); - std::vector suc = s->successors(s); + std::vector> suc = s->successors(s); EXPECT_THAT(suc, testing::UnorderedElementsAre( - Field(&Step::board, Board{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,0,15}}), - Field(&Step::board, Board{{1,2,3,4,5,6,7,8,9,10,11,0,13,14,15,12}}))); + Pointee(Field(&Step::board, Board{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,0,15}})), + Pointee(Field(&Step::board, Board{{1,2,3,4,5,6,7,8,9,10,11,0,13,14,15,12}})))); } TEST(Step, FourSuccessors) { auto s = std::make_shared(Step{{{1,2,3,4,5,0,6,7,8,9,10,11,12,13,14,15}}, nullptr}); - std::vector suc = s->successors(s); + std::vector> suc = s->successors(s); EXPECT_THAT(suc, testing::UnorderedElementsAre( - Field(&Step::board, Board{{1,2,3,4,0,5,6,7,8,9,10,11,12,13,14,15}}), - Field(&Step::board, Board{{1,2,3,4,5,6,0,7,8,9,10,11,12,13,14,15}}), - Field(&Step::board, Board{{1,0,3,4,5,2,6,7,8,9,10,11,12,13,14,15}}), - Field(&Step::board, Board{{1,2,3,4,5,9,6,7,8,0,10,11,12,13,14,15}}))); + Pointee(Field(&Step::board, Board{{1,2,3,4,0,5,6,7,8,9,10,11,12,13,14,15}})), + Pointee(Field(&Step::board, Board{{1,2,3,4,5,6,0,7,8,9,10,11,12,13,14,15}})), + Pointee(Field(&Step::board, Board{{1,0,3,4,5,2,6,7,8,9,10,11,12,13,14,15}})), + Pointee(Field(&Step::board, Board{{1,2,3,4,5,9,6,7,8,0,10,11,12,13,14,15}})))); } TEST(Step, Output) { -- 2.44.1