From 886119cd7674c29166e0a884896423f87cfe22a9 Mon Sep 17 00:00:00 2001
From: simon <simon@cda61777-01e9-0310-a592-d414129be87e>
Date: Fri, 22 Jul 2005 11:55:50 +0000
Subject: [PATCH] The `Solve' operation now rotates and/or reflects the
 solution grid to bring it as close as possible to the current game state.
 This means that if you request `Solve' after solving a puzzle yourself, with
 the intention of finding out how similar your solution is to the program's,
 then you will mostly see the differences in _shape_ rather than those being
 masked by the fact that yours happened to be the other way up.

git-svn-id: svn://svn.tartarus.org/sgt/puzzles@6126 cda61777-01e9-0310-a592-d414129be87e
---
 untangle.c | 137 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 136 insertions(+), 1 deletion(-)

diff --git a/untangle.c b/untangle.c
index 37a6ddb..901bcf4 100644
--- a/untangle.c
+++ b/untangle.c
@@ -726,12 +726,147 @@ static void free_game(game_state *state)
 static char *solve_game(game_state *state, game_state *currstate,
 			char *aux, char **error)
 {
+    int n = state->params.n;
+    int matrix[4];
+    point *pts;
+    int i, j, besti;
+    float bestd;
+    char buf[80], *ret;
+    int retlen, retsize;
+
     if (!aux) {
 	*error = "Solution not known for this puzzle";
 	return NULL;
     }
 
-    return dupstr(aux);
+    /*
+     * Decode the aux_info to get the original point positions.
+     */
+    pts = snewn(n, point);
+    aux++;                             /* eat 'S' */
+    for (i = 0; i < n; i++) {
+        int p, k;
+        long x, y, d;
+	int ret = sscanf(aux, ";P%d:%ld,%ld/%ld%n", &p, &x, &y, &d, &k);
+        if (ret != 4 || p != i) {
+            *error = "Internal error: aux_info badly formatted";
+            sfree(pts);
+            return NULL;
+        }
+        pts[i].x = x;
+        pts[i].y = y;
+        pts[i].d = d;
+        aux += k;
+    }
+
+    /*
+     * Now go through eight possible symmetries of the point set.
+     * For each one, work out the sum of the Euclidean distances
+     * between the points' current positions and their new ones.
+     * 
+     * We're squaring distances here, which means we're at risk of
+     * integer overflow. Fortunately, there's no real need to be
+     * massively careful about rounding errors, since this is a
+     * non-essential bit of the code; so I'll just work in floats
+     * internally.
+     */
+    besti = -1;
+    bestd = 0.0F;
+
+    for (i = 0; i < 8; i++) {
+        float d;
+
+        matrix[0] = matrix[1] = matrix[2] = matrix[3] = 0;
+        matrix[i & 1] = (i & 2) ? +1 : -1;
+        matrix[3-(i&1)] = (i & 4) ? +1 : -1;
+
+        d = 0.0F;
+        for (j = 0; j < n; j++) {
+            float px = (float)pts[j].x / pts[j].d;
+            float py = (float)pts[j].y / pts[j].d;
+            float sx = (float)currstate->pts[j].x / currstate->pts[j].d;
+            float sy = (float)currstate->pts[j].y / currstate->pts[j].d;
+            float cx = (float)currstate->w / 2;
+            float cy = (float)currstate->h / 2;
+            float ox, oy, dx, dy;
+
+            px -= cx;
+            py -= cy;
+
+            ox = matrix[0] * px + matrix[1] * py;
+            oy = matrix[2] * px + matrix[3] * py;
+
+            ox += cx;
+            oy += cy;
+
+            dx = ox - sx;
+            dy = oy - sy;
+
+            d += dx*dx + dy*dy;
+        }
+
+        if (besti < 0 || bestd > d) {
+            besti = i;
+            bestd = d;
+        }
+    }
+
+    assert(besti >= 0);
+
+    /*
+     * Now we know which symmetry is closest to the points' current
+     * positions. Use it.
+     */
+    matrix[0] = matrix[1] = matrix[2] = matrix[3] = 0;
+    matrix[besti & 1] = (besti & 2) ? +1 : -1;
+    matrix[3-(besti&1)] = (besti & 4) ? +1 : -1;
+
+    retsize = 256;
+    ret = snewn(retsize, char);
+    retlen = 0;
+    ret[retlen++] = 'S';
+    ret[retlen] = '\0';
+
+    for (i = 0; i < n; i++) {
+        float px = (float)pts[i].x / pts[i].d;
+        float py = (float)pts[i].y / pts[i].d;
+        float cx = (float)currstate->w / 2;
+        float cy = (float)currstate->h / 2;
+        float ox, oy;
+        int extra;
+
+        px -= cx;
+        py -= cy;
+
+        ox = matrix[0] * px + matrix[1] * py;
+        oy = matrix[2] * px + matrix[3] * py;
+
+        ox += cx;
+        oy += cy;
+
+        /*
+         * Use a fixed denominator of 2, because we know the
+         * original points were on an integer grid offset by 1/2.
+         */
+        pts[i].d = 2;
+        ox *= pts[i].d;
+        oy *= pts[i].d;
+        pts[i].x = ox + 0.5;
+        pts[i].y = oy + 0.5;
+
+        extra = sprintf(buf, ";P%d:%ld,%ld/%ld", i,
+                        pts[i].x, pts[i].y, pts[i].d);
+        if (retlen + extra >= retsize) {
+            retsize = retlen + extra + 256;
+            ret = sresize(ret, retsize, char);
+        }
+        strcpy(ret + retlen, buf);
+        retlen += extra;
+    }
+
+    sfree(pts);
+
+    return ret;
 }
 
 static char *game_text_format(game_state *state)
-- 
2.11.0