From 3fba56cbf5cad13401f183ca7e38a512e7090ae3 Mon Sep 17 00:00:00 2001 From: simon Date: Sun, 11 Sep 2005 14:22:32 +0000 Subject: [PATCH] Run the final solution-reduction pass in both directions, since Gareth managed to find an example (10x8#458168771440033 in r6289) where running it in only one direction failed to eliminate an obviously redundant piece of path. git-svn-id: svn://svn.tartarus.org/sgt/puzzles@6290 cda61777-01e9-0310-a592-d414129be87e --- inertia.c | 278 +++++++++++++++++++++++++++++++++----------------------------- 1 file changed, 149 insertions(+), 129 deletions(-) diff --git a/inertia.c b/inertia.c index 41bcc89..d45ecc8 100644 --- a/inertia.c +++ b/inertia.c @@ -1160,7 +1160,7 @@ static char *solve_game(game_state *state, game_state *currstate, } } -#ifdef TSP_DIAGNOSTICS +#ifndef TSP_DIAGNOSTICS printf("before reduction, moves are "); x = nodes[circuit[0]] / DP1 % w; y = nodes[circuit[0]] / DP1 / w; @@ -1198,159 +1198,179 @@ static char *solve_game(game_state *state, game_state *currstate, */ while (1) { int oldlen = circuitlen; + int dir; - for (i = 0; i < wh; i++) - unvisited[i] = 0; - for (i = 0; i < circuitlen; i++) { - int xy = nodes[circuit[i]] / DP1; - if (currstate->grid[xy] == GEM) - unvisited[xy]++; - } + for (dir = +1; dir >= -1; dir -= 2) { - /* - * If there's any gem we didn't end up visiting at all, - * give up. - */ - for (i = 0; i < wh; i++) { - if (currstate->grid[i] == GEM && unvisited[i] == 0) { - err = "Unable to find a solution from this starting point"; - break; + for (i = 0; i < wh; i++) + unvisited[i] = 0; + for (i = 0; i < circuitlen; i++) { + int xy = nodes[circuit[i]] / DP1; + if (currstate->grid[xy] == GEM) + unvisited[xy]++; } - } - if (i < wh) - break; - for (i = j = 0; i < circuitlen; i++) { - int xy = nodes[circuit[i]] / DP1; - if (currstate->grid[xy] == GEM && unvisited[xy] > 1) { - unvisited[xy]--; - } else if (currstate->grid[xy] == GEM || i == circuitlen-1) { - /* - * circuit[i] collects a gem for the only time, or is - * the last node in the circuit. Therefore it cannot be - * removed; so we now want to replace the path from - * circuit[j] to circuit[i] with a bfs-shortest path. - */ - int k, dest, ni, ti, thisdist; + /* + * If there's any gem we didn't end up visiting at all, + * give up. + */ + for (i = 0; i < wh; i++) { + if (currstate->grid[i] == GEM && unvisited[i] == 0) { + err = "Unable to find a solution from this starting point"; + break; + } + } + if (i < wh) + break; -#ifdef TSP_DIAGNOSTICS - printf("optimising section from %d - %d\n", j, i); + for (i = j = (dir > 0 ? 0 : circuitlen-1); + i < circuitlen && i >= 0; + i += dir) { + int xy = nodes[circuit[i]] / DP1; + if (currstate->grid[xy] == GEM && unvisited[xy] > 1) { + unvisited[xy]--; + } else if (currstate->grid[xy] == GEM || i == circuitlen-1) { + /* + * circuit[i] collects a gem for the only time, + * or is the last node in the circuit. + * Therefore it cannot be removed; so we now + * want to replace the path from circuit[j] to + * circuit[i] with a bfs-shortest path. + */ + int p, q, k, dest, ni, ti, thisdist; + + /* + * Set up the upper and lower bounds of the + * reduced section. + */ + p = min(i, j); + q = max(i, j); + +#ifndef TSP_DIAGNOSTICS + printf("optimising section from %d - %d\n", p, q); #endif - for (k = 0; k < n; k++) - dist[k] = -1; - head = tail = 0; - - dist[circuit[j]] = 0; - list[tail++] = circuit[j]; - - while (head < tail && dist[circuit[i]] < 0) { - int ni = list[head++]; - for (k = edgei[ni]; k < edgei[ni+1]; k++) { - int ti = edges[k]; - if (ti >= 0 && dist[ti] < 0) { - dist[ti] = dist[ni] + 1; - list[tail++] = ti; + for (k = 0; k < n; k++) + dist[k] = -1; + head = tail = 0; + + dist[circuit[p]] = 0; + list[tail++] = circuit[p]; + + while (head < tail && dist[circuit[q]] < 0) { + int ni = list[head++]; + for (k = edgei[ni]; k < edgei[ni+1]; k++) { + int ti = edges[k]; + if (ti >= 0 && dist[ti] < 0) { + dist[ti] = dist[ni] + 1; + list[tail++] = ti; + } } } - } - thisdist = dist[circuit[i]]; - assert(thisdist >= 0 && thisdist <= i-j); + thisdist = dist[circuit[q]]; + assert(thisdist >= 0 && thisdist <= q-p); - memmove(circuit+j+thisdist, circuit+i, - (circuitlen - i) * sizeof(int)); - circuitlen -= i-j; - i = j + thisdist; - circuitlen += i-j; + memmove(circuit+p+thisdist, circuit+q, + (circuitlen - q) * sizeof(int)); + circuitlen -= q-p; + q = p + thisdist; + circuitlen += q-p; -#ifdef TSP_DIAGNOSTICS - printf("new section runs from %d - %d\n", j, i); + if (dir > 0) + i = q; /* resume loop from the right place */ + +#ifndef TSP_DIAGNOSTICS + printf("new section runs from %d - %d\n", p, q); #endif - dest = i; - assert(dest >= 0); - ni = circuit[i]; + dest = q; + assert(dest >= 0); + ni = circuit[q]; - while (1) { - /* printf("dest=%d circuitlen=%d ni=%d dist[ni]=%d\n", dest, circuitlen, ni, dist[ni]); */ - circuit[dest] = ni; - if (dist[ni] == 0) - break; - dest--; - ti = -1; - for (k = backedgei[ni]; k < backedgei[ni+1]; k++) { - ti = backedges[k]; - if (ti >= 0 && dist[ti] == dist[ni] - 1) + while (1) { + /* printf("dest=%d circuitlen=%d ni=%d dist[ni]=%d\n", dest, circuitlen, ni, dist[ni]); */ + circuit[dest] = ni; + if (dist[ni] == 0) break; + dest--; + ti = -1; + for (k = backedgei[ni]; k < backedgei[ni+1]; k++) { + ti = backedges[k]; + if (ti >= 0 && dist[ti] == dist[ni] - 1) + break; + } + assert(k < backedgei[ni+1] && ti >= 0); + ni = ti; } - assert(k < backedgei[ni+1] && ti >= 0); - ni = ti; - } - /* - * Now re-increment the visit counts for the new - * path. - */ - while (++j < i) { - int xy = nodes[circuit[j]] / DP1; - if (currstate->grid[xy] == GEM) - unvisited[xy]++; - } + /* + * Now re-increment the visit counts for the + * new path. + */ + while (++p < q) { + int xy = nodes[circuit[p]] / DP1; + if (currstate->grid[xy] == GEM) + unvisited[xy]++; + } -#ifdef TSP_DIAGNOSTICS - printf("during reduction, circuit is"); - for (k = 0; k < circuitlen; k++) { - int nc = nodes[circuit[k]]; - printf(" (%d,%d,%d)", nc/DP1%w, nc/(DP1*w), nc%DP1); - } - printf("\n"); - printf("moves are "); - x = nodes[circuit[0]] / DP1 % w; - y = nodes[circuit[0]] / DP1 / w; - for (k = 1; k < circuitlen; k++) { - int x2, y2, dx, dy; - if (nodes[circuit[k]] % DP1 != DIRECTIONS) - continue; - x2 = nodes[circuit[k]] / DP1 % w; - y2 = nodes[circuit[k]] / DP1 / w; - dx = (x2 > x ? +1 : x2 < x ? -1 : 0); - dy = (y2 > y ? +1 : y2 < y ? -1 : 0); - for (d = 0; d < DIRECTIONS; d++) - if (DX(d) == dx && DY(d) == dy) - printf("%c", "89632147"[d]); - x = x2; - y = y2; - } - printf("\n"); + j = i; + +#ifndef TSP_DIAGNOSTICS + printf("during reduction, circuit is"); + for (k = 0; k < circuitlen; k++) { + int nc = nodes[circuit[k]]; + printf(" (%d,%d,%d)", nc/DP1%w, nc/(DP1*w), nc%DP1); + } + printf("\n"); + printf("moves are "); + x = nodes[circuit[0]] / DP1 % w; + y = nodes[circuit[0]] / DP1 / w; + for (k = 1; k < circuitlen; k++) { + int x2, y2, dx, dy; + if (nodes[circuit[k]] % DP1 != DIRECTIONS) + continue; + x2 = nodes[circuit[k]] / DP1 % w; + y2 = nodes[circuit[k]] / DP1 / w; + dx = (x2 > x ? +1 : x2 < x ? -1 : 0); + dy = (y2 > y ? +1 : y2 < y ? -1 : 0); + for (d = 0; d < DIRECTIONS; d++) + if (DX(d) == dx && DY(d) == dy) + printf("%c", "89632147"[d]); + x = x2; + y = y2; + } + printf("\n"); #endif + } } - } -#ifdef TSP_DIAGNOSTICS - printf("after reduction, moves are "); - x = nodes[circuit[0]] / DP1 % w; - y = nodes[circuit[0]] / DP1 / w; - for (i = 1; i < circuitlen; i++) { - int x2, y2, dx, dy; - if (nodes[circuit[i]] % DP1 != DIRECTIONS) - continue; - x2 = nodes[circuit[i]] / DP1 % w; - y2 = nodes[circuit[i]] / DP1 / w; - dx = (x2 > x ? +1 : x2 < x ? -1 : 0); - dy = (y2 > y ? +1 : y2 < y ? -1 : 0); - for (d = 0; d < DIRECTIONS; d++) - if (DX(d) == dx && DY(d) == dy) - printf("%c", "89632147"[d]); - x = x2; - y = y2; - } - printf("\n"); +#ifndef TSP_DIAGNOSTICS + printf("after reduction, moves are "); + x = nodes[circuit[0]] / DP1 % w; + y = nodes[circuit[0]] / DP1 / w; + for (i = 1; i < circuitlen; i++) { + int x2, y2, dx, dy; + if (nodes[circuit[i]] % DP1 != DIRECTIONS) + continue; + x2 = nodes[circuit[i]] / DP1 % w; + y2 = nodes[circuit[i]] / DP1 / w; + dx = (x2 > x ? +1 : x2 < x ? -1 : 0); + dy = (y2 > y ? +1 : y2 < y ? -1 : 0); + for (d = 0; d < DIRECTIONS; d++) + if (DX(d) == dx && DY(d) == dy) + printf("%c", "89632147"[d]); + x = x2; + y = y2; + } + printf("\n"); #endif + } /* - * If we've managed an entire reduction pass and not made - * the solution any shorter, we're _really_ done. + * If we've managed an entire reduction pass in each + * direction and not made the solution any shorter, we're + * _really_ done. */ if (circuitlen == oldlen) break; -- 2.11.0