yarrg/rssearch.c

   1 /**/
   2
   3 #include "rscommon.h"
   4
   5 DEBUG_DEFINE_DEBUGF(search);
   6 DEBUG_DEFINE_SOME_DEBUGF(filter,fildebugf);
   7
   8 typedef struct Neighbour {
   9   struct Neighbour *next;
  10   int islandid;
  11   int dist;
  12 } Neighbour;
  13
  14 static Neighbour **neighbours; /* neighbours[islandid]->islandid etc. */
  15 static sqlite3_stmt *ss_neigh;
  16
  17 static int ports[MAX_ROUTELEN];
  18 static int final_isle;
  19
  20 static Neighbour *get_neighbours(int isle) {
  21   Neighbour **np= &neighbours[isle];
  22   Neighbour *head= *np;
  23   if (head) return head;
  24
  25   SQL_BIND(ss_neigh, 1, isle);
  26   while (SQL_STEP(ss_neigh)) {
  27     Neighbour *add;
  28     NEW(add);
  29     add->islandid= sqlite3_column_int(ss_neigh, 0);
  30     add->dist= sqlite3_column_int(ss_neigh, 1);
  31     add->next= head;
  32     head= add;
  33   }
  34   SQL_MUST( sqlite3_reset(ss_neigh) );
  35
  36   *np= head;
  37   return head;
  38 }
  39
  40
  41 static PotentialResult ***strat_base[STRATS];
  42
  43
  44 static double process_route(int nports, int totaldist,
  45                             double overestimate_excepting_tail) {
  46   int i, ap;
  47   int leagues_divisor= totaldist + nports;
  48
  49   ctr_routes_considered++;
  50
  51   int wrong_final= final_isle && ports[nports-1] != final_isle;
  52
  53   debugf("========== ROUTE");
  54   for (i=0; i<nports; i++)
  55     debugf(" %d",ports[i]);
  56   debugf("\n");
  57
  58   double guess[AP]={0,0};
  59   if (nports>=2) {
  60     int pair[2], i;
  61     pair[1]= ports[nports-1];
  62     guess[A]= overestimate_excepting_tail;
  63
  64     for (i=0; i<nports; i++) {
  65       pair[0]= ports[i];
  66       IslandPair *ip= ipair_get_maybe(pair[0], pair[1]);
  67       if (!ip) continue;
  68       if (ip->route_tail_value < 0) {
  69         ctr_subroute_tails_valued++;
  70         ip->route_tail_value= value_route(2, pair, pair[0]!=pair[1]);
  71       }
  72       guess[A] += ip->route_tail_value;
  73     }
  74     guess[P]= guess[A] / leagues_divisor;
  75
  76     if (wrong_final) {
  77       ctr_routes_wrongfinalelim++;
  78       debugf(" WFELIM\n");
  79       return guess[A];
  80     }
  81
  82     if (guess[A] <= highscores[minstrat][A][0].value &&
  83         guess[P] <= highscores[minstrat][P][0].value) {
  84       ctr_routes_quickelim++;
  85       debugf(" QELIM %f %f\n", guess[A], guess[P]);
  86       return guess[A];
  87     }
  88   }
  89
  90   int finisle= ports[nports-1];
  91   int finarch= isle2arch(finisle);
  92
  93   int midisle= ports[nports/2];
  94   int midarch= route2midarch(ports,nports);
  95
  96   PotentialResult *strats[STRATS];
  97   int strati;
  98   for (strati=minstrat; strati<STRATS; strati++) {
  99     PotentialResult **strat_fin;
 100     int mid, fin;
 101     switch (strati) {
 102     case 0: fin=finisle; mid=midisle; break;
 103     case 1: fin=finisle; mid=midarch; break;
 104     case 2: fin=finarch; mid=midarch; break;
 105     default: abort();
 106     }
 107     strat_fin= ONDEMAND(strat_base[strati][fin], stratsz_mid[strati]);
 108     strats[strati]= ONDEMAND(strat_fin[mid], 1);
 109   }
 110
 111   if (nports>=2) {
 112     if (guess[A] <= strats[minstrat]->value[A] &&
 113         guess[P] <= strats[minstrat]->value[P]) {
 114       ctr_routes_stratelim++;
 115       debugf(" ELIM %f %f\n", guess[A], guess[P]);
 116       return guess[A];
 117     }
 118     debugf(" COMPUTE %f %f\n", guess[A], guess[P]);
 119   }
 120
 121   ctr_routes_valued++;
 122
 123   double value[AP];
 124   value[A]= value_route(nports, ports, 0);
 125   value[P]= value[A] / leagues_divisor;
 126
 127   if (wrong_final) {
 128     ctr_routes_wrongfinal++;
 129     return value[0];
 130   }
 131
 132   for (strati=minstrat; strati<STRATS; strati++) {
 133     PotentialResult *strat= strats[strati];
 134
 135     if (value[A] <= strat->value[A] &&
 136         value[P] <= strat->value[P])
 137       continue;
 138
 139     debugf(" SOMEHOW %d BEST\n",strati);
 140
 141     fildebugf("final %d:%3d mid %d ",finarch,finisle,midarch);
 142
 143     for (ap=0; ap<AP; ap++) {
 144       HighScoreEntry *scores= highscores[strati][ap];
 145       int *nscores= &nhighscores[strati][ap];
 146
 147       fildebugf("ap=%d %15f", ap, value[ap]);
 148       if (value[ap] < strat->value[ap]) {
 149         debugf("      ");
 150       } else {
 151         int pos;
 152         ctr_newbests_strat[ap]++;
 153         strat->value[ap]= value[ap];
 154         memcpy(strat->ports[ap], ports, sizeof(*ports) * nports);
 155         if (nports < MAX_ROUTELEN-1) strat->ports[ap][nports]= -1;
 156         fildebugf("** ");
 157         for (pos=0; pos < *nscores; pos++)
 158           if (scores[pos].pr == strat) goto found;
 159         /* not found */
 160         pos= -1;
 161       found:
 162         for (;;) {
 163           pos++;
 164           if (pos >= *nscores-1) break; /* new top */
 165           if (scores[pos].value >= value[ap]) break; /* found spot */
 166           if (pos>0)
 167             scores[pos-1]= scores[pos];
 168         }
 169         pos--;
 170         if (pos>0) {
 171           scores[pos].value= value[ap];
 172           scores[pos].pr= strat;
 173         }
 174         fildebugf("@%2d", pos);
 175       }
 176     }
 177   }
 178
 179   fildebugf(" route");
 180
 181   for (i=0; i<nports; i++)
 182     fildebugf(" %d",ports[i]);
 183   fildebugf("\n");
 184
 185   return value[0];
 186 }
 187
 188 static void recurse(int last_isle,
 189                     int nports /* excluding last_isle */,
 190                     int totaldist /* including last_isle */,
 191                     double last_estimate) {
 192   ports[nports++]= last_isle;
 193   double estimate= process_route(nports, totaldist, last_estimate);
 194   if (nports >= MAX_ROUTELEN) return;
 195
 196   Neighbour *add;
 197   for (add= get_neighbours(last_isle); add; add=add->next) {
 198     int newdist= totaldist + add->dist;
 199     if (newdist > max_dist) continue;
 200
 201     recurse(add->islandid, nports, newdist, estimate);
 202   }
 203 }
 204
 205 void search(int start_isle, int final_isle_spec,
 206             PotentialResult ****strat_base_io[STRATS]) {
 207   int strati;
 208   for (strati=0; strati<STRATS; strati++)
 209     strat_base[strati]= ONDEMAND(*strat_base_io[strati], stratsz_fin[strati]);
 210
 211   final_isle= final_isle_spec <= 0 ? 0 : final_isle_spec;
 212   recurse(start_isle,0,0,1e6);
 213 }
 214
 215 int nhighscores[STRATS][AP];
 216 HighScoreEntry *highscores[STRATS][AP];
 217 int minstrat, stratsz_fin[STRATS], stratsz_mid[STRATS];
 218
 219 int narches;
 220 char **archnames;
 221 int *islandid2arch;
 222
 223 void setup_search(void) {
 224   MCALLOC(neighbours, islandtablesz);
 225
 226   SQL_PREPARE(ss_neigh,
 227               "SELECT biid, dist FROM routes WHERE aiid=?");
 228
 229   int max_narches=
 230     sql_single_int(" SELECT count(*) FROM (\n"
 231                    "  SELECT DISTINCT archipelago\n"
 232                    "   FROM islands\n"
 233                    "  )");
 234   MCALLOC(archnames, max_narches);
 235   MCALLOC_INITEACH(islandid2arch, islandtablesz, *this=-1);
 236
 237   sqlite3_stmt *archs;
 238   SQL_PREPARE(archs,
 239               " SELECT islandid, archipelago\n"
 240               "  FROM islands\n"
 241               "  ORDER BY archipelago");
 242   while (SQL_STEP(archs)) {
 243     int isle= sqlite3_column_int(archs,0);
 244     const char *archname= (const char*)sqlite3_column_text(archs,1);
 245     int arch;
 246     for (arch=0; arch<narches; arch++)
 247       if (!strcmp(archnames[arch], archname)) goto found;
 248     assert(narches < max_narches);
 249     arch= narches++;
 250     archnames[arch]= masprintf("%s",archname);
 251   found:
 252     islandid2arch[isle]= arch;
 253   }
 254   sqlite3_finalize(archs);
 255
 256   stratsz_fin[0]=                stratsz_mid[0]= islandtablesz;
 257   stratsz_fin[1]= islandtablesz; stratsz_mid[1]= narches;
 258   stratsz_fin[2]=                stratsz_mid[2]= narches;
 259 }