We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Game Theory
  4. A Chessboard Game
  5. Discussions

A Chessboard Game

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 59 Discussions, By:

votes

Please Login in order to post a comment

  • rolfbuch
    6 years ago+ 11 comments

    Editorial seemed very overly complex. This is easily solved by:

    public static String findWinner(int x, int y){
        x=x%4; 
        y=y%4;
        if((y==0)||(y==3)||(x==0)||(x==3)) return "First";
        return "Second";
    }    
    
    48|
    Permalink
    View more Comments..
  • _spd96
    6 years ago+ 2 comments

    I drowed a table 15x15 starting from 0,0 to 14,14. It represents what player1 does. It looks like this :

    W -> win ; L -> lose
    
    "LLWWLLWWLLWWLLW",
    "LLWWLLWWLLWWLLW",
    "WWWWWWWWWWWWWWW",
    "WWWWWWWWWWWWWWW",
    "LLWWLLWWLLWWLLW",
    "LLWWLLWWLLWWLLW",
    "WWWWWWWWWWWWWWW",
    "WWWWWWWWWWWWWWW",
    "LLWWLLWWLLWWLLW",
    "LLWWLLWWLLWWLLW",
    "WWWWWWWWWWWWWWW",
    "WWWWWWWWWWWWWWW",
    "LLWWLLWWLLWWLLW",
    "LLWWLLWWLLWWLLW",
    "WWWWWWWWWWWWWWW", ;
    
    you should drow it by walking on its diagonals like that : 0,0 -> 0,1 -> 1,0 -> 0,2 -> 1,1 -> 2,0 -> ... till end. i hardcodated it becouse i was lasy to implement it. i solve it like a DP problem :D
    
    10|
    Permalink
  • Haseena_CSE
    5 years ago+ 2 comments

    My C solution with O(1) time complexity

    #include<stdio.h>
    int main()
    {
    	int t,x,y;
    	scanf("%d",&t);
    	while(t--)
    	{
    		scanf("%d%d",&x,&y);
    		x=x%4;
    		y=y%4;
    		if((x==0) || (x==3) || (y==0) || (y==3))
    			printf("First\n");
    		else
    			printf("Second\n");
    			
    	}
    	return 0;
    }
    
    8|
    Permalink
  • tashaffin
    4 years ago+ 0 comments

    A lot of posts show a gimmick solution based on the fact that a pattern was found. What if there was not such an easy to observe pattern? Here is a proper recursive solution in Javascript:

    const moves = [[-2, 1], [-2, -1], [1, -2], [-1, -2]];
    function whoWins(x, y, player) {
        if (x < 1 || y < 1) // The last player did not have a legal move
            return player;
    
        // Only one path needs to return a win for the current player since he will play optimally
        return (moves.some((val) => {
            return whoWins(x + val[0], y + val[1], (player + 1) % 2) === player;
        })) ? player : (player + 1) % 2;
    }
    
    // Complete the chessboardGame function below.
    function chessboardGame(x, y) {
     return whoWins(x, y, 0) === 0 ? "First" : "Second";
    }
    
    7|
    Permalink
  • jpritcha3_14
    5 years ago+ 0 comments

    The editorial for this problem is both needlessly complex and provides a sub-optimal recursive solution for this problem in O(n^2) when it can be solved far more simply in O(1)

    Start by mapping out the win states for the first and second players. Starting at the top left, the second player (S) wins in the square of 4 spaces by default, since first player (F) has no moves. From there propogate outwards and mark each square with the approprite win state.

      0 1 2 3 4 5 6 7...
    0 S S F F S S F F
    1 S S F F S S F F
    2 F F F F F F F F
    3 F F F F F F F F
    4 S S F F S S F F
    5 S S F F S S F F
    6 F F F F F F F F
    7 F F F F F F F F*
    .
    . # *if board were 8x8, this corner would be S
    .
    

    The pattern becomes clear, if we shift the indicies down by 1 (start at 0), then the second player only wins if the coin starts at a space where (x//2)%2==0 and (y//2)%2==0, otherwise the first player wins. The code is relatively trival. (Note that there is one corner case that could arise at the bottom right corner of the board depending on the size of the board, but in the 15x15 case this is not an issue).

    t = int(input())
    for _ in range(t):
        x, y = list(map(lambda x: int(x)-1, input().split()))
        print('Second' if x//2 % 2 == 0 and y//2 % 2 == 0 else 'First')
    
    2|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature