Generate self-avoiding loops of a specific length

Question

This question is a sequel to this one, working in the opposite direction.

For a reminder of terminology, the letters L, R, U, and D represent one-unit movement of a robot on the coordinate plane in the directions left, right, up, and down respectively. Given a positive even integer n, generate and print all sequences of L, R, U, and D of length n that result in a closed loop that does not intersect itself. In other words, when the robot follows the instructions in the sequence of letters, it must visit a new cell with every movement until it completes the loop and returns to the original cell.

Any of the generally accepted output formats for arrays and strings are allowed. The elements printed must be in alphabetical order. It can be assumed that the input is always a positive even integer.

Test cases

2 -> {"DU", "LR", "RL", "UD"}
4 -> {"DLUR", "DRUL", "LDRU", "LURD", "RDLU", "RULD", "ULDR", "URDL"}
6 -> {"DDLUUR", "DDRUUL", "DLLURR", "DLUURD", "DRRULL", "DRUULD", "LDDRUU", "LDRRUL", "LLDRRU", "LLURRD", "LURRDL", "LUURDD", "RDDLUU", "RDLLUR", "RRDLLU", "RRULLD", "RULLDR", "RUULDD", "ULDDRU", "ULLDRR", "URDDLU", "URRDLL", "UULDDR", "UURDDL"}

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

Answer 1

APL (Dyalog Extended), 39 bytes

{∧'LURD'⊇⍨m⌿⍨(⍲∘⍧=⊢/)⍤1+\0J1*m←⍉4⊤⍳4*⍵}

Try it online!

The output is a matrix of characters, one path on a line.

How it works

{∧'LURD'⊇⍨m⌿⍨(⍲∘⍧=⊢/)⍤1+\0J1*m←⍉4⊤⍳4*⍵}  ⍝ Input ⍵←n

m←⍉4⊤⍳4*⍵  ⍝ A matrix of all length-n combinations of 0..3
     ⍳4*⍵  ⍝ 0..4^n-1
   4⊤      ⍝ Convert each to base 4 (each goes to a column)
m←⍉        ⍝ Transpose and assign to m

∧'LURD'⊇⍨m⌿⍨(⍲∘⍧=⊢/)⍤1+\0J1*m
                        0J1*m  ⍝ Power of i (directions on complex plane)
                      +\       ⍝ Cumulative sum; the path of the robot
            (      )⍤1  ⍝ Test each row:
                 ⊢/     ⍝   the last number (real+imag is always even)
                =       ⍝   equals
             ⍲∘⍧        ⍝   NAND of the nub-sieve
                        ⍝   (0 if all numbers are unique, 1 otherwise)
                        ⍝ The condition is satisfied only if both are 0
         m⌿⍨  ⍝  Extract the rows that satisfy the above
 'LURD'⊇⍨     ⍝  Index each number into the string 'LURD'
∧             ⍝  Ascending sort

Answer 2

Python 2, 119 106 104 bytes

def f(n,s="",p=0,*v):
 if p==n<1:print s
 for d in"DLRU":p in v or 0<n<f(n-1,s+d,p+1j**(ord(d)%15),p,*v)

Try it online!

---

Same idea in Python 3:

Python 3, 102 100 bytes

-2 bytes thanks to @ovs!

def f(n,s="",p=0,*v):p==n<1==print(s);p in v or[f(n-1,s+d,p+1j**(ord(d)%15),p,*v)for d in"DLRU"if n]

Try it online!

---

A recursive function that prints the results to STDOUT. Keep track of s, p, v which are the current sequence, the current position (as a complex number), and the list of visited positions respectively.

The sequence is printed when n == 0 and the position is back to 0, aka p==n<1.

Otherwise, if there is still moves and no self-intersection (n > 0 and p not in v), the function tries to move the current position in 4 directions, and recurs. Given the character d that is one of the 4 character D, L, R, U, the direction is determined as

1j ** (ord(d) % 15)

since

d  ord(d)  ord(d)%15  1j**...
D   68        8         1
L   76        1         1j
R   82        7        -1j
U   85        10       -1

Answer 3

Husk, 21 bytes

fS=oḟȯE½M#₁Q`π₁
"RULD

Try it online!

Explanation

A string over RULD encodes a self-avoiding loop if and only if the only contiguous substring with an equal number of R and L, and of U and D, is the entire string. I loop over all strings of the given length and check this condition by brute force.

fS=oḟȯE½M#₁Q`π₁  Implicit input n
            `π₁  Length-n words over string "RULD" (from second line).
f                Keep those that satisfy this:
           Q       List of substrings
   oḟ              Get the first one that satisfies this:
        M#₁          Counts of each letter in "RULD"
       ½             Split in half
     ȯE              The halves (counts of R,U vs counts of L,D) are equal
 S=                That equals the string, which is the last substring in the list

Answer 4

Wolfram Language (Mathematica), 99 96 bytes

^{-3 bytes thanks to my pronoun is monicareinstate!}

Sort["ULDR"~StringPart~#&/@Select[Range@4~Tuples~#,Tr[a=I^#]==0&&DuplicateFreeQ@Accumulate@a&]]&

Try it online! Pure function. Takes a number as input and returns a list of character lists as output. (I believe such a format is acceptable.) The logic is pretty simple: It takes all n-tuples of 1, 2, 3, 4, interprets them as powers of i, checks that the sequences end at 0 and contain no duplicates, and converts them to the ULDR format.

Answer 5

Jelly, 19 bytes

“ḅḍʂ»ðṗẆċⱮṚƑ¥ƇḢɗƑƇ⁸

A monadic Link accepting a non negative integer which yields a list of lists of characters.

Try it online!

How?

Much the same as Zgarb's Husk answer...

“ḅḍʂ»ðṗẆċⱮṚƑ¥ƇḢɗƑƇ⁸ - Link: integer, L
“ḅḍʂ»               - compressed string "URLD"
     ð              - start a new dyadic chain, f("URLD", L)
      ṗ             - ("URLD") Cartesian power (L) -> all length L strings using "URLD"
                 Ƈ  - keep those (s in those strings) for which:
                Ƒ   -   is invariant under?:
                  ⁸ -     use chain's left argument, "URLD", as the right argument of:
               ɗ    -       last three links as a dyad, f(s, "URLD"):
       Ẇ            -         all sublists (s)
             Ƈ      -         keep those (b in sublists(s)) for which:
            ¥       -           last two links as a dyad, f(b, "URLD"):
         Ɱ          -             map across (for c in "URLD") with f(b, c):
        ċ           -               count
           Ƒ        -             is invariant under?:
          Ṛ         -               reverse - i.e. count('U')=count('D')
                                               and count('R')=count('L')
              Ḣ     -         head (iff the only sublist with equal counts is the string
                                    itself then this will be that same string)

Answer 6

Python 2, 155 139 bytes

r=input()
for y in range(4**r):
 n=0;s=[];k='';exec'c=y%4;y/=4;s+=n,;n+=1j**(6>>c);k="DLRU"[c]+k;'*r
 if n==0<2>max(map(s.count,s)):print k

Try it online!

Answer 7

perl -M5.010 -n, 189 bytes

$k=2*$_;@m=(D,L,R,U);y=D====y=U==&&y=R====y=L==&&!/.+(??{!($&=~y=D====$&=~y=U==&&$&=~y=R====$&=~y=L==&&y===c-length$&)})/&&say for map{sprintf("%0$k".b,$_)=~s/../'$m['."0b$&]"/geer}0..4**$_

Try it online!

This iterates over the numbers from 0 to 4^$_, where $_ is the input number. Each number is turned into a binary format (padded out with zeros so they're all the same length (twice the size of the input)), and then 00 is replaced with D, 01 with L, 10 with R, and 11 with U. This enforces the correct order. Note that we include the number 4^$_ which will lead to a string that is "too long" (RDDD..D0), but will not pass the tests later on.

We then print the string if 1) they are a loop (contains the same number of Us and Ds, and the same number of Rs and Ls), and 2) no proper substring does contain a loop.

Expanding the program gives us:

#!/opt/perl/bin/perl

use 5.026;

use strict;
use warnings;
no  warnings 'syntax';

use experimental 'signatures';

my $k = 2 * $_;
my @m = ("D", "L", "R", "U");

y/D// == y/U//  &&   # Does $_ contain as many D's as U's ?
y/R// == y/L//  &&   # Does $_ contain as many R's as L's ?
!/.+                 # Grab a substring
  (??{               # Code block, result is seen as a pattern
       !(            # Negate what follows, if true, the result is ""
                     #     and "" will always match
                     #                      if false, the result is 1,
                     #     and since the string does not contain a 1,
                     #     the match will fail
         $& =~ y!D!! == $& =~ y!U!!  && # Does the substring contain as many
                                        # D's as U's?
         $& =~ y!R!! == $& =~ y!L!!  && # Does the substring contain as many
                                        # R's as L's?
         y!!!c - length ($&)            # Is this a proper substring?
                                        # y!!!c is a funny way getting the
                                        # length of $_, saving 1 byte over
                                        # using length, and if the lengths
                                        # are unequal, subtracting them is
                                        # a true value
       )})/x    &&   # if all conditions are met
say                  # print the results
for                  # do this for each
map {
    sprintf ("%0$k" . "b", $_)          # Get the binary representation
    =~ s/../'$m[' . "0b$&]"/geer        # And replace pairs of digits
                                        # with directions; we're using a
                                        # double eval -- first to turn the
                                        # replacement part into '$m[0bXX]',
                                        # with XX the two binary digits from
                                        # match, then we eval that result to
                                        # get the right direction.
} 0 .. 4 ** $_;      # Range of numbers


__END__

Answer 8

Python 3, 232 bytes

from itertools import*
x,y,z={"D":1,"U":-1},{"L":-1,"R":1},()
for j in product(*("DLRU",)*int(input())):
 n,m,s=0,0,()
 for c in j:
  if (n,m)in s:n=1e999
  s+=(n,m),;n+=x.get(c,0);m+=y.get(c,0);
 z+=("".join(j),)*(n==m==0)
print(z)

Brute-force approach (checks every possible string of the given length, with no optimization for performance).

Can probably be golfed a lot more, but still includes several non-obvious tricks to it. The most notable is setting n to 1e999 (a short form for infinity) when a self-crossing path is detected, ensuring that it never goes back to zero and saving 3 bytes over the more obvious approach of break in the loop and moving the assignment to z into a else.

Try it online!

Answer 9

JavaScript (V8), 106 bytes

Prints the paths to STDOUT.

f=(n,s='',p=0,o=[])=>s[n-1]?p||print(s):(o[n*n+p]^=1)&&[n,-1,1,-n].map((d,i)=>f(n,s+'DLRU'[i],p+d,[...o]))

Try it online!

Commented

f = (                   // a recursive function taking:
  n,                    //   n = input
  s = '',               //   s = output string
  p = 0,                //   p = position
  o = []                //   o[] = array holding all visited positions
) =>                    //
  s[n - 1] ?            // if s has the requested length:
    p || print(s)       //   print it only if we're back to our starting point
  :                     // else:
    (o[n * n + p] ^= 1) //   toggle the item in o[] at n² + p
                        //   NB: we need n² to make sure it's positive
    &&                  //   abort if it's now set to 0 (meaning that this
                        //   position was already visited)
    [n, -1, 1, -n]      //   list of directions (down, left, right, up)
    .map((d, i) =>      //   for each direction d at position i:
      f(                //     do a recursive call:
        n,              //       pass n unchanged
        s + 'DLRU'[i],  //       append the direction character to s
        p + d,          //       add the direction to the position
        [...o]          //       pass a copy of o[]
      )                 //     end of recursive call
    )                   //   end of map()

Answer 10

Charcoal, 60 59 bytes

Ｎθ⊞υωＦυ«≔Ｅι§⟦¹θ±¹±θ⟧⌕LURDκζ¿¬№ＥζΣ…ζλΣζ¿‹ＬιθＦLURD⊞υ⁺ικ¿¬Σζ⟦ι

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

Ｎθ

Input n.

⊞υω

Start the list of sequences off with an empty sequence.

Ｆυ«

Perform a breadth-first search of sequences.

≔Ｅι§⟦¹θ±¹±θ⟧⌕LURDκζ

Convert the sequence into a list of directions 1, i, -1 and -i. As Charcoal doesn't have complex numbers, I'm simulating them using n instead of i. It's not possible for n of these numbers to overflow to zero (I need n 1s and an n+1th -n to do that) so I'm safe.

¿¬№ＥζΣ…ζλΣζ

Take the sums of the proper prefixes and check that the sum of the directions does not appear. Note that due to a Charcoal quirk the sum of [] is not zero, so we can allow a single zero to appear as a sum of the sequence.

¿‹Ｌιθ

Is this sequence of the desired length? If not...

ＦLURD

Loop over each direction.

⊞υ⁺ικ

Append the direction and push this candidate sequence to the list of sequences.

¿¬Σζ

Did this sequence of the desired length finish back at the origin?

⟦ι

If so then print it on its own line.

Answer 11

Swift 5/Xcode 10.3, 434 433 417 399 366 360 273 bytes

func g(_ a:[(Int,Int)],_ b:String)->[String]{let l=a.last!;if b.count==n{return l==(0,0) ?[b]:[]};return[(l.0,l.1-1,"D"),(l.0-1,l.1,"L"),(l.0+1,l.1,"R"),(l.0,l.1+1,"U")].flatMap{m in a[1...].contains{$0.0==m.0 && $0.1==m.1} ?[]:g(a+[(m.0,m.1)],b+m.2)}};return g([(0,0)],"")

Try it online!