Serpents valides dans un avion

23

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é)

DenDenDo
la source
L'entrée doit-elle être effectuée dans le programme ou peut-elle être lue à partir d'un fichier?
MI Wright
1
Le SRRR doit-il être vrai ou faux? Il se connecte mais ne se recoupe pas.
orlp
des serpents touchants défient NSFW?
Ewan
3
si vous dessinez SRRRsur un papier millimétré avec un carré par segment, il se chevaucherait et n'est donc pas valide, tout simplement RRRcependant, occuperait exactement un carré 2x2 sans chevauchements (tout comme dans le jeu classique)
DenDenDo
Similaire mais pas en double (en raison d'objectifs différents et de règles de construction différentes).
trichoplax

Réponses:

20

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.

orlp
la source
SRRR = vrai ????
Ewan
@Ewan En y regardant de plus près - je ne sais pas si cela doit être faux ou non. La tête et la queue se connectent, mais ne se croisent pas.
orlp
qu'en est-il de SRRRS?
Ewan
@Ewan Même histoire - connexion mais pas d'intersection. La question n'est pas claire de ce qui devrait être retourné pour ces derniers.
orlp
1
comment dessinerais-tu SRRR?
Ewan
6

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 .

Optimiseur
la source
Merde, c'était rapide. Je n'ai même pas encore pensé à un algorithme pour le résoudre moi-même.
DenDenDo
SRRRS = vrai ???
Ewan
@Ewan umm, supposons-nous que 0 est initialement rempli et compte?
Optimizer
1
Je suppose que je l'interprète comme un jeu de serpent, où les mouvements prennent des blocs d'espace. et certains d'entre vous l'interprètent comme une ligne de largeur nulle
Ewan
@Ewan Ma question est cependant un peu différente. Quand nous avons un seul mouvement, disons S, cela signifie-t-il que le serpent a déjà occupé à la fois (0,0) et (1,0)?
Optimizer
6

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>

edc65
la source
6

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.

lirtosiast
la source
5

TI-BASIC, 60 58 octets

Edit: Ignorez tout ci-dessous: une solution ti-basique est , 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+.

MI Wright
la source
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
}
Cristian Lupascu
la source
0

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).

Cristian Lupascu
la source