Shortest self-avoiding path given a sequence of turns

Question

Write a program or function which, given a non-empty sequence of right or left turns, outputs the length of the shortest self-avoiding path on a 2D lattice with those turns.

The input should be taken as a string, with each character being R or L for a right or left turn respectively.

The output should be an integer, the length of the shortest path with the given turns.

This is a gode golf - shortest code wins.

Example

Given the input

LLLLLLLLLLRRL

The shortest path is the following (starting at #):

+-+-+-+-+-+-+
|           |  
+ . + +-+-+ +
|   | |   | |  
+ +-+ + #-+ +
| |   |     |  
+ +-+ +-+-+-+
|   |          
+-+-+ . . . .

And the total length of this path is 29 (counting the -s and |s, not the +s).

Test Cases

L 2
RRRRRRRRRR 23
LRRLRLRRRRL 15
LLRRLRRRRLLL 17
LLRRRRRRLLLL 21
LLLLRLLRRLLRL 16
LRLRLRLLRLRRL 14
RLLRRRRLLRRLRL 17
RRRRLLRLLLRLRL 20
LLLLRRLRLRRRLRL 19
RRRLRRRLRRLRLRL 20

Answer 1

Prolog, 284 bytes

e(S,[0|X]):-e(S,X).
e([A|S],[A|X]):-S=X;e(S,X).
v(X/Y,76,Y/Z):-Z is -X.
v(X/Y,82,Z/X):-Z is -Y.
v(D,0,D).  
c([],0/0-0/1,[0/0]).
c([H|T],K/L-D/E,[K/L|C]):-c(T,I/J-X/Y,C),v(X/Y,H,D/E),K is I+X,L is J+Y,\+member(K/L,C).
n(X):-X=0;n(Y),X#=Y+1.
p(S,L):-n(L),length(X,L),e([0|S],X),c(X,_,_).

This is a pretty straightforward statement of the algorithm, and fairly inefficient (not all the test cases ran in reasonable time, although most did). It works via generating all possible lengths for the output from 1 upwards (n); generating all possible sequences of left/forward/right of that length which are consistent with the input (implemented in e; the new path is called X); then checking for the first such path that's valid (c, which calls into v to handle the effects of left and right turns on the x and y deltas). The return length is the first output seen in L. (+2 penalty if you want to prevent the function returning other possible outputs for the length if you backtrack into it; it's never quite clear how Prolog's idiosyncratic function returns should be counted.)

There isn't much in the way of golfing tricks here, but there is some. n was implemented with a constraint solver because it allows more whitespace to be removed without confusing the parser; this might require GNU Prolog to be used, not sure on that. (I couldn't do the same in c as it needs to handle negative numbers.) The implementation of e is considerably less efficient than it needs to be, via matching a list in multiple ways; the more efficient e([],[]). would be six bytes longer (it'd allow the S=X; on line 2 to be removed, but that's only a gain of four compared to a loss of ten). To allow me to match coordinates and directions as a whole, or just part, I represent them as X/Y (i.e. an unevaluated AST, which can be matched on), allowing me to use infix notation.

Prolog, 256 bytes, too inefficient to easily test

Of course, because this is Prolog, many of the functions are reversible, e.g. c can be used to generate all paths from the origin to a particular coordinate pair. Additionally, c naturally generates from shortest to longest. This means that instead of asking for a minimum length explicitly, we can just get c to generate all paths that go anywhere, then look for the first one that's consistent with the input:

e(S,[0|X]):-e(S,X).
e([A|S],[A|X]):-S=X;e(S,X).
v(X/Y,76,Y/Z):-Z is -X.
v(X/Y,82,Z/X):-Z is -Y.
v(D,0,D).
c([],0/0-0/1,[0/0]).
c([H|T],K/L-D/E,[K/L|C]):-c(T,I/J-X/Y,C),v(X/Y,H,D/E),K is I+X,L is J+Y,\+member(K/L,C).
p(S,L):-c(X,_,_),length(X,L),e([0|S],X).

This has exponential performance (O(3ⁿ), where n is the output). However, I did manage to verify it on some of the smaller tests (it takes around 7 seconds to output 14, and around 20 to output 15, on my computer).

Answer 2

Pyth, 36 bytes

ff{I.u+NYY0f>r8YlQ.C+1*M._m^.j)hCdQT

Try it online!

This is pretty slow, but it works, and it's fast enough for short inputs.

The program works by representing directions as complex units (1,-1,i,-i), and points as complex numbers. First I convert the list of turns into a list of directions, then generate all list of n steps, filter for those with at least one step between each turn, and convert the directions into a list of points visited, and check if that list is unique. I increment n in a loop until I succeed.

Map to complex numbers:

m^.j)hCdQ
m       Q    Map over the input
      Cd     Convert to ASCII codepoint
     h       Increment
 ^.j)        Raise i to that power.

Since L has ASCII codepoint 76 and R has ASCII codepoint 82, this maps L to i and R to -i.

Map to absolute directions:

+1*M._ ...
    ._      Form all prefixes
  *M        Map each to its product
+1          Add the first direction, before any turns

Form lists of n steps with at least 1 step between each turn

f>r8YlQ.C ... T
       .C     T    Form all list of T steps
f                  Filter for lists where
  r8Y              Run length encoding of list
 >   lQ            With the first len(input) removed
                   is nonempty

There should be one more movement than there are turns in the input. Each movement is in a different direction, so the run length encoding should be longer than the input.

Map to points visited:

.u+NYY0  ...
.u   Y0   Reduce the following function over
          the list of steps, starting at 0.
          Return all intermediates.
  +NY     Add the new step to the current position.

Filter on non-self-intersecting:

f{I ...
f     Filter on
  I   Invariant under
 {    Deduplication

Find the first T where this succeeds: f.