15 bool operator< (const try_order &other) const
17 return (cost < other.cost);
21 static unsigned best_so_far = UINT_MAX;
24 int distance_switch(unsigned from, unsigned to)
26 /* on the same side of the middle? 9.6m per switch. */
27 if ((from > 3) == (to > 3)) {
28 return abs(from - to) * 96;
31 /* have to cross the border? 25.8m from sw3->sw4 => 16.2m extra gap. */
32 /* that's _got_ to be wrong. say it's 3m. */
33 return abs(from - to) * 96 + 30;
36 int distance_middle(unsigned sw, unsigned middle)
38 /* symmetry: 4-5-6 are just mirrored 3-2-1. */
43 /* estimate 25.8m/2 = 12.9m from sw3 to the middle */
44 return 129 + (3 - sw) * 96;
47 /* more symmetry -- getting from 1-6 to the top is like getting from 6-1 to the bottom. */
53 /* guesstimate 4.8m extra to get to the bottom */
55 return 48 + 162 + (sw - 1) * 96;
57 return 48 + (sw - 1) * 96;
60 int distance_row(unsigned from, unsigned to)
62 /* don't calculate gaps here just yet, just estimate 4.1m per double row */
63 return 41 * abs(from - to);
66 int distance(int row_from, int switch_from, int side_from, int row_to, int switch_to, int side_to)
68 /* can we just walk directly? */
69 if (row_from == row_to && side_from == side_to) {
70 return distance_switch(switch_from, switch_to);
73 /* can we just switch sides? */
74 if (row_from + 1 == row_to && side_from == 1 && side_to == -1) {
75 return distance_switch(switch_from, switch_to);
77 if (row_from == row_to + 1 && side_from == -1 && side_to == 1) {
78 return distance_switch(switch_from, switch_to);
81 /* we'll need to go to one of the three middles */
82 int best1 = distance_middle(switch_from, 1) + distance_middle(switch_to, 1);
83 int best2 = distance_middle(switch_from, 2) + distance_middle(switch_to, 2);
84 int best3 = distance_middle(switch_from, 3) + distance_middle(switch_to, 3);
85 return std::min(std::min(best1, best2), best3) + distance_row(row_from, row_to);
88 int optimistic_distance(int row_from, int switch_from, int row_to, int switch_to)
90 if (abs(row_from - row_to) == 1)
91 return distance_switch(switch_from, switch_to);
93 return distance(row_from, switch_from, -1, row_to, switch_to, -1);
96 // extremely primitive O(V^2) prim
97 int prim_mst(std::vector<std::pair<unsigned, unsigned> > &points, try_order *temp, unsigned toi)
99 std::set<std::pair<unsigned, unsigned> > set1, set2;
101 for (unsigned i = 0; i < toi; ++i)
102 set1.insert(points[temp[i].o.pt]);
104 // pick the first one
105 std::set<std::pair<unsigned, unsigned> >::iterator start = set1.begin();
109 unsigned total_cost = 0;
110 while (set1.size() > 0) {
111 unsigned best_this_cost = UINT_MAX;
112 std::set<std::pair<unsigned, unsigned> >::iterator best_set1;
114 for (std::set<std::pair<unsigned, unsigned> >::iterator i = set1.begin(); i != set1.end(); ++i) {
115 for (std::set<std::pair<unsigned, unsigned> >::iterator j = set2.begin(); j != set2.end(); ++j) {
116 unsigned d = optimistic_distance(i->first, i->second, j->first, j->second);
117 if (d < best_this_cost) {
124 set2.insert(*best_set1);
125 set1.erase(best_set1);
126 total_cost += best_this_cost;
133 void print_tour(std::vector<std::pair<unsigned, unsigned> > &points)
135 for (unsigned i = 0; i < points.size(); ++i) {
136 if (best_tour[i].side == -1)
137 printf("%2u-%u (left side) ", points[best_tour[i].pt].first,
138 points[best_tour[i].pt].second);
140 printf("%2u-%u (right side) ", points[best_tour[i].pt].first,
141 points[best_tour[i].pt].second);
145 unsigned cost = distance(
146 points[best_tour[i-1].pt].first,
147 points[best_tour[i-1].pt].second,
149 points[best_tour[i].pt].first,
150 points[best_tour[i].pt].second,
152 printf("cost=%4u\n", cost);
157 unsigned do_tsp(std::vector<std::pair<unsigned, unsigned> > &points, order *ord, try_order *temp, unsigned ind, unsigned cost_so_far)
159 if (cost_so_far >= best_so_far)
161 if (ind == points.size()) {
162 memcpy(best_tour, ord, sizeof(order) * points.size());
163 printf("\nNew best tour found! cost=%u\n", cost_so_far);
165 best_so_far = cost_so_far;
170 * Simple heuristic: always search for the closest points from this one first; that
171 * will give us a sizable cutoff.
174 unsigned last_row = points[ord[ind-1].pt].first;
175 unsigned last_switch = points[ord[ind-1].pt].second;
176 unsigned last_side = ord[ind-1].side;
178 for (unsigned i = 0; i < points.size(); ++i) {
180 for (unsigned j = 0; j < ind; ++j) {
187 temp[toi].o.side = -1;
188 temp[toi].cost = distance(last_row, last_switch, last_side,
189 points[i].first, points[i].second, -1);
193 temp[toi].o.side = +1;
194 temp[toi].cost = distance(last_row, last_switch, last_side,
195 points[i].first, points[i].second, +1);
202 unsigned min_rest_cost = prim_mst(points, temp, toi);
203 if (cost_so_far + min_rest_cost >= best_so_far) {
207 std::sort(temp, temp + toi);
209 unsigned best_this_cost = UINT_MAX;
210 for (unsigned i = 0; i < toi; ++i)
212 ord[ind] = temp[i].o;
213 unsigned cost_rest = do_tsp(points, ord, temp + points.size() * 2, ind + 1, cost_so_far + temp[i].cost);
214 best_this_cost = std::min(best_this_cost, cost_rest);
217 return best_this_cost;
222 std::vector<std::pair<unsigned, unsigned> > points;
226 if (scanf("%u-%u", &row, &sw) != 2)
229 points.push_back(std::make_pair(row, sw));
232 order *ord = new order[points.size()];
233 best_tour = new order[points.size()];
234 try_order *temp = new try_order[points.size() * points.size() * 4];
236 /* always start at the first one, left side (hack) */
240 do_tsp(points, ord, temp, 1, 0);
241 printf("All done.\n");