12 bool operator< (const order &other) const
14 return (cost < other.cost);
18 static unsigned best_so_far = UINT_MAX;
21 int distance_switch(unsigned from, unsigned to)
23 /* on the same side of the middle? 9.6m per switch. */
24 if ((from > 3) == (to > 3)) {
25 return abs(from - to) * 96;
28 /* have to cross the border? 25.8m from sw3->sw4 => 16.2m extra gap. */
29 /* that's _got_ to be wrong. say it's 3m. */
30 return abs(from - to) * 96 + 30;
33 int distance_middle(unsigned sw, unsigned middle)
35 /* symmetry: 4-5-6 are just mirrored 3-2-1. */
40 /* estimate 25.8m/2 = 12.9m from sw3 to the middle */
41 return 129 + (3 - sw) * 96;
44 /* more symmetry -- getting from 1-6 to the top is like getting from 6-1 to the bottom. */
50 /* guesstimate 4.8m extra to get to the bottom */
52 return 48 + 162 + (sw - 1) * 96;
54 return 48 + (sw - 1) * 96;
57 int distance_row(unsigned from, unsigned to)
59 /* don't calculate gaps here just yet, just estimate 4.1m per double row */
60 return 41 * abs(from - to);
63 int distance(int row_from, int switch_from, int side_from, int row_to, int switch_to, int side_to)
65 /* can we just walk directly? */
66 if (row_from == row_to && side_from == side_to) {
67 return distance_switch(switch_from, switch_to);
70 /* can we just switch sides? */
71 if (row_from + 1 == row_to && side_from == 1 && side_to == 0) {
72 return distance_switch(switch_from, switch_to);
74 if (row_from == row_to + 1 && side_from == 0 && side_to == 1) {
75 return distance_switch(switch_from, switch_to);
78 /* we'll need to go to one of the three middles */
79 int best2 = distance_middle(switch_from, 2) + distance_middle(switch_to, 2);
80 int distrow = distance_row(row_from, row_to);
81 if ((switch_from > 3) != (switch_to > 3))
82 return best2 + distrow;
83 if (switch_from > 3) {
84 int best3 = distance_middle(switch_from, 3) + distance_middle(switch_to, 3);
85 return std::min(best2, best3) + distrow;
87 int best1 = distance_middle(switch_from, 1) + distance_middle(switch_to, 1);
88 return std::min(best2, best1) + distrow;
92 int optimistic_distance(int row_from, int switch_from, int row_to, int switch_to)
94 if (abs(row_from - row_to) == 1)
95 return distance_switch(switch_from, switch_to);
97 return distance(row_from, switch_from, 0, row_to, switch_to, 0);
100 // extremely primitive O(V^2) prim
101 int prim_mst(std::set<std::pair<unsigned, unsigned> > &set1)
103 std::set<std::pair<unsigned, unsigned> > set2;
105 // pick the first one
106 std::set<std::pair<unsigned, unsigned> >::iterator start = set1.begin();
110 unsigned total_cost = 0;
111 while (set1.size() > 0) {
112 unsigned best_this_cost = UINT_MAX;
113 std::set<std::pair<unsigned, unsigned> >::iterator best_set1;
115 for (std::set<std::pair<unsigned, unsigned> >::iterator i = set1.begin(); i != set1.end(); ++i) {
116 for (std::set<std::pair<unsigned, unsigned> >::iterator j = set2.begin(); j != set2.end(); ++j) {
117 unsigned d = optimistic_distance(i->first, i->second, j->first, j->second);
118 if (d < best_this_cost) {
125 set2.insert(*best_set1);
126 set1.erase(best_set1);
127 total_cost += best_this_cost;
134 void print_tour(std::vector<std::pair<unsigned, unsigned> > &points)
136 std::set<std::pair<unsigned, unsigned> > points_left;
137 for (unsigned i = 0; i < points.size(); ++i) {
138 points_left.insert(points[i]);
141 for (unsigned i = 0; i < points.size(); ++i) {
142 if (best_tour[i].side == 0)
143 printf("%2u-%u (left side) ", best_tour[i].row, best_tour[i].num);
145 printf("%2u-%u (right side) ", best_tour[i].row, best_tour[i].num);
149 printf("cost=%4u ", best_tour[i].cost);
152 // let's see how good the MST heuristics are
153 if (i != points.size() - 1) {
154 std::set<std::pair<unsigned, unsigned> > mst_tree = points_left;
155 printf("mst_bound=%5u, ", prim_mst(mst_tree));
157 unsigned rest_cost = 0;
158 for (unsigned j = i + 1; j < points.size(); ++j) {
159 rest_cost += best_tour[j].cost;
162 printf("rest_cost=%5u", rest_cost);
167 std::set<std::pair<unsigned, unsigned> >::iterator j = points_left.find(std::make_pair(best_tour[i].row, best_tour[i].num));
168 points_left.erase(j);
172 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)
174 if (cost_so_far >= best_so_far)
176 if (ind == points.size()) {
177 memcpy(best_tour, ord, sizeof(order) * points.size());
178 printf("\nNew best tour found! cost=%u\n", cost_so_far);
180 best_so_far = cost_so_far;
185 * Simple heuristic: always search for the closest points from this one first; that
186 * will give us a sizable cutoff.
189 unsigned last_row = ord[ind-1].row;
190 unsigned last_switch = ord[ind-1].num;
191 unsigned last_side = ord[ind-1].side;
193 std::set<std::pair<unsigned, unsigned> > mst_set = points_left;
194 mst_set.insert(std::make_pair(last_row, last_switch));
196 for (std::set<std::pair<unsigned, unsigned> >::iterator i = points_left.begin(); i != points_left.end(); ++i) {
198 temp[toi].row = i->first;
199 temp[toi].num = i->second;
201 temp[toi].cost = distance(last_row, last_switch, last_side, i->first, i->second, 0);
204 temp[toi].row = i->first;
205 temp[toi].num = i->second;
207 temp[toi].cost = distance(last_row, last_switch, last_side, i->first, i->second, 1);
211 unsigned min_rest_cost = prim_mst(mst_set);
212 if (cost_so_far + min_rest_cost >= best_so_far) {
216 std::sort(temp, temp + toi);
218 unsigned best_this_cost = UINT_MAX;
219 for (unsigned i = 0; i < toi; ++i)
223 std::set<std::pair<unsigned, unsigned> >::iterator j = points_left.find(std::make_pair(temp[i].row, temp[i].num));
224 points_left.erase(j);
225 unsigned cost_rest = do_tsp(points, points_left, ord, temp + points.size() * 2, ind + 1, cost_so_far + temp[i].cost);
226 points_left.insert(std::make_pair(temp[i].row, temp[i].num));
228 best_this_cost = std::min(best_this_cost, cost_rest);
231 return best_this_cost;
236 std::vector<std::pair<unsigned, unsigned> > points;
237 std::set<std::pair<unsigned, unsigned> > points_left;
241 if (scanf("%u-%u", &row, &sw) != 2)
244 points.push_back(std::make_pair(row, sw));
245 if (points.size() != 1)
246 points_left.insert(std::make_pair(row, sw));
249 order *ord = new order[points.size()];
250 best_tour = new order[points.size()];
251 order *temp = new order[points.size() * points.size() * 4];
253 /* always start at the first one, left side (hack) */
254 ord[0].row = points[0].first;
255 ord[0].num = points[0].second;
258 do_tsp(points, points_left, ord, temp, 1, 0);
259 printf("All done.\n");