chiark
/
gitweb
/
~ianmdlvl
/
matchsticks-search.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
.gitignore: profiling output files
[matchsticks-search.git]
/
main.c
diff --git
a/main.c
b/main.c
index 11bdf0fba64e7605e11e54511142be5d20bbf689..57a979654f705bd01912fe773cd01668a92ddb07 100644
(file)
--- a/
main.c
+++ b/
main.c
@@
-58,7
+58,8
@@
*
* We search all possible adjacency matrices, and for each one we run
* GLPK's simplex solver. We represent the adjacency matrix as an
*
* We search all possible adjacency matrices, and for each one we run
* GLPK's simplex solver. We represent the adjacency matrix as an
- * array of bitmaps.
+ * array of bitmaps: one word per input stick, with one bit per output
+ * stick.
*
* However, there are a couple of wrinkles:
*
*
* However, there are a couple of wrinkles:
*
@@
-76,11
+77,15
@@
* nondecreasing in array order.
*
* Once we have a solution, we also avoid considering any candidate
* nondecreasing in array order.
*
* Once we have a solution, we also avoid considering any candidate
- * which involves dividing one of the
out
put sticks into so many
+ * which involves dividing one of the
in
put sticks into so many
* fragment that the smallest fragment would necessarily be no bigger
* than our best solution. That is, we reject candidates where any of
* the hamming weights of the adjacency bitmap words are too large.
*
* fragment that the smallest fragment would necessarily be no bigger
* than our best solution. That is, we reject candidates where any of
* the hamming weights of the adjacency bitmap words are too large.
*
+ * We further winnow the set of possible adjacency matrices, by
+ * ensuring the same bit is not set in too many entries of adjmatrix
+ * (ie, as above, only considering output sticks).
+ *
* And, we want to do the search in order of increasing maximum
* hamming weight. This is because in practice optimal solutions tend
* to have low hamming weight, and having found a reasonable solution
* And, we want to do the search in order of increasing maximum
* hamming weight. This is because in practice optimal solutions tend
* to have low hamming weight, and having found a reasonable solution
@@
-512,7
+517,7
@@
static void optimise(bool doprint) {
glp_set_obj_coef(prob, X_minimum, 1);
for (i=0; i<n; i++) {
glp_set_obj_coef(prob, X_minimum, 1);
for (i=0; i<n; i++) {
-
for (j=0, jbit=1; j<m; j++, jbit<<=1
) {
+
FOR_BITS(j,m
) {
if (!(adjmatrix[i] & jbit))
continue;
/* x_total_i += x_minimum */
if (!(adjmatrix[i] & jbit))
continue;
/* x_total_i += x_minimum */