7
\$\begingroup\$

I'm trying to implement Knuth's Five-guess Mastermind algorithm in my own version of Mastermind, but when running step 6 it takes my code hours to actually run through everything to get the neccesary information. I was wondering if any of you would know a better way to obtain the same results?

Here is my code with relevant classes, step 6 is mainly executed in the method calculateScore().

The following code is the class in which all of the calculation is being done (it exists mainly to do this, except for a few functions which are not called

import java.util.ArrayList;
import java.util.Collections;

public class PhaseComputer extends Phase {

    private ArrayList<String> possibleCombList = new ArrayList<String>();
    private ArrayList<String> combList = new ArrayList<String>();
    private ArrayList<Outcome> possibleOutcomes = new ArrayList<Outcome>();

    private String combination = "";
    private String code = "";

    private int totalGuesses = 0;

    public PhaseComputer() {
        setPossibleCombList();
        setOutComeList();
        this.guess = new ArrayList<>();
        this.exactlyRight = new ArrayList<>();
        this.wrongPlace = new ArrayList<>();
    }

    public void play() {

        generateCode();

        blackPins = 0;
        whitePins = 0;

        System.out.println("Guess " + (totalGuesses + 1) + ": " + code + "\n");

        checkBlackPins();

        if (blackPins == 4) {
            this.win = true;
        } else {
            checkWhitePins();
        }

        exactlyRight.add(blackPins);
        wrongPlace.add(whitePins);
        guess.add(code);

    }

    public void generateCode() { // Generates the next guess.

        if (totalGuesses == 0) { // If this is the first turn, put the next guess equal to 'AABB'.
            code = "AABB";
        }

        else if (possibleCombList.size() == 1) { // If there's only one possible combination left;
            code = possibleCombList.get(0);
        }

        else { // If none of the above are true;

            removeLastGuess();

            deleteCombinations();

            createScoreList();

        }

        System.out.println("possibleCombList size: " + possibleCombList.size());

    }

    public boolean checkIfPossible(String answer, String randomGuess, Outcome outcome) {  // Checks if the outcome of a randomly given combination, with previously guessed code as the answer, is the same as the the outcome that the user just returned.
        if ((calculatePins(randomGuess, answer).equals(outcome))) {
            return true;
        } else {
            return false;
        }

    }

    public void createScoreList() { // Creates a list of all best guesses.
        ArrayList<String> bestGuesses = new ArrayList<String>();
        int maxMinimum = 0;
        for (String guess : combList) {
            for (String solution : combList) {
                int minimum = calculateScore(solution);
                if (minimum > maxMinimum) {
                    maxMinimum = minimum;
                    bestGuesses.clear();
                    bestGuesses.add(guess);
                }
                if (minimum == maxMinimum) {
                    bestGuesses.add(guess);
                }

            }

        }
        for (String guess : bestGuesses) {
            if (possibleCombList.contains(guess)) {
                code = guess;
            }
            else {
                code = bestGuesses.get(0);
            }
        }
        System.out.println(bestGuesses.size());
    }

    public int calculateScore(String solution) { // Calculate the score of 'solution' on every available combination of pins.
        ArrayList<Integer> minimum = new ArrayList<Integer>();
        for (Outcome outcome : possibleOutcomes) {
            int min = 0;
            for (String combination : combList) {
                if (!checkIfPossible(solution, combination, outcome)) {
                    min++;
                }
            }
            minimum.add(min);
        }

        return  Collections.min(minimum);
    }

    public Outcome calculatePins(String combination, String guess) { // Calculates the amount of pins that 'combinations'would return if 'guess' were the answer and makes an Outcome object out of this.
        ArrayList<Integer> solutionIndex = new ArrayList<Integer>();
        ArrayList<Integer> checkedIndexes = new ArrayList<Integer>();
        int compBlackPins = 0;
        int compWhitePins = 0;
        for (int a = 0; a < combination.length(); a++) {
            if (guess.charAt(a) == combination.charAt(a) && !checkedIndexes.contains(a)) {
                compBlackPins++;
                solutionIndex.add(a);
                checkedIndexes.add(a);
            }

            if (!checkedIndexes.contains(a)) {
                for (int l = 0; l < guess.length(); l++) {
                    if (guess.charAt(l) == combination.charAt(a) && !solutionIndex.contains(l)) {
                        compWhitePins++;
                        checkedIndexes.add(a);
                        solutionIndex.add(l);
                    }
                }
            }
        }
        return (new Outcome(compBlackPins, compWhitePins));
    }

    public void removeLastGuess() { // Removes previously used code from the list of remaining combinations.
        possibleCombList.remove(code);
    }

    public void deleteCombinations() {
        ArrayList<String> toRemove = new ArrayList<String>();
        for (String solution : possibleCombList) {
            if (!checkIfPossible(code, solution, new Outcome(blackPins, whitePins))) {
                toRemove.add(solution);
            }
        }
        for (String combinations : toRemove) {
            possibleCombList.remove(combinations);
        }

    }

    public void checkBlackPins() { // Asks for input on black pins.
        boolean blackPinsInput = true;
        do {
            blackPinsInput = true;
            System.out.println("How many colors are exactly right?");
            input = in.next();
            blackPins = Integer.parseInt(input);

            if (blackPins > 4 || blackPins < 0) {
                System.out.println("Invalid input! Please type a value from 0 to 5.");
                blackPinsInput = false;
            }
        } while (!blackPinsInput);
    }

    public void checkWhitePins() { // Asks for input for white pins.
        boolean whitePinsInput = true;

        do {
            whitePinsInput = true;
            System.out.println("How many colors are right, but are in the wrong spot?");
            input = in.next();
            this.whitePins = Integer.parseInt(input);
            if (whitePins > 4 || whitePins < 0) {
                System.out.println("Invalid input! Please type a value from 0 to 5.");
                whitePinsInput = false;
            }
        } while (!whitePinsInput);
    }

    public void totalGuessesIncrease() {

        this.totalGuesses = totalGuesses + 1;

    }

    public void setOutComeList() {
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                if (i + j < 5) {
                    possibleOutcomes.add(new Outcome(i, j));
                }
            }
        }
    }

    public void setPossibleCombList() { // Creates a list of all possible (1296) combinations.

        if (combination.length() == 4) { // If the current combination is 4 letters long;

            possibleCombList.add(combination);
            combList.add(combination);

        } else { // If not, add a letter and process the String again.
            for (int i = 0; i < colors.length; i++) {
                String oldCombination = combination;
                combination = combination + colors[i];
                setPossibleCombList();
                combination = oldCombination;
            }
        }
    }
}
\$\endgroup\$
0

2 Answers 2

3
\$\begingroup\$

Since you said that Step 6 takes a lot of time, and is mainly executed in the calculateScore() method, why don't we simplify it?

public int calculateScore(String solution) { // Calculate the score of 'solution' on every available combination of pins.
    ArrayList<Integer> minimum = new ArrayList<Integer>();
    for (Outcome outcome : possibleOutcomes) {
        int min = 0;
        for (String combination : combList) {
            if (!checkIfPossible(solution, combination, outcome)) {
                min++;
            }
        }
        minimum.add(min);
    }

    return  Collections.min(minimum);
}

Here, you calculate min, add it to a List, and then return the minimum in the List.

It can be faster if you have a variable that holds the minimum of mins:

public int calculateScore(String solution) {
    int minimum = Integer.MAX_VALUE;
    for (Outcome outcome : possibleOutcomes) {
        int min = 0;
        for (String combination : combList) {
            if (!checkIfPossible(solution, combination, outcome)) {
                min++;
            }
        }
        if(minimum > min) {
            minimum = min;
        }
    }
    return min;
}
\$\endgroup\$
2
\$\begingroup\$
  • Inconsistent whitespace. There are empty lines in places where it doesn't help readability.
  • Too many responsibilities in one class. It

    • Contains the scoring logic
    • Models the state of the game
    • Handles user interaction
    • A computer game strategy

    Split those into separate types.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Thank you for the inconsistent whitespace tip, Ill make sure to fix that ASAP. Unfortunately for assignment purposes I'm not allowed to create any more classes than told, and this is the class that I'm required to do this in. If you have any more tips I'd love to hear them. \$\endgroup\$ Commented Jan 19, 2015 at 17:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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