Festival Charging Carts
A music festival runs a few phone-charging carts. Each evening the organisers look at where people stood (from wristband pings) and move the carts. Their routine: every person is served by whichever cart is closest; then each cart is rolled to the average position of the people it served. With the carts in new places, some people now have a different closest cart, so they repeat, until nobody switches carts or they run out of time.
That routine is k-means, the classic way to find groups in data nobody has labelled. It is used to group similar documents by their embeddings, to compress colours in images, and to split a large vector-search index into regions so a query only searches the nearest few.
Your task
Write placeCarts(people, carts, maxRounds). people[i] and carts[j] are positions with the same number of coordinates. Repeat for at most maxRounds rounds:
- Assign. Give every person to the nearest cart by straight-line distance, using the cart positions from the start of this round. If two carts are equally near, pick the lower cart index.
- Check. If every person has the same cart as in the previous round's assignment, stop now. In round 1 there is no previous assignment, so always go on to Move.
- Move. Move each cart to the average of its people's positions (each coordinate averaged separately). A cart with nobody assigned stays where it is.
Return the final cart positions, in the original cart order.
placeCarts(people: float[][], carts: float[][], maxRounds: int) → float[][] Numbers are accepted within 1e-6.
Examples
people = [[0, 0], [0, 2], [10, 0], [10, 2]] carts = [[0, 1], [1, 1]] maxRounds = 10
[[0, 1], [10, 1]]
Round 1: (0, 0) and (0, 2) are nearer cart 0; (10, 0) and (10, 2) are nearer cart 1. Cart 0 moves to the average of its two people, (0, 1). Cart 1 moves to (10, 1). Round 2: everyone keeps the same cart, so stop. Answer [[0, 1], [10, 1]].
people = [[0], [2], [4], [10]] carts = [[1], [3]] maxRounds = 1
[[1], [7]]
Only 1 round is allowed. Carts start at 1 and 3. The person at 0 is nearer cart 0. The person at 2 is 1 away from both carts, so the tie goes to cart 0. The people at 4 and 10 are nearer cart 1. Cart 0 moves to (0 + 2) / 2 = 1, cart 1 to (4 + 10) / 2 = 7. Answer [[1], [7]].
people = [[1, 1], [2, 2]] carts = [[0, 0], [50, 50]] maxRounds = 5
[[1.5, 1.5], [50, 50]]
Cart 1 is far from everyone and never gets a person, so it stays at (50, 50). Cart 0 moves to (1.5, 1.5) in round 1, and round 2 changes nothing.
Constraints
- 1 ≤ people.length ≤ 1,000
- 1 ≤ carts.length ≤ 20
- 1 ≤ number of coordinates ≤ 5
- -1,000 ≤ each coordinate ≤ 1,000
- 1 ≤ maxRounds ≤ 100
- Answers within 0.000001 of the expected values are accepted.
Start with brute force
The "perfect" answer would be the grouping of people into carts that makes the total squared distance smallest. Finding it by trying every grouping means k^n options: with 20 carts and 1,000 people that number has over 1,300 digits.
k-means does not search all groupings. Each round can only lower (or keep) the total squared distance, so it settles quickly, usually at a good answer, though not always the best one. Each round costs O(n · k · d) for n people, k carts and d coordinates.
Hints
0 of 4 shown- Hint 1
Run the first example by hand for one round. Where does each cart end up? Now imagine moving cart 0 the moment its first person is assigned. Would the next person still see the same carts?
- Hint 2
Each round has two separate phases. First decide everybody's cart using the positions from the start of the round. Only then move the carts. Keep the assignment in its own list.
- Hint 3
Moving a cart needs, for each cart, a running sum of coordinates and a count of people. A cart whose count is 0 has no average, so leave it where it is.
- Hint 4
Loop up to
maxRoundstimes: build the assignment list (nearest cart, lower index on ties, compare squared distances); if it equals the previous round's list, stop; otherwise sum and count per cart, divide, and remember this assignment for the next round.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
k-means alternates two simple steps. Holding the carts still, each person picks the nearest cart. Holding those choices still, each cart moves to the middle of its people. Neither step can make the total squared distance worse, so the process settles.
Trace the first example: people (0, 0), (0, 2), (10, 0), (10, 2); carts at (0, 1) and (1, 1).
- Round 1, assign: (0, 0) is 1 from cart 0 and √2 from cart 1, so cart 0. (0, 2) likewise cart 0. (10, 0) and (10, 2) are nearer cart 1. Assignment [0, 0, 1, 1]. There is no previous round, so continue.
- Round 1, move: cart 0 to the mean of (0, 0) and (0, 2), which is (0, 1). Cart 1 to the mean of (10, 0) and (10, 2), which is (10, 1).
- Round 2, assign: still [0, 0, 1, 1]. Same as last round, so stop.
Two details trip people up. Do not move a cart while you are still assigning people, or later people see a cart that is half way through moving. And never divide by a zero count: a cart that attracted nobody simply keeps its position.
function placeCarts(people, carts, maxRounds) {
const nearest = (p, centers) => {
let best = 0, bestDist = Infinity;
centers.forEach((c, j) => {
let dist = 0;
for (let d = 0; d < p.length; d++) dist += (p[d] - c[d]) * (p[d] - c[d]);
if (dist < bestDist) { best = j; bestDist = dist; } // strict: ties keep the lower index
});
return best;
};
let centers = carts.map((c) => c.slice());
let previous = null;
for (let round = 0; round < maxRounds; round++) {
// 1. Assign everyone using the current positions. Nobody moves yet.
const owner = people.map((p) => nearest(p, centers));
if (previous && owner.every((o, i) => o === previous[i])) break; // stable
// 2. Move each cart to the mean of its people. An empty cart stays put.
const sums = centers.map((c) => c.map(() => 0));
const counts = centers.map(() => 0);
people.forEach((p, i) => {
counts[owner[i]]++;
p.forEach((v, d) => { sums[owner[i]][d] += v; });
});
centers = centers.map((c, j) => (counts[j] ? sums[j].map((s) => s / counts[j]) : c));
previous = owner;
}
return centers;
}def place_carts(people, carts, max_rounds):
def nearest(p, centers):
best, best_dist = 0, float('inf')
for j, c in enumerate(centers):
dist = 0.0
for a, b in zip(p, c):
dist += (a - b) * (a - b)
if dist < best_dist: # strict: ties keep the lower index
best, best_dist = j, dist
return best
centers = [list(c) for c in carts]
previous = None
for _ in range(max_rounds):
# 1. Assign everyone using the current positions. Nobody moves yet.
owner = [nearest(p, centers) for p in people]
if owner == previous:
break # stable: nothing would move
# 2. Move each cart to the mean of its people. An empty cart stays put.
dims = len(carts[0])
sums = [[0.0] * dims for _ in centers]
counts = [0] * len(centers)
for p, o in zip(people, owner):
counts[o] += 1
for d, v in enumerate(p):
sums[o][d] += v
centers = [[s / counts[j] for s in sums[j]] if counts[j] else centers[j]
for j in range(len(centers))]
previous = owner
return centersRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.