10 #define SWITCHES_PER_ROW 6
11 #define TRUNCATE_METRIC 1
12 #define TENPLUSTEN 250
13 #define THIRTYPLUSTEN 450
14 #define FIFTYPLUSTEN 650
17 unsigned char row, num;
19 sw(unsigned char row, unsigned char num) : row(row), num(num) {}
21 int distro_placements[NUM_DISTRO] = {
24 unsigned horiz_cost[SWITCHES_PER_ROW] = {
25 346, 250, 154, 104, 200, 296
30 unsigned char sw_ind, distro_bound, distro_bound_hard;
31 unsigned char ports_left[NUM_DISTRO];
33 bool operator< (const key &other) const
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]);
49 unsigned cost, this_cost;
51 std::map<key, value> cache;
52 unsigned cache_hits = 0;
53 std::vector<sw> switches;
55 unsigned distance(sw from_where, unsigned distro)
57 // FIXME: calculate gaps as well
58 unsigned base_cost = 41 * abs(from_where.row - distro_placements[distro]) + horiz_cost[from_where.num];
60 if ((from_where.row <= 9) == (distro_placements[distro] >= 10))
62 if ((from_where.row <= 17) == (distro_placements[distro] >= 18))
64 if ((from_where.row <= 25) == (distro_placements[distro] >= 26))
66 if ((from_where.row <= 34) == (distro_placements[distro] >= 35))
85 // return ((base_cost + 90) / 100) * 100;
89 unsigned find_optimal_cost(key &k)
91 unsigned best_cost = 999999990, best_this_cost = 0;
93 unsigned char db = k.distro_bound;
94 unsigned char dbh = k.distro_bound_hard;
96 if (k.sw_ind == switches.size())
100 return cache[k].cost;
103 bool next_changes_row = (k.sw_ind + 1U < switches.size() && switches[k.sw_ind].row != switches[k.sw_ind + 1].row);
105 for (unsigned char i = dbh; i < dbh + 2 && i < NUM_DISTRO; ++i) {
106 if (k.ports_left[i] == 0)
109 unsigned cost = distance(switches[k.sw_ind], i);
114 k.distro_bound = std::max(i, db);
115 if (next_changes_row) {
116 k.distro_bound_hard = k.distro_bound;
119 cost += find_optimal_cost(k);
123 if (best == -1 || cost < best_cost) {
126 best_this_cost = distance(switches[k.sw_ind], i);
130 k.distro_bound_hard = dbh;
132 value v = { best, best_cost, best_this_cost };
142 std::map<unsigned, unsigned> cable_count;
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));
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));
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));
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));
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));
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;
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);
185 int last_row = 0, last_num = -1;
186 for (unsigned i = 0; i < switches.size(); ++i) {
188 bool next_changes_row = (k.sw_ind + 1U < switches.size() && switches[k.sw_ind].row != switches[k.sw_ind + 1].row);
190 if (cache.count(k) == 0) {
191 fprintf(stderr, "FATAL: no solutions!\n");
195 k.distro_bound = std::max(k.distro_bound, v.distro);
196 if (next_changes_row)
197 k.distro_bound_hard = k.distro_bound;
199 if (last_row != switches[k.sw_ind].row) {
203 for (int j = last_num; j + 1 < switches[k.sw_ind].num; ++j) {
208 printf("
\e[%um%u ", v.distro + 33, v.distro);
210 if (v.this_cost == FIFTYPLUSTEN)
212 else if (v.this_cost == THIRTYPLUSTEN)
214 else if (v.this_cost == TENPLUSTEN)
217 printf("(%-3u ) ", v.this_cost / 10);
218 cable_count[v.this_cost]++;
220 printf("(%3.1f) ", v.this_cost / 10.0);
223 last_row = switches[k.sw_ind].row;
224 last_num = switches[k.sw_ind].num;
227 --k.ports_left[v.distro];
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);