A courier leaves the depot, visits every drop-off point exactly once and returns to where they
started. Write plan_route(cities) that returns the order of the visits as a list of city indices
(every index from 0 to n - 1 exactly once). The route is closed: after the last city the
courier drives back to the first.
cities is a list of (x, y) points on a 1000 × 1000 map. The tests build their maps with
city_map(n, seed), and tour_length(cities, tour) measures a route. Both are available in your
code, so you can try them with Run.
How this problem is scored
There is no single right answer. A route passes if it is valid and no longer than the route you get by always driving to the nearest unvisited city, starting at city 0. Its quality (0 to 100) says how much of the gap between that simple route and the best route we know you close: 0 matches the simple route, 100 matches (or beats) the best known one. Match the reference solution's quality (the par in the header) for the third star.
Examples
Input: cities = city_map(8, 1)
Output: a list such as [0, 5, 2, 7, 4, 1, 6, 3]
any order of 0..7 that is no longer than the nearest-city route passes
Constraints
8 <= len(cities) <= 120- Each test must finish in well under a second in your browser. Limit your loops by a number of rounds, not by the clock, so the result is the same on every run.
Goals
- Build a complete tour greedily
- Improve a tour with local moves until none helps
- Measure a heuristic against a baseline and a best-known value