Remove loops from a walk
J, 51 39 bytes
([,~i.~{.])/@|.&.([:+/\0,0j1^'ULDR'&i.)
Try it online!
-12 bytes thanks to Bubbler! For the idea of combining "Under"s into a single train, and skipping an unnecessary increment of the indexes
The idea
- Convert the letters to their indexes within the
ULDR
Convert those indexes to complex vectors: Think
U = i
,L = -1
,D = -i
R = 1
In fact, because of rotational symmetry, we don't actually care which direction is "up" as long the relative order of the directions is preserved.
- Scan sum those vectors to get the path positions (still as complex numbers)
- Reduce the path into a loop free version: Any time we arrive at a point we've seen, remove all history up to and including that old point.
- Invert steps 1 to 3, in reverse order.
The fun thing is that step 5 is accomplished with J's Under conjunction, which allows you to perform a transformation, do stuff, and then have the inverse transformation automatically applied. Here, J is smart enough to know how to invert the entire train comprising steps 1 through 3 in reverse order:
Elementwise
reduce to Scan sum index within
remove loops of... 'ULDR'
| | |
vvvvvvvvvvvvv vvvvv vvvvvvvv
([,~i.~{.])/@|.&.([:+/\0,0j1^'ULDR'&i.)
^^ ^^^^^^
| |
Under 0 prepended to
i raised to...
Jelly, 20 bytes
O2ȷ:ı*S
ẆÇÐḟḢ⁸œṣFµÐL
Try it online! Or see the test-suite.
How?
O2ȷ:ı*S - Link 1, distance travelled: list of UDLR characters
O - ordinals -> U:85 D:68 L:76 R:82
2ȷ - 2000
: - integer division -> U:23 D:29 L:26 R:24 (Note mod 4 these are 3 1 2 0)
ı - square root of -1 - i.e. (0+1j)
* - exponentiate -> U:(0-1j) D:(0+1j) L:(-1+0j) R:(1+0j)
S - sum - 0 iff the path is a loop
ẆÇÐḟḢ⁸œṣFµÐL - Main Link: list of UDLR characters
µÐL - loop until no change occurs:
Ẇ - all sublists
Ðḟ - filter discard those which are truthy (non-zero) under:
Ç - call last Link (1) as a monad
Ḣ - head - X = first, shortest loop (if none this yields 0)
⁸ - chain's left argument
œṣ - split at sublists equal to X
F - flatten
JavaScript (Node.js), 101 ... 91 90 bytes
f=s=>s&&[s[Buffer(s).every(c=>p+=[w=s.length,~!++i,1,-w][c%5],i=p=0)-1]]+f(s.slice(p?1:i))
Try it online!
How?
Method
For each index \$n\$ in the input string, we initialize our position to \$(0,0)\$ and run a simulation of the walk starting from the \$n\$-th character. If there's some move at \$n+i-1,i>0\$ that brings us back to \$(0,0)\$, it means that we have identified a loop: we skip the entire segment and restart at \$n+i\$.
n n+i-1
v v
...LLURRD...
^
n+i
Otherwise, we append the current move to the output (L in the above example) and advance to \$n+1\$.
Implementation
Instead of relying on an explicit counter \$n\$, we use recursive calls to our main function where the leading characters of the input string are gradually removed.
Instead of using a pair \$(x,y)\$ to keep track of our position, we actually use a scalar value \$p=x+y\cdot w\$, where \$w\$ is the remaining number of characters in the string. This is safe because we can't have more than \$w\$ moves in the same direction from this point.
To convert a character move into a direction, we take its ASCII code modulo \$5\$. The ASCII codes of \$(D,L,R,U)\$ are \$(68,76,82,85)\$, which are conveniently turned into \$(3,1,2,0)\$.
Commented
f = s => // f is a recursive function taking a string s
s && // if s is empty, stop recursion
[ // wrapper to turn undefined into an empty string:
s[ // get either s[0] (next char.) or s[-1] (undefined):
Buffer(s).every(c => // for each ASCII code c in s:
p += [ // add to p:
w = s.length, // +s.length for up ('U' -> 85 -> 85 % 5 = 0)
~!++i, // -1 for left ('L' -> 76 -> 76 % 5 = 1)
// (increment i)
1, // +1 for right ('R' -> 82 -> 82 % 5 = 2)
-w // -s.length for down ('D' -> 68 -> 68 % 5 = 3)
][c % 5], // using c modulo 5
// stop if p = 0, meaning that we're back to our
// starting point
i = p = 0 // start with i = p = 0
) - 1 // end of every(), subtract 1
] // end of s[] lookup
] + // end of wrapper
f( // recursive call with either:
s.slice(p ? 1 : i) // s.slice(1) (no loop)
) // or s.slice(i) (skipping the loop)