23
\$\begingroup\$

Inspired by one of Vi Hart's videos (which are a treasure trove full of potential challenge ideas)

A snake is made up of segments of same length and the connection between each segment can be straight or make a 90° turn.
We can encode such a snake (up to a rotation, which depends on the initial direction) by writing down a slither, the direction of turns (Straight/Left/Right) it takes. This one, starting in the top left and pointing to the right

-+    +--+    SR    RSSR
 |  +-+  |     S  RSL  S
 +--+  --+     LSSL  SSR

Would be represented by the slither SRSLSSLRLRSSRSRSS

And of course a planar snake cannot intersect itself (like in SSSSLLLSS), that would result in a horrible pixelated Game Over.

Your task is to determine whether a slither is valid or not (results in at least one self-intersection)

Input
A string made from letters SLR with 2 < length < 10000
Output
Something Truthy if it is a valid slither and something Falsey if its not.

Test cases

__Valid__
SSLSLSRSRSSRSSSLLSSSRRLRSLRLLSSS
SRRLSLLRRLLSLRRSRLLRSRRLLRRSRLLSSLLRSRRLLRRSRLLRSRRLSLLRRLLSLRR (A hilbert curve)
RLLRSRRLSLLRRLLSLRRSRLLRSRRLLRRSRLLSSLLRSRRLLRRSRLLRSRRLSLLRRLLSLRRSRLLRSRRLLRRSRLLSSLLRSRRLLRR
SRRSRSRSSRSSRSSSRSSSRSSSSRSSSSRSSSSSRSSSSSRSSSSSSRSSSSSSRSSSSSS (Spiral)
SSSSSSSSSSLSSSSSSSLSSSSSSSSLSSSSSLSSSSSSLSSSLLRRLLRRLLSLSSSRRSSSSRSSSRSSSSSSRSSSSSRSSSSSSSSRSSSSSSSRSSSSSSSSS (bigger, squigglier spiral)
LRSLLRLSRSLLSRLSLRSLSSSLRRSSLSRRLRSRLRLSLRLLRLRSSLSLRLRSRSSSSSLSRRLSLSSSRRLRLRLRLRRLLSSLSSSRRLRLRLRLRLSLSSSSSSSSSSSSSRLRLLRLRLRLRLRLRLRLSLSSSLSLSLL

__Invalid__
SRRLSLLRRLLSLRRSRLLRSRRLLRRSRLLLLRSRRLLRRSRLLRSRRLSLLRRLLSLRR
SRRLSLLRRLLSLRRSRLLRSRRLLSRSSSRSSSSSSSRSRSSSSSSSRRLLRRSRLLRSRRLSLLRRLLSLRR
SRRSRSRSSRSSRSSSRSSSRSSSSSSSSSSRSSSSRSSSSSRSSSSSRSSSSSSRSSSSSSRSSSSSS
SSSSSSSSSSLSSSSSSSLSSSSSSSSLSSSSSLSSSSSSLSSSLLRRLRLRRLLSLSSSRRSSSSRSSSRSSSSSSRSSSSSRSSSSSSSSRSSSSSSSRSSSSSSSSS
LRSLLRLSRSLLSRLSLRSLSSSLRRSSLSRRLRSRLRLSLRLLRLRSSLSLRLRSRSSSSSLSRRLSLSSSRRLRLRLRLRRLLSSLSSSRRLRLRLRLRLSLSSSSSSSSSSSSSRLRLLRLRLRLRLRLRLRLSLSSSLSLSLLSLRLSLRSLRSLRSLSLSLRSRLSLRSLRLSRSLLLRLRLRRRRSLSLSSLLSLSLSLSSLLSLSLLRLRSLLRSRLSLSSLLLLSSSSSSSSSSSSSSSSSSSSRLRLLRRLRLRLLRLRLRLRLRLSSSSLSLRLLRLSLSSLSLSLSLSLRLLRLSLLLSRSSSSSSSSSSSSSSSRLRLRLLRLRLSLSRSRSSSLSRLRLRLRSLSLSLSRLLSRLSLSLSLSLSSLSLSLLSLSRLLRLRLRLRLRLRLRLRLRLRLSLSRLRLSLLRRLSLLSLSLSLSLSLLSLSLSLRLRLRLRLRLRLRLRLRLRRLRSLSLSLSLSLSLSLSSLSSSSSLSLSSSLSLSLSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS

You can draw the slithers here (R and L are flipped, but it doesnt affect validity)

\$\endgroup\$
  • \$\begingroup\$ Does input have to be done in the program or can it be read from a file? \$\endgroup\$ – M. I. Wright May 7 '15 at 0:31
  • 1
    \$\begingroup\$ Should SRRR be True or False? It connects but doesn't intersect itself. \$\endgroup\$ – orlp May 7 '15 at 8:22
  • \$\begingroup\$ touching snakes challenge NSFW? \$\endgroup\$ – Ewan May 7 '15 at 8:39
  • 3
    \$\begingroup\$ if you draw SRRR on a graph paper with one square per segment then it would overlap and is therefore invalid, simply RRR however, would occupy exactly a 2x2 square without overlaps (just like in the classic game) \$\endgroup\$ – DenDenDo May 7 '15 at 10:06
  • \$\begingroup\$ Similar but not a duplicate (due to different objective and different construction rules). \$\endgroup\$ – trichoplax May 7 '15 at 20:30
20
\$\begingroup\$

Pyth, 22 20 bytes

ql{m+=Z*=T^.j)hCdzlz

Try it yourself or run the testsuite.

Note the ASCII values of SRL, respectively 83, 76, 82. I abuse the fact that:

i 83 + 1 = 1
i 76 + 1 = i
i 82 + 1 = -i

From here I just keep a variable for the current position and current direction. For every character I multiply the current direction with the above complex number, then add it to the current position.

At the end I check if all the visited positions are unique.

\$\endgroup\$
  • \$\begingroup\$ SRRR = true???? \$\endgroup\$ – Ewan May 7 '15 at 8:11
  • \$\begingroup\$ @Ewan On closer inspection - I'm not sure if that should be false or not. The head and tail connect, but do not intersect. \$\endgroup\$ – orlp May 7 '15 at 8:20
  • \$\begingroup\$ what about SRRRS? \$\endgroup\$ – Ewan May 7 '15 at 8:22
  • \$\begingroup\$ @Ewan Same story - connection but no intersection. The question isn't clear what should be returned for these. \$\endgroup\$ – orlp May 7 '15 at 8:23
  • 1
    \$\begingroup\$ how would you draw SRRR? \$\endgroup\$ – Ewan May 7 '15 at 8:47
6
\$\begingroup\$

CJam, 30 bytes

q{iF%U+:U[XWe4W1e4]=T+:T}%__&=

Explanation to follow soon.

Try it online here or run the whole suite.

\$\endgroup\$
  • \$\begingroup\$ Damn, that was fast. I didnt even think of an algorithm to solve it myself yet. \$\endgroup\$ – DenDenDo May 6 '15 at 23:16
  • \$\begingroup\$ SRRRS = true??? \$\endgroup\$ – Ewan May 7 '15 at 8:13
  • \$\begingroup\$ @Ewan umm, are we assuming that 0 is initially filled up and counts ? \$\endgroup\$ – Optimizer May 7 '15 at 9:12
  • 1
    \$\begingroup\$ I guess I am interpreting it like a game of snake, where moves take up blocks of space. and some of you guys are interpreting it as a zero width line \$\endgroup\$ – Ewan May 7 '15 at 9:16
  • \$\begingroup\$ @Ewan My question is a bit different though. When we have a single move, say S, does it mean that the snake has already occupied both (0,0) and (1,0) ? \$\endgroup\$ – Optimizer May 7 '15 at 9:18
6
\$\begingroup\$

JavaScript (ES6), 84 89

Run snippet in Firefox to test.

Some notes:

  • the snake moves inside the f array. Unvisited cells have value undefined. On first visit, the tilde operator change it to -1 that is a truthy. Eventually, on a second visit the value change to 0 that is falsy and the every loop terminates returning false.
  • in JS, array elements with non canonic indices (not numeric or negative) are somehow 'hidden', but they do exist. Here I use negative indices with no problem.

F=s=>[...s].every(c=>f[p+=[1,1e5,-1,-1e5][d=d+{R:1,L:3,S:0}[c]&3]]=~f[p],d=p=0,f=[])

//TEST
$('#S').on('keyup mouseup change', Draw);

function Draw(){
  var s = S.value.toUpperCase();
  if (!s) {
    C.width = C.height = 0;
    return
  }
  C.width = 600;
  C.height = 400;
  
  var ctx = C.getContext("2d");  
  var px, py, int=0;
  
  ctx.strokeStyle = '#008';
  ctx.lineWidth = 2;
  ctx.translate(300,200);
  ctx.beginPath();
  ctx.moveTo(0,0);
  
  [...s].forEach(c=>{
    (f[p+=[1,1e4,-1,-1e4][d=d+{R:1,L:3,S:0}[c]&3]]=~f[p])
    ? 1 
    : (++int)
    if (int==1) ctx.stroke(), ctx.strokeStyle = '#800', ctx.beginPath(), ctx.moveTo(10*px,10*py);
    
    py = (p / 1e4 | 0) - 5e3;
    px = (p % 1e4) -5e3
    ctx.lineTo(10*px, 10*py);
  }, d=0,p=50005000,f=[]);
  ctx.stroke();
  
}

valid=["SSLSLSRSRSSRSSSLLSSSRRLRSLRLLSSS",
"SRRLSLLRRLLSLRRSRLLRSRRLLRRSRLLSSLLRSRRLLRRSRLLRSRRLSLLRRLLSLRR",
"RLLRSRRLSLLRRLLSLRRSRLLRSRRLLRRSRLLSSLLRSRRLLRRSRLLRSRRLSLLRRLLSLRRSRLLRSRRLLRRSRLLSSLLRSRRLLRR",
"SRRSRSRSSRSSRSSSRSSSRSSSSRSSSSRSSSSSRSSSSSRSSSSSSRSSSSSSRSSSSSS",
"SSSSSSSSSSLSSSSSSSLSSSSSSSSLSSSSSLSSSSSSLSSSLLRRLLRRLLSLSSSRRSSSSRSSSRSSSSSSRSSSSSRSSSSSSSSRSSSSSSSRSSSSSSSSS",
"LRSLLRLSRSLLSRLSLRSLSSSLRRSSLSRRLRSRLRLSLRLLRLRSSLSLRLRSRSSSSSLSRRLSLSSSRRLRLRLRLRRLLSSLSSSRRLRLRLRLRLSLSSSSSSSSSSSSSRLRLLRLRLRLRLRLRLRLSLSSSLSLSLL"];
invalid=["SRRLSLLRRLLSLRRSRLLRSRRLLRRSRLLLLRSRRLLRRSRLLRSRRLSLLRRLLSLRR",
"SRRLSLLRRLLSLRRSRLLRSRRLLSRSSSRSSSSSSSRSRSSSSSSSRRLLRRSRLLRSRRLSLLRRLLSLRR",
"SRRSRSRSSRSSRSSSRSSSRSSSSSSSSSSRSSSSRSSSSSRSSSSSRSSSSSSRSSSSSSRSSSSSS",
"SSSSSSSSSSLSSSSSSSLSSSSSSSSLSSSSSLSSSSSSLSSSLLRRLRLRRLLSLSSSRRSSSSRSSSRSSSSSSRSSSSSRSSSSSSSSRSSSSSSSRSSSSSSSSS",
"LRSLLRLSRSLLSRLSLRSLSSSLRRSSLSRRLRSRLRLSLRLLRLRSSLSLRLRSRSSSSSLSRRLSLSSSRRLRLRLRLRRLLSSLSSSRRLRLRLRLRLSLSSSSSSSSSSSSSRLRLLRLRLRLRLRLRLRLSLSSSLSLSLLSLRLSLRSLRSLRSLSLSLRSRLSLRSLRLSRSLLLRLRLRRRRSLSLSSLLSLSLSLSSLLSLSLLRLRSLLRSRLSLSSLLLLSSSSSSSSSSSSSSSSSSSSRLRLLRRLRLRLLRLRLRLRLRLSSSSLSLRLLRLSLSSLSLSLSLSLRLLRLSLLLSRSSSSSSSSSSSSSSSRLRLRLLRLRLSLSRSRSSSLSRLRLRLRSLSLSLSRLLSRLSLSLSLSLSSLSLSLLSLSRLLRLRLRLRLRLRLRLRLRLRLSLSRLRLSLLRRLSLLSLSLSLSLSLLSLSLSLRLRLRLRLRLRLRLRLRLRRLRSLSLSLSLSLSLSLSSLSSSSSLSLSSSLSLSLSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS"];

V.innerHTML=valid.map(s=>F(s)+' '+s).join('\n')
I.innerHTML=invalid.map(s=>F(s)+' '+s).join('\n')
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
Type to check and draw <input id=S>
(better full page)<br>
<canvas id=C width=1 height=1 ></canvas><br>
Valid<pre id=V></pre>
Invalid<pre id=I></pre>

\$\endgroup\$
6
\$\begingroup\$

TI-BASIC, 49 56 53 51 bytes

abs(e^(i)-cumSum(i^cumSum(seq(inString("SL",sub(Ans,X,1))-1,X,1,length(Ans→X
SortA(∟X
min(ΔList(∟X

Similar to orlp's method, this creates a list of all points in the complex plane visited by the snake, starting at the origin. If the list has no duplicate elements, the code returns some positive value. Note that on a string of more than 999 elements, the calculator will be unable to generate a sufficiently long list, and will error.

EDIT: Saved two bytes at the cost of ugliness as no two lattice points on the complex plane can be the same distance away from e^i.

\$\endgroup\$
5
\$\begingroup\$

TI-BASIC, 60 58 bytes

Edit: Ignore everything below: a working ti-basic solution is here, by thomas-kwa. Go upvote that!

is the [(-)] key, and Ans is [2ND]->[(-)]. Run it by enclosing the snake's instructions in quotes ([ALPHA]->[+]) followed by a colon then the program's name. For instance, if you name the program "SNAKE", you'd run the test case in the OP as "SRSLSSLRLRSSRSRSS":prgmSNAKE.

seq(inString("SRL",sub("0"+Ans,I,1)),I,1,length(Ans
Disp 0<sum(⁻1+2seq(Ans(I)≠(Ans(I-1),I,2,dim(Ans

Edit: Fails on SRRLSLLRRRS. I have a revised version at 61 bytes, but it fails on the first invalid test case:

seq(inString("SRL",sub("0"+Ans,I,1)),I,1,length(Ans
cumSum(⁻1+2seq(Ans(I)≠(Ans(I-1),I,2,dim(Ans
Disp 0<Ans(dim(Ans

I'll try to fix tomorrow.


Update: so the problem is actually that my algorithm is flawed. If I had used a For( loop as opposed to seq( (to achieve the same thing) it (both algorithms above, actually) could be described as this:

  1. Initialize the counter variable to 1.
  2. Read the string. If the symbol changes, increment the counter variable. If the symbol repeats, decrement it.
  3. If the counter variable is greater than 0, display 1 (valid). Otherwise, display 0 (invalid).

However, this fails on invalid slithers like SRLRLRLRLRRRSS. I will now try to come up with a better algorithm... or steal from another answer.


I'm 90% sure that this can be replaced with a single seq( command, actually, but for now this is as small as I can get it. If you intend to build this to an 8xp using Sourcecoder as opposed to actually typing it out, note that should be replaced with != and the ⁻1+ bit should be replaced with ~1+.

\$\endgroup\$
1
\$\begingroup\$

Ruby 87 89

F=->s{d=[1,w=1e4,-1,-w]
v=[w]+s.chars.map{|c|w+=d.rotate!(c<?R?-1:c>?R?0:1)[0]}
v==v&v}

Online test: http://ideone.com/pepeW2

Ungolfed version:

F = -> input {
  # Coordinates are expressed using one number,
  # that is computed using the formula `y + x*max_x`.
  # Assume max horizontal field width (max_x) to be 10000,
  # since that's the max length of the input.
  position = max_x = 1e4

  # These are possible directions to move to (coordinate deltas).
  # The current direction is always the first in the array.
  directions = [1,max_x,-1,-max_x]

  visited = [position]

  visited += input.chars.map{|c|
    # adjust current direction...
    directions.rotate! case c
    when ?L
      -1
    when ?R
      1
    when ?S
      0
    end

    # ...and move there
    position += directions[0]
  }

  # Return `true` if `visited` only contains distinct elements, `false` otherwise
  visited == visited & visited
}
\$\endgroup\$
0
\$\begingroup\$

Golfscript 48 49 50

[10.4?:z-10z~)]z*z@{'R L S'?@>(@+.`n}%n/@;\;..&=

Expects the string to exist on the stack and returns either 0 or 1.

You can try it online with tests for valid and invalid snakes.

This is basically the same idea as in my Ruby answer. Just the direction array is dealt with differently, because AFAIK Golfscript does not have an arary rotate function. In this case, I build a sufficiently large directions array, by multiplying it 10000 times and then trimming from its start 0, 1, or 3 elements, depending on the current command (S, R, or L). The current "direction" to move to is always the first item in the array.

Here it is with comments:

# Build the direction array and set current position
[1 10000:z-1z~)]z*z

@{
  # For each character in the input:

  # set current direction by cutting 0, 1 or 3 elements 
  # from the beginning of the directions array
  'SR L'?
  @>

  # move to current direction
  .0=@+.

  # format as number and addd newline
  `n
}%

# split by newlines
n/

# cleanup
@;\;

# return 1 if array contains distinct elements, 0 otherwise
..&=

Edit:

Saved 1 char by modifying how the "directions" array is consumed.

Edit:

saved 1 char by moving increments of 10 instead of 1 to make use of the ? (power) syntax.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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