23
1
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)
Does input have to be done in the program or can it be read from a file? – M. I. Wright – 2015-05-07T00:31:29.363
1Should SRRR be True or False? It connects but doesn't intersect itself. – orlp – 2015-05-07T08:22:33.660
touching snakes challenge NSFW? – Ewan – 2015-05-07T08:39:07.450
3if you draw
SRRR
on a graph paper with one square per segment then it would overlap and is therefore invalid, simplyRRR
however, would occupy exactly a 2x2 square without overlaps (just like in the classic game) – DenDenDo – 2015-05-07T10:06:24.603Similar but not a duplicate (due to different objective and different construction rules). – trichoplax – 2015-05-07T20:30:15.953
+1 for Vi Hart :)
– trichoplax – 2015-05-07T22:23:10.660