Serpientes válidas en un avión

23

Inspirado en uno de los videos de Vi Hart (que son un tesoro lleno de posibles ideas de desafío)

Una serpiente está formada por segmentos de la misma longitud y la conexión entre cada segmento puede ser recta o girar 90 °.
Podemos codificar una serpiente de este tipo (hasta una rotación, que depende de la dirección inicial) escribiendo una diapositiva , la dirección de las vueltas (recta / izquierda / derecha) que toma. Este, comenzando en la parte superior izquierda y apuntando a la derecha

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

Estaría representado por el slither SRSLSSLRLRSSRSRSS

Y, por supuesto, una serpiente plana no puede cruzarse (como en SSSSLLLSS), lo que daría como resultado un horrible juego pixelado.

Su tarea es determinar si un deslizamiento es válido o no (resulta en al menos una auto-intersección)

Input
Una cadena hecha de letras SLRcon 2 < length < 10000
Output
Something Truthy si es un slither válido y algo Falsey si no lo es.

Casos de prueba

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

__Invalid__
SRRLSLLRRLLSLRRSRLLRSRRLLRRSRLLLLRSRRLLRRSRLLRSRRLSLLRRLLSLRR
SRRLSLLRRLLSLRRSRLLRSRRLLSRSSSRSSSSSSSRSRSSSSSSSRRLLRRSRLLRSRRLSLLRRLLSLRR
SRRSRSRSSRSSRSSSRSSSRSSSSSSSSSSRSSSSRSSSSSRSSSSSRSSSSSSRSSSSSSRSSSSSS
SSSSSSSSSSLSSSSSSSLSSSSSSSSLSSSSSLSSSSSSLSSSLLRRLRLRRLLSLSSSRRSSSSRSSSRSSSSSSRSSSSSRSSSSSSSSRSSSSSSSRSSSSSSSSS
LRSLLRLSRSLLSRLSLRSLSSSLRRSSLSRRLRSRLRLSLRLLRLRSSLSLRLRSRSSSSSLSRRLSLSSSRRLRLRLRLRRLLSSLSSSRRLRLRLRLRLSLSSSSSSSSSSSSSRLRLLRLRLRLRLRLRLRLSLSSSLSLSLLSLRLSLRSLRSLRSLSLSLRSRLSLRSLRLSRSLLLRLRLRRRRSLSLSSLLSLSLSLSSLLSLSLLRLRSLLRSRLSLSSLLLLSSSSSSSSSSSSSSSSSSSSRLRLLRRLRLRLLRLRLRLRLRLSSSSLSLRLLRLSLSSLSLSLSLSLRLLRLSLLLSRSSSSSSSSSSSSSSSRLRLRLLRLRLSLSRSRSSSLSRLRLRLRSLSLSLSRLLSRLSLSLSLSLSSLSLSLLSLSRLLRLRLRLRLRLRLRLRLRLRLSLSRLRLSLLRRLSLLSLSLSLSLSLLSLSLSLRLRLRLRLRLRLRLRLRLRRLRSLSLSLSLSLSLSLSSLSSSSSLSLSSSLSLSLSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS

Puede dibujar los slithers aquí (R y L están invertidos, pero no afecta la validez)

DenDenDo
fuente
¿La entrada tiene que hacerse en el programa o puede leerse desde un archivo?
MI Wright
1
¿Debería SRRR ser verdadero o falso? Se conecta pero no se cruza.
orlp
tocar serpientes desafían NSFW?
Ewan
3
si dibuja SRRRen un papel cuadriculado con un cuadrado por segmento, entonces se superpondría y, por lo tanto, no es válido, simplemente RRRocuparía exactamente un cuadrado de 2x2 sin superposiciones (al igual que en el juego clásico)
DenDenDo
Similar pero no un duplicado (debido a diferentes objetivos y diferentes reglas de construcción).
trichoplax

Respuestas:

20

Pyth, 22 20 bytes

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

Pruébelo usted mismo o ejecute el testuite .

Tenga en cuenta los valores ASCII de SRL, respectivamente 83, 76, 82. Abuso del hecho de que:

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

Desde aquí solo mantengo una variable para la posición actual y la dirección actual. Para cada personaje, multiplico la dirección actual con el número complejo anterior, luego lo agrego a la posición actual.

Al final verifico si todos los puestos visitados son únicos.

orlp
fuente
SRRR = verdadero ????
Ewan
@Ewan En una inspección más cercana, no estoy seguro de si eso debería ser falso o no. La cabeza y la cola se conectan, pero no se cruzan.
orlp
¿Qué pasa con SRRRS?
Ewan
@Ewan Misma historia: conexión pero sin intersección. La pregunta no está clara sobre qué debería devolverse para estos.
orlp
1
¿Cómo dibujarías SRRR?
Ewan
6

CJam, 30 bytes

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

Explicación a seguir pronto.

Pruébelo en línea aquí o ejecute toda la suite .

Optimizador
fuente
Maldición, eso fue rápido. Ni siquiera pensé en un algoritmo para resolverlo yo mismo todavía.
DenDenDo
SRRRS = verdadero ???
Ewan
@Ewan umm, ¿estamos asumiendo que 0 se llena inicialmente y cuenta?
Optimizador
1
Supongo que lo estoy interpretando como un juego de serpiente, donde los movimientos ocupan bloques de espacio. y algunos de ustedes lo están interpretando como una línea de ancho cero
Ewan
@Ewan Sin embargo, mi pregunta es un poco diferente. Cuando tenemos un solo movimiento, por ejemplo S, ¿significa que la serpiente ya ha ocupado tanto (0,0) como (1,0)?
Optimizador
6

JavaScript (ES6), 84 89

Ejecute el fragmento en Firefox para probar.

Algunas notas:

  • la serpiente se mueve dentro de la matriz f. Las celdas no visitadas tienen valor undefined. En la primera visita, el operador tilde lo cambia a -1, lo cual es una verdad. Finalmente, en una segunda visita, el valor cambia a 0 que es falso y el everyciclo termina devolviendo falso.
  • en JS, los elementos de matriz con índices no canónicos (no numéricos o negativos) están de alguna manera 'ocultos', pero existen. Aquí uso índices negativos sin problema.

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
fuente
6

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 al método de orlp, esto crea una lista de todos los puntos en el plano complejo visitado por la serpiente, comenzando en el origen. Si la lista no tiene elementos duplicados, el código devuelve algún valor positivo. Tenga en cuenta que en una cadena de más de 999 elementos, la calculadora no podrá generar una lista suficientemente larga y generará un error.

EDITAR: se guardaron dos bytes a costa de la fealdad, ya que no hay dos puntos de red en el plano complejo que puedan estar a la misma distancia de e ^ i.

lirtosiast
fuente
5

TI-BASIC, 60 58 bytes

Editar: ignore todo lo siguiente: una solución básica de trabajo está aquí , por Thomas-Kwa. ¡Vota eso!

es la [(-)]clave, y Ans es [2ND]->[(-)]. Ejecútelo encerrando las instrucciones de la serpiente entre comillas ( [ALPHA]->[+]) seguidas de dos puntos y luego el nombre del programa. Por ejemplo, si nombra el programa "SNAKE", ejecutaría el caso de prueba en el OP como "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

Editar: falla SRRLSLLRRRS. Tengo una versión revisada de 61 bytes, pero falla en el primer caso de prueba no válido:

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

Intentaré arreglarlo mañana.


Actualización: el problema es que mi algoritmo es defectuoso. Si hubiera usado un For (bucle en lugar de seq ((para lograr lo mismo)) (ambos algoritmos anteriores, en realidad) podría describirse así:

  1. Inicialice la variable del contador a 1.
  2. Lee la cuerda. Si el símbolo cambia, incremente la variable del contador. Si el símbolo se repite, decremente.
  3. Si la variable del contador es mayor que 0, muestre 1 (válido). De lo contrario, muestra 0 (no válido).

Sin embargo, esto falla en deslizadores inválidos como SRLRLRLRLRRRSS. Ahora intentaré encontrar un algoritmo mejor ... o robar de otra respuesta.


Estoy 90% seguro de que esto se puede reemplazar con un solo seq(comando, en realidad, pero por ahora esto es lo más pequeño que puedo obtener. Si tiene la intención de construir esto en un 8xp usando Sourcecoder en lugar de escribirlo, tenga en cuenta que debe reemplazarse por !=y el ⁻1+bit debe reemplazarse por ~1+.

MI Wright
fuente
1

Rubí 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}

Prueba en línea: http://ideone.com/pepeW2

Versión sin golf:

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
fuente
0

Golfscript 48 49 50

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

Espera que la cadena exista en la pila y devuelve 0o 1.

Puede probarlo en línea con pruebas para serpientes válidas e inválidas .

Esta es básicamente la misma idea que en mi respuesta de Ruby . Solo la matriz de dirección se trata de manera diferente, porque AFAIK Golfscript no tiene una función de rotación araria. En este caso, construyo una matriz de direcciones suficientemente grande, multiplicándola 10000 veces y luego recortando desde su inicio 0, 1 o 3 elementos, dependiendo del comando actual (S, R o L). La "dirección" actual para moverse es siempre el primer elemento de la matriz.

Aquí está con comentarios:

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

Editar:

Se guardó 1 carácter modificando cómo se consume la matriz de "direcciones".

Editar:

ahorró 1 char moviendo incrementos de 10 en lugar de 1 para hacer uso de la ?sintaxis (potencia).

Cristian Lupascu
fuente