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

• Aug 2, 2016 at 9:08
• I think you should add the test case PONMLKJIHGFEDCBA, since the result is not just a square and contrasts with ABCDEFGHIJKLMNOP to highlight the asymmetry in the rules. Oct 12, 2016 at 23:06

# 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}}


# 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

• Answers must be complete and valid. Please delete your answer or finish it. Also, 30 minutes isn't very long. I've spent hours on answers before. Sep 7, 2016 at 21:22

# 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 :-)

• You might be able to do a smaller byte count using a char[] as input. ((c<p?d-1:c>p?d+1:d)+4)%4 Also, + 4 % 4 = 0, correct me if I'm wrong there but removing that +4 should not change your code. Sep 12, 2016 at 20:10
• @carusocomputing It is true that char[] as input would save many bytes but I am not sure if this is permitted by the question. The question mentions an "input string". Also the +4 is required because d which is the direction has to be bounded between 0 and 4. % is the remainder in java and it can be negative which is not desired. Thanks for the suggestions :-) Sep 12, 2016 at 20:19
• Ah... Good catch, fallacy on my end being that the inputs offered by OP covered all scenarios... "LNOPFg1#" breaks it without the +4. Sorry, even reading that code took me a minute. Sep 12, 2016 at 20:28

# 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()
`