git.sesse.net Git - nms/blob - planning/planning.cpp

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <unistd.h>
   4 #include <limits.h>
   5 #include <vector>
   6 #include <map>
   7 #include <algorithm>
   8
   9 #define NUM_DISTRO 5
  10 #define SWITCHES_PER_ROW 6
  11 #define TRUNCATE_METRIC 1
  12 #define TENPLUSTEN 250
  13 #define THIRTYPLUSTEN 450
  14 #define FIFTYPLUSTEN 650
  15
  16 struct sw {
  17         unsigned char row, num;
  18
  19         sw(unsigned char row, unsigned char num) : row(row), num(num) {}
  20 };
  21 int distro_placements[NUM_DISTRO] = {
  22         5, 12, 19, 26, 33
  23 };
  24 unsigned horiz_cost[SWITCHES_PER_ROW] = {
  25         346, 250, 154, 104, 200, 296
  26 };
  27
  28 // memoization table
  29 struct key {
  30         unsigned char sw_ind, distro_bound, distro_bound_hard;
  31         unsigned char ports_left[NUM_DISTRO];
  32
  33         bool operator< (const key &other) const
  34         {
  35                 if (sw_ind != other.sw_ind)
  36                         return (sw_ind < other.sw_ind);
  37                 if (distro_bound != other.distro_bound)
  38                         return (distro_bound < other.distro_bound);
  39                 if (distro_bound_hard != other.distro_bound_hard)
  40                         return (distro_bound_hard < other.distro_bound_hard);
  41                 for (unsigned i = distro_bound_hard; i < NUM_DISTRO - 1; ++i)
  42                         if (ports_left[i] != other.ports_left[i])
  43                                 return (ports_left[i] < other.ports_left[i]);
  44                 return (ports_left[NUM_DISTRO - 1] < other.ports_left[NUM_DISTRO - 1]);
  45         }
  46 };
  47 struct value {
  48         unsigned char distro;
  49         unsigned cost, this_cost;
  50 };
  51 std::map<key, value> cache;
  52 unsigned cache_hits = 0;
  53 std::vector<sw> switches;
  54
  55 unsigned distance(sw from_where, unsigned distro)
  56 {
  57         // FIXME: calculate gaps as well
  58         unsigned base_cost = 41 * abs(from_where.row - distro_placements[distro]) + horiz_cost[from_where.num];
  59
  60         if ((from_where.row <= 9) == (distro_placements[distro] >= 10))
  61                 base_cost += 25;
  62         if ((from_where.row <= 17) == (distro_placements[distro] >= 18))
  63                 base_cost += 25;
  64         if ((from_where.row <= 25) == (distro_placements[distro] >= 26))
  65                 base_cost += 25;
  66         if ((from_where.row <= 34) == (distro_placements[distro] >= 35))
  67                 base_cost += 25;
  68
  69 #if TRUNCATE_METRIC
  70         if (base_cost > 600)
  71                 return 1000;
  72         if (base_cost > 500)
  73                 return FIFTYPLUSTEN;
  74         if (base_cost > 400)
  75                 return 500;
  76         if (base_cost > 300)
  77                 return THIRTYPLUSTEN;
  78         if (base_cost > 200)
  79                 return 300;
  80         if (base_cost > 100)
  81                 return TENPLUSTEN;
  82         return 100;
  83 #else
  84         return base_cost;
  85 //      return ((base_cost + 90) / 100) * 100;
  86 #endif
  87 }
  88
  89 unsigned find_optimal_cost(key &k)
  90 {
  91         unsigned best_cost = 999999990, best_this_cost = 0;
  92         int best = -1;
  93         unsigned char db = k.distro_bound;
  94         unsigned char dbh = k.distro_bound_hard;
  95
  96         if (k.sw_ind == switches.size())
  97                 return 0;
  98         if (cache.count(k)) {
  99                 ++cache_hits;
 100                 return cache[k].cost;
 101         }
 102
 103         bool next_changes_row = (k.sw_ind + 1U < switches.size() && switches[k.sw_ind].row != switches[k.sw_ind + 1].row);
 104
 105         for (unsigned char i = dbh; i < dbh + 2 && i < NUM_DISTRO; ++i) {
 106                 if (k.ports_left[i] == 0)
 107                         continue;
 108
 109                 unsigned cost = distance(switches[k.sw_ind], i);
 110
 111                 --(k.ports_left[i]);
 112                 ++(k.sw_ind);
 113
 114                 k.distro_bound = std::max(i, db);
 115                 if (next_changes_row) {
 116                         k.distro_bound_hard = k.distro_bound;
 117                 }
 118
 119                 cost += find_optimal_cost(k);
 120                 --(k.sw_ind);
 121                 ++(k.ports_left[i]);
 122
 123                 if (best == -1 || cost < best_cost) {
 124                         best = i;
 125                         best_cost = cost;
 126                         best_this_cost = distance(switches[k.sw_ind], i);
 127                 }
 128         }
 129         k.distro_bound = db;
 130         k.distro_bound_hard = dbh;
 131
 132         value v = { best, best_cost, best_this_cost };
 133         cache[k] = v;
 134
 135         return best_cost;
 136 }
 137
 138 int main()
 139 {
 140         struct key start;
 141 #if TRUNCATE_METRIC
 142         std::map<unsigned, unsigned> cable_count;
 143 #endif
 144
 145         switches.push_back(sw(1, 3));
 146         switches.push_back(sw(1, 4));
 147         switches.push_back(sw(1, 5));
 148         switches.push_back(sw(2, 3));
 149         switches.push_back(sw(2, 4));
 150         switches.push_back(sw(2, 5));
 151
 152         for (unsigned i = 3; i < 35; ++i)
 153                 for (unsigned j = 0; j < SWITCHES_PER_ROW; ++j)
 154                         switches.push_back(sw(i, j));
 155
 156         switches.push_back(sw(35, 1));
 157         switches.push_back(sw(35, 2));
 158         switches.push_back(sw(35, 3));
 159         switches.push_back(sw(35, 4));
 160
 161         switches.push_back(sw(36, 1));
 162         switches.push_back(sw(36, 2));
 163         switches.push_back(sw(36, 3));
 164         switches.push_back(sw(36, 4));
 165
 166         switches.push_back(sw(37, 1));
 167         switches.push_back(sw(37, 2));
 168         switches.push_back(sw(37, 3));
 169         switches.push_back(sw(37, 4));
 170
 171         start.sw_ind = 0;
 172         start.distro_bound = 0;
 173         start.distro_bound_hard = 0;
 174         start.ports_left[0] = 40;
 175         start.ports_left[1] = 40;
 176         start.ports_left[2] = 50;
 177         start.ports_left[3] = 40;
 178         start.ports_left[4] = 40;
 179
 180         printf("Finding optimal layout for %u switches\n", switches.size());
 181         find_optimal_cost(start);
 182         printf("%u cache nodes, %u cache hits.\n", cache.size(), cache_hits);
 183
 184         key k = start;
 185         int last_row = 0, last_num = -1;
 186         for (unsigned i = 0; i < switches.size(); ++i) {
 187                 value v = cache[k];
 188                 bool next_changes_row = (k.sw_ind + 1U < switches.size() && switches[k.sw_ind].row != switches[k.sw_ind + 1].row);
 189
 190                 if (cache.count(k) == 0) {
 191                         fprintf(stderr, "FATAL: no solutions!\n");
 192                         exit(1);
 193                 }
 194
 195                 k.distro_bound = std::max(k.distro_bound, v.distro);
 196                 if (next_changes_row)
 197                         k.distro_bound_hard = k.distro_bound;
 198
 199                 if (last_row != switches[k.sw_ind].row) {
 200                         printf("\n");
 201                         last_num = -1;
 202                 }
 203                 for (int j = last_num; j + 1 < switches[k.sw_ind].num; ++j) {
 204                         printf("%11s", "");
 205                 }
 206
 207
 208                 printf("\e[%um%u ", v.distro + 33, v.distro);
 209 #if TRUNCATE_METRIC
 210                 if (v.this_cost == FIFTYPLUSTEN)
 211                         printf("(50+10)  ");
 212                 else if (v.this_cost == THIRTYPLUSTEN)
 213                         printf("(30+10)  ");
 214                 else if (v.this_cost == TENPLUSTEN)
 215                         printf("(10+10)  ");
 216                 else
 217                         printf("(%-3u  )  ", v.this_cost / 10);
 218                 cable_count[v.this_cost]++;
 219 #else
 220                 printf("(%3.1f)   ", v.this_cost / 10.0);
 221 #endif
 222
 223                 last_row = switches[k.sw_ind].row;
 224                 last_num = switches[k.sw_ind].num;
 225
 226                 ++(k.sw_ind);
 227                 --k.ports_left[v.distro];
 228         }
 229         printf("\n");
 230
 231         for (std::map<unsigned,unsigned>::iterator i = cable_count.begin(); i != cable_count.end(); ++i)
 232                 printf("%u => %u\n", i->first, i->second);
 233 }