From 87a15e960e31365698df7e06cd3e6b851e17c1a5 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Sun, 5 Mar 2023 10:13:01 +0100 Subject: I made a mess, but it works. Still need to implement new optimal solver. After that, a big redesign is due. --- src/solver_step.c | 296 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 296 insertions(+) create mode 100644 src/solver_step.c (limited to 'src/solver_step.c') diff --git a/src/solver_step.c b/src/solver_step.c new file mode 100644 index 0000000..5c9d149 --- /dev/null +++ b/src/solver_step.c @@ -0,0 +1,296 @@ +#include "solver_step.h" + +typedef struct { + Cube * cube; + uint64_t * val; + Trans * t; +} CubeData; + +static void apply_alg_cubedata(void *, void *, Alg *); +static void init_indexes(Step *, CubeData *); +static void * prepare_cube(void *, Cube *); +static bool move_check_stop_eager(void *, DfsArg *, Threader *); +static bool move_check_stop_lazy(void *, DfsArg *, Threader *); +static bool move_check_stop_nonsol(void *, DfsArg *, Threader *); +static bool is_solved_step(void *, void *); +static Alg * validate_solution(void *, Alg *); +static void * alloc_cubedata(void *); +static void copy_cubedata(void *, void *, void *); +static void free_cubedata(void *, void *); +static void invert_cubedata(void *, void *); +static bool niss_makes_sense(void *, void *, Alg *); +static Solver * new_stepsolver_nocheckstop(Step *step); + +static void +apply_alg_cubedata(void *param, void *cubedata, Alg *alg) +{ + Step *s = (Step *)param; + CubeData *data = (CubeData *)cubedata; + + apply_alg(alg, data->cube); + init_indexes(s, data); +} + +static void +init_indexes(Step *step, CubeData *data) +{ + int i; + Cube moved; + Trans t, tt; + + for (i = 0; i < step->n_coord; i++) { + t = step->coord_trans[i]; + copy_cube(data->cube, &moved); + apply_trans(t, &moved); + data->val[i] = index_coord(step->coord[i], &moved, &tt); + data->t[i] = transform_trans(tt, t); + } +} + +static void * +prepare_cube(void *param, Cube *cube) +{ + int i; + Step *s; + CubeData *data; + + s = (Step *)param; + + for (i = 0; i < s->n_coord; i++) { + s->pd[i] = malloc(sizeof(PruneData)); + s->pd[i]->moveset = s->moveset; +/* TODO: check if moveset initialization works fine, + e.g. if there is a variable to save the initialized status + or if it gets initialized multiple times */ + init_moveset(s->moveset); + s->pd[i]->coord = s->coord[i]; + gen_coord(s->coord[i]); + s->pd[i]->compact = s->pd_compact[i]; + s->pd[i] = genptable(s->pd[i], 4); /* TODO: threads */ + } + + data = alloc_cubedata(param); + data->cube = malloc(sizeof(Cube)); + copy_cube(cube, data->cube); + init_indexes(s, data); + + return data; +} + +static bool +move_check_stop_eager(void *param, DfsArg *arg, Threader *threader) +{ + int nsol; + + if (move_check_stop_nonsol(param, arg, threader)) + return true; + + nsol = threader->get_nsol(arg->threaddata); + return nsol >= arg->opts->max_solutions; +} + +static bool +move_check_stop_lazy(void *param, DfsArg *arg, Threader *threader) +{ + int nsol; + + nsol = threader->get_nsol(arg->threaddata); + if (nsol >= arg->opts->max_solutions) + return true; + + return move_check_stop_nonsol(param, arg, threader); +} + +static bool +move_check_stop_nonsol(void *param, DfsArg *arg, Threader *threader) +{ + int i, goal, bound; + Move mm, lastmove; + Trans tt = uf; + CubeData *data; + Step *s; + + s = (Step *)param; + data = (CubeData *)arg->cubedata; + + bound = 0; + goal = arg->d - arg->current_alg->len; +/* TODO: check if len is 0 */ + lastmove = arg->current_alg->move[arg->current_alg->len-1]; + for (i = 0; i < s->n_coord; i++) { + mm = transform_move(data->t[i], lastmove); + data->val[i] = move_coord(s->coord[i], mm, data->val[i], &tt); + data->t[i] = transform_trans(tt, data->t[i]); + + bound = MAX(bound, ptableval(s->pd[i], data->val[i])); + if (arg->opts->can_niss && !arg->niss) + bound = MIN(1, bound); + + if (bound > goal) { + return true; + } + } + + return false; +} + +static bool +is_solved_step(void *param, void *cubedata) +{ + int i; + Step *s; + CubeData *data; + + s = (Step *)param; + data = (CubeData *)cubedata; + + for (i = 0; i < s->n_coord; i++) + if (data->val[i] != 0) + return false; + + return true; +} + +static Alg * +validate_solution(void *param, Alg *alg) +{ + return ((Step *)param)->is_valid(alg); +} + +static void * +alloc_cubedata(void *param) +{ + Step *s; + CubeData *data; + + s = (Step *)param; + + data = malloc(sizeof(CubeData)); + /* We do not need to allocate a cube */ + data->val = malloc(s->n_coord * sizeof(uint64_t)); + data->t = malloc(s->n_coord * sizeof(Trans)); + + return data; +} + +static void +copy_cubedata(void *param, void *src, void *dst) +{ + int i; + Step *s; + CubeData *newdata, *olddata; + + s = (Step *)param; + olddata = (CubeData *)src; + newdata = (CubeData *)dst; + + /* Copy reference: we never move the cube */ + newdata->cube = olddata->cube; + for (i = 0; i < s->n_coord; i++) { + newdata->val[i] = olddata->val[i]; + newdata->t[i] = olddata->t[i]; + } +} + +static void +free_cubedata(void *param, void *cubedata) +{ + CubeData *data; + + data = (CubeData *)cubedata; + + free(data->t); + free(data->val); + /* We do not free the cube */ + free(data); +} + +static void +invert_cubedata(void *param, void *cubedata) +{ + Step *s; + CubeData *data; + + s = (Step *)param; + data = (CubeData *)cubedata; + + invert_cube(data->cube); + init_indexes(s, data); +} + +static bool +niss_makes_sense(void *param, void *cubedata, Alg *alg) +{ + Step *s; + CubeData *data; + + s = (Step *)param; + data = (CubeData *)cubedata; + + if (s->final) + return false; + + if (alg->len_normal == 0) + return true; + + Move m = inverse_move(alg->move_normal[alg->len_normal-1]); + for (int i = 0; i < s->n_coord; i++) { + Move mm = transform_move(data->t[i], m); + uint64_t u = move_coord(s->coord[i], mm, 0, NULL); + if (ptableval(s->pd[i], u) > 0) + return true; + } + + return false; +} + +static Solver * +new_stepsolver_nocheckstop(Step *step) +{ + Solver *solver; + + solver = malloc(sizeof(Solver)); + + solver->moveset = step->moveset; + solver->param = step; + + solver->apply_alg = apply_alg_cubedata; + solver->prepare_cube = prepare_cube; + solver->is_solved = is_solved_step; + solver->validate_solution = validate_solution; + solver->alloc_cubedata = alloc_cubedata; + solver->copy_cubedata = copy_cubedata; + solver->free_cubedata = free_cubedata; + solver->invert_cube = invert_cubedata; + solver->niss_makes_sense = niss_makes_sense; + + return solver; +} + +Solver * +new_stepsolver_eager(Step *step) +{ + Solver *solver; + + solver = new_stepsolver_nocheckstop(step); + solver->move_check_stop = move_check_stop_eager; + + return solver; +} + +Solver * +new_stepsolver_lazy(Step *step) +{ + Solver *solver; + + solver = new_stepsolver_nocheckstop(step); + solver->move_check_stop = move_check_stop_lazy; + + return solver; +} + +void +free_stepsolver(Solver *solver) +{ + free(solver); +} -- cgit v1.3