1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
|
#ifndef SOLVING_ALGORITHM_SENTRY
#define SOLVING_ALGORITHM_SENTRY
#include "puzzle.hpp"
#include <memory>
#include <vector>
#include <queue>
#include <unordered_set>
#include <algorithm>
#include <string>
class Node {
private:
std::vector<GameParams::coordinates> state;
Node *parent_p;
int depth;
int evaluation;
friend struct std::hash<std::shared_ptr<Node>>;
friend class ASearch;
public:
Node(std::vector<GameParams::coordinates>& s, Node *p = nullptr,
int d = 0, int e = 0)
: state(s), parent_p(p), depth(d), evaluation(e) {}
bool operator==(const Node& n) const { return this->state == n.state; }
struct Comp {
bool operator()(const std::shared_ptr<Node>& first,
const std::shared_ptr<Node>& second) {
return first->evaluation > second->evaluation;
}
};
};
template<>
struct std::hash<std::shared_ptr<Node>> {
std::size_t operator()(const std::shared_ptr<Node>& node) const {
std::string str_hash;
std::for_each(node->state.begin(), node->state.end(),
[&str_hash](const GameParams::coordinates& c) {
str_hash.append(std::to_string(c.x));
str_hash.append(std::to_string(c.y));
});
return std::hash<std::string>()(str_hash);
}
};
typedef std::vector<std::shared_ptr<Node>> vect_node; // using of
// ComputeFreeMoves
class ASearch {
struct EqualNode {
bool operator()(const std::shared_ptr<Node>& first,
const std::shared_ptr<Node>& second) const {
return *first == *second;
}
};
std::priority_queue<std::shared_ptr<Node>, vect_node, Node::Comp>
open_queue;
std::unordered_set<std::shared_ptr<Node>,
std::hash<std::shared_ptr<Node>>,
EqualNode> close_set;
Node initial;
Node goal;
GameParams *gp;
ASearch(Node i, Node g, GameParams *a_gp = nullptr)
: initial(i), goal(g), gp(a_gp) {}
public:
static std::unique_ptr<ASearch> Start(GameParams *gp);
Node *FindSolution();
void ApplyFairEvaluator(Node &n) const;
vect_node ComputeFreeMoves(const std::shared_ptr<Node>& n) const;
bool IsNearEmptyBox(const GameParams::coordinates c) const;
void ShowSolution(Node *goal);
};
/*
* Priority_queue does not allow to get begin() and end()
* So we get underlying container vector<shared_ptr<Node>>
*
* The container is a protected member of the priority_queue
*/
template <class T, class S, class C>
S& GetPQContainer(std::priority_queue<T, S, C>& q) {
struct HackedQueue : private std::priority_queue<T, S, C> {
static S& Container(std::priority_queue<T, S, C>& q) {
return q.*(&HackedQueue::c); // is pointer to member of class
}
};
return HackedQueue::Container(q);
}
#endif
|
