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
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)
20Fun Fact: According to the linked Wikipedia article, Manhattan distance is also known as snake distance! – user81655 – 2016-04-07T10:22:22.930
Would an input like http://hastebin.com/asugoropin.vbs be correct ?
– FliiFe – 2016-04-07T11:35:34.843@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 – 2016-04-07T11:51:28.573
Can the input be a two-dimensional array (i.e each character as an element) ? – FliiFe – 2016-04-07T12:24:29.347
@FliiFe Sure. Anything that works as long as it's in a "grid"-type format. – user81655 – 2016-04-07T12:41:21.390
29Surely this puzzle needs an answer in python? – abligh – 2016-04-07T22:51:44.280
What happens when both the start AND the end have the same manhattan distance? – Luis Masuelli – 2016-04-08T15:43:05.037
@LuisMasuelli "Both ends will never have the same distance." – user81655 – 2016-04-08T23:19:12.490
That last puzzle looks like Texas to me – Charlie – 2016-04-14T05:38:45.383
@abligh It's a different species, in fact. – Erik the Outgolfer – 2016-09-30T13:28:12.227
The premise reminds me of HPC channel: “It is EKS-tremely dein-gerous and may UTT-ack at any time, so we must DIEL wiz it!” – Andreï Kostyrka – 2016-10-02T11:43:13.963