Zwykły ciąg wygląda następująco:

Hello,IAmAStringSnake!

A wąż strunowy wygląda mniej więcej tak:

Hel         
  l      rin
  o,IAmASt g
           S
       !ekan

Twoje zadanie

Węże łańcuchowe są niebezpieczne, więc musisz stworzyć program, który pobiera łańcuch węża jako dane wejściowe i wyprowadza go jako zwykły łańcuch.

Dane techniczne

• Dane wejściowe mogą być ciągiem wieloliniowym lub tablicą ciągów.
• Każda linia danych wejściowych zostanie wypełniona spacjami, tworząc prostokątną siatkę.
• Postacie w wężu mogą łączyć się tylko z sąsiednimi postaciami powyżej, poniżej, po lewej lub prawej stronie (tak jak w grze Snake). Nie mogą iść po przekątnej.
• Postacie węża nigdy nie będą sąsiadować z inną częścią węża, tylko z połączonymi postaciami.
• Pierwszy znak ciągu to znak końcowy o najkrótszej odległości na Manhattanie od lewego górnego rogu siatki wejściowej (tj. Minimalna liczba ruchów, których zajęłoby wąż, aby przejść bezpośrednio od znaku końcowego do lewego górnego rogu kąt). Oba końce nigdy nie będą miały takiej samej odległości.
• Ciąg może zawierać dowolny znak ASCII między punktami kodu 33 i 126 włącznie (bez spacji i znaków nowej linii).
• Ciąg będzie miał od 2 do 100 znaków.
• Najkrótszy kod w bajtach wygrywa.

Przypadki testowe

(Siatka wejściowa, a po niej ciąg wyjściowy)

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

APL, 55 bajtów

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

Ta funkcja pobiera macierz znaków z wężem łańcucha.

Przykład:

      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{|}~

Wyjaśnienie:

• (,⍵≠' ')/,⍳⍴⍵: uzyskaj współrzędne wszystkich spacji
• (⊂0 0): zaczyna się od (0,0) (która jest nieprawidłową współrzędną)
• {... }: podążaj za wężem, podaną pozycją i wężem:
  • 1<⍴⍵:: jeśli pozostało więcej niż 1 element:
    • ∆←⍵~⍺: usuń bieżącą pozycję z węża i zapisz ją ∆.
    • +/¨|⍺-∆: znajdź odległość między bieżącą pozycją a każdym punktem w pozostałej części węża
    • ∆[⊃⍋...] `: zdobądź najbliższy punkt węża
    • ∇: uruchom ponownie funkcję, z najbliższym punktem jako nowym bieżącym punktem i skróconym wężem jako nowym wężem.
    • ⍺,: dodaj bieżącą pozycję do wyniku
  • ⋄⍺: w przeciwnym razie po prostu zwróć bieżącą pozycję
• 1↓: upuść pierwszy element z wyniku (czyli pozycję (0,0))
• ⍵[... ]: pobierz te elementy z ⍵, w tej kolejności

JavaScript (ES6) + SnakeEx , 176 bajtów

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,"")

Pamiętasz SnakeEx? Dobrze, bo ja też nie! Sugestie dotyczące gry w golfa mile widziane.

MATL , 80 bajtów

Dzięki @LevelRiverSt za korektę

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

Dane wejściowe są w postaci tablicy znaków 2D z wierszami oddzielonymi ;. Przypadki testowe w tym formacie to

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

Wypróbuj online!

Wyjaśnienie

Współrzędne każdego znaku spacji są reprezentowane przez liczbę zespoloną. Dla każdej bieżącej postaci otrzymywany jest następny jako najbliższy (minimalna bezwzględna różnica ich złożonych współrzędnych).

Aby określić początkowy znak, należy znaleźć dwa punkty końcowe. Odbywa się to w następujący sposób. Punkt końcowy to znak spacji, który ma dokładnie jednego sąsiada spacji. Liczbę sąsiadów uzyskuje się przez splot 2D z odpowiednią maską. Punktem początkowym jest punkt końcowy, którego złożona współrzędna ma najmniejszą sumę części rzeczywistych i urojonych; tj. jest najbliżej odległości Manhattanu od liczby zespolonej 0 lub równoważnie do 1 + 1j, która jest złożoną współrzędną lewego górnego rogu.

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

C 198 190 179 180 181 bajtów

Edycja: Użyłem końcówki przez użytkownika 81655 i usunąłem nawias w operatorze trójskładnikowym, dzięki! Zmieniłem również nieporęczny (S i 1) test na równość dla bardziej odpowiedniego (i krótszego!) S% 2.

Edycja2: Mocne użycie * stylu adresowania sprawiło, że nie zauważyłem oczywistych optymalizacji w definicji S, tj. Zastąpienie * (a + m) przez [m] itd. Następnie sam S zastąpiłem przez T, co zasadniczo połowa tego, co robi S. Kod korzysta teraz również z wartości zwracanej przez putchar.

Edycja3: Naprawiono błąd, który pojawił się od początku, kryteria zatrzymania wyszukiwania na Manhattanie a <b + m są poprawne tylko wtedy, gdy a zostało już zmniejszone. Dodaje to 2 bajty, ale odzyskuje się jeden, czyniąc definicję m globalną.

Edit4: Moje golfa minęło minimum i idzie teraz w złą stronę. Kolejna poprawka związana z wyszukiwaniem na Manhattanie. Pierwotnie miałem wbudowane kontrole na miejscu i bez nich wyszukiwanie jest kontynuowane dla dużych tablic wejściowych (gdzieś w okolicy 50 x 50) poza tablicą b. Dlatego tablica ta musi zostać powiększona do co najmniej dwukrotności poprzedniego rozmiaru, co dodaje jeszcze jeden bajt.

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

Nie golfił i wyjaśnił:

/* 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);
}

C, 272 bajtów

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

Spójrz na źródło @ Zunga. Teraz spójrz na moje. Chcesz wiedzieć, skąd mam dodatkowe 91 bajtów?
Nie golfowany:

#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 i 3), 640 624 604 583 575 561 546 538 bajtów

Nadal jestem golfistą n00b, więc jest trochę duży.

Edycja: Dzięki @porglezomp za sugestie! Nie usunąłem wszystkich operatorów „i”, ponieważ spowodowałoby to uszkodzenie Python 3.

Edycja2: Podziękowania dla @Aleksi Torhamo za komentarz na temat isspace (). Wynikowa redukcja kompensuje wprowadzoną przeze mnie poprawkę. Również dzięki anonimowemu podświetleniu składni!

Edycja3: Dzięki @ mbomb007 za kilka dodatkowych bajtów.

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

A oto moja wersja przed golfem

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

JavaScript (ES6), 195

Zobacz objaśnienie wewnątrz fragmentu testowego

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>

Lua, 562 535 529 513 507 504 466 458 bajtów

Zdecydowanie najbardziej masywny golf w tej chwili, myślę, że wciąż mogę odciąć 100 bajtów, nad którymi będę pracował, ale opublikowałem to jako odpowiedź, ponieważ zajęło to już trochę czasu :). Miałem rację, skróciłem ponad 100 bajtów! Nie sądzę, żeby było dużo miejsca na ulepszenia.

tę funkcję należy wywołać za pomocą tablicy 2D zawierającej jeden znak na komórkę.

Dzięki niemu zaoszczędziłem 40 bajtów podczas pracy z @KennyLau !

Łał! Poniżej 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

Nie golfił

Wyjaśnienia nadejdą, kiedy skończę grać w golfa, na razie pożyczę ci czytelną wersję tego kodu źródłowego: D Oto wyjaśnienia!

Edycja: nie zaktualizowano o najnowszą modyfikację, nadal gra w golfa przed aktualizacją. To samo dotyczy wyjaśnień

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

Oto kilka szczegółowych wyjaśnień na temat działania tego programu.

Po pierwsze, rozważmy pętlę oznaczoną etykietą a, która pozwala nam znaleźć najbliższy koniec lewego górnego rogu. Zapętli się na zawsze, jeśli nie będzie końca, ale to nie jest problem: D.

Na siatce 4x4 są to odległości węża (po lewej) i kolejność, w jakiej są oglądane (po prawej)

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

Dla każdej z tych postaci musi być koniec dwóch warunków: - Nie bycie spacją - Otoczenie dokładnie 3 spacjami (lub dokładnie 1 spacją)

Warunki te są sprawdzane przez następujący fragment kodu

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

Wyrażenie sprawdza, czy char nie jest spacją m[i][j]~=s.

Sprawdzając, czy otaczają nas tylko 1 spacje, uzyskujemy xor powyższe warunki dla naszego otoczenia, można to zapisać jako

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

I wreszcie, jeśli wszystko powyższe zostanie ocenione jako prawdziwe, trójka zwróci to, co jest w ostatnim and-> m[i][j]. W przeciwnym razie pozwalamy rrozbroić :)

Teraz, gdy mamy już głowę węża, przejdźmy do drugiego końca! Iteracja węża jest osiągana głównie przez następujące trójskładniki zagnieżdżone:

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

Zresetujemy się, ia jjednocześnie unikamy konieczności używania manekinów do przechowywania starych wartości. Obie mają dokładnie taką samą strukturę i używają prostych warunków, więc przedstawię je w formie zagnieżdżonej if, co powinno umożliwić ich odczytanie łatwiejsze. :)

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

Można przetłumaczyć na:

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

Sprawdź to!

Oto kod, którego używam do uruchomienia tego. Możesz go przetestować online , kopiując i wklejając.

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)

Lua, 267 bajtów

Wymagany jest Lua 5.3.

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

Stosowanie:

$ 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, 245 243 241 236 bajtów

sjest łańcuchem wejściowym, nto wyjście jest wypisywane na standardowe wyjście:

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)

Edycja: Podziękowania dla @Cees Timmerman za oszczędność 5 bajtów!

Python, 537

Moje wstępne rozwiązanie:

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

Trochę zagęszczony, ale pozostawiony jako metoda:

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 bajtów

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, zajęło to trochę czasu. W niektórych językach programowania nie ma znaczenia, czy tablica xiy znajduje się poza granicami tablicy 2D, ale w Javie wyrzuci ArrayIndexOutOfBoundsExceptions, więc wszystko trzeba sprawdzić.

Najpierw określam punkt początkowy, a następnie używam metody rekurencyjnej, aby stamtąd zbudować ciąg. Ponadto używam listy, aby śledzić koordynacje, które już napotkałem, więc nie będzie ona przechodzić w pętlę do przodu i do tyłu (co spowoduje wyjątek StackOverflowException).

Jest to prawdopodobnie najdłuższa odpowiedź, jaką do tej pory opublikowałem, ale chociaż niektóre części mogą być rozgrywane w golfa, nie sądzę, że to wyzwanie może być o wiele krótsze w Javie. Java po prostu nie nadaje się do podążania ścieżką w siatce. To było jednak fajne wyzwanie. :)

Przypadki bez golfa i testy:

Wypróbuj tutaj.

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

Wynik:

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

PHP, 199 184 182 182 bajtów

wciąż może mieć mały potencjał golfowy

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;

pobiera dane wejściowe jako ciąg multilinii z wiersza poleceń, oczekuje podziału linii w stylu linux.
Uruchom php -r '<code>' '<string>'; ucieczki przed łamaniem linii.

awaria

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

(Edycja: naprawa błędów)

Funkcja z parametrem ciągu wielowierszowego, zwracająca ciąg.

Uwzględnienie żądanej usingliczby bajtów.

To jest przeniesienie mojej odpowiedzi w javascript.

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

Przetestuj na ideonie

Ze spacjami

    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 bajtów

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

Lub, jeśli chcesz prowadzić nowe wiersze w testach, 257 bajtó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])

Przechodzi wszystkie przypadki testowe.

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

Prowadzi do:

SlipperyStringSnakesSilentlySlitherSomewhereSafe

Japt -P , 106 bajtów

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

Wypróbuj online!

To ... hmm ... obrzydliwość.

Rozpakowane i jak to działa

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

Jednym z godnych uwagi punktów jest to, że użyłem pierwszeństwa operatora między operatorami przypisania i przecinków w JS, aby spakować niektóre linie i zachować użyteczność skrótu @( XYZ{).