Task 3 of 6

Reading the Seam Back Out

The cost map now knows the price of every seam: cost[71][x] is what the cheapest seam ending at column x costs. What it does not contain is the seam. To get that you start at the cheapest cell of the bottom row and walk upwards, at each step moving to the cheapest of the (at most) three cells you could have come from.

Here is the part worth saying out loud: this walk does not go on the GPU. It is 72 steps, each of which reads three numbers and picks one, and each step needs the answer to the one before it. A kernel launch costs more than the whole walk does. Knowing which part of an algorithm to leave on the host is not a compromise — it is the skill. (The same is true of the traceback in Wavefronts: Aligning DNA on the Diagonal: the expensive half is parallel, the cheap half is a loop.)

The picture also has flat regions, and flat regions have ties. There is usually more than one cheapest seam; any of them is a correct answer, and the tests below check that the seam you produce is optimal, not that it is one particular optimum.

the cost map holds the price; the path has to be walked back out of it — A six by four grid of cumulative costs. The cheapest cell of the bottom row, holding eight, is the start; from it a path is traced upwards, each step taking the cheapest of the three cells above, until it reaches the top row.

Goal: write backtrack(cost) so it returns one column index per row, top to bottom, tracing the cheapest seam — then plot it.

Requirements

Start at the column of the smallest value in the LAST row of cost
Walking up, from column x in row y + 1 the seam can only have come from x - 1, x or x + 1 in row y — take the cheapest that exists
Return an array of cost.length column indices, one per row
plot(seam, …) — it draws the path, and it is how the tests read your answer

Hint 1 — where the walk starts

The bottom row holds the finished prices, so the cheapest seam is the one that ends at its smallest entry:

let x = 0;
for (let i = 1; i < w; i++) if (cost[h - 1][i] < cost[h - 1][x]) x = i;

Hint 2 — the step upwards

Exactly the mirror of the recurrence that built the map — the same window of three, the same two guards:

let best = x;
if (x > 0 && cost[y][x - 1] < cost[y][best]) best = x - 1;
if (x + 1 < w && cost[y][x + 1] < cost[y][best]) best = x + 1;
x = best;

Only cells within one column of where you already are — that is what makes the result a connected seam rather than 72 unrelated minima.

Hint 3 — direction

The loop runs for (let y = h - 2; y >= 0; y--). Walking the other way looks plausible and is wrong: the cumulative map was built downwards, so only the bottom row holds finished prices. Row 0's numbers are raw energies.

Same idea elsewhere

Every dynamic program ends this way: a parallel fill and a serial traceback. CUDA DP kernels return the score matrix and walk it on the host; production Smith–Waterman implementations do the same, and even hand back only the score when the alignment is not needed. The lesson generalises past DP — if a step is O(n) with a serial dependency and the fill was O(n²) in parallel, the launch overhead alone decides where it belongs.

All tasks in Seam Carving: Content-Aware Resizing

This page is an interactive exercise — the editor, the GPU runner and your saved progress need JavaScript. The text above is the full brief.