Remove loops from a walk

Question

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.

Answer 1

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

Answer 2

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...

Answer 3

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)

Answer 4

MATL, 26 bytes

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

Try it online! Or verify all test cases.

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)

Answer 5

T-SQL, 236 bytes

First time I ever use PI() in sql

I am using table as input

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

Answer 6

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

• 5 bytes saved thanks to ceilingcat
• 22 bytes saved thanks to Kevin Cruijssen

Answer 7

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
  

Answer 8

perl -nF/(?{s-.*(??{!($&=~y&R&&c==$&=~y&L&&c&&$&=~y&U&&c==$&=~y&D&&c)})--g;print})(*COMMIT)/, 62 12 5 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.

Answer 9

Java (OpenJDK 8), 253 252 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.

Answer 10

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.

Answer 11

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.

Answer 12

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.

Answer 13

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.

Answer 14

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.

Answer 15

Python 3.8 (pre-release), 168 164 163 126 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!

Answer 16

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!

Answer 17

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!

Try it online or verify all test cases.

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

Answer 18

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|-'