Lead Your Turtle by a String

Question

Write a program or function that takes in a nonempty single-line string of printable ascii characters excluding space:

!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~

You may assume the input is valid.

Based on the input, draw a new string arranged on a textual grid of spaces and newlines following turtle graphics-esque rules where the turtle always occupies one grid space and can only face the cardinal directions.

Print the first character in the input string to the text grid. The turtle starts here facing right. Iterate over the rest of the characters in the input string (only stopping if the turtle gets stuck), repeating this process:

1. If the 4 grid spaces directly neighboring the turtle are all filled (i.e. none of them is a space), stop iterating. The turtle is stuck and the grid is as complete as it can be.

2. Look at the current character in the input compared to the previous character:

   • If the current character is lexically before the previous, rotate the turtle a quarter turn left.

   • If the current character is lexically after the previous, rotate the turtle a quarter turn right.

   • If the current character equals the previous, don't rotate the turtle.

3. If the grid space the turtle is now facing is not empty (i.e. not a space), repeatedly rotate the turtle a quarter turn left until she is facing an empty grid space.

4. Move the turtle one grid step forward in the direction she's facing and print the current character on the grid in the turtle's new location.

Print or return the resulting text grid string with no extraneous rows or columns of whitespace. Lines may have trailing spaces up to the rightmost column with a non-space, but not beyond. A single trailing newline is optionally allowed.

The shortest code in bytes wins.

Example

Here are all the steps of the input spattuuxze. The ^V<> characters show the direction the turtle is facing, they are not part of the input or output.

s>

^
p
s

<ap
  s

^
t
ap
 s

^
t
t
ap
 s

tu>
t
ap
 s

tuu>
t
ap
 s

tuu
t x
apV
 s

tuu
<zx
ap
 s

At this point the turtle is stuck so the e never gets printed and the final output is:

tuu
tzx
ap
 s

Following is a similar but invalid output since it has an unnecessary leading column of whitespace:

 tuu
 tzx
 ap
  s

Test Cases

spattuuxze

tuu
tzx
ap
 s

spattuuxxze

tuu
t x
apx
 sze

1111111

1111111

ABCDEFGHIJKLMNOP

PEFG
ODAH
NCBI
MLKJ

`_^]\[ZYXWVUTSR

 ^_RS
\]`UT
[ZWV
 YX

Woo!

W
o
o!

woo!

!o
 o
 w

Wheeee

W
heeee

banana

  a
 an
an
b

Turtle

T
ure
 tl

turTle

  e
tTl
ur

^{(Do tell me right away if any of these seem wrong.)}

Answer 1

Groovy (357 Bytes)

No external turtle libs were used and no turtles were harmed.

R={s->s[0]?[0,-1*s[0]]:[s[1],0]}
L={s->s[0]?[0,s[0]]:[-1*s[1],0]}
def y(s){l=s.length()*2;z(new String[l][l],[l/4,l/4],s,null,[0,1])}
def z(g,l,w,p,h){if(w.length() && !g[(int)(l[0]+h[0])][(int)(l[1]+h[1])]){c=w.getAt(0);w=w.substring(1);if(p && p<c){h=R(h)}else if(p>c){h=L(h)};g[(int)l[0]+h[0]][(int)l[1]+h[1]]=c;z(g,[l[0]+h[0],l[1]+h[1]],w,c,h)}else{g}}

Try it here: https://groovyconsole.appspot.com/edit/5115774872059904

---

Previous Attempts

Groovy (397 Bytes)

rotR={s->s[0]!=0?[0,-1*s[0]]:[s[1],0]}
rotL={s->s[0]!=0?[0,s[0]]:[-1*s[1],0]}
def y(s){z(new String[s.length()][s.length()],[s.length()/2,s.length()/2],s,null,[0,1])}
def z(g,l,w,p,h){if(w.length() && !g[(int)(l[0]+h[0])][(int)(l[1]+h[1])]){c=w.getAt(0);w=w.substring(1);if(p && p<c){h=rotR(h)}else if(p > c){h=rotL(h)};g[(int)l[0]+h[0]][(int)l[1]+h[1]]=c;z(g,[l[0]+h[0],l[1]+h[1]],w,c,h)}else{g}}

https://groovyconsole.appspot.com/script/5179465747398656

Answer 2

Java, 408 406 bytes

String f(String I){int l=I.length(),x=l,y=x,z=x,t=y,Z=x,T=y,d=1,i=1,a;char[][]g=new char[l*2][l*2];int[]D={-1,0,1,0};for(char c,p=g[x][y]=I.charAt(0);i<l;p=c){c=I.charAt(i++);d=((c<p?d-1:c>p?d+1:d)+4)%4;for(a=0;g[x+D[d]][y+D[3-d]]>0&&a++<4;)d=(d+3)%4;if(a>3)break;g[x+=D[d]][y+=D[3-d]]=c;z=z<x?z:x;Z=Z>x?Z:x;t=t<y?t:y;T=T>y?T:y;}for(I="";z<=Z;z++,I+="\n")for(a=t;a<=T;a++)I+=g[z][a]<1?32:g[z][a];return I;}

The function gets the the input as String and returns the outcome as a String.

Internally it uses a 2D char array to store the letters and keeps the min and max columns and rows used in order to return the sub-array that was used.

So, in the outcome String there are no leading columns of white-spaces but there are trailing white-spaces up to the rightmost column with a non-space character. A newline is added at the end.

Any suggestions to golf it more are welcome :-)

Answer 3

Python3, 419 414 bytes

Z=input();l=r=c=M=R=C=N=len(Z);t=(r*2)+1;A=[0]*t;J=range
for i in J(t):A[i]=[" "]*t
A[r][c]=Z[0];i=1;Q=[1,0,-1,0];d=q=0
while i<l:
 if Z[i]<Z[i-1]:d+=3
 elif Z[i]>Z[i-1]:d+=1
 while A[r+Q[(d-1)%4]][c+Q[d%4]]!=" "and q<4:d+=3;q+=1
 if q>3:break
 r+=Q[(d-1)%4];c+=Q[d%4];R=min(R,r);C=min(C,c);M=max(M,r);N=max(N,c);A[r][c]=Z[i];i+=1;q=0
for i in J(R,M+1):
 for j in J(C,N+1):print(A[i][j],end="")
 print()