WIP routesearch; searcher

diff --git a/yarrg/Makefile b/yarrg/Makefile
index ed4f372ac3bf78b0a449510710c90e6e286554a4..a9c833b622760f697f86d30fe52c5b1bef6d547e 100644 (file)
--- a/yarrg/Makefile
+++ b/yarrg/Makefile
@@ -38,7 +38,7 @@ all: default routesearch
 
 CONVERT_OBJS= convert.o ocr.o pages.o structure.o rgbimage.o resolve.o
 COMMON_OBJS= common.o
-ROUTESEARCH_OBJS= rsvalue.o rsmain.o rssql.o
+ROUTESEARCH_OBJS= rsvalue.o rsmain.o rssql.o rssearch.o
 
 yarrg: $(CONVERT_OBJS) $(COMMON_OBJS) -lnetpbm -lXtst -lX11 -lpcre -lm
        $(CC) $(CFLAGS) $(LDFLAGS) -o $@ $^ $(LDLIBS)

diff --git a/yarrg/rscommon.h b/yarrg/rscommon.h
index d068fa02ba25a040eae556ebb3b278519f67a76e..1e710dc0075082cfc821d997f5f86c01bc85144f 100644 (file)
--- a/yarrg/rscommon.h
+++ b/yarrg/rscommon.h
@@ -8,7 +8,9 @@
    DF(sql2)                                    \
    DF(value)                                   \
    DF(lp)
+
 #define debug stdout
+#define DEBUG_DEV "/dev/stdout"
 
 #include "common.h"
 
@@ -43,14 +45,19 @@ void sql_bind(sqlite3_stmt *ss, int index, int value,
 
 extern sqlite3 *db;
 
-void setup(void);
+void setup_sql(void);
 double value_route(int nislands, const int *islands);
 void setup_value(void);
-void setup_commods(void);
+void setup_search(void);
+void search(int start_isle);
 
 extern double max_mass, max_volu, max_capi;
 extern double distance_loss_factor_per_league;
+extern int max_dist;
 
 #define LOSS_FACTOR_PER_DELAY_SLOT (1-1e-8)
 
+extern int islandtablesz;
+
+
 #endif /*RSCOMMON_H*/

diff --git a/yarrg/rsmain.c b/yarrg/rsmain.c
index 49a59a4067ab42cee48f2f839c8b28607f47754b..4b7dea9907678a6840d778d92891f919e8f2d24c 100644 (file)
--- a/yarrg/rsmain.c
+++ b/yarrg/rsmain.c
@@ -5,12 +5,16 @@
 int o_quiet= 0;
 double max_mass=-1, max_volu=-1, max_capi=-1;
 double distance_loss_factor_per_league;
+int max_dist= -1;
 
 int main(int argc, const char **argv) {
-  int ia[argc], ni=0;
+  const char *arg;
 
   debug_flags= ~( dbg_sql2 );
-  setup();
+
+  setup_sql();
+  setup_value();
+  setup_search();
 
   max_mass= atof(*++argv);
   max_volu= atof(*++argv);
@@ -20,11 +24,20 @@ int main(int argc, const char **argv) {
   if (!loss_per_league) loss_per_league= 1e-7;
   distance_loss_factor_per_league= 1.0 - loss_per_league;
   
-  const char *arg;
-  while ((arg= *++argv)) {
-    ia[ni++]= atoi(arg);
+  arg= *++argv;
+  if (!strcmp(arg,"specific")) {
+    int ia[argc], ni=0;
+    while ((arg= *++argv))
+      ia[ni++]= atoi(arg);
+
+    double val= value_route(ni, ia);
+    printf("route value is %g\n", val);
+  } else if (!strcmp(arg,"search")) {
+    max_dist= atoi(*++argv);
+    while ((arg= *++argv))
+      search(atoi(arg));
+  } else {
+    abort();
   }
-  double val= value_route(ni, ia);
-  printf("route value is %g\n", val);
   return 0;
 }

diff --git a/yarrg/rssearch.c b/yarrg/rssearch.c
new file mode 100644 (file)
index 0000000..c51aae0
--- /dev/null
+++ b/yarrg/rssearch.c
@@ -0,0 +1,75 @@
+/**/
+
+#include "rscommon.h"
+
+typedef struct Neighbour {
+  struct Neighbour *next;
+  int islandid;
+  int dist;
+} Neighbour;
+
+static Neighbour **neighbours; /* neighbours[islandid]->islandid etc. */
+static sqlite3_stmt *ss_neigh;
+
+static int ports[MAX_ROUTELEN];
+
+static Neighbour *get_neighbours(int isle) {
+  Neighbour **np= &neighbours[isle];
+  Neighbour *head= *np;
+  if (head) return head;
+
+  SQL_BIND(ss_neigh, 1, isle);
+  while (SQL_STEP(ss_neigh)) {
+    Neighbour *add= mmalloc(sizeof(*add));
+    add->islandid= sqlite3_column_int(ss_neigh, 0);
+    add->dist= sqlite3_column_int(ss_neigh, 1);
+    add->next= head;
+    head= add;
+  }
+  SQL_MUST( sqlite3_reset(ss_neigh) );
+
+  *np= head;
+  return head;
+}
+
+static double bestsofar;
+
+static void process_route(int nports) {
+  double value= value_route(nports, ports);
+  if (value < bestsofar) return;
+
+  fprintf(stderr,"value %20f route", value);
+  int i;
+  for (i=0; i<nports; i++)
+    fprintf(stderr," %d",ports[i]);
+  putc('\n',stderr);
+  
+  bestsofar= value;
+}
+
+static void recurse(int last_isle,
+                   int nports, /* excluding last_isle */
+                   int totaldist /* including last_isle */) {
+  ports[nports++]= last_isle;
+  process_route(nports);
+  if (nports >= MAX_ROUTELEN) return;
+
+  Neighbour *add;
+  for (add= get_neighbours(last_isle); add; add=add->next) {
+    int newdist= totaldist + add->dist;
+    if (newdist > max_dist) continue;
+
+    recurse(add->islandid, nports, newdist);
+  }
+}
+
+void search(int start_isle) {
+  recurse(start_isle,0,0);
+}
+
+void setup_search(void) {
+  neighbours= mcalloc(sizeof(*neighbours) * islandtablesz);
+
+  SQL_PREPARE(ss_neigh,
+             "SELECT biid, dist FROM routes WHERE aiid=?");
+}

diff --git a/yarrg/rssql.c b/yarrg/rssql.c
index 463ef8b560c76dff97b047b22db55f5e4b7d73ca..898ac3b268350b4824021ba987002622600c88e3 100644 (file)
--- a/yarrg/rssql.c
+++ b/yarrg/rssql.c
@@ -4,6 +4,8 @@
 sqlite3 *db;
 sqlite3_stmt *ss_ipair;
 
+int islandtablesz;
+
 DEBUG_DEFINE_DEBUGF(sql);
 
 static int busy_handler(void *u, int previous) {
@@ -12,7 +14,7 @@ static int busy_handler(void *u, int previous) {
   return 1;
 }
 
-void setup(void) {
+void setup_sql(void) {
   sqlite3_stmt *sst;
   
   SQL_MUST( sqlite3_open("OCEAN-Midnight.db", &db) );
@@ -22,7 +24,8 @@ void setup(void) {
   assert( !SQL_STEP(sst) );
   sqlite3_finalize(sst);
 
-  setup_value();
+  islandtablesz= 1 + sql_single_int("SELECT max(islandid) FROM islands");
+  debugf("SQL islandtablesz=%d\n",islandtablesz);
 }
 
 int sql_single_int(const char *stmt) {

diff --git a/yarrg/rsvalue.c b/yarrg/rsvalue.c
index f1a8d224cab316a116012ff74b41c45d09704560..f046c99a896c56ee753a9430144ebd99b6fe7857 100644 (file)
--- a/yarrg/rsvalue.c
+++ b/yarrg/rsvalue.c
@@ -32,7 +32,6 @@ typedef struct {
   TradesBlock *trades;
 } IslandPair;
 
-int nislands;
 IslandPair ***ipairs; /* ipairs[sislandid][dislandid] */
 
 typedef struct IslandTradeEnd {
@@ -108,7 +107,7 @@ static int setup_leg_constraints(double max_thing, int legs, const char *wh) {
   int leg, startrow;
   if (max_thing < 0 || !legs) return -1;
   startrow= lpx_add_rows(lp, legs);
-  for (leg=0; leg<nislands-1; leg++) {
+  for (leg=0; leg<legs; leg++) {
     int row= leg+startrow;
     lpx_set_row_bnds(lp, row, LPX_UP, 0, max_thing);
     if (DEBUGP(value)) {
@@ -129,11 +128,11 @@ static void add_leg_c(int startrow, int leg, double value) {
 static IslandPair *ipair_get(int si, int di) {
   IslandPair *ip, **ipa;
 
-  assert(si < nislands);
-  assert(di < nislands);
+  assert(si < islandtablesz);
+  assert(di < islandtablesz);
 
   if (!(ipa= ipairs[si])) {
-    ipa= ipairs[si]= mcalloc(sizeof(*ipa) * nislands);
+    ipa= ipairs[si]= mcalloc(sizeof(*ipa) * islandtablesz);
   }
   if ((ip= ipa[di]))
     return ip;
@@ -301,7 +300,6 @@ double value_route(int nislands, const int *islands) {
 
        double unit_profit= (t->dst_price - t->src_price) * loss_factor;
        debugf("    unit profit %f\n", unit_profit);
-assert(unit_profit < 1e6);
 
        lpx_set_col_bnds(lp, col, LPX_LO, 0, 0);
        lpx_set_obj_coef(lp, col, unit_profit);
@@ -325,17 +323,21 @@ assert(unit_profit < 1e6);
   next_s:;
   } /* for (s) */
 
-  if (DEBUGP(lp))
-    lpx_write_cpxlp(lp, (char*)"/dev/stdout");
+  double profit= 0;
 
-  int ipr= lpx_interior(lp);
-  assert(ipr==LPX_E_OK);
+  if (lpx_get_num_cols(lp)) {
+    if (DEBUGP(lp))
+      lpx_write_cpxlp(lp, (char*)DEBUG_DEV);
 
-  if (DEBUGP(lp))
-    lpx_print_ips(lp, (char*)"/dev/stdout");
+    int ipr= lpx_interior(lp);
+    assert(ipr==LPX_E_OK);
 
-  assert(lpx_ipt_status(lp) == LPX_T_OPT);
-  double profit= lpx_ipt_obj_val(lp);
+    if (DEBUGP(lp))
+      lpx_print_ips(lp, (char*)DEBUG_DEV);
+
+    assert(lpx_ipt_status(lp) == LPX_T_OPT);
+    profit= lpx_ipt_obj_val(lp);
+  }
 
   lpx_delete_prob(lp);
   lp= 0;
@@ -347,9 +349,6 @@ void setup_value(void) {
   sqlite3_stmt *sst;
   int i;
 
-  nislands= sql_single_int("SELECT max(islandid) FROM islands") + 1;
-  debugf("VALUE nislands=%d\n",nislands);
-
   commodstablesz= sql_single_int("SELECT max(commodid) FROM commods") + 1;
   commodstable= mmalloc(sizeof(*commodstable)*commodstablesz);
   for (i=0; i<commodstablesz; i++)
@@ -392,5 +391,5 @@ void setup_value(void) {
   BS(sell)
 #undef BS
 
-  ipairs= mcalloc(sizeof(*ipairs) * nislands);
+  ipairs= mcalloc(sizeof(*ipairs) * islandtablesz);
 }