12
\$\begingroup\$

The challenge

Write a program or function which takes a string input as a function parameter or from stdin and determines if it is a valid FEN string.

Input

You can assume the input will only ever include the following characters (case sensitive)
pkqrbnPKQRBN12345678/
The length of the input will always be a minimum of 1 character and a maximum of 100 characters

Output

Output should be a truthy/falsey value. These can be any values you wish as long as they are consistent (all truthy results have the same output, all falsey results have the same output). You should have exactly two distinct possible outputs.

What counts as valid

Lowercase letters represent black pieces, uppercase letters represent white pieces.
You should ensure it is possible in a game of chess for the pieces in the current position to exist.
Each player will always have exactly 1 king (k/K)
Each player may have no more than 8 pawns (p/P)
Each player will usually have no more than 1* queen (q/Q)
Each player will usually have no more than 2* rooks (r/R)
Each player will usually have no more than 2* knights (n/N)
Each player will usually have no more than 2* bishops (b/B)
* It is legal for a player to 'promote' a pawn to any of these four pieces.
The total of pawns, queens, rooks, knights and bishops for each player will never be more than 15

The total number of pieces plus empty squares (denoted by numbers) should always add up to exactly 8 for each rank. And there should always be exactly 8 ranks, separated by a forward slash.

Things you can ignore

You do not need to concern yourself with whether or not it is possible to play into the position denoted, or if the position is legal, only that the pieces can exist in the quantities given.
You can ignore further complexities of FEN strings such as player turn, castling rights and en passant.

This is code golf. Shortest program in bytes wins. Usual loopholes and rules apply.

Test Cases

Input rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR
Output True

Input 2br2k1/1p2n1q1/p2p2p1/P1bP1pNp/1BP2PnP/1Q1B2P1/8/3NR2K
Output True

Input r2r2k1/p3q2p/ppR3pr/rP4bp/3p4/5B1P/P4PP1/3Q1RK1
Output False
(black has 7 pawns and 4 rooks - impossible)

Input 6k1/pp3ppp/4p3/2P3b1/bPP3P1/3K4/P3Q1q1
Output False (only 7 ranks)

Input 3r1rk1/1pp1bpp1/6p1/pP1npqPn/8/4N2P/P2PP3/1B2BP2/R2QK2R
Output False (9 ranks)

Input 5n1k/1p3r1qp/p3p3/2p1N2Q/2P1R3/2P5/P2r1PP1/4R1K1
Output False (2nd rank has 9 squares/pieces)

Input rnbqkbnr/pppppppp/8/35/8/8/PPPPPPPP/RNBQKBNR
Output True
Thanks to Feersum and Arnauld for clarifying this case (3+5=8)

What is FEN?

FEN is a standard notation for recording the position of the pieces on a chess board. enter image description here
Image credit http://www.chessgames.com

\$\endgroup\$
  • \$\begingroup\$ “Each player will usually have no more than 1* queen”—please clarify what counts as valid, since I assume it doesn’t matter what counts as “usual”. Is it valid for white to have nine queens? Ten queens? Eight pawns and two queens? Zero kings? An unpromoted pawn on the first or last rank? \$\endgroup\$ – Anders Kaseorg Jul 1 '17 at 2:06
  • \$\begingroup\$ @AndersKaseorg * It is legal for a player to 'promote' a pawn to any of these four pieces. The player may have up to 9 queens so long as the number of pawns is reduced to compensate. You do not need to worry about the position of the pieces being legal or illegal, only the number of pieces. \$\endgroup\$ – Darren H Jul 1 '17 at 2:08
  • 1
    \$\begingroup\$ In your third test-case, black has 6 pawns, not 7, making it a 'True' (?) \$\endgroup\$ – pizzapants184 Jul 1 '17 at 5:10
  • 1
    \$\begingroup\$ @DarrenH The FEN position proposed by feersum is valid according to your current rules. 35 is just an unusual way to describe 8 empty squares. \$\endgroup\$ – Arnauld Jul 1 '17 at 10:57
  • 1
    \$\begingroup\$ @PatrickRoberts pawns on first or last rank are valid for the purpose of this challenge. You do not need to account for the legality of a position, only the quantity of pieces. Accounting for the legality of a position (such as both players being in check) adds a lot of complexity so I figured a blanket of 'position doesn't matter' is clearer than a debate on where to draw the line of what needs accounted for and what doesn't. \$\endgroup\$ – Darren H Jul 1 '17 at 14:18
4
\$\begingroup\$

Retina, 105 bytes

[1-8]
$*
^
/
iG`^(/[1KQRBNP]{8}){8}$
G`K
G`k
A`K.*K|k.*k
{2`N

2`B

2`R

1`Q

K

T`L`P
8`P

A`P
}T`l`L
^.

Try it online! Link includes test cases. Explanation:

[1-8]
$*

Expand digits to empty squares, which we denote using 1s.

^
/
iG`^(/[1KQRBNP]{8}){8}$

Delete the input if it does not match 8 sets of 8 valid squares joined with /s. (An extra / is prefixed to simplify the check.)

G`K
G`k
A`K.*K|k.*k

Delete the input if it has no white or no black king, or if it has two of either.

{2`N

2`B

2`R

1`Q

K

Delete white's starting pieces, if they are still there.

T`L`P

Demote any remaining white pieces to pawns.

8`P

Delete the valid white pawns.

A`P

Delete the input if there are any white pawns left over.

}T`l`L

Check again but with the black pieces.

^.

Output a truthy value unless the line was deleted.

\$\endgroup\$
6
\$\begingroup\$

JavaScript (ES6), 168 174 ... 155

This answer has been edited an embarrassing number of times. Hopefully, the current version is both reliable and decently golfed.


Returns a boolean.

s=>[...s].map(c=>++n%9?+c?n+=--c:a[i='pP/KkQqRrBbNn'.search(c),i&=i>4&a[i]>(i>6)||i]=-~a[i]:x+=c=='/',a=[x=n=0])&&!([p,P,s,k,K]=a,n-71|x-7|s|k*K-1|p>8|P>8)

Formatted and commented

s => [...s].map(c =>                  // for each character 'c' in the FEN string 's':
  ++n % 9 ?                           //   if we haven't reached the end of a rank:
    +c ?                              //     if the character is a digit:
      n += --c                        //       advance the board pointer by c - 1 squares
    :                                 //     else:
      a[                              //       update the piece counter array:
        i =                           //         i = piece identifier (0 to 12)
          'pP/KkQqRrBbNn'.search(c),  //             with special case: '/' --> 2
        i &=                          //         we count it as a promoted pawn instead if:
          i > 4 &                     //           it's a Q, R, B or N and we already have
          a[i] > (i > 6) ||           //           2 of them for R, B, N or just 1 for Q
          i                           //           else, we keep the identifier unchanged
      ] = -~a[i]                      //         '-~' allows to increment 'undefined'
  :                                   //   else:
    x += c == '/',                    //     check that the expected '/' is there
  a = [                               //   initialize the piece counter array 'a'
    x =                               //   initialize the '/' counter 'x',
    n = 0 ]                           //   initialize the board pointer 'n'
) &&                                  // end of map()
!(                                    // now it's time to perform all sanity checks:
  [p, P, s, K, k] = a,                //   copy the 5 first entries of 'a' to new variables
  n - 71 |                            //   have we reached exactly the end of the board?
  x - 7 |                             //   have we identified exactly 7 ends of rank?
  s |                                 //   have we encountered any unexpected '/' character?
  k * K - 1 |                         //   do we have exactly one king on each side?
  p > 8 |                             //   no more than 8 black pawns, including promotions?
  P > 8)                              //   no more than 8 white pawns, including promotions?

Test cases

let f =

s=>[...s].map(c=>++n%9?+c?n+=--c:a[i='pP/KkQqRrBbNn'.search(c),i&=i>4&a[i]>(i>6)||i]=-~a[i]:x+=c=='/',a=[x=n=0])&&!([p,P,s,k,K]=a,n-71|x-7|s|k*K-1|p>8|P>8)

console.log(f("rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR")) // True
console.log(f("2br2k1/1p2n1q1/p2p2p1/P1bP1pNp/1BP2PnP/1Q1B2P1/8/3NR2K")) // True
console.log(f("r2r2k1/p3q2p/ppR3pr/rP4bp/3p4/5B1P/P4PP1/3Q1RK1")) // False (black has 7 pawns and 4 rooks - impossible)
console.log(f("6k1/pp3ppp/4p3/2P3b1/bPP3P1/3K4/P3Q1q1")) // False (only 7 ranks)
console.log(f("3r1rk1/1pp1bpp1/6p1/pP1npqPn/8/4N2P/P2PP3/1B2BP2/R2QK2R")) // False (9 ranks)
console.log(f("5n1k/1p3r1qp/p3p3/2p1N2Q/2P1R3/2P5/P2r1PP1/4R1K1")) // False (2nd rank has 9 squares/pieces)
console.log(f("rnbqkbnr/pppppppp/8/35/8/8/PPPPPPPP/RNBQKBNR")) // True
console.log(f("rnbqkbnr/pppppppp/8/9/7/8/PPPPPPPP/RNBQKBNR")) // False (additional test case suggested by Rick Hitchcock)
console.log(f("rnbqkbnr/pppp/ppp/8/8/8/8/PPPPPPPP/RNBQKBNR")) // False (additional test case)

\$\endgroup\$
3
\$\begingroup\$

Python 3, 284 259 236 225 247 234 bytes

import re
s=input()
t,c=s.split("/"),s.count;P=p=9;o=0
for x in"pqrnb":p-=max(0,c(x)-o);P-=max(0,c(x.upper())-o);o+=o<2
v=8==len(t)and all(8==sum(int(x)for x in re.sub("[A-z]","1",p))for p in t)and p>0<P and c('k')==c('K')==1
print(v)

Try it Online!

Try it Online with all of the test cases!

-11 bytes thanks to Mr. Xcoder

-13 bytes thanks to Jonathan Allen

+22 I forgot kings existed.

Semi-ungolfed with some explanation:

import re
string = input()
split = string.split("/")
count = string.count # find # of occurences of char in string
pawns = 9 # represents the # of pawns a player has out of the game... plus one, e.g. 1 is all in game, 2 is one out, 0 is invalid
PAWNS = 9 # would be 8, but then I would need >= instead of >
offset = 0 # default for pawns
for char in "pqrnb": # for each pawn, each queen over 1, and each rook/knight/bishop over 2 for each player
    # subtract one from the players 'pawns' var, which must end up 1 or greater to be valid
    # otherwise too many pawns/queens/etc of that player are on the board
    pawns -= max(0,count(char)-offset)
    PAWNS -= max(0,count(char.upper())-offset)
    offset += (offset 0 and PAWNS>0 and \ # make sure each player does not have an invalid number of pawns/q/n/b/r
    count('k')==count('K')==1 # correct # of kings
print(valid)
\$\endgroup\$
  • 1
    \$\begingroup\$ 234 bytes. I replaced ,p,P=9,9 with ;P=p=9. \$\endgroup\$ – Mr. Xcoder Jul 1 '17 at 7:24
  • 1
    \$\begingroup\$ 230 bytes. Why did you have unnecessary spaces in the for-loop :/ \$\endgroup\$ – Mr. Xcoder Jul 1 '17 at 7:27
  • 1
    \$\begingroup\$ 225 bytes: You can use p>0<P instead of p>0and P>0 to save 5 bytes too. Alternatively, you could have used p and P (for -3 bytes), you don't need the >0, because non-zero values are truthy in Python \$\endgroup\$ – Mr. Xcoder Jul 1 '17 at 7:32
  • 1
    \$\begingroup\$ Pawns can be upgraded, the spec says that there are 7 lowercase pawns and 4 rooks, whereas my eyes only see 6 lowercase 'p's. \$\endgroup\$ – pizzapants184 Jul 1 '17 at 7:50
  • 1
    \$\begingroup\$ You can save 13 bytes by initialising with o=0 before the loop and incrementing with o+=o<2 at the end of the loop's body. \$\endgroup\$ – Jonathan Allan Jul 1 '17 at 23:33
2
\$\begingroup\$

PHP, 269 bytes

$t=($o=count_chars($a="$argn/"))[47]==8&$o[107]==1&$o[75]==1&9>($w=$u=$o[80])&9>$b=$l=$o[112];foreach([81,82,78,66]as$k=>$v){$z=$k?11:10;$b+=$x=$o[32+$v];$t&=$l+$x<$z;$w+=$x=$o[$v];$t&=$u+$x<$z;}$t&=$b<16&$w<16;for(;$c=$a[$n++];)$c<A?$c>0?$s+=$c:$t&=!$s-=8:++$s;echo$t;

Try it online!

\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 181 172 174 bytes

f=([c,...s],n=1,o={p:0,P:0})=>c?c=='/'&&n%9?0:f(s,n+(+c||1),(o[c]=(o[c]||0)+(/[qrbn]/i.test(c)&&o[c]>1-/q/i.test(c)?!o[c>'a'?'p':'P']++:1),o)):o.p<9&o.P<9&n==72&o.k==1&o.K==1

Ungolfed:

f=
  ([c,...s],                 //c is current character
   n=1,                      //n is current square, range [1-72] (board is 9x8 due to slashes)
   o={p:0,P:0}               //o holds piece counts
  )=>
  c?
    c=='/'&&n%9?0:           //ensure 8 squares per row
    f(s,
      n+(+c||1),             //increment n by the correct number of squares
      (o[c]=(o[c]||0)+(/[qrbn]/i.test(c)&&o[c]>1-/q/i.test(c)?!o[c>'a'?'p':'P']++:1),o)
                             //"depromote" extra queens, rooks, bishops, or knights
     ):
  o.p<9&o.P<9&               //no more than 8 pawns per side (accounting for promotions)
  o.k==1&o.K==1&             //each side has one and only one king  
  n==72                      //correct number of squares

f=([c,...s],n=1,o={p:0,P:0})=>c?c=='/'&&n%9?0:f(s,n+(+c||1),(o[c]=(o[c]||0)+(/[qrbn]/i.test(c)&&o[c]>1-/q/i.test(c)?!o[c>'a'?'p':'P']++:1),o)):o.p<9&o.P<9&n==72&o.k==1&o.K==1

console.log(f('rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR')); //true
console.log(f('2br2k1/1p2n1q1/p2p2p1/P1bP1pNp/1BP2PnP/1Q1B2P1/8/3NR2K')) //true
console.log(f('r2r2k1/p3q2p/ppR3pr/rP4bp/3p4/5B1P/P4PP1/3Q1RK1')); //false
console.log(f('6k1/pp3ppp/4p3/2P3b1/bPP3P1/3K4/P3Q1q1')); //false
console.log(f('3r1rk1/1pp1bpp1/6p1/pP1npqPn/8/4N2P/P2PP3/1B2BP2/R2QK2R')); //false
console.log(f('5n1k/1p3r1qp/p3p3/2p1N2Q/2P1R3/2P5/P2r1PP1/4R1K1')); //false
console.log(f('rnbqkbnr/pppppppp/8/35/8/8/PPPPPPPP/RNBQKBNR')); //true
console.log(f('rnbqkbnr/pppppppp/8/35/8/8/PPPPPPPP/RNQQKBNR')); //false, too many queens

\$\endgroup\$
1
\$\begingroup\$

Python 3, 263 bytes

s=input()
n=0
for a in s.split('/'):n+=sum([int(c)if c in"123456789"else 1for c in a])
m=lambda k:{c:s.count(c)for c in s}.get(k,0)
p=[m("p"),m("P")]
for c in"rnbqRNGQ":b=c in"qQ";p[c<"Z"]+=m(c)+b-2if m(c)>2-b else 0
print((n==64)&(p[0]<9>p[1])&(m("K")>0<m("k")))

Try it online!

Not the smallest Python submission, but I think it still has some promise.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.