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\$
6
  • \$\begingroup\$ Does input have to be done in the program or can it be read from a file? \$\endgroup\$
    – user39326
    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\$
11
  • \$\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\$
7
  • \$\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\$
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.