A regular string looks like this:


And a string snake looks something like this:

  l      rin
  o,IAmASt g

Your Task

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


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

  l      rin
  o,IAmASt g






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



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

  • 23
    \$\begingroup\$ Fun Fact: According to the linked Wikipedia article, Manhattan distance is also known as snake distance! \$\endgroup\$
    – user81655
    Commented Apr 7, 2016 at 10:22
  • \$\begingroup\$ Would an input like hastebin.com/asugoropin.vbs be correct ? \$\endgroup\$
    – THC
    Commented Apr 7, 2016 at 11:35
  • \$\begingroup\$ @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. \$\endgroup\$
    – user81655
    Commented Apr 7, 2016 at 11:51
  • \$\begingroup\$ Can the input be a two-dimensional array (i.e each character as an element) ? \$\endgroup\$
    – THC
    Commented Apr 7, 2016 at 12:24
  • 32
    \$\begingroup\$ Surely this puzzle needs an answer in python? \$\endgroup\$
    – abligh
    Commented Apr 7, 2016 at 22:51

17 Answers 17


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


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']
['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!


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
  • \$\begingroup\$ I shall assume an explanation is forthcoming? \$\endgroup\$
    – Matt
    Commented Apr 7, 2016 at 16:19
  • \$\begingroup\$ @Matt Sure... later in the day :-) \$\endgroup\$
    – Luis Mendo
    Commented Apr 7, 2016 at 16:19
  • \$\begingroup\$ Explanation added @Matt \$\endgroup\$
    – Luis Mendo
    Commented Apr 7, 2016 at 19:02
  • \$\begingroup\$ 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! \$\endgroup\$ Commented Apr 8, 2016 at 11:46
  • \$\begingroup\$ @LevelRiverSt Thank you! Corrected \$\endgroup\$
    – Luis Mendo
    Commented Apr 8, 2016 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 */


  char b[m<<8],*e=b,*a=e+m;

  /* This reads the input array into the 256x103 array */


  /* 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. */


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

  • 1
    \$\begingroup\$ This answer is great. \$\endgroup\$
    – abligh
    Commented Apr 8, 2016 at 6:03
  • \$\begingroup\$ +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? \$\endgroup\$
    – mIllIbyte
    Commented Apr 8, 2016 at 8:11
  • \$\begingroup\$ mIllIbyte - feel free to add the comments, that's the road towards new ideas. \$\endgroup\$
    – Zunga
    Commented Apr 8, 2016 at 12:42
  • \$\begingroup\$ 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. \$\endgroup\$
    – Zunga
    Commented Apr 8, 2016 at 12:49
  • \$\begingroup\$ Very nice. Save some more with a[1], a[-m] etc, and making m global - m=103;main(). \$\endgroup\$
    – ugoren
    Commented Apr 8, 2016 at 14:54

APL, 55 bytes

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

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


      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 


  • (,⍵≠' ')/,⍳⍴⍵: 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
  • 2
    \$\begingroup\$ fails at the last test: SlipperyStr.. \$\endgroup\$
    – ngn
    Commented Sep 17, 2020 at 2:28

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?

#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;
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(t=p=4;p--;)t-=X(E);  //a ton of bytes can be saved with determining 
  //the neighbors, see @Zunga's source
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(c=0,p=4;!c*p--;)  //determining the neighbors again

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):
 for x in r(f):
  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))
while o(m[c][1])>1:
 for k in r(o(b)):
  if b[k]!=t:t=c;c=b[k];break

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]

  • 1
    \$\begingroup\$ I saved 12 bytes by introducing S=lambda s:s.isspace() and then doing S(s) instead of s.isspace(). \$\endgroup\$
    – porglezomp
    Commented Apr 9, 2016 at 19:41
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – porglezomp
    Commented Apr 9, 2016 at 19:48
  • 1
    \$\begingroup\$ m[(x,y)]= is the same as the shorter m[x,y]= \$\endgroup\$
    – porglezomp
    Commented Apr 9, 2016 at 20:01
  • 2
    \$\begingroup\$ @porglezomp: it's even shorter to say S=str.isspace \$\endgroup\$ Commented Apr 10, 2016 at 14:08
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – mbomb007
    Commented Sep 30, 2016 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


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

  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


  l      rin
  o,IAmASt g
 `   ~ 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
<pre id=O></pre>

  • \$\begingroup\$ Are the semicolons in ););} needed? \$\endgroup\$ Commented Sep 29, 2016 at 22:02
  • 1
    \$\begingroup\$ @CeesTimmerman yes. The first is inside the for header where 2 colons are needed. The second is the delimeter for the for body \$\endgroup\$
    – edc65
    Commented Sep 30, 2016 at 6:40

APL (Dyalog Unicode), 59 bytes

{⍵[i][{⍵∪⍸∨⌿g[⍵;]}⍣≡,j⊃⍨⊃⍋+/↑i[j←⍸≠/g←1=+/|↑∘.-⍨i←⍸' '≠⍵]]}

Try it online!


Lua, 562 535 529 513 507 504 466 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


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
          and m[i][j+1]~=s)      -- (more explanations below)
          and m[i-1][j]~=s)
          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,
         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

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

    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(m[i+1][j]~=" ")
  if(m[i-1][j]~=" ")

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

"  tSyrep    ",
"  r    p    ",
"  in Sli    ",
"   g    Sile",
"   Snakes  n",
"Ser      ylt",
"a eh   ilS  ",
"fe w   t    ",
"   emo h    ",
"     Sre    ",
for i=1,#s1
  s1[i]:gsub(".",function(c)test1[i][#test1[i]+1]=c end)
  • 1
    \$\begingroup\$ A have a soft spot for longer answers that have little to now choice because of the language choice. \$\endgroup\$
    – Matt
    Commented Apr 7, 2016 at 16:25
  • \$\begingroup\$ @Matt thanks a lot for the support! actually, i'm still finding ways to golf this down, but it's getting harder and harder! \$\endgroup\$
    – Katenkyo
    Commented Apr 7, 2016 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
p=m%#s repeat q,p=p,n[p]-q io.write(s:sub(q,q))until p<1


$ lua desnakify.lua \
>    "  tSyrep    " \
>    "  r    p    " \
>    "  in Sli    " \
>    "   g    Sile" \
>    "   Snakes  n" \
>    "Ser      ylt" \
>    "a eh   ilS  " \
>    "fe w   t    " \
>    "   emo h    " \
>    "     Sre    "

Python 3, 245 243 241 236 bytes

s is the input string, n is the output printed to stdout:

for i in range(l*l):
 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]

Edit: Thanks to @Cees Timmerman for saving 5 bytes!

  • \$\begingroup\$ c>' 'and and print n in Python 2. \$\endgroup\$ Commented Oct 3, 2016 at 8:19
  • \$\begingroup\$ Can't you do if instead of elif? \$\endgroup\$
    – clismique
    Commented Oct 3, 2016 at 9:31
  • \$\begingroup\$ @Qwerp-Derp unfortunately not, I have tried it before, but it prints, for example "!ekanSgnirtSAmAI,olleHello,IAmAStringSnake!" and "SlipperyStSyreppilS". \$\endgroup\$
    – pgks
    Commented Oct 3, 2016 at 9:37
  • \$\begingroup\$ What's the input format? \$\endgroup\$
    – clismique
    Commented Oct 3, 2016 at 9:41
  • \$\begingroup\$ @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) \$\endgroup\$
    – pgks
    Commented Oct 3, 2016 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:
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, 927 924 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,
  static char[][] z;
  static Set p = new HashSet();

  static String c(String[] a){
    int x=0,
        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;
      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)){
          if(y < 1 | (y > 0 && z[x][y-1] < 33)){
          if(x > l-2 | (x < l-1 && z[x+1][y] < 33)){
          if(y > k-2 | (y < k-1 && z[x][y+1] < 33)){
        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){

  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    " }));


  • \$\begingroup\$ 924 bytes, jesus christ... lol \$\endgroup\$
    – Shaun Wild
    Commented Sep 30, 2016 at 12:03
  • \$\begingroup\$ @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 \$\endgroup\$ Commented Sep 30, 2016 at 12:54
  • \$\begingroup\$ 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 \$\endgroup\$
    – edc65
    Commented Sep 30, 2016 at 15:29

PHP, 199 184 182 bytes

may still have a little golfing potential

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


    // find width
    // 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

    $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;
        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])

Or, if you want leading newlines in your testcases, 257 bytes:

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.

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

Results in:

  • 3
    \$\begingroup\$ I think you can replace b.append(...) with b+=[...] and def n(x,y):return ... with n=lambda x,y:... \$\endgroup\$
    – acrolith
    Commented Sep 29, 2016 at 20:59
  • 1
    \$\begingroup\$ Create a variable for ' '. \$\endgroup\$
    – pacholik
    Commented Oct 1, 2016 at 14:53
  • 1
    \$\begingroup\$ and use ~-x instead of x-1, you won't have to use parentheses. \$\endgroup\$
    – pacholik
    Commented Oct 1, 2016 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

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.