Directional Tiles: Find a Valid Reconfiguration Path
Duolingo● MediumINTERNPHONE SCREENProblem statement
A one-dimensional board contains red tiles R, black tiles B, and empty positions _.
- A red tile may move only to the right.
- A black tile may move only to the left.
- A tile may move one position into an adjacent empty position.
- A tile may instead jump over exactly one tile of the other color and land in the empty position immediately beyond it.
Given start and end, return a valid sequence of board states that transforms start into end. Include both endpoint states. The path does not need to be globally shortest.
For deterministic judging, perform depth-first search with a visited-state set. At each state, inspect tile positions from left to right; for a tile, consider its one-step move before its two-step jump. Return the first path found by that search. If no path exists, return an empty array.
Function
findTilePath(start: String[], end: String[]) → String[][]Examples
Example 1
start = ["R","_","B","B"]end = ["B","_","B","R"]return = [["R","_","B","B"],["_","R","B","B"],["B","R","_","B"],["B","R","B","_"],["B","_","B","R"]]The returned states are exactly the source example. Each transition is either a legal one-step move or a legal jump over one opposite-color tile.
Example 2
start = ["R","R","_"]end = ["_","R","R"]return = [["R","R","_"],["R","_","R"],["_","R","R"]]The rightmost red tile moves first, then the remaining red tile moves into the empty position.
Constraints
1 <= start.length == end.length <= 12.- Every entry is
R,B, or_. startandendcontain the same number of red tiles, black tiles, and empty positions.- The returned path follows the deterministic search order stated above.