# Reading the Seam Back Out

*Task 3 of 6 · [Seam Carving: Content-Aware Resizing](https://gpu.rocks/learn/seam-carving-a23a0d9b.md) · GPU.js Learn*

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.

## Figures

- **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

**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:

```js
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:

```js
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.

## Starter code

```js
// The cost map knows the price. The seam has to be read back out of it —
// on the host, because 72 dependent steps is not a job for a kernel.

function backtrack(cost) {
  const h = cost.length;
  const w = cost[0].length;
  const seam = new Array(h).fill(0);

  // TODO 1: find the column of the cheapest cell in the LAST row of cost,
  //         and record it as this seam's bottom end.
  let x = 0;
  seam[h - 1] = x;

  // TODO 2: walk upwards, row by row. From column x you could only have come
  //         from x - 1, x or x + 1 in the row above — take the cheapest of
  //         those that exist, and record it in seam[y].

  return seam;
}

const seam = backtrack(cost);

// The plot IS the seam: column against row, wandering down the picture.
plot(seam, { title: 'the cheapest seam: column by row', xLabel: 'row' });
console.log('ends at column', seam[seam.length - 1],
  '· total energy', cost[cost.length - 1][seam[seam.length - 1]]);
```

---

Interactive version: https://gpu.rocks/learn/seam-carving-a23a0d9b/3

[Previous task](https://gpu.rocks/learn/seam-carving-a23a0d9b/2.md) · [Next task](https://gpu.rocks/learn/seam-carving-a23a0d9b/4.md)