Added A* solution algorithm

1 files changed, 93 insertions, 0 deletions

diff --git a/solution_algorithm.hpp b/solution_algorithm.hpp
new file mode 100644
index 0000000..440264b
--- /dev/null
+++ b/solution_algorithm.hpp
@@ -0,0 +1,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