commit 1ec688620365568d1f8a8d57d7bb3a85aafb0165
parent a0b89016dc7ea42fe8af0aeb956fd383cd1b66f1
Author: Sebastiano Tronto <sebastiano.tronto@gmail.com>
Date: Wed, 8 Dec 2021 17:39:56 +0100
Cleanup
Diffstat:
| M | TODO.md | | | 4 | ---- |
| M | src/pruning.c | | | 176 | ------------------------------------------------------------------------------- |
2 files changed, 0 insertions(+), 180 deletions(-)
diff --git a/TODO.md b/TODO.md
@@ -58,10 +58,6 @@ and just use previous values for all 3 axes.
## Coordinates, symmetries, pruning tables
* use multiple threads to search for solutions in parallel
-* Faster pruning table generation: keep track of which positions are "nasty"
-(i.e. self-symmetric with respect to the base symmetry coordinate but not
-self-symmetric overall) by adding a function to struct coord and some datafield
-to struct symdata.
* Faster pruning table generation: multithreading (divide table into large
sections and use one mutex for each section to avoid too much locking)
* Cleanup symcoord.c: some coordinates and symdata are never actually used;
diff --git a/src/pruning.c b/src/pruning.c
@@ -1,18 +1,5 @@
#include "pruning.h"
-/*
- * The commented functions are a way to generate a pruning table
- * without using anti-indexes. It does not matter too much because
- * we still need anti-indexes in gensym.
- */
-/*
-static bool dfs_get_visited(PruneData *pd, DfsData *dd, Cube c);
-static bool dfs_get_visited_index(DfsData *dd, uint64_t ind);
-static void dfs_set_visited(PruneData *pd, DfsData *dd, Cube c, bool b);
-static void dfs_set_visited_index(DfsData *dd, uint64_t ind, bool b);
-static void genptable_dfs(Cube c, PruneData *pd, DfsData *dd);
-*/
-
static void genptable_bfs(PruneData *pd, int d, Move *ms);
static void genptable_branch(PruneData *pd,uint64_t ind,int d,Move *ms);
static void ptable_update(PruneData *pd, Cube cube, int m);
@@ -172,53 +159,6 @@ genptable_bfs(PruneData *pd, int d, Move *ms)
static void
genptable_branch(PruneData *pd, uint64_t ind, int d, Move *ms)
{
- /*
- * Here we deal with the following problem:
- * The set of positions reached by applying each move to
- * a certain position X could depend on the representative
- * used for X in its symmetry class.
- * This is a terribly inefficient way to deal with this.
- * TODO: make it more efficient.
- */
- /*
- * IDEA (with the example of khuge in mind):
- * The problem only happens when two position that are actually
- * in the same class are considered different. This can happen
- * because only CO is used to determine which transformation
- * to apply to get a representative for the class. So if the
- * corners are in a self-symmetric position more than one
- * transformation to the representative is possible, only one
- * (essentially at random) is picked, but this is not necessarily
- * the correct one if the edges are not in a self-symmetric
- * position.
- * SOLUTION: Keep in mind which corner positions are
- * self-symmetric (add a field to symdata). Add a function
- * to coord that tells if a position has this problem, or
- * even the list of transformations that need to be tried.
- * The second option is a bit more complicated but more
- * efficient and allows for removing the ntrans and trans
- * field from struct coordinate.
- */
- /* Work in progress, first attempt */
-
- /*
- int i, j;
- Cube ci, cc, c;
-
-
- ci = pd->coord->cube(ind);
-
- for (i = 0; i < pd->coord->ntrans; i++) {
- c = i == 0 ? ci :
- apply_trans(pd->coord->trans[i], ci);
- for (j = 0; ms[j] != NULLMOVE; j++) {
- cc = apply_move(ms[j], c);
- if (ptableval(pd, cc) > d+1)
- ptable_update(pd, cc, d+1);
- }
- }
- */
-
int i;
Cube c, cc;
@@ -339,119 +279,3 @@ write_ptable_file(PruneData *pd)
return written == ptablesize(pd);
}
-/*
- I'll put here all the leftover code from the genptable-dfs attempt.
- Might be useful in the future.
-*/
-
-/*
-void
-genptable(PruneData *pd)
-{
- Move *ms;
- uint64_t j, oldn;
- DfsData dd;
-
- if (pd->generated)
- return;
-
- pd->ptable = malloc(ptablesize(pd) * sizeof(uint8_t));
-
- if (read_ptable_file(pd)) {
- pd->generated = true;
- return;
- }
- pd->generated = true;
-
- fprintf(stderr, "Cannot load %s, generating it\n", pd->filename);
-
- ms = malloc(NMOVES * sizeof(Move));
- moveset_to_list(pd->moveset, ms);
-
- for (j = 0; j < pd->coord->max; j++)
- ptable_update_index(pd, j, 15);
-
- dd = (DfsData) { .m = 0 };
- dd.visited = malloc((ptablesize(pd)/4 + 1) * sizeof(uint8_t));
- dd.sorted_moves = malloc(NMOVES * sizeof(Move));
- moveset_to_list(pd->moveset, dd.sorted_moves);
- oldn = 0;
- pd->n = 0;
-
- for (dd.d = 0; dd.d < 15 && pd->n < pd->coord->max; dd.d++) {
- for (j = 0; j < pd->coord->max; j++)
- dfs_set_visited_index(&dd, j, false);
- genptable_dfs((Cube){0}, pd, &dd);
- fprintf(stderr, "Depth %d done, generated %"
- PRIu64 "\t(%" PRIu64 "/%" PRIu64 ")\n",
- dd.d+1, pd->n - oldn, pd->n, pd->coord->max);
- oldn = pd->n;
- }
-
- if (!write_ptable_file(pd))
- fprintf(stderr, "Error writing ptable file\n");
-
- free(ms);
- free(dd.visited);
- free(dd.sorted_moves);
-}
-
-static void
-genptable_dfs(Cube c, PruneData *pd, DfsData *dd)
-{
- int i, j, pv;
- Move mm;
- Cube cc;
-
- pv = ptableval(pd, c);
-
- if (pv < dd->m || dd->m > dd->d)
- return;
-
- if (dfs_get_visited(pd, dd, c))
- return;
- dfs_set_visited(pd, dd, c, true);
-
- if (pv != dd->m)
- ptable_update(pd, c, dd->m);
-
- for (i = 0; i < pd->coord->ntrans; i++) {
- cc = i == 0 ? c :
- apply_trans(pd->coord->trans[i], c);
- for (j = 0; dd->sorted_moves[j] != NULLMOVE; j++) {
- mm = dd->sorted_moves[j];
- dd->m++;
- genptable_dfs(apply_move(mm, cc), pd, dd);
- dd->m--;
- }
- }
-}
-
-static bool
-dfs_get_visited(PruneData *pd, DfsData *dd, Cube c)
-{
- return dfs_get_visited_index(dd, pd->coord->index(c));
-}
-
-static bool
-dfs_get_visited_index(DfsData *dd, uint64_t ind)
-{
- return dd->visited[ind/8] & ((uint8_t)1 << (ind % 8));
-}
-
-static void
-dfs_set_visited(PruneData *pd, DfsData *dd, Cube c, bool b)
-{
- dfs_set_visited_index(dd, pd->coord->index(c), b);
-}
-
-static void
-dfs_set_visited_index(DfsData *dd, uint64_t ind, bool b)
-{
- if (b)
- dd->visited[ind/8] |= ((uint8_t)1 << (ind % 8));
- else
- dd->visited[ind/8] &= ~((uint8_t)1 << (ind % 8));
-}
-
-*/
