From d1a5218935ed0007832c85150d5697e1e1d8513e Mon Sep 17 00:00:00 2001 From: Franciszek Malinka Date: Sun, 24 Apr 2022 21:53:07 +0200 Subject: Added solver class, pruning table generating works --- src/algo.cpp | 5 ----- src/cube.h | 39 +++++++++++++++++++++------------------ src/main.cpp | 5 +++++ src/solver.cpp | 57 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/solver.hpp | 19 +++++++++++++++++++ 5 files changed, 102 insertions(+), 23 deletions(-) delete mode 100644 src/algo.cpp create mode 100644 src/main.cpp create mode 100644 src/solver.cpp create mode 100644 src/solver.hpp (limited to 'src') 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 #include #include @@ -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 +#include +#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 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 + +#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 solve(cube_t *cube); +}; + +#endif /* _ALGO_HPP_ */ -- cgit v1.2.3