Table of Contents
Simplified Chess Engine II – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ replace HackerRank Solution
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <utility>
using namespace std;
#define CLEAN_BOARD "................"
#define Z(x, i, j) x[(i)+(j)*4]
void debug(const string B) {
cout << B[0] << B[1] << B[2] << B[3] << endl;
cout << B[4] << B[5] << B[6] << B[7] << endl;
cout << B[8] << B[9] << B[10]<< B[11] << endl;
cout << B[12]<< B[13]<< B[14]<< B[15] << endl;
}
bool has_figure(const string &b, char c) {
return b.find(c) != std::string::npos;
}
vector<string> knight_moves(const string &B, int color, int i, int j) {
vector<string> res;
int sign = color == 1 ? 0 : 32;
if (i+2 < 4 && j+1 < 4)
if ((Z(B,i+2,j+1)&32) != sign || Z(B,i+2,j+1) == '.') { string M(B); Z(M,i+2,j+1) = Z(M,i,j); Z(M,i,j) = '.'; res.push_back(M); }
if (i+2 < 4 && j-1 >= 0)
if ((Z(B,i+2,j-1)&32) != sign || Z(B,i+2,j-1) == '.') { string M(B); Z(M,i+2,j-1) = Z(M,i,j); Z(M,i,j) = '.'; res.push_back(M); }
if (i+1 < 4 && j+2 < 4)
if ((Z(B,i+1,j+2)&32) != sign || Z(B,i+1,j+2) == '.') { string M(B); Z(M,i+1,j+2) = Z(M,i,j); Z(M,i,j) = '.'; res.push_back(M); }
if (i+1 < 4 && j-2 >= 0)
if ((Z(B,i+1,j-2)&32) != sign || Z(B,i+1,j-2) == '.') { string M(B); Z(M,i+1,j-2) = Z(M,i,j); Z(M,i,j) = '.'; res.push_back(M); }
if (i-2 >= 0 && j+1 < 4)
if ((Z(B,i-2,j+1)&32) != sign || Z(B,i-2,j+1) == '.') { string M(B); Z(M,i-2,j+1) = Z(M,i,j); Z(M,i,j) = '.'; res.push_back(M); }
if (i-2 >= 0 && j-1 >= 0)
if ((Z(B,i-2,j-1)&32) != sign || Z(B,i-2,j-1) == '.') { string M(B); Z(M,i-2,j-1) = Z(M,i,j); Z(M,i,j) = '.'; res.push_back(M); }
if (i-1 >= 0 && j+2 < 4)
if ((Z(B,i-1,j+2)&32) != sign || Z(B,i-1,j+2) == '.') { string M(B); Z(M,i-1,j+2) = Z(M,i,j); Z(M,i,j) = '.'; res.push_back(M); }
if (i-1 >= 0 && j-2 >= 0)
if ((Z(B,i-1,j-2)&32) != sign || Z(B,i-1,j-2) == '.') { string M(B); Z(M,i-1,j-2) = Z(M,i,j); Z(M,i,j) = '.'; res.push_back(M); }
return res;
}
vector<string> bishop_moves(const string &B, int color, int i, int j) {
vector<string> res;
int sign = color == 1 ? 0 : 32;
int ii=i-1, jj=j-1;
while (ii>=0 && jj>=0) {
if (Z(B,ii,jj) == '.') {
string M(B); Z(M,ii,jj) = Z(M,i,j); Z(M,i,j) = '.'; res.push_back(M);
}
else if ((Z(B,ii,jj)&32) != sign) {
string M(B); Z(M,ii,jj) = Z(M,i,j); Z(M,i,j) = '.'; res.push_back(M);
break;
}
else { break; }
--ii;--jj;
}
ii=i+1, jj=j-1;
while (ii<4 && jj>=0) {
if (Z(B,ii,jj) == '.') {
string M(B); Z(M,ii,jj) = Z(M,i,j); Z(M,i,j) = '.'; res.push_back(M);
}
else if ((Z(B,ii,jj)&32) != sign) {
string M(B); Z(M,ii,jj) = Z(M,i,j); Z(M,i,j) = '.'; res.push_back(M);
break;
}
else { break; }
++ii;--jj;
}
ii=i+1, jj=j+1;
while (ii<4 && jj<4) {
if (Z(B,ii,jj) == '.') {
string M(B); Z(M,ii,jj) = Z(M,i,j); Z(M,i,j) = '.'; res.push_back(M);
}
else if ((Z(B,ii,jj)&32) != sign) {
string M(B); Z(M,ii,jj) = Z(M,i,j); Z(M,i,j) = '.'; res.push_back(M);
break;
}
else { break; }
++ii;++jj;
}
ii=i-1, jj=j+1;
while (ii>=0 && jj<4) {
if (Z(B,ii,jj) == '.') {
string M(B); Z(M,ii,jj) = Z(M,i,j); Z(M,i,j) = '.'; res.push_back(M);
}
else if ((Z(B,ii,jj)&32) != sign) {
string M(B); Z(M,ii,jj) = Z(M,i,j); Z(M,i,j) = '.'; res.push_back(M);
break;
}
else { break; }
--ii;++jj;
}
return res;
}
vector<string> rook_moves(const string &B, int color, int i, int j) {
vector<string> res;
int sign = color == 1 ? 0 : 32;
int ii=i-1;
while (ii>=0) {
if (Z(B,ii,j) == '.') {
string M(B); Z(M,ii,j) = Z(M,i,j); Z(M,i,j) = '.'; res.push_back(M);
}
else if ((Z(B,ii,j)&32) != sign) {
string M(B); Z(M,ii,j) = Z(M,i,j); Z(M,i,j) = '.'; res.push_back(M);
break;
}
else { break; }
--ii;
}
ii=i+1;
while (ii<4) {
if (Z(B,ii,j) == '.') {
string M(B); Z(M,ii,j) = Z(M,i,j); Z(M,i,j) = '.'; res.push_back(M);
}
else if ((Z(B,ii,j)&32) != sign) {
string M(B); Z(M,ii,j) = Z(M,i,j); Z(M,i,j) = '.'; res.push_back(M);
break;
}
else { break; }
++ii;
}
int jj=j-1;
while (jj>=0) {
if (Z(B,i,jj) == '.') {
string M(B); Z(M,i,jj) = Z(M,i,j); Z(M,i,j) = '.'; res.push_back(M);
}
else if ((Z(B,i,jj)&32) != sign) {
string M(B); Z(M,i,jj) = Z(M,i,j); Z(M,i,j) = '.'; res.push_back(M);
break;
}
else { break; }
--jj;
}
jj=j+1;
while (jj<4) {
if (Z(B,i,jj) == '.') {
string M(B); Z(M,i,jj) = Z(M,i,j); Z(M,i,j) = '.'; res.push_back(M);
}
else if ((Z(B,i,jj)&32) != sign) {
string M(B); Z(M,i,jj) = Z(M,i,j); Z(M,i,j) = '.'; res.push_back(M);
break;
}
else { break; }
++jj;
}
return res;
}
vector<string> pawn_moves(const string &B, int color, int i, int j) {
vector<string> res;
if (color == 1) {
if (Z(B,i,j+1) == '.') {
string M(B); Z(M,i,j) = '.';
if (j == 2) {
Z(M,i,j+1) = 'B'; res.push_back(M);
Z(M,i,j+1) = 'R'; res.push_back(M);
Z(M,i,j+1) = 'N'; res.push_back(M);
}
else {
Z(M,i,j+1) = 'P'; res.push_back(M);
}
}
if (i!=3 && (Z(B,i+1,j+1) == 'q' || Z(B,i+1,j+1) == 'b' || Z(B,i+1,j+1) == 'r' || Z(B,i+1,j+1) == 'n' || Z(B,i+1,j+1) == 'p')) {
string M(B); Z(M,i,j) = '.';
if (j == 2) {
Z(M,i+1,j+1) = 'B'; res.push_back(M);
Z(M,i+1,j+1) = 'R'; res.push_back(M);
Z(M,i+1,j+1) = 'N'; res.push_back(M);
}
else {
Z(M,i+1,j+1) = 'P'; res.push_back(M);
}
}
if (i!=0 && (Z(B,i-1,j+1) == 'q' || Z(B,i-1,j+1) == 'b' || Z(B,i-1,j+1) == 'r' || Z(B,i-1,j+1) == 'n' || Z(B,i-1,j+1) == 'p')) {
string M(B); Z(M,i,j) = '.';
if (j == 2) {
Z(M,i-1,j+1) = 'B'; res.push_back(M);
Z(M,i-1,j+1) = 'R'; res.push_back(M);
Z(M,i-1,j+1) = 'N'; res.push_back(M);
}
else {
Z(M,i-1,j+1) = 'P'; res.push_back(M);
}
}
}
else {
if (Z(B,i,j-1) == '.') {
string M(B); Z(M,i,j) = '.';
if (j == 1) {
Z(M,i,j-1) = 'b'; res.push_back(M);
Z(M,i,j-1) = 'r'; res.push_back(M);
Z(M,i,j-1) = 'n'; res.push_back(M);
}
else {
Z(M,i,j-1) = 'p'; res.push_back(M);
}
}
if (i!=3 && (Z(B,i+1,j-1) == 'Q' || Z(B,i+1,j-1) == 'B' || Z(B,i+1,j-1) == 'R' || Z(B,i+1,j-1) == 'N' || Z(B,i+1,j-1) == 'P')) {
string M(B); Z(M,i,j) = '.';
if (j == 1) {
Z(M,i+1,j-1) = 'b'; res.push_back(M);
Z(M,i+1,j-1) = 'r'; res.push_back(M);
Z(M,i+1,j-1) = 'n'; res.push_back(M);
}
else {
Z(M,i+1,j-1) = 'p'; res.push_back(M);
}
}
if (i!=0 && (Z(B,i-1,j-1) == 'Q' || Z(B,i-1,j-1) == 'B' || Z(B,i-1,j-1) == 'R' || Z(B,i-1,j-1) == 'N' || Z(B,i-1,j-1) == 'P')) {
string M(B); Z(M,i,j) = '.';
if (j == 1) {
Z(M,i-1,j-1) = 'b'; res.push_back(M);
Z(M,i-1,j-1) = 'r'; res.push_back(M);
Z(M,i-1,j-1) = 'n'; res.push_back(M);
}
else {
Z(M,i-1,j-1) = 'p'; res.push_back(M);
}
}
}
return res;
}
vector<string> queen_moves(const string &B, int color, int i, int j) {
vector<string> res;
vector<string> A1 = bishop_moves(B, color, i, j);
vector<string> A2 = rook_moves(B, color, i, j);
res.insert(res.end(), A1.begin(), A1.end());
res.insert(res.end(), A2.begin(), A2.end());
return res;
}
int moves_to_win(const string &B, int depth, int max_depth) {
if (depth >= max_depth) return 1000000;
vector<string> moves;
for(int j=0; j<4; ++j) {
for(int i=0; i<4; ++i) {
switch(Z(B, i, j)) {
case 'Q':
{
vector<string> Q = queen_moves(B, 1, i, j);
moves.insert(moves.end(), Q.begin(), Q.end());
break;
}
case 'N':
{
vector<string> N = knight_moves(B, 1, i, j);
moves.insert(moves.end(), N.begin(), N.end());
break;
}
case 'B':
{
vector<string> Bi = bishop_moves(B, 1, i, j);
moves.insert(moves.end(), Bi.begin(), Bi.end());
break;
}
case 'R':
{
vector<string> R = rook_moves(B, 1, i, j);
moves.insert(moves.end(), R.begin(), R.end());
break;
}
case 'P':
{
vector<string> P = pawn_moves(B, 1, i, j);
moves.insert(moves.end(), P.begin(), P.end());
break;
}
}
}
}
int ans = 1000000;
vector<string> good_moves;
for(string m: moves)
if (!has_figure(m, 'q'))
return depth+1;
if (depth+2 > max_depth)
return ans;
for(string m: moves) {
vector<string> op_moves;
for(int j=0; j<4; ++j) {
for(int i=0; i<4; ++i) {
switch(Z(m, i, j)) {
case 'q':
{
vector<string> Q = queen_moves(m, 2, i, j);
op_moves.insert(op_moves.end(), Q.begin(), Q.end());
break;
}
case 'n':
{
vector<string> N = knight_moves(m, 2, i, j);
op_moves.insert(op_moves.end(), N.begin(), N.end());
break;
}
case 'b':
{
vector<string> Bi = bishop_moves(m, 2, i, j);
op_moves.insert(op_moves.end(), Bi.begin(), Bi.end());
break;
}
case 'r':
{
vector<string> R = rook_moves(m, 2, i, j);
op_moves.insert(op_moves.end(), R.begin(), R.end());
break;
}
case 'p':
{
vector<string> P = pawn_moves(m, 2, i, j);
op_moves.insert(op_moves.end(), P.begin(), P.end());
break;
}
}
}
}
bool is_good = true;
for(auto o: op_moves) {
if (!has_figure(o, 'Q')) {
is_good = false;
break;
}
}
if (is_good) {
int ans_next = 0;
for(auto o: op_moves) {
ans_next = max(ans_next, moves_to_win(o, depth+2, max_depth));
if (ans_next > max_depth) break;
}
ans = min(ans, ans_next);
}
}
return ans;
}
int main() {
int T; cin >> T;
for(int t=0; t<T; ++t) {
string B(CLEAN_BOARD);
int w,b,m; cin >> w >> b >> m;
for(int i=0; i<w; ++i) {
char f, col; cin >> f >> col;
int row; cin >> row;
B[col-'A' + (row-1)*4] = f;
}
for(int i=0; i<b; ++i) {
char f, col; cin >> f >> col;
int row; cin >> row;
B[col-'A' + (row-1)*4] = f + ('a' - 'A');
}
cout << (moves_to_win(B, 0, m%2==0 ? m-1 : m) <= m ? "YES" : "NO") << endl;
}
return 0;
}
Java rep HackerRank Solution
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
static class Piece {
public char type;
public boolean isWhite;
public Piece (char type, boolean isWhite) {
this.type = type;
this.isWhite = isWhite;
}
public Piece (Piece p) {
this.type = p.type;
this.isWhite = p.isWhite;
}
}
static class Board {
public Piece[][] pieces = new Piece[4][4];
public Board(ArrayList<String> w, ArrayList<String> b) {
for (String p : w) {
String[] p3 = p.split(" ");
char type = p3[0].charAt(0);
int x = p3[1].charAt(0)-'A';
int y = p3[2].charAt(0)-'1';
pieces[x][y] = new Piece(type, true);
}
for (String p : b) {
String[] p3 = p.split(" ");
char type = p3[0].charAt(0);
int x = p3[1].charAt(0)-'A';
int y = p3[2].charAt(0)-'1';
pieces[x][y] = new Piece(type, false);
}
}
public Board(Board b) {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (b.pieces[i][j] != null)
this.pieces[i][j] = new Piece(b.pieces[i][j]);
}
}
}
public ArrayList<Board> legalMoves(boolean whiteToMove) {
ArrayList<Board> moves = new ArrayList<Board>();
for (int a = 0; a < 4; a++) {
for (int b = 0; b < 4; b++) {
if (pieces[a][b] != null && pieces[a][b].isWhite == whiteToMove) {
if (pieces[a][b].type == 'P') {
int d = whiteToMove?b+1:b-1;
if (pieces[a][d] == null) {
if (d==0||d==3) {
Board newBoard = new Board(this);
newBoard.pieces[a][d] = newBoard.pieces[a][b];
newBoard.pieces[a][b] = null;
newBoard.pieces[a][d].type = 'R';
moves.add(newBoard);
newBoard = new Board(this);
newBoard.pieces[a][d] = newBoard.pieces[a][b];
newBoard.pieces[a][b] = null;
newBoard.pieces[a][d].type = 'B';
moves.add(newBoard);
newBoard = new Board(this);
newBoard.pieces[a][d] = newBoard.pieces[a][b];
newBoard.pieces[a][b] = null;
newBoard.pieces[a][d].type = 'N';
moves.add(newBoard);
}
else {
Board newBoard = new Board(this);
newBoard.pieces[a][d] = newBoard.pieces[a][b];
newBoard.pieces[a][b] = null;
moves.add(newBoard);
}
}
for (int c = a-1; c <= a+1; c+=2) {
if (c>=0&&c<4) {
if (pieces[c][d] != null && pieces[c][d].isWhite != whiteToMove) {
if (d==0||d==3) {
Board newBoard = new Board(this);
newBoard.pieces[c][d] = newBoard.pieces[a][b];
newBoard.pieces[a][b] = null;
newBoard.pieces[c][d].type = 'R';
moves.add(newBoard);
newBoard = new Board(this);
newBoard.pieces[c][d] = newBoard.pieces[a][b];
newBoard.pieces[a][b] = null;
newBoard.pieces[c][d].type = 'B';
moves.add(newBoard);
newBoard = new Board(this);
newBoard.pieces[c][d] = newBoard.pieces[a][b];
newBoard.pieces[a][b] = null;
newBoard.pieces[c][d].type = 'N';
moves.add(newBoard);
}
else {
Board newBoard = new Board(this);
newBoard.pieces[c][d] = newBoard.pieces[a][b];
newBoard.pieces[a][b] = null;
moves.add(newBoard);
}
}
}
}
}
if (pieces[a][b].type == 'N') {
for (int c = -2; c <= 2; c+=4) {
for (int d = -1; d <= 1; d+=2) {
int e = a+c;
int f = b+d;
int g = a+d;
int h = b+c;
if (e >= 0 && e < 4 && f >= 0 && f < 4) {
if (pieces[e][f] == null || pieces[e][f].isWhite != whiteToMove) {
Board newBoard = new Board(this);
newBoard.pieces[e][f] = newBoard.pieces[a][b];
newBoard.pieces[a][b] = null;
moves.add(newBoard);
}
}
if (g >= 0 && g < 4 && h >= 0 && h < 4) {
if (pieces[g][h] == null || pieces[g][h].isWhite != whiteToMove) {
Board newBoard = new Board(this);
newBoard.pieces[g][h] = newBoard.pieces[a][b];
newBoard.pieces[a][b] = null;
moves.add(newBoard);
}
}
}
}
}
if (pieces[a][b].type == 'R' || pieces[a][b].type == 'Q') {
for (int c = -1; c <= 1; c += 2) {
for (int d = a+c; d >= 0 && d < 4; d += c) {
if (pieces[d][b] == null || pieces[d][b].isWhite != whiteToMove) {
Board newBoard = new Board(this);
newBoard.pieces[d][b] = newBoard.pieces[a][b];
newBoard.pieces[a][b] = null;
moves.add(newBoard);
}
if (pieces[d][b] != null)
break;
}
for (int d = b+c; d >= 0 && d < 4; d += c) {
if (pieces[a][d] == null || pieces[a][d].isWhite != whiteToMove) {
Board newBoard = new Board(this);
newBoard.pieces[a][d] = newBoard.pieces[a][b];
newBoard.pieces[a][b] = null;
moves.add(newBoard);
}
if (pieces[a][d] != null)
break;
}
}
}
if (pieces[a][b].type == 'B' || pieces[a][b].type == 'Q') {
for (int c = -1; c <= 1; c += 2) {
for (int d = -1; d <= 1; d += 2) {
for (int e = 1; a+e*c >= 0 && a+e*c < 4 && b+e*d >= 0 && b+e*d < 4; e++) {
int f = a+e*c;
int g = b+e*d;
if (pieces[f][g] == null || pieces[f][g].isWhite != whiteToMove) {
Board newBoard = new Board(this);
newBoard.pieces[f][g] = newBoard.pieces[a][b];
newBoard.pieces[a][b] = null;
moves.add(newBoard);
}
if (pieces[f][g] != null)
break;
}
}
}
}
}
}
}
return moves;
}
public boolean doesQueenExist(boolean whiteQueen) {
for (int a = 0; a < 4; a++) {
for (int b = 0; b < 4; b++) {
if (pieces[a][b] != null && pieces[a][b].type == 'Q' && pieces[a][b].isWhite == whiteQueen)
return true;
}
}
return false;
}
public boolean canCaptureQueen(boolean whiteToMove) {
ArrayList<Board> moves = legalMoves(whiteToMove);
for (Board b : moves) {
if (!b.doesQueenExist(!whiteToMove))
return true;
}
return false;
}
public boolean canReachGoalWhite(int rem) {
if (canCaptureQueen(true))
return true;
if (rem==1)
return false;
ArrayList<Board> moves = legalMoves(true);
for (Board b : moves) {
if (!b.canStopGoalBlack(rem))
return true;
}
return false;
}
public boolean canStopGoalBlack(int rem) {
if (canCaptureQueen(false))
return true;
ArrayList<Board> moves = legalMoves(false);
for (Board b : moves) {
if (!b.canReachGoalWhite(rem-1))
return true;
}
return false;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int g = sc.nextInt();
for (int z = 0; z < g; z++) {
int w = sc.nextInt();
int b = sc.nextInt();
int m = (sc.nextInt()+1)/2;
ArrayList<String> wl = new ArrayList<String>();
ArrayList<String> bl = new ArrayList<String>();
sc.nextLine();
for (int i = 0; i < w; i++) {
wl.add(sc.nextLine());
}
for (int i = 0; i < b; i++) {
bl.add(sc.nextLine());
}
Board start = new Board(wl, bl);
System.out.println(start.canReachGoalWhite(m)?"YES":"NO");
}
}
}
Python 3 rep HackerRank Solution
# coding: utf-8
from __future__ import print_function, unicode_literals
class Piece(object):
def __init__(self, color, ptype, row, col):
self.color = color
self.ptype = ptype
self.row = row
self.col = col
self.captured = False
def valid_moves(self, board):
pass
def can_move_to(self, r, c):
if r == self.row and c == self.col:
return False
if r < 0 or r > 3:
return False
if c < 0 or c > 3:
return False
if board.mat[r][c] is None:
return True
elif board.mat[r][c].color != self.color:
return True
return False
def _straight_moves(self, board):
possible = []
# straight up
for row in range(1, 4):
r, c = self.row - row, self.col
if self.can_move_to(r, c):
possible.append((r, c))
if not board.is_open(r, c):
break
# straight down
for row in range(1, 4):
r, c = self.row + row, self.col
if self.can_move_to(r, c):
possible.append((r, c))
if not board.is_open(r, c):
break
# straight left
for col in range(1, 4):
r, c = self.row, self.col - col
if self.can_move_to(r, c):
possible.append((r, c))
if not board.is_open(r, c):
break
# straight right
for col in range(1, 4):
r, c = self.row, self.col + col
if self.can_move_to(r, c):
possible.append((r, c))
if not board.is_open(r, c):
break
return possible
def _diagonal_moves(self, board):
possible = []
# straight left up
for rc in range(1, 4):
r, c = self.row - rc, self.col - rc
if self.can_move_to(r, c):
possible.append((r, c))
if not board.is_open(r, c):
break
# straight left down
for rc in range(1, 4):
r, c = self.row + rc, self.col - rc
if self.can_move_to(r, c):
possible.append((r, c))
if not board.is_open(r, c):
break
# straight right up
for rc in range(1, 4):
r, c = self.row - rc, self.col + rc
if self.can_move_to(r, c):
possible.append((r, c))
if not board.is_open(r, c):
break
# straight right down
for rc in range(1, 4):
r, c = self.row + rc, self.col + rc
if self.can_move_to(r, c):
possible.append((r, c))
if not board.is_open(r, c):
break
return possible
class Rook(Piece):
def valid_moves(self, board):
possible = self._straight_moves(board)
return possible
class Queen(Piece):
def valid_moves(self, board):
possible = self._straight_moves(board) + self._diagonal_moves(board)
return possible
class Knight(Piece):
def valid_moves(self, board):
r, c = self.row, self.col
possible = [
(r - 2, c - 1), (r - 2, c + 1),
(r - 1, c + 2), (r - 1, c - 2),
(r + 1, c + 2), (r + 1, c - 2),
(r + 2, c - 1), (r + 2, c + 1),
]
return [(rw, cl) for rw, cl in possible if self.can_move_to(rw, cl)]
class Bishop(Piece):
def valid_moves(self, board):
possible = self._diagonal_moves(board)
return possible
type_dict = {
"B": Bishop,
"R": Rook,
"Q": Queen,
"N": Knight,
}
class Pawn(Piece):
def valid_moves(self, board):
if self.ptype != "P":
return type_dict[self.ptype].valid_moves(self, board)
r, c = self.row, self.col
if self.color == "B":
possible = [
(r - 1, c), (r - 1, c - 1), (r - 1, c + 1),
]
else:
possible = [
(r + 1, c), (r + 1, c - 1), (r + 1, c + 1),
]
v = [(rw, cl) for rw, cl in possible if self.can_move_to(rw, cl)]
return v
def can_move_to(self, r, c):
if self.ptype != "P":
return type_dict[self.ptype].can_move_to(self, r, c)
if r == self.row and c == self.col:
return False
if r < 0 or r > 3:
return False
if c < 0 or c > 3:
return False
if board.mat[r][c] is None and c == self.col:
return True
elif board.mat[r][c] is not None and board.mat[r][c].color != self.color and c != self.col:
return True
return False
class Board(object):
def __init__(self):
self.mat = [[None for i in range(4)] for u in range(4)]
self.white = []
self.black = []
def add_piece(self, color, ptype, row, col):
if ptype == "Q":
piece = Queen(color, ptype, row, col)
elif ptype == "N":
piece = Knight(color, ptype, row, col)
elif ptype == "B":
piece = Bishop(color, ptype, row, col)
elif ptype == "R":
piece = Rook(color, ptype, row, col)
elif ptype == "P":
piece = Pawn(color, ptype, row, col)
else:
raise Exception("Invalid type")
self.mat[row][col] = piece
if color == "W":
self.white.append(piece)
elif color == "B":
self.black.append(piece)
def move_to(self, piece, row, col):
self.mat[piece.row][piece.col] = None
if self.mat[row][col] is not None:
captured = self.mat[row][col]
captured.captured = True
self.mat[row][col] = piece
piece.row = row
piece.col = col
if piece.ptype == "P":
# promotion
if piece.color == "W" and piece.row == 3:
return True
elif piece.color == "B" and piece.row == 0:
return True
return False
def undo_move(self, captured, piece, prev_r, prev_c, was_pawn):
self.move_to(piece, prev_r, prev_c)
if was_pawn:
piece.ptype = "P"
if captured:
cr, cc = captured.row, captured.col
self.mat[cr][cc] = captured
captured.captured = False
def is_open(self, r, c):
if r < 0 or r > 3:
return False
if c < 0 or c > 3:
return False
if self.mat[r][c] is None:
return True
return False
def white_can_win(self, turns_left):
if turns_left <= 0:
return False
white_pieces = self.white
q = []
for piece in white_pieces:
if piece.captured is True:
continue
valid_moves = piece.valid_moves(self)
for r, c in valid_moves:
captured = self.mat[r][c]
if captured is not None and captured.ptype == "Q":
return True
q.insert(0, (piece, r, c))
for piece, r, c in q:
prev_r, prev_c = piece.row, piece.col
captured = self.mat[r][c]
was_pawn = self.move_to(piece, r, c)
ptypes = [piece.ptype]
before = piece
if was_pawn:
ptypes = ["B", "R", "N"]
for ptype in ptypes:
piece.ptype = ptype
# if for all follow-up opponent moves, we can find a winning move within the limit, return True
if self.black_cannot_avoid_loss(turns_left - 1):
self.undo_move(captured, piece, prev_r, prev_c, was_pawn)
return True
self.undo_move(captured, piece, prev_r, prev_c, was_pawn)
return False
def black_cannot_avoid_loss(self, turns_left):
if turns_left <= 0:
return False
black_pieces = self.black
for piece in black_pieces:
if piece.captured is True:
continue
valid_moves = piece.valid_moves(self)
for r, c in valid_moves:
prev_r, prev_c = piece.row, piece.col
captured = self.mat[r][c]
if captured is not None and captured.ptype == "Q":
return False
was_pawn = self.move_to(piece, r, c)
ptypes = [piece.ptype]
before = piece
if was_pawn:
ptypes = ["B", "R", "N"]
for ptype in ptypes:
piece.ptype = ptype
if not self.white_can_win(turns_left - 1):
self.undo_move(captured, piece, prev_r, prev_c, was_pawn)
return False
self.undo_move(captured, piece, prev_r, prev_c, was_pawn)
return True
def __repr__(self):
s = []
for i, row in enumerate(self.mat[::-1]):
s.append("{} ".format(4 - i))
for col in row:
if col is None or col.captured is True:
s.append(".")
elif col.color == "W":
s.append(col.ptype.upper())
elif col.color == "B":
s.append(col.ptype.lower())
s.append("\n")
s.append(" ABCD")
return "".join(s)
if __name__ == '__main__':
games = int(input())
for g in range(games):
board = Board()
cols = "ABCD"
w, b, m = map(int, input().split(" "))
for i in range(w):
ptype, col, row = input().split(" ")
col = cols.index(col)
row = int(row) - 1
board.add_piece("W", ptype, row, col)
for i in range(b):
ptype, col, row = input().split(" ")
col = cols.index(col)
row = int(row) - 1
board.add_piece("B", ptype, row, col)
print("YES" if board.white_can_win(m) else "NO")
Python 2 rep HackerRank Solution
BLACK=2
WHITE=1
OTHER=[0,2,1] # index table to find other player id quickly
DEBUG=0
def promote(x,y):
return set(
[('R',x,y),
('B',x,y),
('N',x,y),
])
# Queen, kNight, Rook, Bishop, Pawn
def amoves(t,c,x,y,board,pawn_capture=False): # available moves to type, color, coordinates
movez=set()
if t == 'P':
if c==WHITE and y<3:
if not pawn_capture and board[x][y+1] is None: # WHITE UP
if y==2: # Promotion
movez.update(promote(x,3))
else:
movez.add((t,x,y+1))
if x>0: # WHITE UP LEFT if it can capture a piece
if board[x-1][y+1] and (pawn_capture or board[x-1][y+1][1]==OTHER[c]):
if y==2: # Promotion
movez.update(promote(x-1,3))
else:
movez.add((t,x-1,y+1))
if x<3: # WHITE UP RIGHT if it can capture a piece
if board[x+1][y+1] and (pawn_capture or board[x+1][y+1][1]==OTHER[c]):
if y==2: # Promotion
movez.update(promote(x+1,3))
else:
movez.add((t,x+1,y+1))
if c==BLACK and y>0:
if not pawn_capture and board[x][y-1] is None: # BLACK DOWN
if y==1: # Promotion
movez.update(promote(x,0))
else:
movez.add((t,x,y-1))
if x>0: # BLACK DOWN LEFT
if board[x-1][y-1] and (pawn_capture or board[x-1][y-1][1] == OTHER[c]):
if y==1: # Promotion
movez.update(promote(x-1,0))
else:
movez.add((t,x-1,y-1))
if x<3: # BLACK DOWN RIGHT
if board[x+1][y-1] and (pawn_capture or board[x+1][y-1][1] == OTHER[c]):
if y==1: # Promotion
movez.update(promote(x+1,0))
else:
movez.add((t,x+1,y-1))
if t in 'QR':
for ix in xrange(x+1,4): # RIGHT
if board[ix][y]:
if board[ix][y][1] != c:
movez.add((t,ix,y))
break
else:
movez.add((t,ix,y))
for ix in xrange(x-1,-1,-1): # LEFT
if board[ix][y]:
if board[ix][y][1] != c:
movez.add((t,ix,y))
break
else:
movez.add((t,ix,y))
for iy in xrange(y+1,4): # DOWN
if board[x][iy]:
if board[x][iy][1] != c:
movez.add((t,x,iy))
break
else:
movez.add((t,x,iy))
for iy in xrange(y-1,-1,-1): # UP
if board[x][iy]:
if board[x][iy][1] != c:
movez.add((t,x,iy))
break
else:
movez.add((t,x,iy))
if t in 'QB':
for d in xrange(1,min(4-x,4-y)): # DOWN+RIGHT
if board[x+d][y+d]:
if board[x+d][y+d][1] != c:
movez.add((t,x+d,y+d))
break
else:
movez.add((t,x+d,y+d))
for d in xrange(1,min(x+1,y+1)): # UP+LEFT
if board[x-d][y-d]:
if board[x-d][y-d][1] != c:
movez.add((t,x-d,y-d))
break
else:
movez.add((t,x-d,y-d))
for d in xrange(1,min(x+1,4-y)): # DOWN+LEFT
if board[x-d][y+d]:
if board[x-d][y+d][1] != c:
movez.add((t,x-d,y+d))
break
else:
movez.add((t,x-d,y+d))
for d in xrange(1,min(4-x,y+1)): # UP+RIGHT
if board[x+d][y-d]:
if board[x+d][y-d][1] != c:
movez.add((t,x+d,y-d))
break
else:
movez.add((t,x+d,y-d))
if t == 'N':
possible=[(a,b) for (a,b) in
[(x-1,y-2),(x+1,y-2),(x-2,y-1),(x+2,y-1),(x-2,y+1),(x+2,y+1),(x-1,y+2),(x+1,y+2)]
if a>=0 and b>=0 and a<4 and b<4
]
for (a,b) in possible:
if not board[a][b] or (board[a][b] and board[a][b][1]!=c):
movez.add((t,a,b))
return movez
def getallmoves(c,whites,blacks,board,pawn_capture=False):
# get all moves that color c can make based on list of figures and board status
# pawn_capture: whether to include pawn diagonal moves or not (for checking suicidal moves)
s=[0,whites,blacks]
movez=set()
for t,x,y in s[c]:
movez.update(amoves(t,c,x,y,board,pawn_capture))
#if DEBUG: print 'all moves', t,c,x,y,'-->',movez
return movez
def whitewins(col,board,level,maxlevel):
# col=color of player, level=current move, maxlevel=max moves
blacks=[]
whites=[]
s=[0,whites,blacks]
for x in xrange(4):
for y in xrange(4):
if board[x][y]:
t,c=board[x][y]
s[c].append((t,x,y))
WQ=tuple([w for w in whites if w[0]=='Q'][0][1:])
BQ=tuple([b for b in blacks if b[0]=='Q'][0][1:])
if col==WHITE:
if DEBUG:print " "*level,"Checking whites", level, whites
allm=getallmoves(WHITE,whites,blacks,board)
allcoords=[tuple(mov[1:]) for mov in allm]
if not allm:
raise ValueError("no possible moves for white.")
if BQ in allcoords:
if DEBUG:print " "*level, 'WIN!','BQ',BQ,'can be captured by white', allm
return True
if level>=maxlevel-1: # we reached max moves and white did not win
return False
blackm=getallmoves(BLACK,whites,blacks,board,pawn_capture=True) # get danger zones
blackcoords=[tuple(mov[1:]) for mov in blackm]
# ALL possible white moves
for t,x,y in whites:
for nt,nx,ny in amoves(t,WHITE,x,y,board):
if t=='Q' and (nx,ny) in blackcoords: # no suicidal move
continue
if DEBUG:print " "*level,' Checking white move', t,x,y,"->",nt,nx,ny
saved=board[nx][ny]
board[nx][ny]=(nt,WHITE)
board[x][y]=None
ww=whitewins(BLACK,board,level+1,maxlevel)
board[x][y]=(t,WHITE)
board[nx][ny]=saved
if ww:
if DEBUG:print " "*level, 'WIN!'
return True
return False #none of all possible white moves won for sure
elif col==BLACK:
if DEBUG:print " "*level, "Checking blacks", level, blacks
if level==maxlevel:
return False # reached max level and it's black's turn so white cannot possibly win
allm=getallmoves(BLACK,whites,blacks,board)
if not allm:
raise ValueError("no possible moves for black.")
allcoords=[tuple(mov[1:]) for mov in allm]
if WQ in allcoords:
return False
whitem=getallmoves(WHITE,whites,blacks,board,pawn_capture=True) # get danger zones
whitecoords=[tuple(mov[1:]) for mov in whitem]
# ALL possible black moves
for t,x,y in blacks:
for nt,nx,ny in amoves(t,BLACK,x,y,board):
if t=='Q' and (nx,ny) in whitecoords: # no suicidal move
continue
if DEBUG:print " "*level,' Checking black move', t,x,y,"->",nt,nx,ny
saved=board[nx][ny]
board[nx][ny]=(nt,BLACK)
board[x][y]=None
ww=whitewins(WHITE,board,level+1,maxlevel) # There is a possible black move for white not to win
board[x][y]=(t,BLACK)
board[nx][ny]=saved
if not ww: # There is a possible black move for white not to win
return False
if DEBUG:print " "*level, 'WIN!','All black moves lead to white winning'
return True #all black moves lead to white winning
for _ in xrange(input()):
board = [[None for _ in xrange(4)] for _ in xrange(4)]
w,b,m=map(int,raw_input().strip().split())
for _ in xrange(w):
t,x,y = raw_input().strip().split()
x={'A':0,'B':1,'C':2,'D':3}[x]
y=int(y)-1
board[x][y]=(t,WHITE)
for _ in xrange(b):
t,x,y = raw_input().strip().split()
x={'A':0,'B':1,'C':2,'D':3}[x]
y=int(y)-1
board[x][y]=(t,BLACK)
print {True:'YES',False:'NO'}[whitewins(WHITE,board,1,m)]
C rep HackerRank Solution
#include <stdio.h>
#include <string.h>
#define QUEEN 1
#define KNIGHT 2
#define BISHOP 3
#define ROOK 4
#define PAWN 5
#define BOUND 8
int m;
unsigned char __board[8][8];
unsigned char *_board[8]={__board[0]+2, __board[1]+2, __board[2]+2, __board[3]+2,
__board[4]+2, __board[5]+2, __board[6]+2, __board[7]+2};
unsigned char **board=_board+2;
unsigned char black[4][4];
int pl[2]={1, -1};
int moves[6][10][3]={
{},
{ {-1, -1, 3}, {-1, 0}, {-1, 1},
{0, -1}, /*QUEEN*/ {0, 1},
{1, -1}, {1, 0}, {1, 1} },
{ {-2, -1, 1}, {-2, 1},
{-1, -2}, {-1, 2},
/*KNIGHT*/
{1, -2}, {1, 2},
{2, -1}, {2, 1} },
{ {-1, -1, 3}, {-1, 1},
/*BISHOP*/
{1, -1}, {1, 1} },
{ {-1, 0, 3},
{0, -1}, /*ROOK*/ {0, 1},
{1, 0} },
{ {-1, 0, 1}, {-1, -1}, {-1, 1}, /* white */
{0, 0}, /*PAWN*/
{1, 0}, {1, 1}, {1, -1} } /* for black */
};
static int min(int a, int b) {
return a<b?a:b;
}
static int max(int a, int b) {
return a>b?a:b;
}
void init_game(void) {
int i, j;
for (i=0; i<8; i++)
for (j=0; j<8; j++)
__board[i][j]=(BOUND+1)*(!(1<i && i<6 && 1<j && j<6));
memset(black, 0, sizeof(black));
}
void print_board(void) {
int i, j;
char fc[6]={'=', 'Q', 'N', 'B', 'R', 'P'};
for (i=0; i<4; i++, printf("\n"))
for (j=0; j<4; j++)
printf("%c ", fc[board[i][j]]+('a'-'A')*black[i][j]);
printf("\n");
}
int solve(int mv) {
int i, j, k, d, b=mv&1;
int ni, nj, t, tb, r, mm=pl[!b], prom[5]={0, 0, 0, 0, 0}, p;
for (i=0; i<4; i++) {
for (j=0; j<4; j++) {
if (board[i][j] && black[i][j]==b) {
for (k=0; moves[board[i][j]][k][0] || moves[board[i][j]][k][1]; k++) {
for (d=1; d<=moves[board[i][j]][0][2]; d++) {
if (board[i][j]!=PAWN || k) {
if (board[i][j]==PAWN)
t=board[ni=(i+moves[board[i][j]][k+b*4][0])][nj=(j+moves[board[i][j]][k+b*4][1])];
else
t=board[ni=(i+moves[board[i][j]][k][0]*d)][nj=(j+moves[board[i][j]][k][1]*d)];
if (t) {
if (t>BOUND)
break;
else if (t==QUEEN && black[ni][nj]!=b)
return pl[b];
break;
}
}
}
}
}
}
}
if ((mv+1)==m)
return 0;
for (i=0; i<4; i++) {
for (j=0; j<4; j++) {
if (board[i][j] && black[i][j]==b) {
for (k=0; moves[board[i][j]][k][0] || moves[board[i][j]][k][1]; k++) {
for (d=1, t=0; d<=moves[board[i][j]][0][2] && !t; d++) {
prom[0]=board[i][j]; prom[1]=board[i][j]; prom[2]=0;
if (board[i][j]==PAWN) {
t=board[ni=(i+moves[board[i][j]][k+b*4][0])][nj=(j+moves[board[i][j]][k+b*4][1])];
if (k) {
if (t==0 || t>BOUND || black[ni][nj]==b)
break;
} else if (t)
break;
if ((ni==0 && !b) || (ni==3 && b)) {
prom[1]=KNIGHT; prom[2]=BISHOP; prom[3]=ROOK; prom[4]=0;
}
} else {
t=board[ni=(i+moves[board[i][j]][k][0]*d)][nj=(j+moves[board[i][j]][k][1]*d)];
if (t>BOUND || (t && black[ni][nj]==b))
break;
}
for (p=1; prom[p]; p++) {
tb=black[ni][nj];
board[ni][nj]=prom[p];
black[ni][nj]=b;
board[i][j]=0;
black[i][j]=0;
r=solve(mv+1);
board[i][j]=prom[0];
board[ni][nj]=t;
black[i][j]=b;
black[ni][nj]=tb;
if (r==pl[b])
return r;
else if (b)
mm=min(mm, r);
else
mm=max(mm, r);
}
}
}
}
}
}
return mm;
}
int main(void) {
int i, j, g, r, b, w;
char figuremap[26]={['Q'-'A']=QUEEN, ['N'-'A']=KNIGHT, ['B'-'A']=BISHOP,
['R'-'A']=ROOK, ['P'-'A']=PAWN};
char t, c;
scanf("%d", &g);
for (i=0; i<g; i++) {
init_game();
scanf("%d%d%d\n", &w, &b, &m);
for (j=0; j<w; j++) {
scanf("%c %c %d\n", &t, &c, &r);
board[4-r][c-'A']=figuremap[t-'A'];
}
for (j=0; j<b; j++) {
scanf("%c %c %d\n", &t, &c, &r);
r=4-r; c-='A';
board[r][c]=figuremap[t-'A'];
black[r][c]=1;
}
printf("%s\n", solve(0)==1?"YES":"NO");
}
return 0;
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
