14
\$\begingroup\$

Chess is a game with 6 different types of pieces that can move in different ways:

  • Pawns - They can only move up or capture diagonally (also forward). Capturing a piece behind them or beside them is illegal. The only exception is en passant. For this challenge, if a pawn reaches the 8th rank (or row), assume it becomes a queen.

  • Bishops - They move diagonally and the squares they travel on will always have the same color (i.e if the square the bishop is currently on is white, the bishop can't move to a darker square for instance).

  • Knights - They move pretty awkwardly. They can move two spaces up/down then one space to the right/left or two spaces right/left then on space up/down.

  • Rooks - They can only move in straight lines, up or down or left or right.

  • Queens - They can move diagonally like a bishop or in straight lines like a rook

  • Kings - They can only move to squares they are touching (including diagonals).

This chess.com link to clarify the above. A chessboard and its coordinates are shown below:

enter image description here

So given an entirely empty chessboard except for one piece and the inputs -- the piece's type and its current position, what are the piece's legal moves?

Examples

Input: Rook a8
Output: a1 a2 a3 a4 a5 a6 a7 b8 c8 d8 e8 f8 g8 h8

Input: Pawn a2
Output: a4 a3 

Input: Pawn a3
Output: a4 

Input: Knight a1
Output: c2 b3

Input: Bishop h1
Output: a8 b7 c6 d5 e4 f3 g2

Input: King b2
Output: c2 c3 c1 b3 b1 a1 a2 a3

Input: Queen h1
Output: a8 b7 c6 d5 e4 f3 g2 h2 h3 h4 h5 h6 h7 h8 a1 b1 c2 d1 e1 f1 g1 

Rules and Specifications

  • A legal move is defined as a move in which the piece can go to while being on the board. So a rook at a1 can go to a8 (moving to the right) but not to b2 since you can't get there with a straight line (only possible in two or more moves)

  • Pawns will never be in the first or eighth rank (it would then be another piece). If a pawn is in the second rank, it can move up two spaces (not for captures). Otherwise, it can only move forward a square.

  • Notation for Queening a pawn is not needed

  • Capitalization does not matter though the letter must come before and attached to the number

  • The acceptable moves must be separated in some way (i.e commas, spaces, different lines, in a list)

  • Always assume that the bottom left corner is a1 and you are playing as White

  • The input can be a single string (i.e rooka3 or Rook a3 or rook a3 or Rook A3) is acceptable and can be in any order (i.e the position before the type like A3 rook). Multiple strings are also acceptable.

Winning Criteria

Shortest code wins!

\$\endgroup\$
  • 1
    \$\begingroup\$ @HyperNeutrino Pawns will now never be on the eighth rank. The extra test cases for queening or changing the pawn to a bishop, rook, or knight was seen as quite annoying \$\endgroup\$ – Anthony Pham Apr 1 '17 at 13:47
  • 1
    \$\begingroup\$ @HyperNeutrino Must have missed that. Pawn captures are not needed \$\endgroup\$ – Anthony Pham Apr 1 '17 at 13:54
  • 1
    \$\begingroup\$ @HyperNeutrino Yes \$\endgroup\$ – Anthony Pham Apr 1 '17 at 13:57
  • 1
    \$\begingroup\$ @officialaimm Yes as you are white \$\endgroup\$ – Anthony Pham Apr 1 '17 at 15:06
  • 2
    \$\begingroup\$ Your first test case is incorrect. It should read a1 a2 a3 a4 a5 a6 a7 b8 c8 d8 e8 f8 g8 h8, not b1 ... h1. \$\endgroup\$ – HyperNeutrino Apr 1 '17 at 15:46
7
\$\begingroup\$

JavaScript (ES6), 256 ... 229 227 bytes

Takes input as two strings (p, s), where p is the case-insensitive name of the piece and s is the source square. Returns a space-separated list of destination squares.

f=(p,s,i=128)=>i--?f(p,s,i)+([x=255,x<<8,2,x,195,60][P=(I=parseInt)(p,32)*5&7]>>i/8&((d=i%8)<(S=(x=I(s,18)-181)/18|x%18*16,P>2?8:P<2|S>23||2))&!((S+=I('gfh1eivx'[i>>4],36)*(i&8?d+1:~d))&136)?'abcdefgh'[S&7]+(S+16>>4)+' ':''):''

How it works

Piece name decoding

The name of the piece p is converted to an integer P by parsing it in base 32, multiplying the result by 5 and isolating the 3 least significant bits: parseInt(p, 32) * 5 & 7

 Piece    | As base 32 |        * 5 | & 7
----------+------------+------------+----
 "king"   |     674544 |    3372720 |  0
 "knight" |  695812669 | 3479063345 |  1
 "pawn"   |        810 |       4050 |  2    NB: 'pawn' is parsed as 'pa', because 'w'
 "queen"  |   28260823 |  141304115 |  3        is not a valid character in base 32
 "rook"   |     910100 |    4550500 |  4
 "bishop" |  388908825 | 1944544125 |  5

In addition to being a perfect hash, a good thing about this formula is that all sliding pieces (Queen, Rook and Bishop) appear at the end of the list, which allows to identify them with a simple P > 2.

Source square decoding

The source square s is converted to an integer S by parsing it in base 18 and converting the result to 0x88 coordinates.

That leads to the following board representation:

     a    b    c    d    e    f    g    h
8  0x70 0x71 0x72 0x73 0x74 0x75 0x76 0x77
7  0x60 0x61 0x62 0x63 0x64 0x65 0x66 0x67
6  0x50 0x51 0x52 0x53 0x54 0x55 0x56 0x57
5  0x40 0x41 0x42 0x43 0x44 0x45 0x46 0x47
4  0x30 0x31 0x32 0x33 0x34 0x35 0x36 0x37
3  0x20 0x21 0x22 0x23 0x24 0x25 0x26 0x27
2  0x10 0x11 0x12 0x13 0x14 0x15 0x16 0x17
1  0x00 0x01 0x02 0x03 0x04 0x05 0x06 0x07

Directions encoding

There are 16 possible directions: 4 along ranks and files, 4 along diagonals and 8 for the knights.

As hexadecimal:                     As decimal:

      +0x1F       +0x21                    +31         +33
+0x0E +0x0F +0x10 +0x11 +0x12        +14   +15   +16   +17   +18
      -0x01 [SRC] +0x01                     -1  [SRC]   +1
-0x12 -0x11 -0x10 -0x0F -0x0E        -18   -17   -16   -15   -14
      -0x21       -0x1F                    -33         -31

Therefore, the list of directions that a piece can move towards can be encoded as a 16-bit bitmask.

Bit:    |   F   E   D   C   B   A   9   8   7   6   5   4   3   2   1   0 | As
Vector: | +33 -33 +31 -31 +18 -18 +14 -14  +1  -1 +17 -17 +15 -15 +16 -16 | decimal
--------+-----------------------------------------------------------------+--------
King    |   0   0   0   0   0   0   0   0   1   1   1   1   1   1   1   1 | 255
Knight  |   1   1   1   1   1   1   1   1   0   0   0   0   0   0   0   0 | 65280
Pawn    |   0   0   0   0   0   0   0   0   0   0   0   0   0   0   1   0 | 2
Queen   |   0   0   0   0   0   0   0   0   1   1   1   1   1   1   1   1 | 255
Rook    |   0   0   0   0   0   0   0   0   1   1   0   0   0   0   1   1 | 195
Bishop  |   0   0   0   0   0   0   0   0   0   0   1   1   1   1   0   0 | 60

The absolute values of the direction vectors can be stored in base 36:

[16, 15, 17, 1, 14, 18, 31, 33][n] <==> parseInt('gfh1eivx'[n], 36)

Formatted and commented

f = (p, s, i = 128) =>                     // given a piece p, a square s and a counter i
  i-- ?                                    // if i is >= 0:
    f(p, s, i) + (                         //   do a recursive call to f()
      [ x = 255, x << 8, 2, x, 195, 60 ][  //   take the direction bitmask for:
        P = (I = parseInt)(p, 32) * 5 & 7  //   P = piece index in [0 .. 5]
      ] >> i / 8 & (                       //   and test the bit for the current direction
        (d = i % 8) < (                    //   d = current move distance - 1
          S = (x = I(s, 18) - 181) / 18 |  //   S = source square in
              x % 18 * 16,                 //       0x88 representation
          P > 2 ? 8 : P < 2 | S > 23 || 2  //   compare d with the maximum move range for
        )                                  //   this piece
      ) ?                                  //   if the above test passes:
        (                                  //     we add to S:
          S += I(                          //       the absolute value of the vector of
            'gfh1eivx'[i >> 4], 36         //       the current direction,
          ) *                              //       multiplied by
          (i & 8 ? d + 1 : ~d)             //       the move distance with the vector sign
        ) & 136 ?                          //     if the result AND'd with 0x88 is not null:
          ''                               //       this is an invalid destination square
        :                                  //     else:
          'abcdefgh'[S & 7] +              //       it is valid: convert it back to ASCII
          (S + 16 >> 4) + ' '              //       and append a space separator
      :                                    //   else:
        ''                                 //     this is an invalid move
    )                                      //   end of this iteration
  :                                        // else:
    ''                                     //   stop recursion

Test cases

f=(p,s,i=128)=>i--?f(p,s,i)+([x=255,x<<8,2,x,195,60][P=(I=parseInt)(p,32)*5&7]>>i/8&((d=i%8)<(S=(x=I(s,18)-181)/18|x%18*16,P>2?8:P<2|S>23||2))&!((S+=I('gfh1eivx'[i>>4],36)*(i&8?d+1:~d))&136)?'abcdefgh'[S&7]+(S+16>>4)+' ':''):''

console.log(f('Rook',   'a8'));
console.log(f('Pawn',   'a2'));
console.log(f('Pawn',   'a3'));
console.log(f('Knight', 'a1'));
console.log(f('Bishop', 'h1'));
console.log(f('King',   'b2'));
console.log(f('Queen',  'h1'));

\$\endgroup\$
  • \$\begingroup\$ This is just... amazing... Wow. Good job! \$\endgroup\$ – HyperNeutrino Apr 1 '17 at 21:17
2
\$\begingroup\$

Python 2, 484 472 423 406 bytes

This is a lot longer than I wanted it to be.

i=input()
a=ord(i[1][0])-97
c=int(i[1][1])
g=range(-8,8)
b=sum([[(a-x,c-x),(a-x,c+x)]for x in g],[])
r=sum([[(a-x,c),(a,c-x)]for x in g],[])
print[chr(x[0]+97)+str(x[1])for x in set([[(a,c+1)]+[(a,c+2)]*(c==2),b,sum([[(a-x,c-y)for x,y in[[X,Y],[X,-Y],[-X,Y],[-X,-Y]]]for X,Y in[[1,2],[2,1]]],[]),r,b+r,[(a-x,c-y)for x in[-1,0,1]for y in[-1,0,1]]]['wsioen'.find(i[0][2])])-set([a,c])if-1<x[0]<8and 0<x[1]<9]

-12 bytes by removing some unnecessary variable names
-49 bytes thanks to ovs by splitting s into multiple variables
-17 bytes thanks to ovs by switching from range to comparison

Input is taken as ['PieceName', '<letter><num>']. Output is given as an array of strings in the same 1-indexed a-h format <letter><num>.

\$\endgroup\$
  • \$\begingroup\$ How do you enter the input (more specifically, what format) \$\endgroup\$ – Anthony Pham Apr 1 '17 at 16:03
  • \$\begingroup\$ @AnthonyPham Forgot to mention; I will edit into post. Thanks. \$\endgroup\$ – HyperNeutrino Apr 1 '17 at 16:06
  • \$\begingroup\$ If you split s into 2 variables, you can save ~50 bytes \$\endgroup\$ – ovs Apr 1 '17 at 18:43
  • \$\begingroup\$ You can replace in range with comparison \$\endgroup\$ – ovs Apr 1 '17 at 18:53
  • \$\begingroup\$ @ovs Thank you, 66 bytes total :P \$\endgroup\$ – HyperNeutrino Apr 1 '17 at 21:16

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