# Make a Snake Parser!

Snakes look like this:

      >>>v
@     ^  v
^  >>>^  v
^        v
^<<<<<<<<<


The snake can cross over itself as in this case:

 @
^
>^>v
^<<


For a crossover to be valid, the characters on either side must be moving the same direction. The case of

 @
>^v
^<


can be considered unclear and invalid.

The output is a string of WASD representing going from the head to the tail (@).

Given a snake that doesn't backtrack and isn't ambiguous, can you write a program that will output the string of moves that the snake takes?

This is code-golf, so shortest answer wins!

### Test cases:

(Note: The @ can be replaced with any character not in v^<>)

Input:

>>>>v
v
v<<  @
v    ^
>>>>>^


Output: ddddssaassdddddww

Input:

@>>v
^  v
^  v
^<<<


Output: dddsssaaawww

Input:

>>>v
v       @
v       ^
>>>>v   ^
>>>>^


Output: dddsssddddsddddwww

Input:

@<< v
^ v
v<^<<
v ^
>>^


Output: ssaaaassddwwwwaa

Input:

@v<v
^v^v
^v^<
^<


Output: ssawwasssawww

• Does the input have to be a single String or can we take a String[]? Is each line of the input padded to be the same length or do we have to deal with irregular line length? – CAD97 Mar 18 '16 at 18:04
• This is giving me horrible flash backs to the path of an Ant on a rubiks cube question. – Matt Mar 18 '16 at 19:08
• Will the beginning segment always be on line 0, char 0, or will we have to find it? – MayorMonty Mar 18 '16 at 20:30
• @SpeedyNinja test cases 2 and 4 both have starts not at (0,0), and test case 0 (snakes look like) doesn't start OR end at (0,0). – CAD97 Mar 18 '16 at 20:31
• @CAD97 Oh, that's devlish ;) – MayorMonty Mar 18 '16 at 20:32

## Java, 626539536 529 bytes

-87 bytes by saving a few in a lot of places. Thanks goes to Mr Public for pointing some out.

-3 bytes because I can't manage to remove all the spaces first try (thanks mbomb007)

+8 bytes to fix for this case:

@v<v
^v^v
^v^<
^<


s->{String o="",t;String[]p=s.split("\n");int h=p.length,w=p[0].length(),y=0,x,b=0,a,n,m;char[][]d=new char[h][w];for(;y<h;y++)for(x=0;x<w;x++){d[y][x]=p[y].charAt(x);if(d[y][x]=='@')d[y][x]=' ';}for(;b<h;b++)for(a=0;a<w;a++){t="";x=a;y=b;n=0;m=0;while(!(y<0|y>h|x<0|x>w||d[y][x]==' ')){if(y+m>=0&y+m<h&x+n>=0&x+n<w&&d[y+m][x+n]==d[y-m][x-n])d[y][x]=d[y-m][x-n];n=m=0;switch(d[y][x]){case'^':t+="W";m--;break;case'<':t+="A";n--;break;case'v':t+="S";m++;break;case'>':t+="D";n++;}x+=n;y+=m;}o=t.length()>o.length()?t:o;}return o;}


static Function<String,String> parser = snake -> {
// declare all variables in one place to minimize declaration overhead
String output = "", path;
String[] split = snake.split("\n");
int h=split.length, w=split[0].length(), y=0, x, startY=0, startX, dx, dy;
char[][] board = new char[h][w];
// setup char[][] board
for (; y<h; y++)
for (x=0; x<w; x++) {
board[y][x]=split[y].charAt(x);
if(board[y][x]=='@')board[y][x]=' ';
}
// find the longest possible path
for (; startY<h; startY++)
for (startX=0; startX<w; startX++) {
path = "";
x=startX; y=startY; dx=0; dy=0;
while (!(y<0 | y>h | x<0 | x>w || board[y][x] == ' ')) {
if (y + dy >= 0 & y + dy < h & x + dx >= 0 & x + dx < w
&& board[y + dy][x + dx] == board[y - dy][x - dx]) {
board[y][x] = board[y - dy][x - dx];
} dx = dy = 0;
switch(board[y][x]) {
case '^':path+="W";dy--;break;
case '<':path+="A";dx--;break;
case 'v':path+="S";dy++;break;
case '>':path+="D";dx++;break;
}
x+=dx; y+=dy;
}
output = path.length()>output.length()?path:output;
}
return output;
};


Takes a String like v @\n>>>^. Creates a path starting at each coordinate, then returns the longest one. The lookahead required for the overlapping paths was the hardest part.

• I am very impressed. I didn't expect anyone to even attempt this. And you're the first one. +1. (2016 bytes is okay, and even better for 2016 :D) – user51533 Mar 18 '16 at 20:29
• Strip all the spaces, names, etc then I'll +1. I'm not voting up until it's golfed properly. – mbomb007 Mar 18 '16 at 20:52
• Or, have two code snippets, one of the fully golfed version, one of the working readable example. – Mr Public Mar 18 '16 at 20:53
• @mbomb007 I finished the logic golfing so here's the properly golfed version! – CAD97 Mar 18 '16 at 21:09
• @CAD97 For this challenge, I would say this is an excellent golf in Java. – Mr Public Mar 18 '16 at 21:52

# Ruby, 217

->a{r=''
z=a.index ?@
a.tr!('<^>v',b='awds').scan(/\w/){c=0
e,n=[a[z,c+=1][?\n]?p: c,d=c*a[/.*
/].size,a[z-c,c][?\n]?p: -c,-d].zip(b.chars).reject{|i,k|!i||a[v=i+z]!=k||0>v}.max_by{|q|q&[a[z]]}until n
z+=e
r=n*c+r}
r}


This starts at the @ and walks backwards, looking for neighbors that point to the current position (z). In order to choose the right way at 4-way intersections, it favors neighbors pointing in the same direction (max_by{...}). If no immediate neighbors are found, it assumes that there must have been a cross-over and reaches out one level at a time until it finds one (until n and c+=1). This process repeats for the number of body segments (not including the head) (.scan(/\w/){...}).

The test case I added to the puzzle kept tripping me up, so I went form 182 char to 218. Those extra characters were all making sure my horizontal moves didn't go into the next/prev lines. I wonder if I can deal with that in a better way.

## Ungolfed:

f=->a{
result=''
position=a.index ?@ # start at the @
a.tr!('<^>v',b='awds') # translate arrows to letters
a.scan(/\w/){           # for each letter found...
search_distance=0
until distance
search_distance+=1
neighbors = [
a[position,search_distance][?\n]?p: search_distance,  # look right by search_distance unless there's a newline
width=search_distance*a[/.*\n/].size,   # look down (+width)
a[position-search_distance,search_distance][?\n]?p: -search_distance, # look left unless there's a newline
-width                  # look up (-width)
]
distance,letter = neighbors.zip(b.chars).reject{ |distance, letter_to_find|
!distance || # eliminate nulls
a[new_position=distance+position]!=letter_to_find || # only look for the letter that "points" at me
0>new_position # and make sure we're not going into negative indices
}.max_by{ |q|
# if there are two valid neighbors, we're at a 4-way intersection
# this will make sure we prefer the neighbor who points in the same
# direction we're pointing in.  E.g., when position is in the middle of
# the below, the non-rejected array includes both the top and left.
#   v
#  >>>
#   v
# We want to prefer left.
q & [a[position]]
# ['>',x] & ['>'] == ['>']
# ['v',x] & ['>'] == []
# ['>'] > [], so we select '>'.
}
end
position+=distance
result=(letter*search_distance)+result # prepend result
}
result # if anyone has a better way of returning result, I'm all ears
}

• You should be able to simplify your logic somewhat as your added case has been deemed out of the intended scope. – CAD97 Mar 20 '16 at 19:58