Zainspirowany jednym z filmów Vi Harta (które są skarbnicą pełną potencjalnych pomysłów na wyzwania)

Wąż składa się z segmentów o tej samej długości, a połączenie między każdym segmentem może być proste lub wykonać obrót o 90 °.
Możemy zakodować takiego węża (do obrotu, który zależy od początkowego kierunku), zapisując ślizgacz , kierunek zwojów (Prosto / Lewo / Prawo). Ten, zaczynający się w lewym górnym rogu i wskazujący w prawo

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

Byłby reprezentowany przez ślizgacz SRSLSSLRLRSSRSRSS

I oczywiście wąż planarny nie może się przecinać (jak w środku SSSSLLLSS), co spowodowałoby straszne pikselowe zakończenie gry.

Twoim zadaniem jest ustalenie, czy ślizgacz jest prawidłowy, czy nie (skutkuje co najmniej jednym przecięciem się)

Wejście
Ciąg wykonany z liter SLRz 2 < length < 10000
wyjściem
Coś prawdy, jeśli jest to prawidłowy ślizg, a coś Falsey, jeśli nie.

Przypadki testowe

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

__Invalid__
SRRLSLLRRLLSLRRSRLLRSRRLLRRSRLLLLRSRRLLRRSRLLRSRRLSLLRRLLSLRR
SRRLSLLRRLLSLRRSRLLRSRRLLSRSSSRSSSSSSSRSRSSSSSSSRRLLRRSRLLRSRRLSLLRRLLSLRR
SRRSRSRSSRSSRSSSRSSSRSSSSSSSSSSRSSSSRSSSSSRSSSSSRSSSSSSRSSSSSSRSSSSSS
SSSSSSSSSSLSSSSSSSLSSSSSSSSLSSSSSLSSSSSSLSSSLLRRLRLRRLLSLSSSRRSSSSRSSSRSSSSSSRSSSSSRSSSSSSSSRSSSSSSSRSSSSSSSSS
LRSLLRLSRSLLSRLSLRSLSSSLRRSSLSRRLRSRLRLSLRLLRLRSSLSLRLRSRSSSSSLSRRLSLSSSRRLRLRLRLRRLLSSLSSSRRLRLRLRLRLSLSSSSSSSSSSSSSRLRLLRLRLRLRLRLRLRLSLSSSLSLSLLSLRLSLRSLRSLRSLSLSLRSRLSLRSLRLSRSLLLRLRLRRRRSLSLSSLLSLSLSLSSLLSLSLLRLRSLLRSRLSLSSLLLLSSSSSSSSSSSSSSSSSSSSRLRLLRRLRLRLLRLRLRLRLRLSSSSLSLRLLRLSLSSLSLSLSLSLRLLRLSLLLSRSSSSSSSSSSSSSSSRLRLRLLRLRLSLSRSRSSSLSRLRLRLRSLSLSLSRLLSRLSLSLSLSLSSLSLSLLSLSRLLRLRLRLRLRLRLRLRLRLRLSLSRLRLSLLRRLSLLSLSLSLSLSLLSLSLSLRLRLRLRLRLRLRLRLRLRRLRSLSLSLSLSLSLSLSSLSSSSSLSLSSSLSLSLSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS

Możesz narysować tutaj ślizgawki (R i L są odwrócone, ale nie wpływa to na ważność)

Pyth, 22 20 bajtów

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

Wypróbuj sam lub uruchom testsuite .

Zwróć uwagę na wartości ASCII dla SRL, odpowiednio 83, 76, 82. Nadużywam faktu, że:

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

Stąd trzymam zmienną dla bieżącej pozycji i bieżącego kierunku. Dla każdego znaku mnożę bieżący kierunek przez powyższą liczbę zespoloną, a następnie dodaj go do bieżącej pozycji.

Na koniec sprawdzam, czy wszystkie odwiedzane pozycje są unikalne.

CJam, 30 bajtów

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

Wyjaśnienie, które wkrótce nastąpi.

Wypróbuj online tutaj lub uruchom cały pakiet .

JavaScript (ES6), 84 89

Uruchom snippet w przeglądarce Firefox, aby przetestować.

Niektóre uwagi:

• wąż porusza się wewnątrz tablicy F. Nieodwiedzone komórki mają wartość undefined. Przy pierwszej wizycie operator tyldy zmienia go na -1, co jest prawdą. Ostatecznie podczas drugiej wizyty wartość zmienia się na 0, co jest fałszem, a everypętla kończy się, zwracając wartość false.
• w JS elementy tablicy z niekanonicznymi indeksami (nie liczbowymi lub ujemnymi) są w jakiś sposób „ukryte”, ale istnieją. Tutaj bez problemu używam indeksów ujemnych.

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 bajtów

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

Podobnie do metody orlp, tworzy listę wszystkich punktów w płaszczyźnie złożonej odwiedzanych przez węża, zaczynając od początku. Jeśli lista nie zawiera zduplikowanych elementów, kod zwraca pewną wartość dodatnią. Zauważ, że w ciągu ponad 999 elementów kalkulator nie będzie w stanie wygenerować wystarczająco długiej listy i popełni błąd.

EDYCJA: Zapisano dwa bajty kosztem brzydoty, ponieważ żadne dwa punkty sieci na płaszczyźnie złożonej nie mogą znajdować się w tej samej odległości od e ^ i.

TI-BASIC, 60 58 bajtów

Edit: Ignoruj wszystko poniżej: Roztwór ti-podstawowy pracy jest tutaj , przez Thomas-KWA. Idź do góry!

⁻jest [(-)]kluczem, a Ans jest [2ND]->[(-)]. Uruchom go, umieszczając instrukcje węża w cudzysłowach ( [ALPHA]->[+]), a następnie dwukropek, a następnie nazwę programu. Na przykład, jeśli nazwiesz program „SNAKE”, uruchomisz test w OP jako "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

Edycja: Nie działa SRRLSLLRRRS. Mam poprawioną wersję o wielkości 61 bajtów, ale nie działa w pierwszym niepoprawnym przypadku testowym:

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

Spróbuję naprawić jutro.

Aktualizacja: więc problem polega na tym, że mój algorytm jest wadliwy. Gdybym użył pętli For (w przeciwieństwie do seq ((aby osiągnąć to samo)), to (właściwie oba powyższe algorytmy) można opisać następująco:

1. Zainicjuj zmienną licznika na 1.
2. Przeczytaj ciąg. Jeśli symbol się zmienia, zwiększ wartość zmiennej licznika. Jeśli symbol się powtarza, zmniejsz go.
3. Jeśli zmienna licznika jest większa niż 0, wyświetl 1 (poprawny). W przeciwnym razie wyświetl 0 (nieprawidłowy).

Nie działa to jednak w przypadku nieprawidłowych ślizgaczy takich jak SRLRLRLRLRRRSS. Spróbuję teraz wymyślić lepszy algorytm ... lub wykraść inną odpowiedź.

Jestem w 90% pewien, że można to seq(właściwie zastąpić jednym poleceniem, ale na razie jest to tak małe, jak tylko mogę. Jeśli zamierzasz zbudować to do 8xp za pomocą Sourcecodera, a nie pisać, pamiętaj, że ≠należy go zastąpić, !=a ⁻1+bit należy zastąpić ~1+.

Rubinowy 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 online: http://ideone.com/pepeW2

Wersja bez golfa:

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 49 49 50

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

Oczekuje, że łańcuch będzie istniał na stosie i zwraca albo 0albo 1.

Możesz wypróbować online z testami na ważne i nieprawidłowe węże.

Jest to w zasadzie ten sam pomysł, co w mojej odpowiedzi Ruby . Tylko tablica kierunkowa jest traktowana inaczej, ponieważ AFAIK Golfscript nie ma funkcji arary obrotu. W tym przypadku buduję odpowiednio dużą tablicę kierunków, mnożąc ją 10000 razy, a następnie przycinając od początku 0, 1 lub 3 elementy, w zależności od bieżącego polecenia (S, R lub L). Bieżący „kierunek”, do którego należy się przenieść, jest zawsze pierwszym elementem w tablicy.

Oto z komentarzami:

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

Edytować:

Zapisano 1 znak, modyfikując sposób zużycia tablicy „kierunków”.

Edytować:

zapisano 1 znak, przesuwając o 10 zamiast 1, aby skorzystać ze ?składni (mocy).