Waterloo Programming Contest: The Game of 31

Question

Please review my program for the Game of 31.

The game of 31 was a favourite of con artists who rode the railroads in days of yore. The game is played with a deck of 24 cards: four labelled each of 1, 2, 3, 4, 5, 6. The cards in the deck are visible to both players, who alternately withdraw one card from the deck and place it on a pile. The object of the game is to be the last player to lay a card such that the sum of the cards in the pile does not exceed 31. Your task is to determine the eventual winner of a partially played game, assuming each player plays the remainder of the game using a perfect strategy.

For example, in the following game player B wins:

Player A plays 3

Player B plays 5

Player A plays 6

Player B plays 6

Player A plays 5

Player B plays 6

Input: The input will consist of several lines; each line consists of a sequence of zero or more digits representing a partially completed game. The first digit is player A’s move; the second player B’s move; and so on. You are to complete the game using a perfect strategy for both players and to determine who wins.

Output: For each game, print a line consisting of the input, followed by a space, followed by A or B to indicate the eventual winner of the game.

GameOf31.java

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Stack;

public class GameOf31 {

private static Scanner stdin = new Scanner(System.in);
static Map<Integer, Integer> cardsKnt = new HashMap<Integer,Integer>();
private static final int MAXSUM = 31;

//initialises the hash map with keys 1 to 6 and makes the values for each equal to 4
//this is because the deck of 24 cards has 4 of each cards numbered 1 to 6
public GameOf31(){
    for(int i = 1; i <= 6; ++i)
        cardsKnt.put(i, 4);
}

//Since I accept input as an integer, I separate it into an integer array
public static int[] separateSequence(int sequence){
    int[] numseq = new int[10];
    Stack<Integer> s1 = new Stack<Integer>();

    while(sequence > 0){
        s1.push(sequence % 10);
        sequence /= 10;
    }

    int sz = s1.size();
    for(int i = 0; i < sz; ++i){
        numseq[i] = s1.pop();
    }

    return numseq;
}

//Pretty straight forward, calculates final winner
public static char getWinner(int[] sequence){
    char winner = 'X';
    int tempSum = 0;
    boolean aTurn = true, bTurn = false, tempTurn = false;

    /*
     * This loop removes cards already played in the turn from the hash map,
     * then determines who's turn is next.
    */
    for(int i = 0; i < sequence.length; ++i){
        tempSum += sequence[i];
        if(cardsKnt.containsKey(sequence[i])){
            int knt = cardsKnt.get(sequence[i]);
            --knt;
            cardsKnt.put(sequence[i], knt);
            tempTurn = aTurn;
            aTurn = bTurn;
            bTurn = tempTurn;
        }
    }

    boolean loop = true;
    while(loop){

        if(tempSum == MAXSUM){

            winner = bTurn == true ? 'A' : 'B';
            loop = false;

        } else if (tempSum > 31){

            winner = aTurn == true ? 'B' : 'A';
            loop = false;

        } else {

            if(aTurn){

                int sum = 0, maxsum = 0, nextToPick = 0;

                for(int i = 1; i <= 6; ++i){

                    //If the card with number 'i' hasn't been used 4 times
                    if(cardsKnt.get(i) > 0){
                        sum = tempSum + i;

                        //If sum is equal to 31 or less, we can still do another iteration
                        if(sum <= 31){
                            if(sum > maxsum){
                                maxsum = sum;
                                nextToPick = i;
                            }
                        } 
                        //else we know the winner is the previous player.
                        else {
                            winner = 'B';
                            return winner;
                        }
                    } 
                    sum = 0;
                }

                tempSum = maxsum;
                int knt = cardsKnt.get(nextToPick);
                --knt;
                //perhaps there is a better way to change hash map values directly?
                cardsKnt.put(nextToPick, knt);
                tempTurn = aTurn;
                aTurn = bTurn;
                bTurn = tempTurn;

            } else if(bTurn) {

                int sum = 0, maxsum = 0, nextToPick = 0;

                for(int i = 1; i <= 6; ++i){
                    if(cardsKnt.get(i) > 0){
                        sum = tempSum + i;
                        if(sum <= MAXSUM){
                            if(sum > maxsum){
                                maxsum = sum;
                                nextToPick = i;
                            }
                        } else {
                            winner = 'A';
                            return winner;
                        }
                    } 
                    sum = 0;
                }

                tempSum = maxsum;
                int knt = cardsKnt.get(nextToPick);
                --knt;
                cardsKnt.put(nextToPick, knt);
                tempTurn = aTurn;
                aTurn = bTurn;
                bTurn = tempTurn;

            }
        }
    }

    return winner;
}

public static void main(String[] args){

    new GameOf31();
    int input = stdin.nextInt();

    char Winner = getWinner(separateSequence(input));
    System.out.println(input + "\t" + (Winner == 'X' ? "Error; no winner." : Winner));


}

}

Thanks in advance, any tips appreciated.

Answer 1

Int too small to represent input

Currently, if there is a very long input such as 111122223333, the numeric value of that input will not fit within an int. I would suggest leaving the input in String format, which would simplify your separateSequence() function because you wouldn't need to use a stack to reverse the digits.

Array instead of HashMap

I noticed that you had this comment for removing a card from the deck:

            int knt = cardsKnt.get(nextToPick);
            --knt;
            //perhaps there is a better way to change hash map values directly?
            cardsKnt.put(nextToPick, knt);

It looks like you found the HashMap a little awkward to use for this purpose. You can use an array to represent your card deck and it would simplify your code:

              // Initializing the array:
              int[] cards = new int[7];

              for (int i = 1; i <= 6; ++i) {
                  cards[i] = 4;
              }

              // Checking if a card remains in the deck:
              if (cards[sequence[i]] > 0) {
              }

              // Removing a card from the deck:
              cards[nextToPick]--;

Solving logic incorrect

I tried the following cases:

356656   B
356655   B
356654   B

The first test case adds up to 31 already, so B should win because B was last to play. However, in the other 2 test cases, the sum adds up to 30 and 29 respectively. So player A should win because player A plays next and can play a card to make the sum 31. So something is wrong with your game solving logic.

From a casual inspection of your solving loop, it looks like you are using some kind of greedy heuristic to play the lower numbered cards first. I believe that in order to play perfect strategy, you will need to do something like an Alpha Beta search instead.

Answer 2

s1, sz - are too short names

there are to many if's inside one of another: if{if{if}}}

getWinner is too long, it would be nice to break it into several methods.