Hitung langkah rook 1D

31

Diberi posisi dengan deretan benteng dan / atau ruang kosong, hasilkan berapa banyak gerakan benteng yang berbeda dimungkinkan. Benteng dapat bergerak ke kiri atau kanan ke ruang kosong, tetapi tidak ke benteng yang membutuhkan melewati benteng lain. Ketika benteng bergerak, benteng-benteng lainnya tetap di tempatnya.

Misalnya, dari posisi ini, 6 gerakan dimungkinkan:

.R..RRR.
  • Benteng pertama (paling kiri) dapat bergerak 1 spasi kiri, atau 1 atau 2 spasi kanan (3 bergerak)
  • Benteng berikutnya hanya bisa bergerak 1 atau 2 spasi tersisa (2 bergerak)
  • Benteng ketiga tidak bisa bergerak sama sekali karena terjepit di antara dua benteng lainnya (0 bergerak)
  • Benteng terakhir hanya bisa bergerak 1 spasi ke kanan (1 bergerak)

Perhatikan bahwa suatu posisi mungkin tidak memiliki benteng sama sekali, atau tidak ada ruang kosong sama sekali.

Input: Daftar non-kosong (string, array, dll.) Dari rooks dan spasi kosong. Anda dapat mewakili mereka sebagai True/ False, 1/ 0, 'R'/ '.', atau dua karakter byte tunggal yang berbeda atau satu digit angka pilihan Anda. Terserah Anda mana yang berarti benteng dan yang berarti ruang kosong.

Output: Bilangan bulat non-negatif. Mengapung seluruh nomor juga baik-baik saja.

Uji kasus

Outputnya adalah angka di sebelah kiri.

6 .R..RRR.
0 .
0 R
4 R..RR
3 ...R
8 ..R..R..
0 ......

Untuk lebih banyak kasus uji, berikut adalah semua input hingga panjang 5.

0 .
0 R
0 ..
1 .R
1 R.
0 RR
0 ...
2 ..R
2 .R.
1 .RR
2 R..
2 R.R
1 RR.
0 RRR
0 ....
3 ...R
3 ..R.
2 ..RR
3 .R..
3 .R.R
2 .RR.
1 .RRR
3 R...
4 R..R
3 R.R.
2 R.RR
2 RR..
2 RR.R
1 RRR.
0 RRRR
0 .....
4 ....R
4 ...R.
3 ...RR
4 ..R..
4 ..R.R
3 ..RR.
2 ..RRR
4 .R...
5 .R..R
4 .R.R.
3 .R.RR
3 .RR..
3 .RR.R
2 .RRR.
1 .RRRR
4 R....
6 R...R
5 R..R.
4 R..RR
4 R.R..
4 R.R.R
3 R.RR.
2 R.RRR
3 RR...
4 RR..R
3 RR.R.
2 RR.RR
2 RRR..
2 RRR.R
1 RRRR.
0 RRRRR
Tidak
sumber

Jawaban:

9

Retina , 14 9 byte

w`_+R|R_+

Cobalah online! Tautan termasuk kasus uji. Menggunakan _ruang kosong karena merupakan karakter non-regex yang paling menyenangkan. Bekerja dengan menghitung jumlah substring yang sesuai dengan langkah Benteng yang valid. Substring adalah gerakan Rook yang valid jika berisi setidaknya satu _ditambah satu Rdi awal atau akhir.

Neil
sumber
Oh, pada dasarnya Anda menemukan cara melakukan apa yang saya sebutkan dalam jawaban saya. Idk kenapa aku tidak memikirkan itu.
mbomb007
9

Python 3 , 30 29 byte

lambda s:sum((s+s).strip())/9

Cobalah online!

-1 byte berkat @JoKing

Fungsi ini mengambil string byte Python sebagai input. Setiap ruang kosong dikodekan sebagai tab dan setiap benteng dikodekan sebagai byte yang b'\x00'memiliki nilai 0.

Perhitungannya sama dengan lambda s:(s+s).strip().count(b'\t')saat memiliki jumlah byte lebih rendah.

Joel
sumber
6

JavaScript (ES6),  38  33 byte

Disimpan 5 byte berkat @ JoKing

Mengambil input sebagai string. Mengharapkan ruang untuk kotak kosong dan karakter lain untuk benteng.

s=>(s+s).trim().split` `.length-1

Cobalah online!

Berkomentar

s =>          // s = input, e.g. " R  RRR "
  (s + s)     // double -> " R  RRR  R  RRR "
  .trim()     // remove leading and trailing spaces -> "R  RRR  R  RRR"
  .split` `   // split on spaces -> [ 'R', '', 'RRR', '', 'R', '', 'RRR' ]
  .length - 1 // return the length - 1 -> 6

Python 2 ,  40  33 byte

Disimpan 7 byte berkat @Grimy

lambda s:(s+s).strip().count(' ')

Cobalah online!

Arnauld
sumber
1
Versi Python seharusnya digunakan countsebagai ganti split( TIO )
Grimmy
@Grimy Terima kasih. :)
Arnauld
5

Japt , 5 byte

²x èS

Cobalah

²x èS        Implicit input string of U
²            U + U
 x           Remove trailing and leading whitespace
   èS        Number of spaces
Perwujudan Ketidaktahuan
sumber
4

Perl 6 , 16 byte

{+m:ex/s+R|Rs+/}

Cobalah online!

Regex yang cocok dengan semua instance rook yang lengkap diikuti oleh spasi, atau spasi yang diikuti oleh rook dan mengembalikan jumlah pertandingan.

Jo King
sumber
4

05AB1E , 5 byte

«ðÚð¢

Cobalah online!

«       # concatenate the input with itself
 ðÚ     # remove leading and trailing spaces
   ð¢   # count spaces
Grimmy
sumber
3

Retina , 23 15 byte

Gandakan jumlah spasi di antara benteng, garis grep dengan setidaknya satu benteng, kemudian hitung jumlah spasi.

R.+R
$0$0
G`R
 

Cobalah online!

Meskipun program ini menggunakan spasi bukan periode, saya menambahkan kode awalan sehingga kasus uji yang diberikan dapat dengan mudah ditempel dan digunakan.

Saya berharap bisa menggunakan pertandingan yang tumpang tindih (?<=R.*) | (?=.*R), tetapi tumpang tindih tidak begitu agresif. Perlu untuk menghitung semua cara yang memungkinkan suatu pertandingan dapat diperoleh untuk mengembalikan hasil yang benar dengan metode itu.

mbomb007
sumber
1
Tampaknya memberikan hasil yang salah untuk .R.R.R.mengubah baris pertama R.+Rmungkin bisa membantu?
Neil
@Neil Tetap. Terima kasih.
mbomb007
2

Jelly , 6 byte

t1;ḟẠS

Cobalah online!

Tautan monadik mengambil daftar 0untuk benteng dan 1untuk ruang dan mengembalikan integer dengan jumlah gerakan. TIO link mengambil daftar papan yang mungkin disisipkan yang diberikan dalam pertanyaan, mengkonversi ke format yang tepat dan kemudian menampilkan jawaban yang dihitung dan benar.

Penjelasan

t1     | Trim 1s from end
  ;    | Concatenate to input
   ḟẠ  | Filter out 1s if all input were 1s, otherwise filter out 0s
     S | Sum
Nick Kennedy
sumber
2

Japt , 6 byte

Spasi untuk spasi, karakter lain untuk benteng.

²x ¸ÊÉ

Cobalah

Shaggy
sumber
1
Kalahkan kamu 10 menit: P
Oliver
Sialan, @Oliver! : p
Shaggy
2

Siput, 7 byte

Setidaknya itu mengalahkan Retina :)

o
\.+\R

Cobalah online!

feersum
sumber
2

Jelly , 5 byte

ḲẈ+ƝS

Cobalah online!

-1 terima kasih kepada Jonathan Allan .

0mewakili benteng, 1mewakili ruang kosong.

Erik the Outgolfer
sumber
1
Jika Anda menggunakan karakter ruang untuk Benteng dan karakter lain untuk ruang yang dapat Anda gunakan untuk mendapatkan lima:ḲẈ+ƝS
Jonathan Allan
@Jonathan Allan LOL tidak memikirkan itu. Dan sebelum itu saya bereksperimen tetapi menggunakan ṣ0...
Erik the Outgolfer
2

C (dentang) , 57 byte

i,r,o;g(*n,z){for(o=r=i=0;z--;i=-~i*!*n++)o+=*n?r=1,i:r;}

Cobalah online!

  • Disimpan 1 berkat @ceilingcat

Saya menyadari itu tidak berfungsi untuk daftar kosong .. Sekarang berfungsi! Plus menghemat beberapa byte!

1 = benteng. 0 = spasi.

untuk (.. i + = n ++? - i: 1) // menghitung spasi atau mengatur ulang gerakan ekstra => i = - ~ i ! * n ++ (@ceilingcat)

o + = * n? r = 1, i: r; // menambahkan ke output -i- (gerakan ekstra) ketika sebuah rook bertemu ditambah set -r- (rook met), -i- akan dihapus untuk kalimat kenaikan.

menambahkan -r- untuk setiap ruang (benteng bertemu dijamin)

AZTECCO
sumber
Batuan? Apakah batu Anda bergerak?
Tiang
1
@Tepat lol maaf! Diedit
AZTECCO
2

Haskell , 36 byte

f s=sum$snd.span(>0)=<<[s,reverse s]

Cobalah online!

Menggunakan 1 untuk ruang kosong, 0 untuk benteng. Menghitung jumlah 1 yang tidak dalam blok awal, dan menambahkannya ke hasil untuk string yang terbalik.

Tidak
sumber
2

Haskell , 33 byte

sum.(t.reverse<>t)
t=snd.span(>0)

Cobalah online!

Fungsi anonim yang mengambil input sebagai daftar 1s (spasi) dan 0s (rooks). Ini memangkas spasi dari awal dan akhir daftar, lalu menyatukan dua versi daftar dan menjumlahkannya.

Ini menggunakan GHC 8.4.1 atau lebih baru untuk memiliki akses ke <>operator tanpa mengimpornya.

Jo King
sumber
1

Python 2 , 59 byte

def f(r):S=map(len,r.split('R'));return sum(S)*2-S[0]-S[-1]

Cobalah online!

Chas Brown
sumber
1

Java 11, 35 32 byte

s->(s+s).strip().chars().sum()/9

Port of @ Joel 's Python 3 menjawab .
-3 byte terima kasih kepada @ Joel juga.

Menggunakan NULL-byte ( \0) untuk Benteng dan tab ( \t) untuk spasi.

Cobalah online.

Saya mencoba menggunakan s->(s+s).trim().chars().sum()/9pada awalnya sebagai 31-byter, tetapi ini tidak berhasil karena String#trimbuiltin tidak hanya menghilangkan spasi / tab / baris baru, tetapi juga semua byte lain yang lebih kecil atau sama dengan U+0020(unicode 32; a space) , jadi itu akan menghapus NULL-byte juga ..
Terima kasih kepada Joel untuk merekomendasikan saya Java 11+ String#stripbuiltin baru (yang saya lupa mereka tambahkan) sebagai alternatif. Yang ini juga menghilangkan bagian trailing / memimpin, tetapi dalam hal ini hanya spasi putih , sehingga NULL-byte dipertahankan.

Penjelasan:

s->                              // Method with String as parameter & integer return-type
  (s+s)                          //  Concatenate the input to itself
       .strip()                  //  Then trim all leading and trailing tabs
               .chars().sum()    //  Sum the unicode values of the remaining characters
                             /9  //  And divide it by 9 to get the amount of remaining tabs
Kevin Cruijssen
sumber
1
Java 11+ memungkinkan penggunaan String.strip()untuk menghapus hanya spasi putih: 32 byte
Joel
@ Joel Ah, benar-benar lupa tentang itu! Terima kasih. :)
Kevin Cruijssen
1

Perl 5 -MList::Util=sum -pF/R/ , 40 byte

$\=2*sum map$_=y///c,@F}{$\-="@F"+$F[-1]

Cobalah online!

Xcali
sumber
1

C # (Visual C # Interactive Compiler) , 27 byte

x=>(x+x).Trim().Sum(d=>d)/9

Menyimpan satu byte berkat @someone

Cobalah online!

Perwujudan Ketidaktahuan
sumber
1
Afaik Anda dapat menggunakan tab untuk menyimpan byte (charcode pendek), tapi saya di telepon.
kata ganti saya adalah monicareinstate
1

Stax , 7 6 byte

-1 byte berkat rekursif

╣ë|óêπ

Jalankan dan debug itu

Oliver
sumber
1
Kerja bagus. Omong-omong, subtrating 1 dapat dilakukan dengan v, yang akan menghemat satu byte.
Rekursif
1

C , 183 156 151 137 96 91 byte

Berkat ceilingcat untuk 91 byte.

c,e;char*z,b[9];main(d){for(gets(z=b);e=*z>81?c-=e*~!d,d=0:e+1,*++z;);printf("%i",d?:c+e);}

R adalah benteng, yang lainnya adalah ruang.

TIO

girobuz
sumber
Beberapa hal - fungsi (alih-alih program lengkap) diperbolehkan, Anda dapat mengandalkan perilaku yang tidak terdefinisi (mis. Secara otomatis nol) selama program Anda bekerja dengan benar pada setidaknya satu kompiler, lebih pendek untuk digunakan 82sebagai gantinya 'R', atau lebih pendek untuk gunakan e+e*ddaripada e*(1+d), e=0,d=1;else e++; can be changed to e = -1, d = 1; e ++; , and b [a] `dan b[++a]dapat diganti dengan *bdan*++b
ASCII
0

Pyth , 7 byte

/r6*2Qd

Cobalah online!

Mengambil string Rfor rooks, (spasi) untuk ruang kosong

/     d  # Count spaces in
 r6      #  Strip spaces from
   *2Q   #   2 * input() (= concatenation)
ar4093
sumber
0

x86-64 - 26 Bytes

Input adalah array hingga 32 bit dan integer yang mewakili jumlah kotak, 1 mewakili benteng, 0 mewakili kosong.

C4 E2 69 F7 C1       shlx        eax,ecx,edx
0B C1                or          eax,ecx  
F3 0F BC C8          tzcnt       ecx,eax  
D3 E8                shr         eax,cl  
F3 0F BD C8          lzcnt       ecx,eax  
F7 D0                not         eax  
F3 0F B8 C0          popcnt      eax,eax  
2B C1                sub         eax,ecx  
C3                   ret  

Menyalin bit sehingga ditambahkan ke sebelah kiri dan menghilangkan bit nol yang tertinggal. Kemudian dapatkan jumlah nol bit terkemuka dan kurangi dari jumlah total nol bit.

x86-64 Machine Code - 22 Bytes - hanya peringkat catur panjang reguler.

Input adalah integer 32-bit dengan byte paling signifikan yang dibuat dari 8 bit mewakili rooks. 1 adalah benteng, 0 kosong.

8A E9                mov         ch,cl  
91                   xchg        eax,ecx
F3 0F BC C8          tzcnt       ecx,eax
D3 E8                shr         eax,cl 
F3 0F BD C8          lzcnt       ecx,eax
F7 D0                not         eax  
F3 0F B8 C0          popcnt      eax,eax
2B C1                sub         eax,ecx
C3                   ret  

Menyalin bit ke byte signifikan berikutnya dan menghilangkan bit nol yang tertinggal. Kemudian dapatkan jumlah nol bit terkemuka dan kurangi dari jumlah total nol bit.

saya'
sumber
Jadi ini hanya berfungsi untuk baris dengan panjang 8? Jika ya, itu sepertinya agak terlalu spesifik untuk tantangan.
ar4093
Secara tidak sengaja berasumsi bahwa mereka adalah peringkat rook reguler, diperbaiki sekarang.
saya