13 static const unsigned num_cache_elem = (MAX_ROW * MAX_SWITCH * 2) * (MAX_ROW * MAX_SWITCH * 2);
14 static unsigned short dist_cache[(MAX_ROW * MAX_SWITCH * 2) * (MAX_ROW * MAX_SWITCH * 2)],
15 opt_dist_cache[MAX_ROW * MAX_SWITCH * MAX_ROW * MAX_SWITCH],
16 pess_dist_cache[MAX_ROW * MAX_SWITCH * MAX_ROW * MAX_SWITCH];
18 inline unsigned short &cache(
19 unsigned row_from, unsigned switch_from, unsigned side_from,
20 unsigned row_to, unsigned switch_to, unsigned side_to)
22 return dist_cache[(row_from * MAX_SWITCH * 2 + switch_from * 2 + side_from) * (MAX_ROW * MAX_SWITCH * 2) +
23 row_to * MAX_SWITCH * 2 + switch_to * 2 + side_to];
26 inline unsigned short &opt_cache(
27 unsigned row_from, unsigned switch_from,
28 unsigned row_to, unsigned switch_to)
30 return opt_dist_cache[(row_from * MAX_SWITCH + switch_from) * (MAX_ROW * MAX_SWITCH) +
31 row_to * MAX_SWITCH + switch_to];
34 inline unsigned short &pess_cache(
35 unsigned row_from, unsigned switch_from,
36 unsigned row_to, unsigned switch_to)
38 return pess_dist_cache[(row_from * MAX_SWITCH + switch_from) * (MAX_ROW * MAX_SWITCH) +
39 row_to * MAX_SWITCH + switch_to];
47 bool operator< (const order &other) const
49 return (cost < other.cost);
53 static unsigned best_so_far = UINT_MAX;
56 int distance_switch(unsigned from, unsigned to)
58 /* on the same side of the middle? 9.6m per switch. */
59 if ((from > 3) == (to > 3)) {
60 return abs(from - to) * 96;
63 /* have to cross the border? 25.8m from sw3->sw4 => 16.2m extra gap. */
64 /* that's _got_ to be wrong. say it's 3m. */
65 return abs(from - to) * 96 + 30;
68 int distance_middle(unsigned sw, unsigned middle)
70 /* symmetry: 4-5-6 are just mirrored 3-2-1. */
75 /* estimate 25.8m/2 = 12.9m from sw3 to the middle */
76 return 129 + (3 - sw) * 96;
79 /* more symmetry -- getting from 1-6 to the top is like getting from 6-1 to the bottom. */
85 /* guesstimate 4.8m extra to get to the bottom */
87 return 48 + 162 + (sw - 1) * 96;
89 return 48 + (sw - 1) * 96;
92 int distance_row(unsigned from, unsigned to)
94 /* 4.1m per double row, plus gaps */
95 unsigned base_cost = 41 * abs(from - to);
97 if ((from <= 9) != (to <= 9))
99 if ((from <= 17) != (to <= 17))
101 if ((from <= 25) != (to <= 25))
103 if ((from <= 34) != (to <= 34))
106 /* don't calculate gaps here just yet, just estimate 4.1m per double row */
110 int pessimistic_distance(int row_from, int switch_from, int row_to, int switch_to)
112 /* we'll need to go to one of the three middles */
113 int best2 = distance_middle(switch_from, 2) + distance_middle(switch_to, 2);
114 int distrow = distance_row(row_from, row_to);
115 if ((switch_from > 3) != (switch_to > 3))
116 return best2 + distrow;
117 if (switch_from > 3) {
118 int best3 = distance_middle(switch_from, 3) + distance_middle(switch_to, 3);
119 return std::min(best2, best3) + distrow;
121 int best1 = distance_middle(switch_from, 1) + distance_middle(switch_to, 1);
122 return std::min(best2, best1) + distrow;
126 int distance(int row_from, int switch_from, int side_from, int row_to, int switch_to, int side_to)
128 /* can we just walk directly? */
129 if (row_from == row_to && side_from == side_to) {
130 return distance_switch(switch_from, switch_to);
133 /* can we just switch sides? */
134 if (row_from + 1 == row_to && side_from == 1 && side_to == 0) {
135 return distance_switch(switch_from, switch_to) + distance_row(row_from, row_to) - 31;
137 if (row_from == row_to + 1 && side_from == 0 && side_to == 1) {
138 return distance_switch(switch_from, switch_to) + distance_row(row_from, row_to) - 31;
141 return pessimistic_distance(row_from, switch_from, row_to, switch_to);
144 int optimistic_distance(int row_from, int switch_from, int row_to, int switch_to)
146 if (row_from == row_to)
147 return distance_switch(switch_from, switch_to);
148 else if (abs(row_from - row_to) == 1)
149 return distance_switch(switch_from, switch_to) + distance_row(row_from, row_to) - 31;
151 return pessimistic_distance(row_from, switch_from, row_to, switch_to);
155 // this is, surprisingly enough, _slower_ than the naive variant below, so it's not enabled
156 struct prim_queue_val {
157 std::pair<unsigned, unsigned> dst;
160 bool operator< (const prim_queue_val &other) const
162 return (cost > other.cost);
166 // standard O(V^2 log v) prim
167 int prim_mst(std::set<std::pair<unsigned, unsigned> > &in)
169 std::set<std::pair<unsigned, unsigned> > set2;
170 std::priority_queue<prim_queue_val> queue;
172 // pick the first one
173 std::set<std::pair<unsigned, unsigned> >::iterator start = in.begin();
175 unsigned row = start->first;
176 unsigned num = start->second;
180 // find all the edges out from it
181 for (std::set<std::pair<unsigned, unsigned> >::iterator j = in.begin(); j != in.end(); ++j) {
185 unsigned d = opt_cache(row, num, j->first, j->second);
186 prim_queue_val val = { *j, d };
190 unsigned total_cost = 0;
191 while (set2.size() != in.size()) {
193 prim_queue_val val = queue.top();
196 // check if dst is already moved
197 if (set2.count(val.dst))
200 unsigned row = val.dst.first;
201 unsigned num = val.dst.second;
202 set2.insert(val.dst);
204 total_cost += val.cost;
206 // find all the edges from this new node
207 for (std::set<std::pair<unsigned, unsigned> >::iterator j = in.begin(); j != in.end(); ++j) {
211 unsigned d = opt_cache(row, num, j->first, j->second);
212 prim_queue_val val = { *j, d };
220 // extremely primitive O(V^3) prim
221 int prim_mst(std::set<std::pair<unsigned, unsigned> > &set1)
223 std::set<std::pair<unsigned, unsigned> > set2;
225 // pick the first one
226 std::set<std::pair<unsigned, unsigned> >::iterator start = set1.begin();
230 unsigned total_cost = 0;
231 while (set1.size() > 0) {
232 unsigned best_this_cost = UINT_MAX;
233 std::set<std::pair<unsigned, unsigned> >::iterator best_set1;
235 for (std::set<std::pair<unsigned, unsigned> >::iterator i = set1.begin(); i != set1.end(); ++i) {
236 for (std::set<std::pair<unsigned, unsigned> >::iterator j = set2.begin(); j != set2.end(); ++j) {
237 unsigned d = opt_cache(i->first, i->second, j->first, j->second);
238 if (d < best_this_cost) {
245 set2.insert(*best_set1);
246 set1.erase(best_set1);
247 total_cost += best_this_cost;
254 void print_tour(std::vector<std::pair<unsigned, unsigned> > &points)
256 std::set<std::pair<unsigned, unsigned> > points_left;
257 for (unsigned i = 0; i < points.size(); ++i) {
258 points_left.insert(points[i]);
261 for (unsigned i = 0; i < points.size(); ++i) {
262 if (best_tour[i].side == 0)
263 printf("%2u-%u (left side) ", best_tour[i].row, best_tour[i].num);
265 printf("%2u-%u (right side) ", best_tour[i].row, best_tour[i].num);
269 printf("cost=%4u ", best_tour[i].cost);
272 // let's see how good the MST heuristics are
273 if (i != points.size() - 1) {
274 std::set<std::pair<unsigned, unsigned> > mst_tree = points_left;
275 printf("mst_bound=%5u, ", prim_mst(mst_tree));
277 unsigned rest_cost = 0;
278 for (unsigned j = i + 1; j < points.size(); ++j) {
279 rest_cost += best_tour[j].cost;
282 printf("rest_cost=%5u", rest_cost);
287 std::set<std::pair<unsigned, unsigned> >::iterator j = points_left.find(std::make_pair(best_tour[i].row, best_tour[i].num));
288 points_left.erase(j);
292 unsigned do_tsp(std::vector<std::pair<unsigned, unsigned> > &points, std::set<std::pair<unsigned, unsigned> > &points_left, order *ord, order *temp, unsigned ind, unsigned cost_so_far)
294 if (cost_so_far >= best_so_far)
296 if (ind == points.size()) {
297 memcpy(best_tour, ord, sizeof(order) * points.size());
298 printf("\nNew best tour found! cost=%u\n", cost_so_far);
300 best_so_far = cost_so_far;
304 unsigned last_row = ord[ind-1].row;
305 unsigned last_switch = ord[ind-1].num;
306 unsigned last_side = ord[ind-1].side;
309 * The minimum spanning tree gives us a reliable lower bound for what we can
310 * achieve for the rest of the graph, so check it before doing anything else.
312 std::set<std::pair<unsigned, unsigned> > mst_set = points_left;
313 mst_set.insert(std::make_pair(last_row, last_switch));
315 unsigned min_rest_cost = prim_mst(mst_set);
316 if (cost_so_far + min_rest_cost >= best_so_far) {
321 * Simple heuristic: always search for the closest points from this one first; that
322 * will give us a sizable cutoff.
326 for (std::set<std::pair<unsigned, unsigned> >::iterator i = points_left.begin(); i != points_left.end(); ++i) {
328 temp[toi].row = i->first;
329 temp[toi].num = i->second;
331 temp[toi].cost = cache(last_row, last_switch, last_side, i->first, i->second, 0);
334 temp[toi].row = i->first;
335 temp[toi].num = i->second;
337 temp[toi].cost = cache(last_row, last_switch, last_side, i->first, i->second, 1);
340 std::sort(temp, temp + toi);
342 unsigned best_this_cost = UINT_MAX;
343 for (unsigned i = 0; i < toi; ++i)
347 std::set<std::pair<unsigned, unsigned> >::iterator j = points_left.find(std::make_pair(temp[i].row, temp[i].num));
348 points_left.erase(j);
349 unsigned cost_rest = do_tsp(points, points_left, ord, temp + points.size() * 2, ind + 1, cost_so_far + temp[i].cost);
350 points_left.insert(std::make_pair(temp[i].row, temp[i].num));
352 best_this_cost = std::min(best_this_cost, cost_rest);
355 return best_this_cost;
360 std::vector<std::pair<unsigned, unsigned> > points;
361 std::set<std::pair<unsigned, unsigned> > points_left;
365 if (scanf("%u-%u", &row, &sw) != 2)
368 if (row < MIN_ROW || row > MAX_ROW || sw < MIN_SWITCH || sw > MAX_SWITCH) {
369 fprintf(stderr, "%u-%u is out of bounds!\n", row, sw);
373 points.push_back(std::make_pair(row, sw));
374 if (points.size() != 1)
375 points_left.insert(std::make_pair(row, sw));
378 // precalculate all distances
379 for (unsigned i = 0; i < points.size(); ++i) {
380 for (unsigned j = 0; j < points.size(); ++j) {
381 cache(points[i].first, points[i].second, 0, points[j].first, points[j].second, 0) =
382 distance(points[i].first, points[i].second, 0, points[j].first, points[j].second, 0);
384 cache(points[i].first, points[i].second, 0, points[j].first, points[j].second, 1) =
385 distance(points[i].first, points[i].second, 0, points[j].first, points[j].second, 1);
387 cache(points[i].first, points[i].second, 1, points[j].first, points[j].second, 0) =
388 distance(points[i].first, points[i].second, 1, points[j].first, points[j].second, 0);
390 cache(points[i].first, points[i].second, 1, points[j].first, points[j].second, 1) =
391 distance(points[i].first, points[i].second, 1, points[j].first, points[j].second, 1);
393 opt_cache(points[i].first, points[i].second, points[j].first, points[j].second) =
394 optimistic_distance(points[i].first, points[i].second, points[j].first, points[j].second);
396 pess_cache(points[i].first, points[i].second, points[j].first, points[j].second) =
397 pessimistic_distance(points[i].first, points[i].second, points[j].first, points[j].second);
401 order *ord = new order[points.size()];
402 best_tour = new order[points.size()];
403 order *temp = new order[points.size() * points.size() * 4];
405 /* always start at the first one, left side (hack) */
406 ord[0].row = points[0].first;
407 ord[0].num = points[0].second;
410 do_tsp(points, points_left, ord, temp, 1, 0);
411 printf("All done.\n");