A factory has n workshops and n free spots on a grid of floor cells. Trolleys run between
workshops all day: flow[a][b] (equal to flow[b][a]) is the number of trips per day between
workshops a and b. spots[s] is the (row, col) cell of spot s, and a trolley drives along
the aisles, so the distance between two spots is |row1 - row2| + |col1 - col2|.
Write arrange_workshops(flow, spots) that returns a list place where place[a] is the spot of
workshop a (every spot used exactly once), making the total trolley distance as small as you
can: the sum over all pairs a < b of flow[a][b] times the distance between their spots.
The tests build their plants with plant_layout(rows, cols, seed), which returns (flow, spots)
for rows * cols workshops, and layout_cost(flow, spots, place) computes the total. Both are
available in your code, so you can try them with Run.
How this problem is scored
A layout passes if it is valid and costs no more than this layout built one workshop at a time: put the workshop with the most trips in total on the most central spot (the smallest sum of distances to all spots); then repeatedly take the unplaced workshop with the most trips to the workshops already placed (ties: more trips in total, then the smaller index) and put it on the free spot that adds the least cost with them (ties: the smaller spot). Its quality (0 to 100) says how much of the gap between that layout and the best one we know you close: 0 matches it, 100 matches (or beats) the best known layout.
Examples
Input: flow = [[0, 5, 0, 0], [5, 0, 5, 0], [0, 5, 0, 5], [0, 0, 5, 0]]
spots = [(0, 0), (0, 1), (1, 0), (1, 1)]
Output: a list such as [2, 0, 1, 3]
Explanation: workshops 0-1, 1-2 and 2-3 exchange trolleys, and each of these pairs sits on
neighbouring cells, so the cost is 5 + 5 + 5 = 15.
Input: flow, spots = plant_layout(4, 5, 2)
Output: any valid layout of the 20 workshops costing no more than the one-at-a-time layout
Constraints
4 <= n <= 56,0 <= flow[a][b] <= 9,flow[a][a] = 0- 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 an assignment greedily, one element at a time
- Evaluate a swap in O(n) instead of recomputing the whole cost
- Escape a local optimum with small random kicks followed by more climbing