# De-Snakify a String

A regular string looks like this:

Hello,IAmAStringSnake!


And a string snake looks something like this:

Hel
l      rin
o,IAmASt g
S
!ekan


String snakes are dangerous, so you must make a program that takes a string snake as input and outputs it as a regular string.

## Specifications

• Input can be a multiline string or an array of strings.
• Each line of the input will be padded with spaces to form a rectangular grid.
• Characters in the snake can only connect to adjacent characters above, below, left or right of them (just like in the game Snake). They cannot go diagonal.
• The snake characters will never be adjacent to another part of the snake, only the connected characters.
• The first character of the string is the end character with the shortest Manhattan distance from the top-left corner of the input grid (i.e. the minimum number of moves it would take for a snake to go directly from the end character to the top-left corner). Both ends will never have the same distance.
• The string can contain any ASCII character between code points 33 and 126 inclusive (no spaces or newlines).
• The string will be between 2 and 100 characters long.
• Shortest code in bytes wins.

## Test Cases

(Input grid, followed by the output string)

Hel
l      rin
o,IAmASt g
S
!ekan

Hello,IAmAStringSnake!

----------

Python

Python

----------

P  ngPu  Code
r  i  z  d  G
o  m  z  n  o
gram  lesA  lf

ProgrammingPuzzlesAndCodeGolf

----------

~ zyx tsr XWVUTSR
}|{ wvu q Y     Q
!          p Z ab P
"#$6789:; o [ _ c O % 5 < n \]^ d N ('& 432 = m e M ) 1 > lkjihgf L *+,-./0 ? K @ABCDEFGHIJ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_abcdefghijklmnopqrstuvwxyz{|}~

----------

tSyrep
r    p
in Sli
g    Sile
Snakes  n
Ser      ylt
a eh   ilS
fe w   t
emo h
Sre

SlipperyStringSnakesSilentlySlitherSomewhereSafe

• Fun Fact: According to the linked Wikipedia article, Manhattan distance is also known as snake distance! – user81655 Apr 7 '16 at 10:22
• Would an input like hastebin.com/asugoropin.vbs be correct ? – FliiFe Apr 7 '16 at 11:35
• @FliiFe No, parts of the snake cannot be next to each other because it's not always possible to tell where the snake is going when this happens (and it would make the challenge a lot harder). I added a line to the spec to explain this. – user81655 Apr 7 '16 at 11:51
• Can the input be a two-dimensional array (i.e each character as an element) ? – FliiFe Apr 7 '16 at 12:24
• Surely this puzzle needs an answer in python? – abligh Apr 7 '16 at 22:51

# APL, 55 bytes

{⍵[1↓(⊂0 0){1<⍴⍵:⍺,∆[⊃⍋+/¨|⍺-∆]∇∆←⍵~⍺⋄⍺}(,⍵≠' ')/,⍳⍴⍵]}


This function takes a character matrix with the string snake in it.

Example:

      s1 s2 s3
┌────────────┬──────────────┬────────────────────┐
│Hel         │P  ngPu  Code │   ~ zyx tsr XWVUTSR│
│  l      rin│r  i  z  d  G │   }|{ wvu q Y     Q│
│  o,IAmAst g│o  m  z  n  o │!          p Z ab P│
│           S│gram  lesA  lf│"#$6789;: o [ _ c O│ │ !ekan│ │ % 5 < n \]^ d N│ │ │ │('& 432 = m e M│ │ │ │) 1 > lkjighf L│ │ │ │*+,-./0 ? K│ │ │ │ @ABCDEFGHIJ│ └────────────┴──────────────┴────────────────────┘ ↑ {⍵[1↓(⊂0 0){1<⍴⍵:⍺,∆[⊃⍋+/¨|⍺-∆]∇∆←⍵~⍺⋄⍺}(,⍵≠' ')/,⍳⍴⍵]} ¨ s1 s2 s3 Hello,IAmAstringSnake! ProgrammingPuzzlesAndCodeGolf !"#$%&'()*+,-./0123456789;:<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_abcdefhgijklmnopqrstuvwxyz{|}~


Explanation:

• (,⍵≠' ')/,⍳⍴⍵: get the coordinates of all non-spaces
• (⊂0 0): begin at (0,0) (which is an invalid coordinate)
• {...}: follow the snake, given position and snake:
• 1<⍴⍵:: if there is more than 1 element left:
• ∆←⍵~⍺: remove the current position from the snake and store it in ∆.
• +/¨|⍺-∆: find the distance between the current position and each point in the rest of the snake
• ∆[⊃⍋...]: get the closest point on the snake
• ∇: run the function again, with the closest point as the new current point and the shortened snake as the new snake.
• ⍺,: add the current position to the result of that
• ⋄⍺: otherwise, just return the current position
• 1↓: drop the first item from the result (which is the (0,0) position)
• ⍵[...]: get those elements from ⍵, in that order

# JavaScript (ES6) + SnakeEx, 176 bytes

a=b=>snakeEx.run("s{A}:<+>([^ ]<P>)+",b).reduce((c,d)=>(e=c.marks.length-d.marks.length)>0?c:e?d:c.x+c.y>d.x+d.y?d:c).marks.reduce((c,d,e,f)=>e%2?c+b.split\n[d][f[e-1]]:c,"")


Remember SnakeEx? Good, because neither do I! Golfing suggestions welcome.

# MATL, 80 bytes

Thanks to @LevelRiverSt for a correction

32>2#fJ*+X:4Mt1Y6Z+l=*2#fJ*+ttXjwYj+K#X<)wt!"tbb6#Yk2#)yw]xxvtXjwYjqGZy1)*+Gw)1e


Input is as a 2D array of char, with rows separated by ;. The test cases in this format are

['Hel         ';'  l      rin';'  o,IAmASt g';'           S';'       !ekan']
['Python']
['P  ngPu  Code ';'r  i  z  d  G ';'o  m  z  n  o ';'gram  lesA  lf']
['   ~ zyx tsr XWVUTSR';'   }|{ wvu q Y     Q';'!          p Z ab P';'"#$6789:; o [ _ c O';' % 5 < n \]^ d N';'(''& 432 = m e M';') 1 > lkjihgf L';'*+,-./0 ? K';' @ABCDEFGHIJ'] [' tSyrep ';' r p ';' in Sli ';' g Sile';' Snakes n';'Ser ylt';'a eh ilS ';'fe w t ';' emo h ';' Sre ']  Try it online! ### Explanation The coordinates of each nonspace character is represented by a complex number. For each current character, the next is obtained as that which is closest (minimum absolute difference of their complex coordinates). To determine the initial char, the two endpoints need to be found. This is done as follows. An endpoint is a nonspace char that has exactly one nonspace neighbour. The number of neighbours is obtained by 2D convolution with a suitable mask. The initial point is the endpoint whose complex coordinate has the least sum of real and imaginary parts; i.e. is closest in Manhattan distance to the complex number 0, or equivalently to 1+1j, which is the complex coordinate of the upper left corner. 32> % Take input as 2D char array. Compute 2D array with true for nonspace, % false for space 2#f % Arrays of row and column indices of nonspaces J*+ % Convert to complex array. Real part is row, imaginary part is column X: % Convert to column array 4Mt % Push arrays of zeros and ones again. Duplicate 1Y6 % Push array [0 1 0; 1 0 1; 0 1 0]. Used as convolution mask to detect % neighbours that are nonspace Z+ % 2D convolution with same size as the input 1= % True for chars that have only one neighbour (endpoints) * % Multiply (logical and): we want nonspaces that are endpoints 2#fJ*+ % Find complex coordinates (as before) ttXjwYj % Duplicate. Take real and imaginary parts + % Add: gives Manhattan distance to (0,0) K#X< % Arg min. Entry with minimum absolute value has least Manhattan % distance to (0,0), and thus to (1,1) (top left corner) ) % Apply as an index, to yield complex coordinate of initial endpoint wt! % Swap, duplicate, transpose. % The stack contains, bottom to top: complex coordinates of initial % endpoint, column array with all complex coordinates, row array of all % coordinates. The latter is used (and consumed) by the next "for" % statement to generate that many iterations " % For loop. Number of iterations is number of nonspaces tbb % Duplicate, bubble up twice (rearrange is stack) 6#Yk % Find which of the remaining points is closest to current point. This % is the next char in the string 2#) % Remove the point with that index from the array of complex % coordinates. Push that point and the rest of the array yw % Duplicate extracted point, swap ] % End for xx % Delete top two elements of the stack v % Concatenate all stack contents into a column array. This array % contains the complex coordinates of chars sorted to form the string tXjwYj % Extract real part and imaginary part GZy1) % Number of rows of input. Needed to convert to linear index *+ % Convert rows and columns to linear index Gw % Push input below that ) % Index to get the original chars with the computed order 1e % Force the result to be a row array (string). Implicitly display  • I shall assume an explanation is forthcoming? – Matt Apr 7 '16 at 16:19 • @Matt Sure... later in the day :-) – Luis Mendo Apr 7 '16 at 16:19 • Explanation added @Matt – Luis Mendo Apr 7 '16 at 19:02 • The initial point is the endpoint whose complex coordinate has the least absolute value Careful: Euclidean distance != Manhattan distance. for example the point 7+7j has Euclidean distance 9.8994 and Manhattan distance 14. 10j is further by Euclidean distance but considerably closer by Manhattan distance. Other than that, great concept! – Level River St Apr 8 '16 at 11:46 • @LevelRiverSt Thank you! Corrected – Luis Mendo Apr 8 '16 at 11:58 # C 198 190 179 180 181 bytes Edit: Used the tip by user81655 and removed the parenthesis in the ternary operator, thanks! I also changed the cumbersome (S&1) test for evenness for the more appropriate (and shorter!) S%2. Edit2: Using the *a addressing style heavily, made me blind to the obvious optimizations in the definition of S, i.e., replacing *(a+m) by a[m] etc. I then replaced S itself by T, which essentially does half of what S does. The code also now takes advantage of the return value of putchar. Edit3: Fixed bug that has been around from the beginning, the Manhattan-search stopping criteria a < b+m is correct only if a has already been decremented. This adds 2 bytes, but one is regained by making the definition of m global. Edit4: My golfing has passed the minimum and is going the wrong way now. Another bug fix related to the Manhattan-search. I originally had in-bound checks in place and without those the search continues for large input arrays (somewhere round 50x50) beyond the array b. Hence that array has to be expanded to at least twice the previous size, which adds one more byte. #define T(x)+x*((a[x]>32)-(a[-x]>32)) m=103;main(){char b[m<<8],*e=b,*a=e+m;while(gets(e+=m));for(e=a;(T(1)T(m))%2**a<33;a=a<b+m?e+=m:a)a-=m-1;for(;*a;a+=T(1)T(m))*a-=putchar(*a);}  Ungolfed and explained: /* T(1)T(m) (formerly S) is used in two ways (we implicitly assume that each cell has one or two neighbors to begin with): 1. (in the first for-loop) T(1)T(m) returns an odd (even) number if cell a has one (two) neighbors with ASCII value > 32. For this to work m must be odd. 2. (in the second for-loop) at this stage each cell a in the array at which T(1)T(m) is evaluated has at most one neighboring cell with ASCII value > 32. T(1)T(m) returns the offset in memory to reach this cell from a or 0 if there is no such cell. Putting the + in front of x here saves one byte (one + here replaces two + in the main part) #define T(x)+x*((a[x]>32)-(a[-x]>32)) /* A snake of length 100 together with the newlines (replaced by 0:s in memory) fits an array of size 100x101, but to avoid having to perform out-of-bounds checks we want to have an empty line above and the array width amount of empty lines below the input array. Hence an array of size 202x101 would suffice. However, we save a (few) bytes if we express the array size as m<<8, and since m must be odd (see 1. above), we put m = 103. Here b and e point to the beginning of the (now) 256x103 array and a points to the beginning of the input array therein */ m=103; main() { char b[m<<8],*e=b,*a=e+m; /* This reads the input array into the 256x103 array */ while(gets(e+=m)); /* Here we traverse the cells in the input array one constant-Manhattan-distance-from-top-left diagonal at a time starting at the top-left singleton. Each diagonal is traversed from bottom-left to top-right since the starting point (memory location e) is easily obtained by moving one line downwards for each diagonal (+m) and the stopping point is found by comparing the present location a to the input array starting position (b+m). The traversal is continued as long as the cell has either an ASCII value < 33 or it has two neighbors with ASCII value > 32 each (T(1)T(m) is even so that (T(1)T(m))%2=0). Note that the pointer e will for wide input arrays stray way outside (below) the input array itself, so that for a 100 cell wide (the maximum width) input array with only two occupied cells in the bottom-right corner, the starting cell will be discovered 98 lines below the bottom line of the input array. Note also that in these cases the traversal of the diagonals will pass through the right-hand side of the 103-wide array and enter on the left-hand side. This, however, is not a problem since the cells that the traversal then passes have a lower Manhattan distance and have thereby already been analyzed and found not to contain the starting cell. */ for(e=a;(T(1)T(m))%2**a<33;a=a<b+m?e+=m:a)a-=m-1; /* We traverse the snake and output each character as we find them, beginning at the previously found starting point. Here we utilize the function T(1)T(m), which gives the offset to the next cell in the snake (or 0 if none), provided that the current cell has at most one neighbor. This is automatically true for the first cell in the snake, and to ensure it for the rest of the cells we put the ASCII value of the current cell to 0 (*a-=putchar(*a)), where we use the fact that putchar returns its argument. The value 0 is convenient, since it makes the stopping condition (offset = 0, we stay in place) easy to test for (*a == 0). */ for(;*a;a+=T(1)T(m)) *a-=putchar(*a); }  • This answer is great. – abligh Apr 8 '16 at 6:03 • +1 This is great. I would like to add an explaination to my answer showing where I waisted bytes compared to your solution, is that OK? – mIllIbyte Apr 8 '16 at 8:11 • mIllIbyte - feel free to add the comments, that's the road towards new ideas. – Zunga Apr 8 '16 at 12:42 • user81655 - thanks for the tip, it shaved off 6 bytes. In fact, I tried that yesterday as well as using S%2 instead of (S&1), which shaved off another 2 bytes, for the evenness test, but for some reason (my code was buggy somewhere else) neither worked appropriately then. Now, however, all seems ok. – Zunga Apr 8 '16 at 12:49 • Very nice. Save some more with a[1], a[-m] etc, and making m global - m=103;main(). – ugoren Apr 8 '16 at 14:54 # C, 272 bytes #define E j+(p/2*i+1)*(p%2*2-1) #define X(Y) a[Y]&&a[Y]-32 char A[999],*a=A+99;j,p,t;i;main(c){for(;gets(++j+a);j+=i)i=strlen(a+j);for(c=j;j--;){for(t=p=4;p--;)t-=X(E);t==3&&X(j)?c=c%i+c/i<j%i+j/i?c:j:0;}for(j=c;c;){putchar(a[j]),a[j]=0;for(c=0,p=4;!c*p--;)X(E)?c=j=E:0;}}  Look at @Zunga's source. Now look at mine. Want to know how I got the extra 91-bytes? Ungolfed: #define E j+(p/2*i+1)*(p%2*2-1) #define X(Y) a[Y]&&a[Y]-32 //can be more concise, see @Zunga's //and then doesn't need the define char A[999],*a=A+99;j,p,t;i; main(c){for(;gets(++j+a);j+=i) i=strlen(a+j); //we don't need to know the length of a line //in @Zunga's solution, lines are spaced a constant distance apart for(c=j;j--;){ for(t=p=4;p--;)t-=X(E); //a ton of bytes can be saved with determining //the neighbors, see @Zunga's source t==3&&X(j)? c=c%i+c/i<j%i+j/i?c:j:0;} //we search for ends of the snake, //and compute the Manhattan distance for(j=c;c;){putchar(a[j]),a[j]=0; for(c=0,p=4;!c*p--;) //determining the neighbors again X(E)?c=j=E:0;}}  ## Python (2 and 3), 640 624 604 583 575 561 546 538 bytes I'm still a golfing n00b so this is a bit large. Edit: Thanks to @porglezomp for the suggestions! I didn't remove all the 'and' operators as that would break Python 3. Edit2: Thanks to @Aleksi Torhamo for the comment about isspace(). The resulting reduction compensates for the bugfix I put in. Also thanks to anonymous for the syntax highlighting! Edit3: Thanks to @mbomb007 for a few additional bytes. import sys;s=sys.stdin.read().split('\n');m={};q=[];o=len;j=o(s);r=range;g='!' for y in r(j): v=s[y];f=o(v);d=y+1 for x in r(f): n=[];a=n.append;U=s[y-1] if v[x]>=g:j>=y>0==(U[x]<g)<=x<o(U)and a((x,y-1));j>y>=0==(v[x-1]<g)<x<=f and a((x-1,y));j>y>-1<x+1<f>(v[x+1]<g)<1and a((x+1,y));j>d>-1<x<o(s[d])>(s[d][x]<g)<1and a((x,d));m[x,y]=[v[x],n];o(n)-1or q.append((x,y)) t=min(q,key=sum);w=sys.stdout.write;w(m[t][0]);c=m[t][1][0] while o(m[c][1])>1: b=m[c][1];w(m[c][0]) for k in r(o(b)): if b[k]!=t:t=c;c=b[k];break print(m[c][0])  And here's my pre-golf version import sys lines = sys.stdin.read().split('\n') startend = [] mydict = {} for y in range( 0, len(lines)): for x in range( 0, len(lines[y])): if not lines[y][x].isspace(): neighbors = [] if x>=0 and x<len(lines[y-1]) and y-1>=0 and y-1<len(lines): if not lines[y-1][x].isspace(): neighbors.append( (x,y-1) ) if x-1>=0 and x-1<len(lines[y]) and y>=0 and y<len(lines): if not lines[y][x-1].isspace(): neighbors.append( (x-1,y) ) if x+1>=0 and x+1<len(lines[y]) and y>=0 and y<len(lines): if not lines[y][x+1].isspace(): neighbors.append( (x+1,y) ) if x>=0 and x<len(lines[y+1]) and y+1>=0 and y+1<len(lines): if not lines[y+1][x].isspace(): neighbors.append( (x,y+1) ) mydict[(x,y)] = [ lines[y][x], neighbors ] if len( neighbors ) == 1: startend.append( (x,y) ) startend.sort( key=lambda x : x[0]*x[0] + x[1]*x[1] ) last = startend[0] sys.stdout.write( mydict[ last ][0] ) current = mydict[last][1][0] while len( mydict[current][1] ) > 1: sys.stdout.write( mydict[current][0] ) for k in range( 0, len( mydict[current][1] ) ): if mydict[current][1][k] != last: last = current current = mydict[current][1][k] break print(mydict[current][0])  • I saved 12 bytes by introducing S=lambda s:s.isspace() and then doing S(s) instead of s.isspace(). – porglezomp Apr 9 '16 at 19:41 • I think you can also change all of your and  to <, since f() < g() < h() is the same as g = g(); f() < g and g < h() in terms of side effects (comparison chains short circuit), and you're ignoring the result of the comparisons anyway. – porglezomp Apr 9 '16 at 19:48 • m[(x,y)]= is the same as the shorter m[x,y]= – porglezomp Apr 9 '16 at 20:01 • @porglezomp: it's even shorter to say S=str.isspace – Aleksi Torhamo Apr 10 '16 at 14:08 • Removing S and instead using <'!' in every occurrence can be the same length, possibly opening an opportunity to save more. Changing if 1-S(v[x]): to if(v[x]<'!')<1:, for example. And maybe you could remove some parentheses in the later comparisons by doing it that way. – mbomb007 Sep 30 '16 at 14:03 # JavaScript (ES6), 195 See explanation inside the test snippet s=>[...s].map((c,i)=>{if(c>' '&([n=-1,1,o=-~s.search('\n'),-o].map(d=>n+=s[i+d]>' '&&!!(e=d)),n<1)&m>(w=i/o+i%o|0))for(m=w,r=c,p=i+e;r+=s[i=p],[e,o/e,-o/e].some(d=>s[p=i+(e=d)]>' '););},m=1/0)&&r  Test f=s=>[...s].map((c,i)=>{if(c>' '&([n=-1,1,o=-~s.search('\n'),-o].map(d=>n+=s[i+d]>' '&&!!(e=d)),n<1)&m>(w=i/o+i%o|0))for(m=w,r=c,p=i+e;r+=s[i=p],[e,o/e,-o/e].some(d=>s[p=i+(e=d)]>' '););},m=1/0)&&r // Less golfed u=s=>( o = -~s.search('\n'), // offset between lines m = 1/0, // current min manhattan distance, init at infinity // scan input looking for the 2 ends of the string [...s].map((c,i)=>{ // for each char c at position i if(c > ' ' // check if part of the string & ( [-1,1,o,-o] // scan in 4 directions and count neighbors .map(d=> n+=s[i+d]>' '&&!!(e=d), n=0), // remember direction in e n < 2) // if at end of string will have exactly 1 neighbor & (w = i/o + i%o |0) < m) // manhattan distance in w, must be less than current min // found one of the ends, follow the path and build the string in r for(m = w, r = c, p = i+e; r += s[i=p], [e,o/e,-o/e] // check 3 directions, avoiding to go back .some(d=>s[p=i+(e=d)]>' '); // save candidate position and direction in p and e ); // empty for body, all the work is inside the condition }), r ) console.log=x=>O.textContent+=x+'\n' ;[Hel l rin o,IAmASt g S !ekan,  ~ zyx tsr XWVUTSR }|{ wvu q Y Q ! p Z \ab P "#$ 6789:; o [ _ c O
% 5    < n \\]^ d N
('& 432  = m     e M
)     1  > lkjihgf L
*+,-./0  ?         K
@ABCDEFGHIJ].forEach(t=>{
console.log(t+'\n\n'+f(t)+'\n')
})
<pre id=O></pre>

• Are the semicolons in ););} needed? – Cees Timmerman Sep 29 '16 at 22:02
• @CeesTimmerman yes. The first is inside the for header where 2 colons are needed. The second is the delimeter for the for body – edc65 Sep 30 '16 at 6:40

## Lua, 562535529513507504466 458 Bytes

By far my most massive golf at the moment, I think I can still cut off 100 bytes, which I'll work toward, but posting it as an answer as it already took some time :). I was right, I've cutted down more than 100 bytes! I don't think there's lot of room for improvement.

this function have to be called with a 2D array containing one character per cell.

Saved 40 bytes while working with @KennyLau, thanks to him!

Woohoo! Under 500!

function f(m)t=2u=1i=1j=1s=" "::a::if s~=m[i][j]and(i<#m and m[i+1][j]~=s)~=(j<#m[i]and m[i][j+1]~=s)~=(i>1 and m[i-1][j]~=s)~=(j>1 and m[i][j-1]~=s)then goto b end
i,t=i%t+1,#m>t and t==i and t+1or t j=j>1 and j-1or u u=u<#m[1]and j==1 and u+1or u goto a::b::io.write(m[i][j])m[i][j]=s
i,j=i<#m and s~=m[i+1][j]and i+1or i>1 and s~=m[i-1][j]and i-1or i,j<#m[i]and s~=m[i][j+1]and j+1or j>1 and s~=m[i][j-1]and j-1or j
if s==m[i][j]then return end goto b end


## Ungolfed

Explanations will come once I'm done golfing this, for the moment, i'll lend you a readable version of this source code :D Here comes the explanations!

Edit: not updated with the latest modification, still golfing before updating. Same goes for the explanations

function f(m)                    -- declare the function f which takes a matrix of characters
t=2                            -- initialise the treshold for i
-- when looking for the first end of the snake
u=1                            -- same thing for j
i,j=1,1                        -- initialise i and j,our position in the matrix
s=" "                          -- shorthand for a space
::a::                          -- label a, start of an infinite loop
if m[i][j]~=s                -- check if the current character isn't a space
and(i<#m                   -- and weither it is surrounded by exactly
and m[i+1][j]~=s)      -- 3 spaces or not
~=(j<#m[i]
and m[i][j+1]~=s)      -- (more explanations below)
~=(i>1
and m[i-1][j]~=s)
~=(j>1
and m[i][j-1]~=s)
then goto b end            -- if it is, go to the label b, we found the head
i,t=                         -- at the same time
i%t+1,                     -- increment i
#m>t and t==i and t+1or t  -- if we checked all chars in the current range, t++
j=j>1 and j-1or u            -- decrement j
u=u>#m[1]and j==1 and u+1or u-- if we checked all chars in the current range, u++
goto a                         -- loop back to label a

::b::                          -- label b, start of infinite loop
io.write(m[i][j])                    -- output the current char
m[i][j]=s                    -- and set it to a space
i,j=i<#m                     -- change i and j to find the next character in the snake
and m[i+1][j]~=s       -- this nested ternary is also explained below
and i+1              -- as it takes a lot of lines in comment ^^'
or i>1
and m[i-1][j]~=s
and i-1
or i,
j<#m[i]
and m[i][j+1]~=s
and j+1
or j>1
and m[i][j-1]~=s
and j-1
or j
if m[i][j]==s                -- if the new char is a space
then                         -- it means we finished
return                  -- exit properly to avoid infinite
end                          -- printing of spaces
goto b                         -- else, loop back to label b
end


So here comes some detailed explanations about how this program works.

First of all, let's consider the loop labeled a, it allows us to find the closest end to the top-left corner. It will loop forever if there's no end, but that's not a problem :D.

On a 4x4 grid, it here are the snake distances(left), and the order they are looked at (right)

1  2  3  4    |     1  2  4  7
2  3  4  5    |     3  5  8 11
3  4  5  6    |     6  9 12 14
4  5  6  7    |    10 13 15 16


For each of this character, to be the end, it have to check two conditions: - Not being a space - Being surrounded by exactly 3 spaces (or exactly 1 non-space)

These conditions are checked the following piece of code

r=m[i][j]~=s
and(i<#m and m[i+1][j]~=s)
==not(j<#m[i] and m[i][j+1]~=s)
==not(i-1>0 and m[i-1][j]~=s)
==not(j-1>0 and m[i][j-1]~=s)
and m[i][j]
or r
-- special note: "==not" is used as an equivalent to xor
-- as Lua doesn't know what is a xor...


Checking if the char isn't a space is achieved by the expression m[i][j]~=s.

Checking if w're surrounded by only 1 non-space is achived by xor-ing the above conditions for our surrounding, this could be written as

m[i+1][j]~=" " ⊕ m[i][j+1]~=" " ⊕ m[i-1][j]~=" " ⊕ m[i][j-1]~=" "


And finally, if all the above is evaluated to true, the ternary will return what's in the last and -> m[i][j]. Else , we let r unset :)

Now that we have the head of the snake, let's get all the way to the other end! Iterating the snake is mainly achieved by the following nested ternaries:

i,j=i<#m and m[i+1][j]~=s and i+1or i-1>0 and m[i-1][j]~=s and i-1or i,
j<#m[i]and m[i][j+1]~=s and j+1or j-1>0 and m[i][j-1]~=s and j-1or j


We re-set i and j at the same time to avoid needing dummies to store the old values They both have the exact same structure, and use simple conditions, so I'll present them in the form of nested if, it should allow you to read them more easily. :)

i=i<#m and m[i+1][j]~=s and i+1or i-1>0 and m[i-1][j]~=s and i-1or i


Can be translated to:

if(i<#m)
then
if(m[i+1][j]~=" ")
then
i=i+1
end
elseif(i-1>0)
then
if(m[i-1][j]~=" ")
then
i=i-1
end
end


### Test it!

Here's the code I use to run this, you can test it online by copy-pasting it.

function f(m)t=2u=1i=1j=1s=" "::a::if s~=m[i][j]and(i<#m and m[i+1][j]~=s)~=(j<#m[i]and m[i][j+1]~=s)~=(i>1 and m[i-1][j]~=s)~=(j>1 and m[i][j-1]~=s)then goto b end
i,t=i%t+1,#m>t and t==i and t+1or t j=j>1 and j-1or u u=u<#m[1]and j==1 and u+1or u goto a::b::io.write(m[i][j])m[i][j]=s
i,j=i<#m and s~=m[i+1][j]and i+1or i>1 and s~=m[i-1][j]and i-1or i,j<#m[i]and s~=m[i][j+1]and j+1or j>1 and s~=m[i][j-1]and j-1or j
if s==m[i][j]then return end goto b end

test1={}
s1={
"  tSyrep    ",
"  r    p    ",
"  in Sli    ",
"   g    Sile",
"   Snakes  n",
"Ser      ylt",
"a eh   ilS  ",
"fe w   t    ",
"   emo h    ",
"     Sre    ",
}
for i=1,#s1
do
test1[i]={}
s1[i]:gsub(".",function(c)test1[i][#test1[i]+1]=c end)
end
f(test1)

• A have a soft spot for longer answers that have little to now choice because of the language choice. – Matt Apr 7 '16 at 16:25
• @Matt thanks a lot for the support! actually, i'm still finding ways to golf this down, but it's getting harder and harder! – Katenkyo Apr 7 '16 at 16:31

## Lua, 267 bytes

Lua 5.3 is required.

e=" "w=#arg[1]+1i=1/0q=0s=table.concat(arg,e)s=e:rep(#s)..s
m,n=i,{}for p in s:gmatch"()%g"do u=-1
for _,d in ipairs{-1,1,-w,w}do u=u+(s:find("^%S",d+p)or 0)end
n[p]=u+1m=math.min(m,p*i^(u//#s)+(p%w*w+p)*#s)end
p=m%#s repeat q,p=p,n[p]-q io.write(s:sub(q,q))until p<1


Usage:

$lua desnakify.lua \ > " tSyrep " \ > " r p " \ > " in Sli " \ > " g Sile" \ > " Snakes n" \ > "Ser ylt" \ > "a eh ilS " \ > "fe w t " \ > " emo h " \ > " Sre " SlipperyStringSnakesSilentlySlitherSomewhereSafe  # Python 3, 245243241 236 bytes s is the input string, n is the output printed to stdout: f=s.find w,l=f('\n')+1,len(s) t=1,w,-1,-w y=z=f(s.strip()[0]);n=s[y];v={y} for i in range(l*l): i%=l;c=s[i] if c>' 'and i not in v: if i-y in t:y=i;n=c+n;v|={i} elif i-z in t:z=i;n+=c;v|={i} if y%w+y//w>z%w+z//w:n=n[::-1] print(n)  Edit: Thanks to @Cees Timmerman for saving 5 bytes! • c>' 'and and print n in Python 2. – Cees Timmerman Oct 3 '16 at 8:19 • Can't you do if instead of elif? – clismique Oct 3 '16 at 9:31 • @Qwerp-Derp unfortunately not, I have tried it before, but it prints, for example "!ekanSgnirtSAmAI,olleHello,IAmAStringSnake!" and "SlipperyStSyreppilS". – pgks Oct 3 '16 at 9:37 • What's the input format? – clismique Oct 3 '16 at 9:41 • @Qwerp-Derp s variable is a multiline string; the last character of the string must be a newline (this is necessary to pass the Python test case) – pgks Oct 3 '16 at 9:47 ## Python, 537 My initial solution: from itertools import chain, product, ifilter from operator import add moves = ((1,0),(0,1),(-1,0),(0,-1)) h = dict(ifilter(lambda (p,v):not v.isspace(),chain(*map(lambda (i,r):map(lambda (j,c):((i,j),c),enumerate(r)),enumerate(s))))) n = defaultdict(list) for m,p in product(moves, h): np = tuple(map(add,m,p)) if np in h: n[p].append(np) def pr(nx): return(lambda l:(h[l[0]], h.pop(l[0]))[0] + pr(l[0]) if l else '')([x for x in n[nx] if x in h]) (lambda y: h[y]+ pr(y))(next(x for x in n if len(n[x])==1))  Compacted a bit, but left it as a method: from itertools import chain, product from operator import add def unsnake(s): (h,n) = (dict(filter(lambda (p,v):not v.isspace(),chain(*map(lambda (i,r):map(lambda (j,c):((i,j),c),enumerate(r)),enumerate(s))))),defaultdict(list)) for m,p in product(((1,0),(0,1),(-1,0),(0,-1)), h):(lambda np: n[p].append(np) if np in h else 0)(tuple(map(add,m,p))) def pr(nx):return(lambda l:(h[l[0]], h.pop(l[0]))[0] + pr(l[0]) if l else '')([x for x in n[nx] if x in h]) return(lambda y: h[y]+ pr(y))(next(x for x in n if len(n[x])==1))  # Java 7, 927924 923 bytes import java.util.*;int l,k;char[][]z;Set p=new HashSet();String c(String[]a){int x=0,y=0,n,t,u,v,w=t=u=v=-1;l=a.length;k=a[0].length();z=new char[l][k];for(String s:a){for(char c:s.toCharArray())z[x][y++]=c;}x++;y=0;}for(x=0;x<l;x++)for(y=0;y<k;y++){n=0;if(z[x][y]>32){if(x<1|(x>0&&z[x-1][y]<33))n++;if(y<1|(y>0&&z[x][y-1]<33))n++;if(x>l-2|(x<l-1&&z[x+1][y]<33))n++;if(y>k-2|(y<k-1&&z[x][y+1]<33))n++;}if(n>2&t<0){t=x;u=y;}if(n>2&t>v){v=x;w=y;}}if(v+w>t+u){p(t,u);return n(""+z[t][u],t,u);}p(v,w);return n(""+z[v][w],v,w);}String n(String r,int x,int y){int a,b;if(x>0&&z[a=x-1][b=y]>32&q(a,b)){p(a,b);return n(r+z[a][b],a,b);}if(y>0&&z[a=x][b=y-1]>32&q(a,b)){p(a,b);return n(r+z[a][b],a,b);}if(x<l-1&&z[a=x+1][b=y]>32&q(a,b)){p(a,b);return n(r+z[a][b],a,b);}if(y<k-1&&z[a=x][b=y+1]>32&q(a,b)){p(a,b);return n(r+z[a][b],a,b);}return r;}boolean q(int x,int y){return!p.contains(x+","+y);}void p(int x,int y){p.add(x+","+y);}  Ok, that took a while.. In some programming languages it doesn't matter if your array x and y are outside the boundaries of a 2D-array, but with Java it'll throw ArrayIndexOutOfBoundsExceptions, so everything has to be checked.. I first determine the starting point, and then use a recursive method to build the string from there. In addition, I use a list to keep track of the coordinations I've already encountered, so it won't go into a loop back-forth-back-forth (resulting in a StackOverflowException). This is probably the longest answer I've posted so far, but although some parts can be golfed, I don't think this challenge can be that much shorter in Java. Java just isn't suitable for following a path in a grid.. It was a fun challenge to figure out nonetheless. :) Ungolfed & test cases: Try it here. import java.util.*; class M{ static int l, k; static char[][] z; static Set p = new HashSet(); static String c(String[] a){ int x=0, y=0, n, t, u, v, w = t = u = v = -1; l = a.length; k = a[0].length(); z = new char[l][k]; for(String s:a){ for(char c:s.toCharArray()){ z[x][y++] = c; } x++; y = 0; } for(x=0; x<l; x++){ for(y=0; y<k; y++){ n = 0; if(z[x][y] > 32){ // [x,y] is not a space if(x < 1 | (x > 0 && z[x-1][y] < 33)){ n++; } if(y < 1 | (y > 0 && z[x][y-1] < 33)){ n++; } if(x > l-2 | (x < l-1 && z[x+1][y] < 33)){ n++; } if(y > k-2 | (y < k-1 && z[x][y+1] < 33)){ n++; } } if(n > 2 & t < 0){ t = x; u = y; } if(n > 2 & t > v){ v = x; w = y; } } } if(v+w > t+u){ p(t, u); return n(""+z[t][u], t, u); } p(v, w); return n(""+z[v][w], v, w); } static String n(String r, int x, int y){ int a,b; if(x > 0 && z[a=x-1][b=y] > 32 & q(a,b)){ p(a, b); return n(r+z[a][b], a, b); } if(y > 0 && z[a=x][b=y-1] > 32 & q(a,b)){ p(a, b); return n(r+z[a][b], a, b); } if(x < l-1 && z[a=x+1][b=y] > 32 & q(a,b)){ p(a, b); return n(r+z[a][b], a, b); } if(y < k-1 && z[a=x][b=y+1] > 32 & q(a, b)){ p(a, b); return n(r+z[a][b], a, b); } return r; } static boolean q(int x, int y){ return !p.contains(x+","+y); } static void p(int x, int y){ p.add(x+","+y); } public static void main(String[] a){ System.out.println(c(new String[]{ "Hel ", " l rin", " o,IAmASt g", " S", " !ekan" })); p = new HashSet(); System.out.println(c(new String[]{ "Python" })); p = new HashSet(); System.out.println(c(new String[]{ "P ngPu Code ", "r i z d G", "o m z n o", "gram lesA lf" })); p = new HashSet(); System.out.println(c(new String[]{ " ~ zyx tsr XWVUTSR", " }|{ wvu q Y Q", "! p Z ab P", "\"#$ 6789:; o [ _ c O",
"  % 5    < n \\]^ d N",
"('& 432  = m     e M",
")     1  > lkjihgf L",
"*+,-./0  ?         K",
"         @ABCDEFGHIJ" }));
p = new HashSet();
System.out.println(c(new String[]{ "  tSyrep    ",
"  r    p   ",
"  in Sli   ",
"   g    Sile",
"   Snakes  n",
"Ser      ylt",
"a eh   ilS ",
"fe w   t   ",
"   emo h   ",
"     Sre    " }));
}
}


Output:

Hello,IAmAStringSnake!
Python
ProgrammingPuzzlesAndCodeGolf
!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_abcdefghijklmnopqrstuvwxyz{|}~ SlipperyStringSnakesSilentlySlitherSomewhereSafe  • 924 bytes, jesus christ... lol – Shaun Wild Sep 30 '16 at 12:03 • @BasicallyAlanTuring Hehe. I simply made the challenge, code-golfed it, and then looked at the byte-count. Was indeed a lot higher than expected, but ah well, at least it's below 1k... If you see anything to improve let me know, and if you have an alternative approach with (a lot) less bytes feel free to make a separate post; I'd be interested to see it. PS: It's now 923 bytes. XD – Kevin Cruijssen Sep 30 '16 at 12:54 • No need to check everythig, just add some padding to your string. Probably using a single multiline string makes that easier. Have a look to my C# answer ported from javascript – edc65 Sep 30 '16 at 15:29 ## PHP, 199184 182 bytes may still have a little golfing potential for($w=strpos($i=$argv[1],"
");;)for($y=++$n;$y--;)if($i[$p=$y*$w+$n-1]>" ")break 2;for($p-=$d=$w++;$d&&print$i[$p+=$e=$d];)foreach([-$w,-1,1,$w,0]as$d)if($d+$e&&" "<$i[$d+$p])break;


takes input as multiline string from command line, expects linux style linebreaks.
Run php -r '<code>' '<string>'; escape linebreaks.

breakdown

for(
// find width
$w=strpos($i=$argv[1],"\n") ; // find first character: initialize$p(osition)
;
)
for($y=++$n             // increase distance
;$y--;) // loop$y from (old)$n to 0 if(" "<$i[$p=$y*$w+$n   // if character at $y*($width+1)+$x(=$d-$y) is no space -1 // (adjust for the premature increment) ]) break 2; // break loops for($p-=            // b) reverse the increment that follows in the pre-condition
$d= // a) initialize$d to anything!=0 to enable the first iteration
$w++; // c) increase$w for easier directions
$d // loop while direction is not 0 (cursor has moved) && print$i[$p+=$e=$d] // remember direction, move cursor, print character ; ) foreach([-$w,-1,1,$w,0]as$d)// loop through directions
if($d+$e                    // if not opposite previous direction
&&" "<$i[$d+\$p]         // and character in that direction is not space
)break;                     // break this loop


# C#, 310

(Edit: bug fix)

A function with a multiline string parameter, returning a string.

Including the requested using in the byte count.

This is a porting of my javascript answer.

using System.Linq;
string f(string s){int o=-~s.IndexOf('\n'),m=99;var r=new string(' ',o);(s=r+s+r).Select((c,i)=>{int n=2,e=0,p,w=i%o+i/o;if(c>' '&w<m&&new[]{-1,1,o,-o}.All(d=>(s[i+d]>' '?(e=d)*--n:n)>0))for(m=w,r=""+c+s[p=i+e];new[]{e,o/e,-o/e}.Any(d=>s[p+(e=d)]>' ');)r+=s[p+=e];return i;}).Max();return r;}


Test on ideone

With spaces

    string f(string s)
{
int o = -~s.IndexOf('\n');
var r = new string(' ', o);
var m = 99;
(s = r + s + r).Select((c, i) =>
{
int n = 2, e = 0, p, w = i % o + i / o;
if (c > ' ' & w < m & new[] { -1, 1, o, -o }.All(d => (s[i + d] > ' ' ? (e = d) * --n : n) > 0))
for (m = w, r = "" + c + s[p = i + e];
new[] { e, o / e, -o / e }.Any(d => s[p + (e = d)] > ' ');
)
r += s[p += e];
return i;
}
).Max();
return r;
}


# Python 2, 251 bytes

w=s.find('\n')+1;q=' ';p=q*w+'\n';s=list(p+s+p);d=-w,1,w,-1
def r(x):c=s[x];s[x]=q;v=[c+r(x+o)for o in d if s[x+o]>q];return v[0]if v else c
e=[x for x in range(len(s))if s[x]>q and sum([s[x+o]>q for o in d])<2]
print r(e[e[0]/w+e[0]%w>e[1]/w+e[1]%w])


w=s.find('\n',1);q=' ';p=q*-~w+'\n';s=list(p+s[1:]+p);d=-w,1,w,-1
def r(x):c=s[x];s[x]=q;v=[c+r(x+o)for o in d if s[x+o]>q];return v[0]if v else c
e=[x for x in range(len(s))if s[x]>q and sum([s[x+o]>q for o in d])<2]
print r(e[e[0]/w+e[0]%w>e[1]/w+e[1]%w])


Passes all testcases.

s="""
tSyrep
r    p
in Sli
g    Sile
Snakes  n
Ser      ylt
a eh   ilS
fe w   t
emo h
Sre
"""


Results in:

SlipperyStringSnakesSilentlySlitherSomewhereSafe

• I think you can replace b.append(...) with b+=[...] and def n(x,y):return ... with n=lambda x,y:... – acrolith Sep 29 '16 at 20:59
• Create a variable for ' '. – pacholik Oct 1 '16 at 14:53
• and use ~-x instead of x-1, you won't have to use parentheses. – pacholik Oct 1 '16 at 14:58

# Japt-P, 106 bytes

K=U·ÌÊÄ ç iU ¬mx T=[-KJ1K]
ËÊ*Tm+E è@gX
[]V£YÃf@gXÃrQ@WpQ Tm+Q kW fZ Ì}V£[XYuK YzK]ÃkÈv ÉÃñx v rÈ+Y*K
W£gX


Try it online!

It's... um... an abomination.

### Unpacked & How it works

K=UqR gJ l +1 ç iU q mx
UqR gJ l +1            Split the input by newline, take last item's length +1
K=                       Assign to K
ç iU       Generate a string of K spaces, and append to U
q mx  Split into chars, and trim whitespaces on each item
Implicit assign to U

T=[-KJ1K]  Assign an array [-K, -1, 1, K] to T (this represents 4-way movement)
I could use implicit assignment, but then 4-argument function below is broken

UmDEF{Dl *Tm+E èXYZ{UgX
UmDEF{                   Map over the list of one- or zero-length strings...
Dl *                 If the length is zero, return zero
Tm+E             Add the index to each element of T
èXYZ{UgX    Count truthy elements at these indices
The result is an array of 0(space/newline), 1(start/end), or 2(body)
Implicit assign to V

[]  Implicit assign to W

VmXYZ{Y} fXYZ{UgX} rQXYZ{WpQ Tm+Q kW fZ gJ }
VmXYZ{Y}                                      Map V into indices
fXYZ{UgX}                            Filter the indices by truthiness of U's element
rQXYZ{                     Reduce on the indices... (Q=last item, Z=array)
WpQ                    Push Q to W
Tm+Q               Take 4-way movements from Q
kW fZ gJ }    Exclude visited ones, take last one in Z

VmXYZ{[XYuK YzK]} kXYZ{Xv -1} ñx v rXYZ{X+Y*K  Starting point of reduce
VmXYZ{[XYuK YzK]}                              Convert elements of V to [elem, col, row]
kXYZ{Xv -1}                  Take the ones where elem(popped)=1
ñx v             Sort by row+col and take first one
rXYZ{X+Y*K  Convert [row,col] back to the index

WmXYZ{UgX  Map indices back to chars

-P  Join with empty string


One notable point is that I used the operator precedence between assignment and comma operators in JS, in order to pack some lines and keep the shortcut @ (XYZ{`) usable.