XL Web

← All challenges

Grid Min Path Sum with Path Tracking

Grid / Path ★★★☆

Same as Grid Min Path Sum, but the formula must also reconstruct the route taken — return the minimum sum AND the cell sequence that produced it.

A1:E5 is a 5×5 cost grid. Starting at A1, moving only right or down, find the minimum-sum path to E5 — but also produce the sequence of cells that path visits.

Output a single string in the format <sum>:<r1-c1>>...><r5-c5>, where each r-c is the 1-indexed row-column of a visited cell.

For example, if the optimal path were just the top row then the right column, the output for an all-1s grid would be 9:1-1>1-2>1-3>1-4>1-5>2-5>3-5>4-5>5-5.

Tie-break: when two child paths yield the same sum, prefer the one going down (matches the formula).

This is the same problem as Grid Min Path Sum, but now the recursion must carry two pieces of state — running total and running path string — so the parent can compare children on one component while keeping both. That’s the compound-return pattern: HSTACK(sum, path) flowing through every call.

Input

Range A1:E5

ABCDE
1 79923
2 74514
3 21239
4 57766
5 26532
Hint

Compound return: each recursive call returns HSTACK(running_total, running_path). At the goal, return the {sum, path} pair as-is. At branch points, recurse both ways and pick the branch whose first component (sum) is smaller — keep both fields. Tie-break: prefer DOWN.

Solution 
=LET(
  tbl, A1:E5,
  ros, ROWS(tbl),
  cols, COLUMNS(tbl),
  big, MAX(tbl)*ros*cols,
  fx, LAMBDA(me, ro, co, total, path,
    IF(OR(ro>ros, co>cols),
      HSTACK(big, "X"),
      LET(
        key, ro & "-" & co,
        cur, INDEX(tbl, ro, co),
        new_total, total + cur,
        new_path, IF(path="", key, path & ">" & key),
        IF(AND(ro=ros, co=cols),
          HSTACK(new_total, new_path),
          LET(
            down, me(me, ro+1, co, new_total, new_path),
            right, me(me, ro, co+1, new_total, new_path),
            d_sum, INDEX(down,,1),
            r_sum, INDEX(right,,1),
            IF(d_sum <= r_sum, down, right)
          )
        )
      )
    )
  ),
  result, fx(fx, 1, 1, 0, ""),
  INDEX(result,,1) & ":" & INDEX(result,,2)
)