#include #include #include #define BOOKS 6 #define BOOK_FAC 720 /* BOOKS! */ int books[BOOKS]; int strat[BOOK_FAC][BOOKS]; double ver[BOOK_FAC]; int nr_of(int books[]); void fill(int nr, int books[]); void find_opt_strat(); void mixbooks(); int notordered(); void move(int oldpos, int newpos); void choose(int oldpos); void move(int oldpos, int newpos) { int i; int booknum = books[oldpos]; if (newpos < oldpos) for (i = oldpos; i > newpos; --i) books[i] = books[i - 1]; else for (i = oldpos; i < newpos; ++i) books[i] = books[i + 1]; books[newpos] = booknum; } /*********** Algorithms ***************/ /***** 2 ******/ int choose_2(int books[], int oldpos) { /* Book N in position N */ return books[oldpos]; } /***** 3 ******/ int choose_3(int books[], int oldpos) { /* Least Inversions */ int inversions; int bestsofar = 1000; int i, j, newpos; for (i = 0; i < BOOKS; ++i) { move(oldpos, i); inversions = 0; for (j = 0; j < BOOKS; ++j) if ( (j < i && books[j] > books[i]) || (i < j && books[i] > books[j])) ++inversions; if (inversions < bestsofar) { bestsofar = inversions; newpos = i; } move(i, oldpos); } return newpos; } /***** 4 ******/ int choose_4(int books[], int oldpos) { /* Move the book left until it is immediately to the right of a lower numbered book. */ int i, newpos; if (oldpos == 0) i = 0; else for (i = oldpos; i > 0; --i) if (books[i - 1] < books[i]) { newpos = i; break; } if (i == 0) newpos = 0; return newpos; } /***** 5 ******/ int choose_5(int books[], int oldpos) { /* Move the book left until it is immediately right of a lower numbered book or move the book right until it is immediately left of a higher numbered book, whichever moves farther. */ int i, newpos; int left = 0, right = 0; if (oldpos == 0) i = 1; else for (i = oldpos; i > 0; --i) if (books[i - 1] < books[i]) { left = oldpos - i; break; } if (i == 0) left = oldpos; if (oldpos == BOOKS - 1) i = 0; else for (i = oldpos; i < BOOKS - 1; ++i) if (books[i] < books[i + 1]) { right = i - oldpos; break; } if (i == BOOKS - 1) right = BOOKS - 1 - oldpos; if (left > right) newpos = oldpos - left; else newpos = oldpos + right; return newpos; } /***** 6 ******/ int choose_6(int books[], int oldpos) { /* Move the book N just to the left of book N + 1; put 5 on the far right. */ int i, newpos, booknum = books[oldpos]; for (i = 0; i < BOOKS; ++i) if (books[i] == booknum + 1) break; if (i < oldpos) newpos = i; else newpos = i - 1; return newpos; } /***** 7 ******/ int choose_7(int books[], int oldpos) { /* A modification of #3, minimizing inversions. */ int i, newpos, booknum = books[oldpos]; int j; int score, bestscore = 0; int noninvs; int rightbefores; for (i = 0; i < BOOKS; ++i) { move(oldpos, i); noninvs = rightbefores = 0; for (j = 0; j < BOOKS - 1; ++j) { if ( (i < j && booknum < books[j]) || (j < i && books[j] < booknum)) ++noninvs; if (books[j] + 1 == books[j + 1]) ++rightbefores; } score = (noninvs + rightbefores) * noninvs; if (score > bestscore) { bestscore = score; newpos = i; } move(i, oldpos); } return newpos; } /***** 8 ******/ int choose_8(int books[], int oldpos) { /* Place to get the longest possible subsequence. */ int i, newpos; int j; int subseq; int bestsofar = 0; for (i = 0; i < BOOKS; ++i) { move(oldpos, i); subseq = 0; for (j = 0; j < BOOKS - 1; ++j) { if (books[j] < books[j + 1]) ++subseq; else subseq = 0; if (subseq > bestsofar) { bestsofar = subseq; newpos = i; } } move(i, oldpos); } return newpos; } /****** 9 - Ilias' count (non-adjacent) books in sequence ******/ int choose_9(int books[], int oldpos) { int i, newpos; int score, bestscore = 0; int j, k, l, m, n; for (i = 0; i < BOOKS; ++i) { move(oldpos, i); score = 0; for (j = 0; j < BOOKS - 1; ++j) for (k = j + 1; k < BOOKS; ++k) if (books[j] < books[k]) { ++score; if (k != BOOKS - 1) for (l = k + 1; l < BOOKS; ++l) if (books[k] < books[l]) { score += 10; if (l != BOOKS - 1) for (m = l + 1; m < BOOKS; ++m) if (books[l] < books[m]) { score += 100; if (m != BOOKS - 1) for (n = m + 1; n < BOOKS; ++n) if (books[m] < books[n]) score += 1000; } } } if (score > bestscore) { bestscore = score; newpos = i; } move(i, oldpos); } return newpos; } /****** 10 - Frans Faase's squares of ordered pairs ******/ int choose_10(int books[], int oldpos) { int i, newpos; int highest_score = 0; int score; for (i = 0; i < BOOKS; ++i) { move(oldpos, i); score = 0; { int a; for (a = 0; a < 6; a++) { int b; int s = 0; for (b = 0; b < 6; b++) { int j; for (j = 0; j < 6; j++) if (books[j] == a) { if (a < b) s++; break; } else if (books[j] == b) { if (a > b) s++; break; } } score += s * s; } } if (score > highest_score) { highest_score = score; newpos = i; } move(i, oldpos); } return newpos; } /****** 11 - Dan Caas' minimize inversions with subsequence tiebreaker ******/ int choose_11(int books[], int oldpos) { int i, newpos, booknum = books[oldpos]; int j, k, l, m, n; int noninvs, bestnoninvs = 0; int seqscore, bestseqscore = 0; for (i = 0; i < BOOKS; ++i) { move(oldpos, i); noninvs = seqscore = 0; for (j = 0; j < BOOKS - 1; ++j) if ( (i < j && booknum < books[j]) || (j < i && books[j] < booknum)) ++noninvs; if (noninvs >= bestnoninvs) { for (j = 0; j < BOOKS - 1; ++j) for (k = j + 1; k < BOOKS; ++k) if (books[j] < books[k]) { ++seqscore; for (l = k + 1; l < BOOKS; ++l) if (books[k] < books[l]) { seqscore += 10; for (m = l + 1; m < BOOKS; ++m) if (books[l] < books[m]) { seqscore += 100; for (n = m + 1; n < BOOKS; ++n) if (books[m] < books[n]) seqscore += 1000; } } } if (noninvs > bestnoninvs || seqscore > bestseqscore) { bestnoninvs = noninvs; bestseqscore = seqscore; newpos = i; } } move(i, oldpos); } return newpos; } /***** 15 ******/ void fill(int nr, int books[]) { int i; books[BOOKS - 1] = 0; /* printf("nr=%3d :", nr); */ for (i = 2; i <= BOOKS; i++) { int p = nr % i; int j; books[BOOKS - i] = p; for (j = BOOKS - i + 1; j < BOOKS; j++) if (books[j] >= p) books[j]++; nr = nr / i; } /* for (i = 0; i < BOOKS; i++) printf("%d", books[i]); printf(" = %d\n", nr_of(books)); */ } int nr_of(int books[]) { int i; int result = 0; int b[BOOKS]; for (i = 0; i < BOOKS; i++) { b[i] = books[i]; /* printf("%d", books[i]); */ } for (i = 0; i < BOOKS - 1; i++) { int j; result = b[i] + (BOOKS - i) * result; for (j = i + 1; j < BOOKS; j++) if (b[j] > b[i]) b[j]--; /* for (j = 0; j < BOOKS; j++) printf("%d", books[j]); printf(",%d ", result); */ } /* printf(" : nr=%d\n", result); */ return result; } void find_opt_strat() { int go = 1; int i; for (i = 0; i < BOOK_FAC; i++) { int j; ver[i] = i == 0 ? 0.0 : 1000.0; for (j = 0; j < BOOKS; j++) strat[i][j] = -1; } while (go) { int nr; go = 0; for (nr = 0; nr < BOOK_FAC; nr++) { double v; double s = 0.0; int x = 0; int i; fill(nr, books); for (i = 0; i < BOOKS; i++) { int a; int book = books[i]; strat[nr][book] = -1; v = ver[nr]; for (a = 0; a < BOOKS; a++) { double vv; move(i, a); vv = ver[ nr_of(books) ]; if (vv < v) { strat[nr][book] = a; v = vv; } move(a, i); } if (v == ver[nr]) x++; else s += v; } if (x < 6) { double new_v = (BOOKS + s)/(BOOKS - x); if (new_v < ver[nr]) { ver[nr] = new_v; go = 1; /* printf("%3d %f\n", nr, ver[nr]); */ } } } /* printf("--------------\n"); */ } } /********* calculating the expected number of steps *********/ void fill_strat(int (*choose)(int books[], int oldpos)) { int go = 1; int nr; for (nr = 0; nr < BOOK_FAC; nr++) { int oldpos; ver[nr] = nr == 0 ? 0.0 : 1000.0; for (oldpos = 0; oldpos < BOOKS; oldpos++) { int newpos; fill(nr, books); newpos = (*choose)(books, oldpos); if (newpos != -1) move(oldpos, newpos); strat[nr][oldpos] = nr_of(books); } } while (go) { go = 0; for (nr = 0; nr < BOOK_FAC; nr++) { double s = 0.0; int x = 0; int oldpos; for (oldpos = 0; oldpos < BOOKS; oldpos++) { int newnr = strat[nr][oldpos]; if (newnr == nr) x++; else s += ver[newnr]; } if (x < 6) { double new_v = (BOOKS + s)/(BOOKS - x); if (new_v < ver[nr]) { ver[nr] = new_v; go = 1; /* printf("%3d %f\n", nr, ver[nr]); */ } } } } } void analyse(int strategy) { switch (strategy) { case 2: fill_strat(choose_2); break; case 3: fill_strat(choose_3); break; case 4: fill_strat(choose_4); break; case 5: fill_strat(choose_5); break; case 6: fill_strat(choose_6); break; case 7: fill_strat(choose_7); break; case 8: fill_strat(choose_8); break; case 9: fill_strat(choose_9); break; case 10: fill_strat(choose_10); break; case 11: fill_strat(choose_11); break; case 15: find_opt_strat(); break; } { int nr; double sum = 0.0; for (nr = 0; nr < BOOK_FAC; nr++) sum += ver[nr]; printf("strategy %d uses an average of %f steps.\n", strategy, sum / BOOK_FAC); } } void main() { analyse(2); analyse(3); analyse(4); analyse(5); analyse(6); analyse(7); analyse(8); analyse(9); analyse(10); analyse(11); analyse(15); }