Ular yang valid di pesawat

23

Terinspirasi oleh salah satu video Vi Hart (yang merupakan harta karun yang penuh dengan ide tantangan potensial)

Seekor ular terdiri dari segmen dengan panjang yang sama dan koneksi antara masing-masing segmen bisa lurus atau berbelok 90 °.
Kita dapat menyandikan ular seperti itu (hingga rotasi, yang tergantung pada arah awal) dengan menuliskan slither , arah belokan (Lurus / Kiri / Kanan) yang diperlukan. Yang ini, mulai dari kiri atas dan menunjuk ke kanan

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

Akan diwakili oleh meluncur SRSLSSLRLRSSRSRSS

Dan tentu saja ular planar tidak dapat memotong dirinya sendiri (seperti di SSSSLLLSS), yang akan menghasilkan Game Over pixelated mengerikan.

Tugas Anda adalah menentukan apakah slither valid atau tidak (menghasilkan setidaknya satu persimpangan-sendiri)

Input
Sebuah string yang terbuat dari huruf SLRdengan 2 < length < 10000
Output
Something Truthy jika itu adalah slither yang valid dan sesuatu Falsey jika tidak.

Uji kasus

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

__Invalid__
SRRLSLLRRLLSLRRSRLLRSRRLLRRSRLLLLRSRRLLRRSRLLRSRRLSLLRRLLSLRR
SRRLSLLRRLLSLRRSRLLRSRRLLSRSSSRSSSSSSSRSRSSSSSSSRRLLRRSRLLRSRRLSLLRRLLSLRR
SRRSRSRSSRSSRSSSRSSSRSSSSSSSSSSRSSSSRSSSSSRSSSSSRSSSSSSRSSSSSSRSSSSSS
SSSSSSSSSSLSSSSSSSLSSSSSSSSLSSSSSLSSSSSSLSSSLLRRLRLRRLLSLSSSRRSSSSRSSSRSSSSSSRSSSSSRSSSSSSSSRSSSSSSSRSSSSSSSSS
LRSLLRLSRSLLSRLSLRSLSSSLRRSSLSRRLRSRLRLSLRLLRLRSSLSLRLRSRSSSSSLSRRLSLSSSRRLRLRLRLRRLLSSLSSSRRLRLRLRLRLSLSSSSSSSSSSSSSRLRLLRLRLRLRLRLRLRLSLSSSLSLSLLSLRLSLRSLRSLRSLSLSLRSRLSLRSLRLSRSLLLRLRLRRRRSLSLSSLLSLSLSLSSLLSLSLLRLRSLLRSRLSLSSLLLLSSSSSSSSSSSSSSSSSSSSRLRLLRRLRLRLLRLRLRLRLRLSSSSLSLRLLRLSLSSLSLSLSLSLRLLRLSLLLSRSSSSSSSSSSSSSSSRLRLRLLRLRLSLSRSRSSSLSRLRLRLRSLSLSLSRLLSRLSLSLSLSLSSLSLSLLSLSRLLRLRLRLRLRLRLRLRLRLRLSLSRLRLSLLRRLSLLSLSLSLSLSLLSLSLSLRLRLRLRLRLRLRLRLRLRRLRSLSLSLSLSLSLSLSSLSSSSSLSLSSSLSLSLSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS

Anda dapat menggambar slithers di sini (R dan L terbalik, tetapi itu tidak mempengaruhi validitas)

DenDenDo
sumber
Apakah input harus dilakukan dalam program atau dapat dibaca dari file?
MI Wright
1
Haruskah SRRR Benar atau Salah? Itu menghubungkan tetapi tidak memotong sendiri.
orlp
menyentuh tantangan ular NSFW?
Ewan
3
jika Anda menggambar SRRRpada kertas grafik dengan satu kotak per segmen maka itu akan tumpang tindih dan karena itu tidak valid RRR, akan tetapi, akan menempati tepat 2x2 persegi tanpa tumpang tindih (seperti dalam game klasik)
DenDenDo
Serupa tetapi bukan duplikat (karena tujuan yang berbeda dan aturan konstruksi yang berbeda).
trichoplax

Jawaban:

20

Pyth, 22 20 byte

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

Cobalah sendiri atau jalankan testuite .

Perhatikan nilai-nilai ASCII dari SRL, masing-masing 83, 76, 82. Saya menyalahgunakan fakta bahwa:

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

Dari sini saya hanya menyimpan variabel untuk posisi saat ini dan arah saat ini. Untuk setiap karakter saya kalikan arah saat ini dengan angka kompleks di atas, kemudian tambahkan ke posisi saat ini.

Pada akhirnya saya memeriksa apakah semua posisi yang dikunjungi unik.

orlp
sumber
SRRR = true ????
Ewan
@ Ewan Pada pemeriksaan lebih dekat - Saya tidak yakin apakah itu harus salah atau tidak. Kepala dan ekor terhubung, tetapi tidak berpotongan.
orlp
bagaimana dengan SRRRS?
Ewan
@ Ewan Kisah yang sama - koneksi tetapi tidak ada persimpangan. Pertanyaannya tidak jelas apa yang harus dikembalikan untuk ini.
orlp
1
bagaimana Anda menggambar SRRR?
Ewan
6

CJam, 30 byte

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

Penjelasan untuk segera menyusul.

Cobalah online di sini atau jalankan seluruh rangkaian .

Pengoptimal
sumber
Sial, cepat sekali. Saya bahkan belum memikirkan algoritma untuk menyelesaikannya sendiri.
DenDenDo
SRRRS = true ???
Ewan
@ Ewan umm, apakah kita mengasumsikan bahwa 0 awalnya diisi dan diperhitungkan?
Pengoptimal
1
Saya kira saya menafsirkannya seperti permainan ular, di mana gerakan mengambil blok ruang. dan beberapa dari kalian menafsirkannya sebagai garis lebar nol
Ewan
@ Ewan Pertanyaan saya agak berbeda. Ketika kita memiliki satu gerakan, katakanlah S, apakah itu berarti ular tersebut telah menempati keduanya (0,0) dan (1,0)?
Pengoptimal
6

JavaScript (ES6), 84 89

Jalankan cuplikan di Firefox untuk menguji.

Beberapa catatan:

  • ular itu bergerak di dalam f array. Sel yang belum dikunjungi memiliki nilai undefined. Pada kunjungan pertama, operator tilde mengubahnya menjadi -1 yang benar. Akhirnya, pada kunjungan kedua perubahan nilai menjadi 0 yang salah dan everyloop berakhir dengan false.
  • di JS, elemen array dengan indeks non kanonik (bukan numerik atau negatif) entah bagaimana 'tersembunyi', tetapi mereka memang ada. Di sini saya menggunakan indeks negatif tanpa masalah.

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

TI-BASIC, 49 56 53 51 byte

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

Mirip dengan metode orlp, ini membuat daftar semua titik di bidang kompleks yang dikunjungi oleh ular, mulai dari asal. Jika daftar tidak memiliki elemen duplikat, kode mengembalikan nilai positif. Perhatikan bahwa pada untaian lebih dari 999 elemen, kalkulator tidak akan dapat menghasilkan daftar yang cukup panjang, dan akan salah.

SUNTING: Menyelamatkan dua byte dengan mengorbankan keburukan karena tidak ada dua titik kisi pada bidang kompleks yang berjarak sama dari e ^ i.

lirtosiast
sumber
5

TI-BASIC, 60 58 byte

Sunting: Abaikan semua yang di bawah ini: solusi ti-basic yang berfungsi ada di sini , oleh thomas-kwa. Pilih itu!

adalah [(-)]kuncinya, dan Ans adalah [2ND]->[(-)]. Jalankan dengan melampirkan instruksi ular di tanda kutip ( [ALPHA]->[+]) diikuti oleh titik dua kemudian nama program. Misalnya, jika Anda memberi nama program "SNAK", Anda akan menjalankan test case di OP as "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: Gagal aktif SRRLSLLRRRS. Saya memiliki versi revisi sebesar 61 byte, tetapi gagal pada kasus uji pertama yang tidak valid:

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

Saya akan mencoba memperbaiki besok.


Perbarui: jadi masalahnya adalah algoritma saya cacat. Jika saya menggunakan For (loop sebagai lawan dari seq ((untuk mencapai hal yang sama)) (kedua algoritma di atas, sebenarnya) dapat digambarkan sebagai ini:

  1. Inisialisasi variabel penghitung ke 1.
  2. Baca string. Jika simbol berubah, tambahkan variabel penghitung. Jika simbol berulang, kurangi itu.
  3. Jika variabel penghitung lebih besar dari 0, tampilkan 1 (valid). Jika tidak, tampilkan 0 (tidak valid).

Namun, ini gagal pada slithers yang tidak valid seperti SRLRLRLRLRRRSS. Sekarang saya akan mencoba untuk membuat algoritma yang lebih baik ... atau mencuri dari jawaban lain.


Saya 90% yakin ini bisa diganti dengan satu seq(perintah, sebenarnya, tapi untuk saat ini sekecil yang saya bisa. Jika Anda berniat untuk membangun ini ke 8xp menggunakan Sourcecoder sebagai lawan benar-benar mengetiknya, perhatikan bahwa harus diganti dengan !=dan ⁻1+bit harus diganti dengan ~1+.

MI Wright
sumber
1

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

Tes online: http://ideone.com/pepeW2

Versi tidak disatukan:

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

Golfscript 48 49 50

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

Mengharapkan string ada di tumpukan dan mengembalikan salah satu 0atau 1.

Anda dapat mencobanya secara online dengan tes untuk valid dan tidak valid ular.

Ini pada dasarnya ide yang sama seperti dalam jawaban Ruby saya . Array arah hanya ditangani secara berbeda, karena AFAIK Golfscript tidak memiliki fungsi putar arary. Dalam hal ini, saya membangun array arah yang cukup besar, dengan mengalikannya 10.000 kali dan kemudian memangkas dari elemen awal 0, 1, atau 3, tergantung pada perintah saat ini (S, R, atau L). "Arahan" saat ini untuk pindah selalu menjadi item pertama dalam array.

Ini dia dengan komentar:

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

Edit:

Disimpan 1 char dengan memodifikasi bagaimana array "arah" dikonsumsi.

Edit:

menghemat 1 char dengan memindahkan selisih 10 bukannya 1 untuk memanfaatkan ?sintaks (daya).

Cristian Lupascu
sumber