The problem
Stations stand at the given points of a city laid out in square blocks. A line between two stations costs their Manhattan distance, abs(x1 - x2) + abs(y1 - y2): the blocks you walk along streets. Any two stations may be joined. Return the least total cost of lines that join every station to every other.
connect_points([(0, 0), (2, 2), (3, 10), (5, 2), (7, 0)])
# 20
connect_points([(5, -5)])
# 0
Coordinates are whole numbers. Two stations may stand at the same point.
Limits
- Up to 2,000 points, so up to 1,999,000 possible lines.
- Making and sorting every possible line is too slow. The big tests have 3 seconds each.
Builds on SPAN-3 Prim.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
8 tests, not run yet
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | The example | Not run | |
| 2 | One point | Not run | |
| 3 | Two points | Not run | |
| 4 | The same place twice | Not run | |
| 5 | In a row | Not run | |
| 6 | 300 points | Not run | |
| 7 | 2,000 points | Not run | |
| 8 | 2,000 points, many ties | Not run |