Inspiré par l' une des vidéos de Vi Hart (qui sont un trésor plein d'idées de défis potentiels)

Un serpent est composé de segments de même longueur et la connexion entre chaque segment peut être droite ou faire un virage à 90 °.
Nous pouvons encoder un tel serpent (jusqu'à une rotation, qui dépend de la direction initiale) en écrivant un slither , la direction des virages (Droite / Gauche / Droite) qu'il faut. Celui-ci, commençant en haut à gauche et pointant vers la droite

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

Serait représenté par le slither SRSLSSLRLRSSRSRSS

Et bien sûr, un serpent plan ne peut pas se croiser (comme dans SSSSLLLSS), ce qui entraînerait un horrible Game Over pixelisé.

Votre tâche consiste à déterminer si un slither est valide ou non (entraîne au moins une auto-intersection)

Input
Une chaîne faite de lettres SLRavec 2 < length < 10000
Output
Something Truthy s'il s'agit d'un slither valide et quelque chose Falsey dans le cas contraire.

Cas de test

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

__Invalid__
SRRLSLLRRLLSLRRSRLLRSRRLLRRSRLLLLRSRRLLRRSRLLRSRRLSLLRRLLSLRR
SRRLSLLRRLLSLRRSRLLRSRRLLSRSSSRSSSSSSSRSRSSSSSSSRRLLRRSRLLRSRRLSLLRRLLSLRR
SRRSRSRSSRSSRSSSRSSSRSSSSSSSSSSRSSSSRSSSSSRSSSSSRSSSSSSRSSSSSSRSSSSSS
SSSSSSSSSSLSSSSSSSLSSSSSSSSLSSSSSLSSSSSSLSSSLLRRLRLRRLLSLSSSRRSSSSRSSSRSSSSSSRSSSSSRSSSSSSSSRSSSSSSSRSSSSSSSSS
LRSLLRLSRSLLSRLSLRSLSSSLRRSSLSRRLRSRLRLSLRLLRLRSSLSLRLRSRSSSSSLSRRLSLSSSRRLRLRLRLRRLLSSLSSSRRLRLRLRLRLSLSSSSSSSSSSSSSRLRLLRLRLRLRLRLRLRLSLSSSLSLSLLSLRLSLRSLRSLRSLSLSLRSRLSLRSLRLSRSLLLRLRLRRRRSLSLSSLLSLSLSLSSLLSLSLLRLRSLLRSRLSLSSLLLLSSSSSSSSSSSSSSSSSSSSRLRLLRRLRLRLLRLRLRLRLRLSSSSLSLRLLRLSLSSLSLSLSLSLRLLRLSLLLSRSSSSSSSSSSSSSSSRLRLRLLRLRLSLSRSRSSSLSRLRLRLRSLSLSLSRLLSRLSLSLSLSLSSLSLSLLSLSRLLRLRLRLRLRLRLRLRLRLRLSLSRLRLSLLRRLSLLSLSLSLSLSLLSLSLSLRLRLRLRLRLRLRLRLRLRRLRSLSLSLSLSLSLSLSSLSSSSSLSLSSSLSLSLSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS

Vous pouvez dessiner les slithers ici (R et L sont inversés, mais cela n'affecte pas la validité)

Pyth, 22 20 octets

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

Essayez-le vous - même ou exécutez la suite de tests .

Notez les valeurs ASCII de SRL, respectivement 83, 76, 82. J'abuse du fait que:

i ^{83 + 1} = 1
i ^{76 + 1} = i
i ^{82 + 1} = -i

De là, je garde juste une variable pour la position actuelle et la direction actuelle. Pour chaque caractère, je multiplie la direction actuelle par le nombre complexe ci-dessus, puis je l'ajoute à la position actuelle.

À la fin, je vérifie si toutes les positions visitées sont uniques.

CJam, 30 octets

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

Explication à suivre bientôt.

Essayez-le en ligne ici ou exécutez toute la suite .

JavaScript (ES6), 84 89

Exécutez l'extrait dans Firefox pour tester.

Quelques notes:

• le serpent se déplace à l'intérieur du tableau f. Les cellules non visitées ont de la valeur undefined. Lors de la première visite, l'opérateur tilde le change en -1, ce qui est vrai. Finalement, lors d'une deuxième visite, la valeur passe à 0, ce qui est faux et la everyboucle se termine en retournant false.
• en JS, les éléments de tableau avec des indices non canoniques (non numériques ou négatifs) sont en quelque sorte «cachés», mais ils existent. Ici, j'utilise des indices négatifs sans problème.

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>

TI-BASIC, 49 56 53 51 octets

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

Semblable à la méthode orlp, cela crée une liste de tous les points dans le plan complexe visité par le serpent, en commençant à l'origine. Si la liste ne contient aucun élément en double, le code renvoie une valeur positive. Notez que sur une chaîne de plus de 999 éléments, la calculatrice ne pourra pas générer une liste suffisamment longue et fera une erreur.

EDIT: deux octets enregistrés au prix de la laideur car aucun point de réseau sur le plan complexe ne peut être à la même distance de e ^ i.

TI-BASIC, 60 58 octets

Edit: Ignorez tout ci-dessous: une solution ti-basique est là , par thomas-kwa. Allez voter!

⁻est la [(-)]clé, et Ans l'est [2ND]->[(-)]. Exécutez-le en plaçant les instructions du serpent entre guillemets ( [ALPHA]->[+]) suivies de deux points puis du nom du programme. Par exemple, si vous nommez le programme "SNAKE", vous exécuterez le cas de test dans l'OP en tant que "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: échoue SRRLSLLRRRS. J'ai une version révisée à 61 octets, mais elle échoue sur le premier cas de test invalide:

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

J'essaierai de réparer demain.

Mise à jour: le problème est donc que mon algorithme est défectueux. Si j'avais utilisé une boucle For (par opposition à seq ((pour obtenir la même chose), elle (les deux algorithmes ci-dessus, en fait) pourrait être décrite comme suit:

1. Initialisez la variable de compteur à 1.
2. Lisez la chaîne. Si le symbole change, incrémentez la variable compteur. Si le symbole se répète, décrémentez-le.
3. Si la variable de compteur est supérieure à 0, affichez 1 (valide). Sinon, affichez 0 (invalide).

Cependant, cela échoue sur des slithers invalides comme SRLRLRLRLRRRSS. Je vais maintenant essayer de trouver un meilleur algorithme ... ou voler une autre réponse.

Je suis sûr à 90% que cela peut être remplacé par une seule seq(commande, en fait, mais pour l'instant, c'est aussi petit que possible. Si vous avez l'intention de le construire sur un 8xp en utilisant Sourcecoder au lieu de le taper, notez que cela ≠doit être remplacé par !=et le ⁻1+bit doit être remplacé par ~1+.

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

Test en ligne: http://ideone.com/pepeW2

Version non golfée:

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
}

Golfscript 48 49 50

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

Attend que la chaîne existe sur la pile et renvoie soit 0ou 1.

Vous pouvez l'essayer en ligne avec des tests pour les serpents valides et invalides .

C'est fondamentalement la même idée que dans ma réponse Ruby . Seul le tableau de direction est traité différemment, car AFAIK Golfscript n'a pas de fonction de rotation araire. Dans ce cas, je crée un tableau de directions suffisamment grand, en le multipliant 10000 fois, puis en coupant à partir de son début 0, 1 ou 3 éléments, selon la commande en cours (S, R ou L). La "direction" actuelle vers laquelle se déplacer est toujours le premier élément du tableau.

Le voici avec des commentaires:

# 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
..&=

Modifier:

1 char sauvé en modifiant la façon dont le tableau "directions" est consommé.

Modifier:

enregistré 1 caractère en déplaçant les incréments de 10 au lieu de 1 pour utiliser la ?syntaxe (puissance).