# Remove loops from a walk

I've been playing around with a robot on the coordinate plane. This robot is able to tell me if it goes left, right, up, or down by reporting back a string consisting of the letters L, R, U, and D, such as DLURRDLURDLLLRRLRLDURRU. Each character represents a movement of one unit. However, it seems that the robot is going in loops on the plane, returning to coordinates that it has already visited. I don't want the robot to do that. I'd like the robot to tell me about the path it takes without any loops included - these loops should be removed from left to right in the string. Every step in the string it reports should represent movement to a cell that it has not yet visited before. If the robot ends where it starts, then it should report back an empty string.

Test cases

ULRURU -> UURU
URDLDRU -> DRU
LLLLRRRL -> LL
LLLULRRRL -> LLLUR
UURDDRULDL -> {empty string}
DLURRDLURDLLLRRLRLDURRU -> R
URULLLDLUULDDLDRDDLLLLLDLLUUULLURU -> URULLLDLUULDDLDRDDLLLLLDLLUUULLURU


This is a standard code golf challenge, where the shortest answer wins. Standard rules apply.

• What's the correct output for URDLDRU: URD, R, DRU, or something else?
– Neil
May 24, 2020 at 19:44
• How flexible are input and output? Can we take other characters? Or numbers? May 24, 2020 at 20:28
• A string containing those characters necessarily? Or can we consistently use 4 other letters of our choice? May 24, 2020 at 23:03
• Whoops, I forgot to remove my vote to close after OP's (almost complete) clarification. I just voted to reopen May 24, 2020 at 23:25
• What's the correct output for URDLDRUUU? Here, the robot makes a loop URDL which is removed, but then later returns to points within that loop. Do those points not count as visited?
– xnor
May 27, 2020 at 18:49

# 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:
Ḣ        -   head - X = first, shortest loop (if none this yields 0)
⁸       -   chain's left argument
œṣ     -   split at sublists equal to X
F    -   flatten


# 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

1. Convert the letters to their indexes within the ULDR
2. 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.

3. Scan sum those vectors to get the path positions (still as complex numbers)
4. 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.
5. 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...

• You can collect the &.-phrases into a single train phrase (it's actually interesting that J does accept certain trains for inverting). Also you don't need >: there since UD and LR have opposite directions anyway. TL;DR: 39 bytes. May 25, 2020 at 3:57
• Fantastic, didn't know that was possible, ty! May 25, 2020 at 4:00
• I didn't know it was possible either. I just guessed from your original code having &.(0,0j1^>:) that Agh-fork is invertible (which is reasonable since (A g h) is equivalent to A&g@:h; J can't invert fgh-forks in general). May 25, 2020 at 4:17

# 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)

• Just curious, what happens when c%5 === 4? How is the presumable undefined handled? May 24, 2020 at 23:06
• Oh, I guess it locks x into being NaN with !NaN === true? May 24, 2020 at 23:08
• @JonathanFrech c is one of 68, 76, 82 or 85 (the ASCII codes of DLRU) and none of them is congruent to 4 modulo 5. May 24, 2020 at 23:12

# MATL, 26 bytes

t"0J&y15\^hYs&=XR&fq&:[]w(


### Explanation

t        % Implicit input. Duplicate
"        % For each
0      %   Push 0
J      %   Push j (imaginary unit)
&y     %   Duplicate third-topmost element from the stack: current string
15\    %   ASCII code of each character, modulo 15. This gives 10, 7, 8, 1
%   for 'U', 'R', 'L', 'D' respectively
^      %   Element-wise power. This gives j^10=-1, j^7=-j, j^8=1, j^1=j for
%   'U', 'R', 'L', 'D'. These are the steps followed by the robot in
%   the complex plane (rotated and reflected, but no matter)
h      %   Concatenate. This prepends the 0, as starting point of the path
Ys     %   Cumulative sum. This computes the path traced by the robot
&=     %   Matrix of pair-wise equality comparisons for robot positions
XR     %   Upper triangular part, without diagonal
&f     %   Row and column indices of nonzeros. This will be non-empty if
%   there is a loop in the path
q      %   Subtract 1
&:     %   Two-input range. This uses the first element from each input,
%   that is, the first loop found
[]w(   %   Push [], swap, assignment index: this removes the characters that
%   caused the loop
%   string
% End (implicit). The loop is run as many times as the input length,
% which is an upper bound to the number of loops
% Display (implicit)


# T-SQL, 236 bytes

First time I ever use PI() in sql

WHILE @@rowcount>0WITH C
as(SELECT*,sum(ascii(a)/12-6+3/(ascii(a)-79)*pi())over(order
by b)x FROM @)DELETE C
FROM C,(SELECT top 1max(b)i,min(b)j
FROM C GROUP BY x HAVING SUM(1)>1or x=0ORDER BY 2)z
WHERE(i=j or j<b)and i>=b
SELECT*FROM @


Try it online

# Java (JDK), 229 bytes

s->{var l=new java.util.Stack();int x=0,y=0,i;for(var c:(s+"").getBytes()){l.add(x+","+y);i="DLUR".indexOf(c);x+=~i%2*~-i;y+=i%2*(i-2);i=l.indexOf(x+","+y);if(i>=0){var z=l.subList(i,l.size());s.delete(i,i+z.size());z.clear();}}}


Try it online!

## Credits

• 229 bytes May 26, 2020 at 8:52

# C (gcc),  119 ... 111  110 bytes

Outputs by modifying the input string.

p;f(char*s){for(char*r,*q=s;*q;p?*s++=*q++:(q=r))for(r=q,p=0;*r?p+=(*r%17?strlen(q):1)*~-(*r++%5&2):0;);*s=0;}


Try it online!

### How?

The algorithm is the same used in my JS answer with a few differences:

• We use a for loop instead of a recursive approach.

• We overwrite the input string with the output. This is safe because what is written is at most as long as what is read, and the meaningful information is always ahead of both the read and the write pointers (q and s respectively).

• Given the ASCII code c of the move character, we use c % 17 to find out if it's a vertical or horizontal move, and c % 5 & 2 to distinguish between down and up or between left and right.

         | 'D' (68) | 'L' (76) | 'R' (82) | 'U' (85)
---------+----------+----------+----------+----------
% 17    |     0    |     8    |    14    |     0
% 5 & 2 |     2    |     0    |     2    |     0


# Java (OpenJDK 8), 253252 243 bytes

static String r(String s){String e=s;int l=s.length();for(int i=0;i<l;i++)for(int j=i+1;j<l;j++){int u=0;for(int k=i;k<=j;k++)u+=(9*(e.charAt(k)%6/3)+1)*2*(5.5-(e.charAt(k)-12)/11);if(u==0)return r(e.replace(e.substring(i,j+1),""));}return e;}


Try it online!

This uses a recursion method, so I'm not entirely sure if it's being scored correctly. It has a limit of going off 9 tiles in a given loop, but that can be increased to any amount as needed. Ungolfed:

public static String remove(String str) {
String removed = str;
int l = str.length();
for (int i = 0; i < l - 1; i++) //-1 optional
for (int j = i + 1; j < l; j++) {
int upDownLeftRight = 0;
for (int k = i; k <= j; k++)
upDownLeftRight +=(9*(e.charAt(k)%6/3)+1)*2*(5.5-(e.charAt(k)-12)/11);
if (upDownLeftRight == 0)
return remove(removed.replace(removed.substring(i, j + 1), ""));
}
return removed;
}


A few seconds before I was going to submit this the post closed, a few days ago. Just realized it was opened back up.

• Ah, those are some really good optimizations @ceilingcat, I learned something May 27, 2020 at 22:26
• 221 bytes May 27, 2020 at 22:32
• You don't have to count the static, so it can be moved to the header (or you can remove it and change your r("...") calls to new Main().r("...")). Also, by switching to JDK 10+ you can change the String e=s; to var e=s;. Jul 8, 2020 at 15:59

# Python 2, 94 93 bytes

-1 byte thanks to @dingledooper!

r=""
x,=l=[0]
for c in input():x+=1j**(ord(c)%15);r+=c;l[len(r):]=x,;r=r[:l.index(x)]
print r


Try it online!

A minor improvement over @xnor's solution using slice assignment. Be sure to check out and upvote his answer!

The current position x is stored as a complex number. For each movement, the program checks the list of visited positions l, and truncates the redundant moves appropriately.

• 93 bytes May 28, 2020 at 23:59
• @dingledooper Thanks! I forgot why I expanded that part out... May 29, 2020 at 0:09
• Ohh, because originally it was a tuple, which throws error during the slice assignment. May 29, 2020 at 0:12
• Your improvement is not at all minor! The new strategy for updating the list l of visited positions is very nice and well worthy of the bounty.
– xnor
May 29, 2020 at 17:40

# Charcoal, 40 bytes

⊞υ⟦ⅈⅉ⟧ＦＳ«Ｍ✳ι⊞υι⊞υ⟦ⅈⅉ⟧≔…υ⊕⌕υ§υ±¹υ»⎚↑Φυ﹪κ²


Try it online! Link is to verbose version of code. Explanation:

⊞υ⟦ⅈⅉ⟧


Save the current coordinates to the predefined empty list.

ＦＳ«


Loop through each character of the input string.

Ｍ✳ι


Move the cursor in that direction.

⊞υι⊞υ⟦ⅈⅉ⟧


Save the direction and the new position.

≔…υ⊕⌕υ§υ±¹υ


Truncate the list to the original appearance of the position.

»⎚


Reset the cursor (possibly due to a bug in Charcoal).

↑Φυ﹪κ²


Output the directions which didn't get truncated.

# Python 3, 178 bytes

x=y=0;c=[[0,0]];a='';t='UDLR';u=['y-=1','y+=1','x-=1','x+=1']
for i in input():
exec(u[t.index(i)])
if[x,y]in c:f=c.index([x,y]);a=a[:f];c=c[:f]
else:a+=i
c+=[[x,y]]
print(a)


Try it online!

Keeps track of visited coordinates and removes letters between duplicate coords.

• Replace t='UDLR';u=['y-=1','y+=1','x-=1','x+=1'] and exec(u[t.index(i)]) with j=ord(i);exec('y x'[j%17%6]+'-+'[j//6%2]+'=1') to save 14 bytes. May 25, 2020 at 17:48

# R, 208 205 bytes

u=function(a){s=function(x)unlist(strsplit(x,''))
m=match
d=s(a)
l=length(d)
for(i in 1:l)for(j in i:l)if(l&!sum(m(d[k<-i:j],s("L R"),2)-2)&!sum(m(d[k],s("D U"),2)-2))return(u(d[-k]))
paste(d,collapse='')}


Try it online!

Recursive function: starting at each position in the string, check whether there are equal numbers of L+R and of U+D in the range up to each subsequent position. If so, then this is the first left-to-right loop, so delete this and call the function using the result. Otherwise, there are no loops, so output whatever is left.

Frustratingly, R is not particularly golfy at string-handling (at least with my ability), and one-third of the code is wasted used splitting strings into characters... so:

# R+stringr, 155 bytes (or R 172 bytes)

u=function(d,l=nchar(d),s=substring){
for(i in 1:l)for(j in i:l)if(l&all(!diff(str_count(e<-s(d,i,j),s("UDLR",1:4,1:4)))[-2]))return(u(str_remove(d,e)))
d}


Try it online!

Exactly the same approach, but using stringr library to work directly on the string instead of splitting into characters.

# Python 2, 98 bytes

r=""
x,=l=0,
for c in input():x+=1j**(ord(c)%15);l+=x,;r+=c;n=l.index(x);l=l[:n+1];r=r[:n]
print r


Try it online!

Instead of branching on whether the current position x has appeared before, we just look for where it first appeared and truncate to right after that. If it never appeared before, we find the current appearance, so nothing gets cut off. The ord(c)%15 is from a suggestion by Jonathan Allan.

• I got 95 bytes by never truncating l, but replacing append with insert at the appropriate index. May 27, 2020 at 14:05
• 94 bytes May 28, 2020 at 21:12
• @SurculoseSputum Nice solution! I think you should post it yourself. It's definitely worthy of an outgolfing bounty
– xnor
May 28, 2020 at 23:04
• Thanks! I didn't want to make a new solution because it was too similar to yours, but if you insist. :) May 28, 2020 at 23:39
• If you use input on Py2 don't that mean your input need pair of "" besides?
– l4m2
May 31, 2020 at 17:24

# Python 3.8 (pre-release), 168164163126 125 bytes

l=[p:=0]
n=""
for s in input():
if(p:=p+1j**(ord(s)%15))in l:x=l.index(p);l=l[:x+1];n=n[:x];p=l[x]
else:l+=[p];n+=s
exit(n)


Try it online!

Assigns a complex number to go up, down, left right on the complex plane. Then iterates over the given path S and either adds the new point to the path in the list of points l and the result string n or if it detected a loop from a previous index up until the current character, it slices the characters and points that created the loops out of the lists.

-35 thanks to @JonathanAllan!

• You could get rid of u and use p:=p+1j**(ord(s)%15)). May 25, 2020 at 15:15
• Also some spaces can be removed and we can print to STDERR with exit TIO - there's probably a slightly terser way of doing this program (possibly as a recursive function) too... May 25, 2020 at 15:26
• I came up with it when building my Jelly answer by just trying a few (although I then realised 2000 integer divided by ord(s) was a byte shorter in Jelly due to the problem that O%15ı is parsed as ord(s)%(15+j)). May 25, 2020 at 17:22
• You still have four redundant spaces in there. if(p:=p+1j**(ord(s)%15)) in l: l= -> if(p:=p+1j**(ord(s)%15))in l: l= and else: l+= -> else:l+= May 25, 2020 at 17:29
• Also the walrus for x costs a byte over if(p:=p+1j**(ord(s)%15))in l:x=l.index(p);l=l[:x+1];n=n[:x];p=l[-1]. Another save is p=l[-1] -> p=l[x] May 25, 2020 at 17:37

# Wolfram Language, 101 100 bytes

StringJoin[Characters@#/.(r={"L"->-"R","U"->-"D"})//.{a___,x__,b___}/;Tr@{x}==0->{a,b}/.Reverse/@r]&


Try it online!

With some fancier formatting and comments:

StringJoin[                                       (*reconvert to input format*)
Characters@#                                    (*split into characters*)
/. (r = {"L" -> -"R", "U" -> -"D"})             (*map L to -R and U to -D*)
//. {a___, x__, b___} /; Tr@{x} == 0 -> {a, b}  (*delete runs that sum to 0*)
/. Reverse /@ r                                 (*convert -R and -D back to L and U*)
]&


This takes a similar method to some of the others, deleting runs that sum to zero, but this one does it by replacing L and U with negative R and negative D respectively.

Another 100 byte solution that uses a similar but distinct technique, using SequenceReplace:

StringJoin@SequenceReplace[Characters@#/.(r={"L"->-"R","U"->-"D"}),{__}?(Tr@#==0&)->{}]/.Reverse/@r&


Try it online!

# perl -nF/(?{s-.*(??{!($&=~y&R&&c==$&=~y&L&&c&&$&=~y&U&&c==$&=~y&D&&c)})--g;print})(*COMMIT)/, 62125 0 bytes

Try it online!

Finds substrings with the same amount of Ls and Rs, and the same amount of Us and Ds, and removes them. Prints the result.

• May 26, 2020 at 10:41
• Or just 5 bytes May 26, 2020 at 10:45
• The size of your command line switches get measured when you do that, no? May 26, 2020 at 14:02
• @Abigail congrats, you found the exact reason why we used to count them. Please don't do this. May 26, 2020 at 15:03
• Sorry you got downvoted for my contribution, I actually found this really interesting - I don't think I've ever seen (*COMMIT) before this (or if I had, I'd forgotten about it)! May 27, 2020 at 20:54

# 05AB1E, 44 bytes

gU0ˆÇ5%v1X‚Â(ìyè¯θ+ˆ¯¤kÐV¯gα<‚Xª£ιнJ¯Y>£´vyˆ


Ugh.. This can definitely be golfed substantially, but it works..

Inspired by both @Arnauld's JavaScript answer and @OlivierGrégoire's Java answer, so make sure to upvote them!

Explanation:

g                # Get the length of the (implicit) input-string
U               # Pop and store it in variable X
0ˆ               # Add 0 to the global array
Ç                # Convert the (implicit) input-string to an integer-list of codepoints
5%              # Take modulo-5 on each
v             # Loop over each integer y:
1X‚          #  Pair 1 with the length X: [1,length]
Â         #  Bifurcate it (short for Duplicate & Reverse copy)
(        #  Negate the values: [-length,-1]
ì       #  Prepend the lists together: [-length,-1,1,length]
yè     #  Index y into this quadruplet
¯θ+  #  Add the last item of the global array to it
ˆ #  And pop and add it to the global array
¯            #  Push the global array
¤           #  Push its last item (without popping)
k          #  Get the first index of this last item in the global array
Ð         #  Triplicate this index
V        #  Pop and store one copy in variable Y
¯g      #  Push the length of the global array
α     #  Take the absolute difference with the index
<    #  Decrease it by 1
‚   #  Pair it with the index
Xª #  And append length X
£            #  Split the string into parts of that size
#  (which uses the implicit input-string in the very first iteration)
ι           #  Uninterleave it
н          #  Only leave the first part of two strings, removing the middle part
J         #  Join this pair together
¯            #  Push the global array again
Y>          #  Push Y + 1
£         #  Only leave the first Y+1 values of the global array
´        #  Empty the global array
v       #  Loop over the Y+1 values of the global array:
yˆ     #   And add each of them back the global array


# PowerShell, 126 120 bytes

$x=$y=0
switch -r(,'-'+$args){U{$y++}D{$y--}R{$x++}L{$x--}.{$g="$g$_$x-$y"-replace"(?<=($x-$y)).*\1$"}}$g-replace'\d|-'


Try it online!

The script:

1. injects $x-$y to input string like -0-0U0-1U0-2R1-2U1-3
2. removes substrings between same coordinates
3. removes digits and minus chars

Less golfed:

$x=$y=0
switch -regex (,'-'+$args){ U {$y++}
D {$y--} R {$x++}
L {$x--} . {$g="$g$_$x-$y"-replace"(?<=($x-$y)).*\1$"} }$g-replace'\d|-'