Count rook moves 1D

Question

Given a position with a row of rooks and/or empty spaces, output how many different rook moves are possible. A rook can move left or right to an empty space, but not to one that requires passing over another rook. When a rook moves, the other rooks remain in place.

For example, from this position, 6 moves are possible:

.R..RRR.

• The first (leftmost) rook can move 1 space left, or 1 or 2 spaces right (3 moves)
• The next rook can only move 1 or 2 spaces left (2 moves)
• The third rook cannot move at all because it's squeezed between two other rooks (0 moves)
• The last rook can only move 1 space right (1 move)

Note that a position might have no rooks at all, or no empty spaces at all.

Input: A non-empty list (string, array, etc..) of rooks and empty spaces. You can represent them as True/False, 1/0, 'R'/'.', or any two consistent distinct single-byte characters or one-digit numbers of your choice. It's up to you which one means rook and which means empty space.

Output: A non-negative integer. Whole-number floats are also fine.

Test cases

The output is the number on the left.

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

For more test cases, here are all inputs up to length 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

Answer 1

Retina, 14 9 bytes

w`_+R|R_+

Try it online! Link includes test cases. Uses _ for empty space as it's the most pleasant non-regex character. Works by counting the number of substrings that correspond to a valid Rook move. A substring is a valid Rook move if it contains at least one _ plus a single R at either the beginning or the end.

Answer 2

Python 3, 30 29 bytes

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

Try it online!

-1 byte thanks to @JoKing

The function takes a Python byte string as input. Each empty space is encoded as a tab and each rook is encoded as a byte b'\x00' having value 0.

The computation is equivalent to lambda s:(s+s).strip().count(b'\t') while having a lower byte count.

Answer 3

JavaScript (ES6),  38  33 bytes

Saved 5 bytes thanks to @JoKing

Takes input as a string. Expects a space for an empty square and any other character for a rook.

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

Try it online!

Commented

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 bytes

Saved 7 bytes thanks to @Grimy

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

Try it online!

Answer 4

Japt, 5 bytes

²x èS

Try it

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

Answer 5

Perl 6, 16 bytes

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

Try it online!

A regex that matches all exhaustive instances of rooks followed by spaces, or spaces followed by a rook and returns the number of matches.

Answer 6

05AB1E, 5 bytes

«ðÚð¢

Try it online!

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

Answer 7

Retina, 23 15 bytes

Double the number of spaces between rooks, grep lines with at least one rook, then count the number of spaces.

R.+R
$0$0
G`R
 

Try it online!

Though the program uses spaces instead of periods, I added prefix code so that the test cases provided may be easily pasted in and used.

I was hoping I could use overlapping matches with (?<=R.*) | (?=.*R), but overlaps aren't quite that aggressive. It would need to count all possible ways a match could be obtained in order to return the correct result with that method.

Answer 8

Jelly, 5 bytes

ḲẈ+ƝS

Try it online!

-1 thanks to Jonathan Allan.

0 represent a rook, 1 represents an empty space.

Answer 9

Jelly, 6 bytes

t1;ḟẠS

Try it online!

A monadic link taking a list of 0 for rook and 1 for space and returning an integer with the number of moves. The TIO link takes the pasted list of possible boards given in the question, converts to the right format and then outputs the calculated and correct answers.

Explanation

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

Answer 10

Japt, 6 bytes

Spaces for spaces, any other character for rooks.

²x ¸ÊÉ

Try it

Answer 11

Snails, 7 bytes

At least it beats Retina :)

o
\.+\R

Try it online!

Answer 12

Stax, 7 6 5 bytes

àσQ█ε

Run and debug it

Use tab for empty square and any other character for rook.

Answer 13

C (clang), 57 bytes

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

Try it online!

• Saved 1 thanks to @ceilingcat

I realized it didn't worked for empty lists.. Now it works! Plus saved some bytes!

1=rook. 0=space.

for(.. i+=n++?-i:1)// counts spaces or reset extra moves => i=-~i!*n++ ( @ceilingcat )

o+=*n?r=1,i:r; // adds to output -i-(extra moves) when a rook is met plus sets -r-(rook met), -i- will be cleared in for increment sentence.

adds -r- for every space(rook met guaranteed )

Answer 14

Haskell, 36 bytes

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

Try it online!

Uses 1 for empty space, 0 for rook. Counts the number of 1's not in an initial block of ones, and adds that to the result for the reversed string.

Answer 15

Haskell, 33 bytes

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

Try it online!

Anonymous function that takes input as a list of 1s (spaces) and 0s (rooks). This trims spaces from the start and the end of the list, then concatenates the two versions of the list and sums them.

This uses GHC 8.4.1 or later to have access to the <> operator without importing it.

Answer 16

Wolfram Language (Mathematica), 43 38 bytes

Count[Subsequences@#,{0,1..}|{1..,0}]&

Try it online!

Port of Neil's Retina solution. Uses 1 for spaces and 0 for rooks.

Answer 17

Python 2, 59 bytes

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

Try it online!

Answer 18

Japt, 6 bytes

²x ¸ÊÉ

Try it online

Answer 19

Stax, 7 6 bytes

-1 byte thanks to recursive

╣ë|óêπ

Run and debug it

Answer 20

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

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

Saved a byte thanks to @someone

Try it online!

Answer 21

Haskell, 68 58 54 bytes

(n#y)(a:x)|a<1=n+(0#1)x|m<-n+1=y+(m#y)x
(_#_)x=0
f=0#0

Try it online!

Answer 22

C, 183 156 151 137 96 91 bytes

Thanks to ceilingcat for 91 bytes.

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 is a rook, everything else is a space.

TIO

Answer 23

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

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

Try it online!

Answer 24

Red, 46 bytes

func[s][length? next split trim append s s sp]

Try it online!

Just a Red port of Arnauld's JavaScript/Python solutions. Takes a space as an empty square.

Answer 25

Java 11, 35 32 bytes

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

Port of @Joel's Python 3 answer.
-3 bytes thanks to @Joel as well.

Uses NULL-bytes (\0) for Rooks and tabs (\t) for spaces.

Try it online.

I tried using s->(s+s).trim().chars().sum()/9 at first as 31-byter, but this doesn't work because the String#trim builtin not only removes leading and trailing spaces/tabs/newlines, but also all other bytes that are smaller than or equal to U+0020 (unicode 32; a space), so it'll remove the NULL-bytes as well..
Thanks to Joel for recommending me the new Java 11+ String#strip builtin (which I forgot they added) as alternative. This one also removes trailing/leading portions, but in this case only whitespaces, so the NULL-bytes are retained.

Explanation:

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

Answer 26

Befunge-98 (PyFunge), 73 bytes

#;ep10fp#;>#v~:'.-#v_$1+0k
v0+ge0*gf0$_v#!-R':<
>ep20fp   v >0fg1-*0eg+.@

Try it online!

Answer 27

Pyth, 7 bytes

/r6*2Qd

Try it online!

Takes a string of R for rooks, (space) for empty spaces

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

Answer 28

x86-64 - 26 Bytes

Input is an array of up to 32 bits and an integer representing number of squares, 1 representing rook, 0 representing empty.

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  

Copies the bits so that it is added to the left of it and removes the trailing zero bits. Then gets number of leading zero bits and subtracts it from the total number of zero bits.

x86-64 Machine Code - 22 Bytes - regular length chess ranks only.

Input is a 32-bit integer with the least significant byte made of 8 bits representing the rooks. 1 is a rook, 0 is empty.

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  

Copies the bits into the next significant byte and removes the trailing zero bits. Then gets number of leading zero bits and subtracts it from the total number of zero bits.