chiark / gitweb /
mention ijackson's repo for jpctb-linkfarmer
[ypp-sc-tools.db-live.git] / yarrg / rssearch.c
1 /*
2  * Route searcher - recursive iteration over all routes
3  */
4 /*
5  *  This is part of the YARRG website, a tool for assisting
6  *  players of Yohoho Puzzle Pirates.
7  * 
8  *  Copyright (C) 2009 Ian Jackson <ijackson@chiark.greenend.org.uk>
9  *
10  *  This program is free software: you can redistribute it and/or modify
11  *  it under the terms of the GNU Affero General Public License as
12  *  published by the Free Software Foundation, either version 3 of the
13  *  License, or (at your option) any later version.
14  *  
15  *  This program is distributed in the hope that it will be useful,
16  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
17  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
18  *  GNU Affero General Public License for more details.
19  *  
20  *  You should have received a copy of the GNU Affero General Public License
21  *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
22  *  
23  *  Yohoho and Puzzle Pirates are probably trademarks of Three Rings and
24  *  are used without permission.  This program is not endorsed or
25  *  sponsored by Three Rings.
26  */
27
28 #include "rscommon.h"
29
30 DEBUG_DEFINE_DEBUGF(search);
31 DEBUG_DEFINE_SOME_DEBUGF(filter,fildebugf);
32
33 typedef struct Neighbour {
34   struct Neighbour *next;
35   int islandid;
36   int dist;
37 } Neighbour;
38
39 static Neighbour **neighbours; /* neighbours[islandid]->islandid etc. */
40 static sqlite3_stmt *ss_neigh;
41
42 static int ports[MAX_ROUTELEN];
43 static int final_isle;
44
45 static Neighbour *get_neighbours(int isle) {
46   Neighbour **np= &neighbours[isle];
47   Neighbour *head= *np;
48   if (head) return head;
49
50   SQL_BIND(ss_neigh, 1, isle);
51   while (SQL_STEP(ss_neigh)) {
52     Neighbour *add;
53     NEW(add);
54     add->islandid= sqlite3_column_int(ss_neigh, 0);
55     add->dist= sqlite3_column_int(ss_neigh, 1);
56     add->next= head;
57     head= add;
58   }
59   SQL_MUST( sqlite3_reset(ss_neigh) );
60
61   *np= head;
62   return head;
63 }
64
65
66 static Bucket ***buckets_base[GRANUS];
67
68
69 static double process_route(int nports, int totaldist,
70                             double overestimate_excepting_tail) {
71   int i, ap, granui;
72   int leagues_divisor= totaldist + nports;
73
74   ctr_routes_considered++;
75
76   int wrong_final= final_isle && ports[nports-1] != final_isle;
77
78   debugf("========== ROUTE");
79   for (i=0; i<nports; i++)
80     debugf(" %d",ports[i]);
81   debugf("\n");
82
83   double guess[AP]={0,0};
84   if (nports>=2) {
85     int pair[2], i;
86     pair[1]= ports[nports-1];
87     guess[A]= overestimate_excepting_tail;
88
89     for (i=0; i<nports; i++) {
90       pair[0]= ports[i];
91       IslandPair *ip= ipair_get_maybe(pair[0], pair[1]);
92       if (!ip) continue;
93       if (ip->route_tail_value < 0) {
94         ctr_subroute_tails_valued++;
95         ip->route_tail_value= value_route(2, pair, pair[0]!=pair[1]);
96       }
97       guess[A] += ip->route_tail_value;
98     }
99     guess[P]= guess[A] / leagues_divisor;
100
101     if (wrong_final) {
102       ctr_routes_wrongfinalelim++;
103       debugf(" WFELIM\n");
104       return guess[A];
105     }
106
107     for (granui=0; granui<granus; granui++) {
108       if (guess[A] > highscores[granui][A][0].value ||
109           guess[P] > highscores[granui][P][0].value)
110         goto not_quickelim;
111     }
112     ctr_routes_quickelim++;
113     debugf(" QELIM %f %f\n", guess[A], guess[P]);
114     return guess[A];
115   not_quickelim:;
116   }
117
118   int finisle= ports[nports-1];
119   int finarch= isle2arch(finisle);
120
121   int midisle= ports[nports/2];
122   int midarch= route2midarch(ports,nports);
123
124   Bucket *buckets[GRANUS];
125   for (granui=0; granui<granus; granui++) {
126     Bucket **buckets_fin;
127     int mid, fin;
128     switch (granui) {
129     case 0: fin=finarch; mid=midarch; break;
130     case 1: fin=finisle; mid=midarch; break;
131     case 2: fin=finisle; mid=midisle; break;
132     default: abort();
133     }
134     buckets_fin= ONDEMAND(buckets_base[granui][fin], granusz_mid[granui]);
135     buckets[granui]= ONDEMAND(buckets_fin[mid], 1);
136   }
137
138   if (nports>=2) {
139     for (granui=0; granui<granus; granui++)
140       for (ap=0; ap<AP; ap++)
141         if (guess[ap] > buckets[granui]->prs[ap].value[ap] &&
142             guess[ap] > highscores[granui][ap][0].value)
143           goto not_bucketelim;
144     ctr_routes_bucketelim++;
145     debugf(" ELIM %f %f\n", guess[A], guess[P]);
146     return guess[A];
147   not_bucketelim:
148     debugf(" COMPUTE %f %f\n", guess[A], guess[P]);
149   }
150
151   ctr_routes_valued++;
152
153   double value[AP];
154   value[A]= value_route(nports, ports, 0);
155   value[P]= value[A] / leagues_divisor;
156
157   if (wrong_final) {
158     ctr_routes_wrongfinal++;
159     return value[0];
160   }
161
162   for (granui=granus-1; granui>=0; granui--) {
163     Bucket *bucket= buckets[granui];
164
165     if (value[A] <= bucket->prs[A].value[A] &&
166         value[P] <= bucket->prs[P].value[P])
167       continue;
168
169     debugf(" SOMEHOW %d BEST\n",granui);
170
171     fildebugf("granu %d f%d:%3d mid%d:%3d ",granui,
172               finarch,finisle,midarch,midisle);
173
174     for (ap=0; ap<AP; ap++) {
175       HighScoreEntry *scores= highscores[granui][ap];
176       int nscores= nhighscores[granui][ap];
177
178       fildebugf("ap=%d %15f", ap, value[ap]);
179       if (value[ap] < bucket->prs[ap].value[ap]) {
180         debugf("      ");
181       } else {
182         int pos;
183         ctr_newbests_granu[granui*AP+ap]++;
184         bucket->prs[ap].length= totaldist;
185         memcpy(bucket->prs[ap].value, value, sizeof(value));
186         memcpy(bucket->prs[ap].ports, ports, sizeof(*ports) * nports);
187         if (nports < MAX_ROUTELEN-1) bucket->prs[ap].ports[nports]= -1;
188         fildebugf("** ");
189         for (pos=0; pos < nscores; pos++)
190           if (scores[pos].bucket == bucket) goto found;
191         /* not found */
192         pos= -1;
193       found:
194         for (;;) {
195           pos++;
196           if (pos >= nscores) break; /* new top */
197           if (scores[pos].value >= value[ap]) break; /* found spot */
198           if (pos>0)
199             scores[pos-1]= scores[pos];
200         }
201         pos--;
202         if (pos>0) {
203           scores[pos].value= value[ap];
204           scores[pos].bucket= bucket;
205           if (granui < granus-1 &&
206               highscores[granui][A][0].bucket &&
207               highscores[granui][P][0].bucket) {
208             /* both absolute and perleague are full at this granularity,
209              * so we don't care about anything more granular */
210             fildebugf("\n                STOP-GRANU            ");
211             granus= granui+1;
212           }
213         }
214         fildebugf("@%2d/%2d ", pos, nscores);
215       } /* new best */
216     } /* ap */
217   } /* granui */
218
219   fildebugf(" route");
220
221   for (i=0; i<nports; i++)
222     fildebugf(" %d",ports[i]);
223   fildebugf("\n");
224
225   return value[0];
226 }
227
228 static void recurse(int last_isle,
229                     int nports /* excluding last_isle */,
230                     int totaldist /* including last_isle */,
231                     double last_estimate) {
232   ports[nports++]= last_isle;
233   double estimate= process_route(nports, totaldist, last_estimate);
234   if (nports >= MAX_ROUTELEN) return;
235
236   Neighbour *add;
237   for (add= get_neighbours(last_isle); add; add=add->next) {
238     int newdist= totaldist + add->dist;
239     if (newdist > max_dist) continue;
240
241     recurse(add->islandid, nports, newdist, estimate);
242   }
243 }
244
245 void search(int start_isle, int final_isle_spec,
246             Bucket ****buckets_base_io[GRANUS]) {
247   int granui;
248   for (granui=0; granui<GRANUS; granui++)
249     buckets_base[granui]=
250       ONDEMAND(*buckets_base_io[granui], granusz_fin[granui]);
251
252   final_isle= final_isle_spec <= 0 ? 0 : final_isle_spec;
253   recurse(start_isle,0,0,1e6);
254 }
255
256 int nhighscores[GRANUS][AP];
257 HighScoreEntry *highscores[GRANUS][AP];
258 int granus=GRANUS, granusz_fin[GRANUS], granusz_mid[GRANUS];
259
260 int narches;
261 char **archnames;
262 int *islandid2arch;
263
264 void setup_search(void) {
265   MCALLOC(neighbours, islandtablesz);
266
267   SQL_PREPARE(ss_neigh,
268               "SELECT biid, dist FROM routes WHERE aiid=?");
269
270   int max_narches=
271     sql_single_int(" SELECT count(*) FROM (\n"
272                    "  SELECT DISTINCT archipelago\n"
273                    "   FROM islands\n"
274                    "  )");
275   MCALLOC(archnames, max_narches);
276   MCALLOC_INITEACH(islandid2arch, islandtablesz, *this=-1);
277
278   sqlite3_stmt *archs;
279   SQL_PREPARE(archs,
280               " SELECT islandid, archipelago\n"
281               "  FROM islands\n"
282               "  ORDER BY archipelago");
283   while (SQL_STEP(archs)) {
284     int isle= sqlite3_column_int(archs,0);
285     const char *archname= (const char*)sqlite3_column_text(archs,1);
286     int arch;
287     for (arch=0; arch<narches; arch++)
288       if (!strcmp(archnames[arch], archname)) goto found;
289     assert(narches < max_narches);
290     arch= narches++;
291     archnames[arch]= masprintf("%s",archname);
292   found:
293     islandid2arch[isle]= arch;
294   }
295   sqlite3_finalize(archs);
296
297   granusz_fin[0]=                granusz_mid[0]= narches;
298   granusz_fin[1]= islandtablesz; granusz_mid[1]= narches;
299   granusz_fin[2]=                granusz_mid[2]= islandtablesz;
300 }