Checker Winner

Elly and Kriss play a game. The game is played on a single row that consists of N cells; we will call it the board. The cells of the board are numbered 0 through N-1, from the left to the right. Each cell of the board is either empty or occupied by a single checker. The girls take alternating turns, until one of them cannot make a move. The girl who is unable to make a move loses the game.

In each move the current player selects a cell containing a checker and performs one of the following two types of moves:A step, in which the checker is moved one cell to the right. The step can only be made if the target cell is empty.

A jump, in which the checker jumps three cells to the right. The jump can only be made if the target cell is empty and the cells it jumped over contain two other checkers.

Once a checker reaches the rightmost cell, it disappears immediately and no longer plays any role in the game.

The initial layout of the board will be given as a String board. The i-th character of board will be ‘.’ (a period) if the i-th cell is empty at the beginning, and it will be ‘o’ (lowercase letter o) if the i-th cell initially contains a checker. Assume that both girls play optimally. Return “YES” (quotes for clarity) if the first player wins the game and “NO” otherwise.

Examples

0)”.o…” = > “YES”

With only one checker it is pretty obvious who will win.

1)”..o..o” = > “YES”

Don’t forget to ignore checkers on the rightmost cell.

2)”.o…ooo..oo..” => “NO”

Here one can jump the checker from cell 5 to cell 8.

3)”……o.ooo.o……” => “YES”

4)”.o..o…o….o…..o” => “NO”

public class EllysCheckers {

    public String getWinner(String board) {
        int c = 0;
        for(int i=0;i<board.Length-1;i++) {
            if(board[i]=='o') c+=board.Length-i-1;
        }
        
        return (c%2)==1?"YES":"NO";
    }
    
    public static void main(String[] args) {
        EllysCheckers el = new EllysCheckers();
        el.getWinner(".o...");
        el.getWinner("..o..o");
        el.getWinner(".o...ooo..oo..");
        el.getWinner("......o.ooo.o......");
        el.getWinner(".o..o...o....o.....o");
        el.getWinner(".......");
        el.getWinner(".");
        el.getWinner("o");
        el.getWinner("oooooooooooooooooooo");
        el.getWinner("ooo.ooo.ooo.ooo.ooo.");
        el.getWinner("o..ooo");
        el.getWinner("oooo...oo");
        el.getWinner("oo.o.......");
        el.getWinner(".ooooo");
        el.getWinner("oooooo..oo.oo..ooooo");
        el.getWinner(".o.o...oooooo...");
        el.getWinner(".o..o.....");
        el.getWinner("ooooo");
            }
}

Advertisement

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: