aboutsummaryrefslogtreecommitdiff
path: root/src/solver_step.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/solver_step.c')
-rw-r--r--src/solver_step.c306
1 files changed, 0 insertions, 306 deletions
diff --git a/src/solver_step.c b/src/solver_step.c
deleted file mode 100644
index 52fa347..0000000
--- a/src/solver_step.c
+++ /dev/null
@@ -1,306 +0,0 @@
1#include "solver_step.h"
2
3typedef struct {
4 Cube * cube;
5 uint64_t * val;
6 Trans * t;
7} CubeData;
8
9static void apply_move_cubedata(void *, void *, Move);
10static void init_indexes(Step *, CubeData *);
11static void * prepare_cube(void *, Cube *);
12static bool move_check_stop_eager(void *, DfsArg *, Threader *);
13static bool move_check_stop_lazy(void *, DfsArg *, Threader *);
14static bool move_check_stop_nonsol(void *, DfsArg *, Threader *);
15static bool is_solved_step(void *, void *);
16static Alg * validate_solution(void *, Alg *);
17static void * alloc_cubedata(void *);
18static void copy_cubedata(void *, void *, void *);
19static void free_cubedata(void *, void *);
20static void invert_cubedata(void *, void *);
21static bool niss_makes_sense(void *, void *, Alg *);
22static Solver * new_stepsolver_nocheckstop(Step *step);
23
24static void
25apply_move_cubedata(void *param, void *cubedata, Move m)
26{
27 Step *s = (Step *)param;
28 CubeData *data = (CubeData *)cubedata;
29
30 Trans tt;
31 for (int i = 0; i < s->n_coord; i++) {
32 Move mm = transform_move(data->t[i], m);
33 data->val[i] = move_coord(s->coord[i], mm, data->val[i], &tt);
34 data->t[i] = transform_trans(tt, data->t[i]);
35 }
36}
37
38static void
39init_indexes(Step *step, CubeData *data)
40{
41 int i;
42 Cube moved;
43 Trans t, tt;
44
45 for (i = 0; i < step->n_coord; i++) {
46 t = step->coord_trans[i];
47 copy_cube(data->cube, &moved);
48 apply_trans(t, &moved);
49 data->val[i] = index_coord(step->coord[i], &moved, &tt);
50 data->t[i] = transform_trans(tt, t);
51 }
52}
53
54static void *
55prepare_cube(void *param, Cube *cube)
56{
57 int i;
58 Step *s;
59 CubeData *data;
60
61 s = (Step *)param;
62
63 for (i = 0; i < s->n_coord; i++) {
64 s->pd[i] = malloc(sizeof(PruneData));
65 s->pd[i]->moveset = s->moveset;
66/* TODO: check if moveset initialization works fine,
67 e.g. if there is a variable to save the initialized status
68 or if it gets initialized multiple times */
69 init_moveset(s->moveset);
70 s->pd[i]->coord = s->coord[i];
71 gen_coord(s->coord[i]);
72 s->pd[i]->compact = s->pd_compact[i];
73 s->pd[i] = genptable(s->pd[i], 4); /* TODO: threads */
74 }
75
76 data = alloc_cubedata(param);
77 data->cube = malloc(sizeof(Cube));
78 copy_cube(cube, data->cube);
79 init_indexes(s, data);
80
81 return data;
82}
83
84static bool
85move_check_stop_eager(void *param, DfsArg *arg, Threader *threader)
86{
87 int nsol;
88
89 if (move_check_stop_nonsol(param, arg, threader))
90 return true;
91
92 nsol = threader->get_nsol(arg->threaddata);
93 return nsol >= arg->opts->max_solutions;
94}
95
96static bool
97move_check_stop_lazy(void *param, DfsArg *arg, Threader *threader)
98{
99 int nsol;
100
101 nsol = threader->get_nsol(arg->threaddata);
102 if (nsol >= arg->opts->max_solutions)
103 return true;
104
105 return move_check_stop_nonsol(param, arg, threader);
106}
107
108/* TODO: split in 2 (nissable / non-nissable) and only move cube
109 when nissable */
110static bool
111move_check_stop_nonsol(void *param, DfsArg *arg, Threader *threader)
112{
113 int i, goal, bound;
114 Move mm, lastmove;
115 Trans tt = uf;
116 CubeData *data;
117 Step *s;
118
119 s = (Step *)param;
120 data = (CubeData *)arg->cubedata;
121
122
123 bound = 0;
124 goal = arg->d - arg->current_alg->len;
125/* TODO: check if len is 0 */
126 lastmove = arg->current_alg->move[arg->current_alg->len-1];
127 for (i = 0; i < s->n_coord; i++) {
128 mm = transform_move(data->t[i], lastmove);
129 data->val[i] = move_coord(s->coord[i], mm, data->val[i], &tt);
130 data->t[i] = transform_trans(tt, data->t[i]);
131
132 bound = MAX(bound, ptableval(s->pd[i], data->val[i]));
133 if (arg->opts->can_niss && !arg->niss)
134 bound = MIN(1, bound);
135
136 if (bound > goal) {
137 return true;
138 }
139 }
140 if (arg->opts->can_niss && !arg->niss)
141 apply_move(lastmove, data->cube);
142
143 return false;
144}
145
146static bool
147is_solved_step(void *param, void *cubedata)
148{
149 int i;
150 Step *s;
151 CubeData *data;
152
153 s = (Step *)param;
154 data = (CubeData *)cubedata;
155
156 for (i = 0; i < s->n_coord; i++)
157 if (data->val[i] != 0)
158 return false;
159
160 return true;
161}
162
163static Alg *
164validate_solution(void *param, Alg *alg)
165{
166 return ((Step *)param)->is_valid(alg);
167}
168
169static void *
170alloc_cubedata(void *param)
171{
172 Step *s;
173 CubeData *data;
174
175 s = (Step *)param;
176
177 data = malloc(sizeof(CubeData));
178 /* We do not need to allocate a cube */
179 data->val = malloc(s->n_coord * sizeof(uint64_t));
180 data->t = malloc(s->n_coord * sizeof(Trans));
181
182 return data;
183}
184
185static void
186copy_cubedata(void *param, void *src, void *dst)
187{
188 int i;
189 Step *s;
190 CubeData *newdata, *olddata;
191
192 s = (Step *)param;
193 olddata = (CubeData *)src;
194 newdata = (CubeData *)dst;
195
196/* TODO: do not copy if not nissable */
197 newdata->cube = malloc(sizeof(Cube));
198 copy_cube(olddata->cube, newdata->cube);
199 for (i = 0; i < s->n_coord; i++) {
200 newdata->val[i] = olddata->val[i];
201 newdata->t[i] = olddata->t[i];
202 }
203}
204
205static void
206free_cubedata(void *param, void *cubedata)
207{
208 CubeData *data;
209
210 data = (CubeData *)cubedata;
211
212 free(data->t);
213 free(data->val);
214 free(data->cube);
215 free(data);
216}
217
218static void
219invert_cubedata(void *param, void *cubedata)
220{
221 Step *s;
222 CubeData *data;
223
224 s = (Step *)param;
225 data = (CubeData *)cubedata;
226
227 invert_cube(data->cube);
228 init_indexes(s, data);
229}
230
231static bool
232niss_makes_sense(void *param, void *cubedata, Alg *alg)
233{
234 Step *s;
235 CubeData *data;
236
237 s = (Step *)param;
238 data = (CubeData *)cubedata;
239
240 if (s->final)
241 return false;
242
243 if (alg->len_normal == 0)
244 return true;
245
246 Move m = inverse_move(alg->move_normal[alg->len_normal-1]);
247 for (int i = 0; i < s->n_coord; i++) {
248 Move mm = transform_move(data->t[i], m);
249 uint64_t u = move_coord(s->coord[i], mm, 0, NULL);
250 if (ptableval(s->pd[i], u) > 0)
251 return true;
252 }
253
254 return false;
255}
256
257static Solver *
258new_stepsolver_nocheckstop(Step *step)
259{
260 Solver *solver;
261
262 solver = malloc(sizeof(Solver));
263
264 solver->moveset = step->moveset;
265 solver->param = step;
266
267 solver->apply_move = apply_move_cubedata;
268 solver->prepare_cube = prepare_cube;
269 solver->is_solved = is_solved_step;
270 solver->validate_solution = validate_solution;
271 solver->alloc_cubedata = alloc_cubedata;
272 solver->copy_cubedata = copy_cubedata;
273 solver->free_cubedata = free_cubedata;
274 solver->invert_cube = invert_cubedata;
275 solver->niss_makes_sense = niss_makes_sense;
276
277 return solver;
278}
279
280Solver *
281new_stepsolver_eager(Step *step)
282{
283 Solver *solver;
284
285 solver = new_stepsolver_nocheckstop(step);
286 solver->move_check_stop = move_check_stop_eager;
287
288 return solver;
289}
290
291Solver *
292new_stepsolver_lazy(Step *step)
293{
294 Solver *solver;
295
296 solver = new_stepsolver_nocheckstop(step);
297 solver->move_check_stop = move_check_stop_lazy;
298
299 return solver;
300}
301
302void
303free_stepsolver(Solver *solver)
304{
305 free(solver);
306}

Generated with cgit - Back to sebastiano.tronto.net