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