bigworld

commit 12d9e95701e4483937ddd262cf0af32c6e25d06d
parent dce073f6b88ce7068d71a418f687920097adb110
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Wed, 20 May 2015 23:46:56 +0200

tidy, fix, all backlash-N now the same

Diffstat:
smallworld.cpp
 | 
41
+++++++++++++++++------------------------
smallworld.sh
 | 
4
+++-

2 files changed, 20 insertions(+), 25 deletions(-)
diff --git a/smallworld.cpp b/smallworld.cpp
@@ -1,18 +1,15 @@
+#include <assert.h>
 #include <cstdio>
+#include <iostream>
 #include <map>
-#include <assert.h>
-#include <vector>
 #include <string>
-#include <iostream>
+#include <vector>
 
 #define NMAX 3200
-//#define AMAX 20000
 #define INF 20000
 #define MULTI 200000
 #define STEP 50
 
-#define max(a, b) ((a)<(b) ? (b) : (a))
-
 using namespace std;
 
 int d[NMAX][NMAX];
@@ -20,7 +17,14 @@ int nx[NMAX][NMAX];
 int airline[NMAX][NMAX];
 vector<string> code;
 map<string, int> alias;
-int fresh;
+
+inline int regcode(string s) {
+  if (!alias.count(s)) {
+    alias[s] = code.size();
+    code.push_back(s);
+  }
+  return alias[s];
+}
 
 // if passed an argument, do the transitive closure
 int main(int argc, char **argv) {
@@ -36,17 +40,8 @@ int main(int argc, char **argv) {
       break;
     string fs, ts;
     cin >> fs >> ts;
-    if (!alias.count(fs)) {
-      alias[fs] = code.size();
-      code.push_back(fs);
-    }
-    if (!alias.count(ts)) {
-      alias[ts] = code.size();
-      code.push_back(ts);
-    }
-    int f = alias[fs], t = alias[ts];
-    printf("%d %d\n", f, t);
-    assert(f < NMAX && t < NMAX);
+    int f = regcode(fs), t = regcode(ts);
+    assert(f < NMAX && t < NMAX && a < MULTI);
     airline[f][t] = (airline[f][t] && airline[f][t] != a) ? MULTI : a;
     d[f][t] = 1;
     nx[f][t] = t;
@@ -83,8 +78,8 @@ int main(int argc, char **argv) {
       if (d[i][j] == INF)
         continue;
       best = max(d[i][j], best);
-      if (d[i][j] == best)
-        printf("%d: %s -> %s\n", best, code[i].c_str(), code[j].c_str());
+      /* if (d[i][j] == best)
+        printf("%d: %s -> %s\n", best, code[i].c_str(), code[j].c_str()); */
     }
   for (unsigned int i = 0; i < n; i++)
     for (unsigned int j = 0; j < n; j++)
@@ -93,10 +88,7 @@ int main(int argc, char **argv) {
         printf("%s ", code[i].c_str());
         int u = i, v = j;
         while (u != v) {
-          if (u < 0) {
-            printf("stuck!");
-            break;
-          }
+          assert(u >= 0);
           u = nx[u][v];
           printf("%s ", code[u].c_str());
         }
@@ -104,3 +96,4 @@ int main(int argc, char **argv) {
       }
   return 0;
 }
+
diff --git a/smallworld.sh b/smallworld.sh
@@ -5,11 +5,13 @@ echo "\\N Y" >> active.dat
 sort -k1,1 active.dat | sponge active.dat
 cut -d, -f2,3,5,7 routes.dat | grep -v 'Y$' | tr ',' ' ' |
   sort -k1,1 > routesb.dat
+# all unregistered airlines get the same code
+# we rely on the fact that all \N come last
 join routesb.dat active.dat |
   grep -v 'N$' | cut -d ' ' -f1-3 |
   awk '{if ($1 == "\\N") {
     print n, $2, $3;
-    n++;
+    # n++;
   } else {
     print $0;
     n = n > $1?n:$1;