Added solver class, pruning table generating works

6 files changed, 105 insertions, 23 deletions

diff --git a/.gitignore b/.gitignore
index a173085..e9a99d2 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1 +1,4 @@
 .ccls-cache
+compile_commands.json
+solver4
+build
diff --git a/src/algo.cpp b/src/algo.cpp
deleted file mode 100644
index 56ed646..0000000
--- a/src/algo.cpp
+++ /dev/null
@@ -1,5 +0,0 @@
-#include "cube.h"
-
-int main() {
-  printf("Hello, world!");
-}
diff --git a/src/cube.h b/src/cube.h
index 3ea20eb..c050d22 100644
--- a/src/cube.h
+++ b/src/cube.h
@@ -1,10 +1,10 @@
+#ifndef _CUBE_H_
+#define _CUBE_H_
+
 #ifdef __cplusplus
 extern "C" {
 #endif
 
-#ifndef _CUBE_H_
-#define _CUBE_H_
-
 #include <stdio.h>
 #include <stdint.h>
 #include <stdlib.h>
@@ -172,6 +172,11 @@ static const rot_f rot_func[] = {
   rotation_b2,
 };
 
+static inline void perform_rotation(cube_t *cube, rotations rot) {
+  if (rot != NULL_ROT)
+	rot_func[rot](cube);
+}
+
 static void perform_rotations(cube_t *cube, rotations rots[]) {
   while(*rots != NULL_ROT) {
 	rot_func[*rots](cube);	
@@ -328,7 +333,9 @@ static void dump_cube_grid(cube_t *cube) {
   int i, j, row, col;
   colors buf[3][4][3][3];	/* XD */
 
-  memset(buf, -1, 3*4*3*3*sizeof(colors));
+  for (i = 0; i < 3*4*3*3; i++) {
+	((colors *)buf)[i] = EMPTY_COLOR;
+  }
   fill_face(cube, UP, buf[0][1]);
   fill_face(cube, LEFT, buf[1][0]);
   fill_face(cube, FRONT, buf[1][1]);
@@ -341,7 +348,7 @@ static void dump_cube_grid(cube_t *cube) {
 	  for (j = 0; j < 4; j++) {
 		for (col = 0; col < 3; col++) {
 		  colors color = buf[i][j][row][col];
-		  printf("%s", (color == -1 ? " " : terminal_letters[color])); 
+		  printf("%s", (color == EMPTY_COLOR ? " " : terminal_letters[color])); 
 		} 
 	  }
 	  printf("\n");
@@ -363,28 +370,23 @@ static void dump_cube_grid(cube_t *cube) {
 #define kh_cube_hash_func(cube) (khint32_t)((first_64(cube)*P1+second_64(cube)*P2+third_64(cube)*P3)%(uint64_t)MOD_M)
 #define kh_cube_hash_equal(cube1, cube2) (first_64(cube1) == first_64(cube2) && second_64(cube1) == second_64(cube2) && third_64(cube1) == third_64(cube2))
 
+typedef uint32_t rot_cnt_t;
+#define build_rot_cnt(rot, cnt) (rot_cnt_t)(((uint32_t)(rot) << 16)|(cnt))
+#define get_rot(rot_cnt) (((uint32_t)(rot_cnt))>>16)
+#define get_cnt(rot_cnt) (uint32_t)((rot_cnt) & 0xffff)
+
+KHASH_INIT(cube, cube_t, rot_cnt_t, 1, kh_cube_hash_func, kh_cube_hash_equal)
 
 #endif /* FACE32 */ 
 
 /******************************************************************************/
 /* Algorithm ******************************************************************/
 
-typedef uint32_t rot_cnt_t;
-#define build_rot_cnt(rot, cnt) (rot_cnt_t)(((uint32_t)rot << 16)|cnt)
-#define get_rot(rot_cnt) (((uint32_t)rot_cnt)>>16)
-#define get_cnt(rot_cnt) (uint32_t)(rot_cnt & 0xffff)
-
-KHASH_INIT(cube, cube_t, rot_cnt_t, 1, kh_cube_hash_func, kh_cube_hash_equal)
-
-khash_t(cube) *generate_pruning_table(int depth) {
-  khash_t(cube) *h = kh_init(cube); 
-
-}
 
 /******************************************************************************/
 /* Main ***********************************************************************/
 
-void test_scrambling() {
+static void test_scrambling() {
   cube_t cube;
   int i;
   char *buf = NULL;
@@ -408,8 +410,9 @@ void test_scrambling() {
 	free(buf);
 }
 
-#endif /* _CUBE_H_ */
 
 #ifdef __cplusplus
 }
 #endif
+
+#endif /* _CUBE_H_ */
diff --git a/src/main.cpp b/src/main.cpp
new file mode 100644
index 0000000..b66e3be
--- /dev/null
+++ b/src/main.cpp
@@ -0,0 +1,5 @@
+#include "solver.hpp"
+
+int main() {
+  Solver solver(6);
+}
diff --git a/src/solver.cpp b/src/solver.cpp
new file mode 100644
index 0000000..98e8a13
--- /dev/null
+++ b/src/solver.cpp
@@ -0,0 +1,57 @@
+#include <queue>
+#include <iostream>
+#include "solver.hpp"
+
+Solver::Solver(uint32_t pruning_tab_depth) {
+  pruning_table = kh_init_cube();
+  visited_states = kh_init_cube(); 
+
+  generate_pruning_table(pruning_tab_depth);
+}
+
+void Solver::generate_pruning_table(uint32_t depth) {
+  std::cerr << "Generating pruning table...\n";
+  cube_t initial, cube, rotated;
+  rot_cnt_t rot_cnt;
+  uint16_t rot, cnt;
+  int ret;
+  khint_t k;
+  std::queue<cube_t> q;
+
+  init_cube(&initial);
+  k = kh_put_cube(pruning_table, initial, &ret);
+  kh_val(pruning_table, k) = build_rot_cnt(NULL_ROT, 0);
+
+  q.push(initial);
+
+  while(!q.empty()) {
+	cube = q.front();
+	q.pop();
+
+	// std::cerr << "processing cube:\n";
+	// dump_cube_grid(&cube);
+
+	k = kh_get_cube(pruning_table, cube);
+	rot_cnt = kh_val(pruning_table, k);
+	cnt = get_cnt(rot_cnt);
+	// std::cerr << cnt << "\n";
+	if (cnt >= depth) 
+	  continue;
+	
+	for (rot = ROT_R; rot != NULL_ROT; rot++) {
+	  rotated = cube;
+	  perform_rotation(&rotated, (rotations)rot); 
+	  
+	  k = kh_get_cube(pruning_table, rotated);
+	  if (k == kh_end(pruning_table)) {
+		k = kh_put_cube(pruning_table, rotated, &ret);	
+		kh_val(pruning_table, k) = build_rot_cnt(rot, cnt+1);
+		q.push(rotated);
+
+		// printf("Cube cnt: %d\n", cnt+1);
+		// dump_cube_grid(&rotated);
+	  }
+	}
+  }
+  std::cerr << "Generated\n";
+}
diff --git a/src/solver.hpp b/src/solver.hpp
new file mode 100644
index 0000000..8c51b56
--- /dev/null
+++ b/src/solver.hpp
@@ -0,0 +1,19 @@
+#ifndef _ALGO_HPP_
+#define _ALGO_HPP_
+
+#include <vector>
+
+#include "cube.h"
+
+class Solver {
+private:
+  kh_cube_t *pruning_table;
+  kh_cube_t *visited_states;
+
+  void generate_pruning_table(uint32_t depth);
+public:
+  Solver(uint32_t pruning_tab_depth=0);
+  std::vector<rotations> solve(cube_t *cube);
+};
+
+#endif /* _ALGO_HPP_ */