MiddleCodeOccasionalNot answered yet
Shorten an L/R/U/D path by cutting out closed sub-loops
A path is a list of unit moves: L, R, U, D. Remove any closed sub-loop — a stretch of moves that returns to a coordinate already visited — so the result follows the same realised route but with redundant loops cut.
Requirements:
- Preserve the route, not just the net displacement:
[D,R,U]stays[D,R,U]. [R,D,L,U,R]becomes[R](the middle four return to start).
std::vector<char> shorten(const std::vector<char>& moves) {
// your code here
}Write the implementation.
Walk the moves tracking the current (x, y) coordinate and a hash map of each visited coordinate to its output-path position. When a coordinate repeats, the moves since its first visit form a closed loop: truncate the output back to that position and drop the coordinates added in between.
- ✗Reducing to net displacement, which discards the realised route shape
- ✗Only cancelling adjacent reversals, missing larger loops like R,D,L,U
- ✗Forgetting to seed the start coordinate at output index 0
- →Why does net displacement give the wrong answer for
[D,R,U]? - →How do you erase the in-between coordinates from the map when truncating?
Contents
Task
Remove closed sub-loops from an L/R/U/D path, keeping the realised route. In O(n).
Solution
#include <vector>
#include <unordered_map>
#include <cstdint>
std::vector<char> shorten(const std::vector<char>& moves) {
auto key = [](int x, int y){ return (int64_t(x) << 32) ^ uint32_t(y); };
std::unordered_map<int64_t, int> seen; // coordinate → index in out
std::vector<char> out;
int x = 0, y = 0;
seen[key(0, 0)] = 0; // start
for (char m : moves) {
if (m == 'L') --x; else if (m == 'R') ++x;
else if (m == 'U') ++y; else --y;
auto it = seen.find(key(x, y));
if (it != seen.end()) { // coordinate repeated → loop
seen.clear(); int cx = 0, cy = 0; // rebuild map from out
seen[key(0, 0)] = 0;
out.resize(it->second); // truncate to the repeat
for (int i = 0; i < (int)out.size(); ++i) {
char c = out[i];
if (c=='L') --cx; else if (c=='R') ++cx; else if (c=='U') ++cy; else --cy;
seen[key(cx, cy)] = i + 1;
}
x = cx; y = cy;
} else { out.push_back(m); seen[key(x, y)] = (int)out.size(); }
}
return out;
}Key points
- A coordinate-to-index hash map finds the repeat and the truncation point.
- Keep the realised route, not the net displacement.
- Cancelling only adjacent reversals is not enough for larger loops.
Contents
