5
\$\begingroup\$

As a summer project, I have been working on a small-scale, console-based version of Mahjong (the Rummy-like hand completion game, and not the solitaire version). While having prior knowledge of the game would help in understanding the problem, I don't believe it is necessary.

Early on in the project I wrote an algorithm for determining whether or not a player's hand is complete. This was my first experience writing something like this outside of a class environment, and while the code passes all my unit tests and works well in test runs, it became a bit of a mess after constantly finding holes in my logic and trying to fix them. I'm coming back to it now intending to make it more easy both to use and to understand, but I thought getting an outside viewpoint could make its issues more clear.

Some relevant information: a pair is two of the same tile, a set is three, and a sequence is three tiles of the same "suit" in numerical order, e.g. 1-2-3. Tenpai is the state of needing only one tile to win. Noten is being further than one tile away from winning.

private Hand myHand;

/**
 * The tile(s) which would put this player in tenpai if discarded.
 */
private final Set<Tile> myTenpaiTiles;

/**
 * The tiles in the player's hand grouped in the individual
 * sets, sequences and the pair it is comprised of.
 */
private final List<List<Tile>> mySolution;

/**
 * Constructs a new completeness checker.
 * @param theHand a hand to check for completeness.
 */
public CompletenessChecker(final Hand theHand) {
    myHand = theHand;
    myTenpaiTiles = new HashSet<>();
    mySolution = new ArrayList<>(SOLUTION_LENGTH);
}

/**
 * Returns all tiles this player could discard to be in tenpai.
 * @return a list of tiles to discard.
 */
public Set<Tile> getTenpaiDiscards() {
    return Collections.unmodifiableSet(myTenpaiTiles);
}

/**
 * Returns a found solution to the player's hand.
 * @return a solution to the hand.
 */
public List<List<Tile>> getSolution() {
    return Collections.unmodifiableList(mySolution);


/**
 * Determines whether or not this player's hand is in a completed state.
 * A complete hand must fit one of these conditions:
 * it consists of one of each one and nine from each suit, as well as 
 * one of each wind and dragon, and one more of any of these tiles;
 * it consists of seven pairs of any type;
 * it consists of four sets or sequences of tiles and any pair.
 * Note that this algorithm requires the player's hand to be sorted
 * according to {@link Tile#compareTo()}. 
 * @return true if and only if this player's hand is complete.
 */
public boolean isComplete() {
    final List<List<Tile>> theSolution = new ArrayList<>(SOLUTION_LENGTH);
    final List<Tile> handTiles = myHand.getAll();
    List<Tile> handCopy;
    boolean complete = false;

    if (YakuCalculator.hasKokushiMusou(handTiles) 
            || YakuCalculator.hasChiiToiTsu(handTiles)) {
        complete = true;
    } else {
        for (int i = 0; i < handTiles.size(); i++) {
            final List<Tile> sequence = findSequence(
                    handTiles.subList(i, handTiles.size() - 1));

            if (!sequence.isEmpty()) {
                handCopy = new ArrayList<>(handTiles);
                removeEachOnce(sequence, handCopy);

                theSolution.add(sequence);

                complete = findComplete(myHand.getCalls().callCount() + 1, handCopy, theSolution);

                /*
                 * We only break if the hand is complete, 
                 * because this allows us to cover possible sequence collisions.
                 * For example, (Man 3-3-4-5-6) where the 4-5-6 is the desired
                 * sequence and 3-3 should be treated as a pair.
                 */
                if (complete) {
                    break;
                }

                theSolution.clear();
            }
        }

        if (!complete) {
            handCopy = new ArrayList<>(handTiles);
            final List<Tile> set = findSet(handCopy);

            if (!set.isEmpty()) {
                theSolution.add(set);
                removeEachOnce(set, handCopy);

                complete = findComplete(myHand.getCalls().callCount() + 1, handCopy, theSolution);
            }
        }
    }

    return complete;
}

/**
 * Helper method for {@link #isComplete()}.
 * This algorithm finds any possible combination 
 * of the tiles in the given hand which will result in a winning shape.
 * If a branch does not find a complete hand, but finds a hand one tile away from
 * completion (tenpai), it notes exactly which tile or tiles could be cut from the hand
 * to maintain this state.
 * @param theMeldCount a number between zero and four denoting the number of sets
 *     or sequences found in the hand by this branch, including any called tiles.
 * @param theHand a hand to find the status of.
 * @param theSolution a list of lists of tiles which keeps track of the current solution.
 * @return true if and only if four melds and one pair have been found.
 */
private boolean findComplete(final int theMeldCount, final List<Tile> theHand, 
        final List<List<Tile>> theSolution) {
    boolean completeHand;

    if (theMeldCount == 4) {
        /*
         * This hand may be complete. We try to find a pair.
         * If successful, this hand is complete.
         * If unsuccessful, the hand is in tenpai, waiting on a pair.
         */
        final List<Tile> pair = findPair(theHand);
        final boolean pairFound = !pair.isEmpty();

        if (pairFound) {
            completeHand = true;
            theSolution.add(pair);

            if (mySolution.isEmpty()) {
                mySolution.addAll(theSolution);
            }
        } else {
            completeHand = false;

            // We have four melds but no pair. Either leftover tile can be cut.
            myTenpaiTiles.addAll(theHand);
        }
    } else {
        /*
         * Either there are sets and/or sequences left to remove,
         * or this hand is not complete.
         */
        final List<Tile> set = findSet(theHand);
        final List<Tile> setList = new ArrayList<>(theHand);
        final boolean setFound = !set.isEmpty();

        removeEachOnce(set, setList);

        final List<Tile> sequence = findSequence(theHand);
        final List<Tile> seqList = new ArrayList<>(theHand);
        final boolean seqFound = !sequence.isEmpty();

        removeEachOnce(sequence, seqList);

        if (setFound && seqFound) {
            theSolution.add(set);
            completeHand = findComplete(theMeldCount + 1, setList, theSolution);

            if (!completeHand) {
                theSolution.remove(set);
                theSolution.add(sequence);
                completeHand = findComplete(theMeldCount + 1, seqList, theSolution);
            }
        } else if (setFound) {
            theSolution.add(set);
            completeHand = findComplete(theMeldCount + 1, setList, theSolution);
        } else if (seqFound) {
            theSolution.add(sequence);
            completeHand = findComplete(theMeldCount + 1, seqList, theSolution);
        } else {
            completeHand = false;

            if (theMeldCount == 3) {
                findTenpai(theHand);
            }
        }
    }

    return completeHand;
}

/**
 * Helper method for {@link #findComplete()}.
 * Called only in the edge case where exactly three melds have been found,
 * and a fourth was not available. This hand is not complete, but it may
 * be in tenpai. This method finds all possible tiles, if they exist, 
 * which could be discarded from the hand to maintain tenpai.
 * @param theHand a hand to find any existing tenpai tiles of.
 */
private void findTenpai(final List<Tile> theHand) {
    final List<Tile> pair = findPair(theHand);
    final List<Tile> pairList = new ArrayList<>(theHand);
    final boolean pairFound = !pairList.isEmpty();

    removeEachOnce(pair, pairList);

    // If we cannot find a pair, this hand is in noten.
    if (pairFound) {
        // Check for partial set.
        final List<Tile> secondPair = findPair(pairList);
        final List<Tile> secondPairList = new ArrayList<>(pairList);
        final boolean secondPairFound = !secondPair.isEmpty();

        removeEachOnce(secondPair, secondPairList);

        if (secondPairFound) {
            myTenpaiTiles.addAll(secondPairList);
        }

        findPartialSequence(pairList);
    }
}

Explanation of methods and instance variables not included for brevity (I can post more of the code if needed): the two static method calls at the beginning are just pattern-matching for the two outlier hand shapes described in the comment. The findX functions return the first occurrence of X shape in the hand or an empty List otherwise. The findComplete method starts with a reference to a callCount() method because a player can call sets or sequences using other players tiles, which puts those sets out of the player's hand. These should still be counted for completeness purposes. removeEachOnce(theSourceHand, theDestHand) is shorthand for

    for (final Tile tile: theSourceHand) {
        theDestHand.remove(tile);
    }

Some issues I want to work out:

  • The naming is not helpful in the least. isComplete() was originally meant to simply check if a hand is complete or not, and this is what anyone would expect such a method to do, but instead it secretly is modifying a set or a list if the hand is in tenpai or complete. I was thinking I would instead use a findPlayerState method which would return a Player.State boolean describing whether the hand is NOTEN, TENPAI, or COMPLETE. Based on which of these you receive you know what information to expect.

  • There's a fair bit of redundancy in the code, particularly in the way isComplete() essentially performs what should be the first iteration of findComplete() itself. I added this in originally to fix the issue of pair tiles colliding with sequences as described in the comment, but I think now a better choice would be to start with removing the first pair and seeing if that works, then trying the first sequence, then the first set. (While writing this I have realized a potential issue with the current code not recognizing a hand as valid if it has called four sets/sequences and has only a pair, as it will never reach the findComplete() code section meant to handle this last pair. I will absolutely need to change this approach.)

  • Many runs of this recursive algorithm contain overlapping subproblems, which would lead me to think that recursion is not necessarily the best approach here. That said, I'm not really sure how I would go about making this algorithm iterative while keeping its functionality intact.

\$\endgroup\$
  • \$\begingroup\$ This code is too partial to be answered, it cannot be compiled so it can be studied or refactored easily. There is just too much going on in the methods to do that by hand if you ask me. Make smaller methods! Think of commenting your code, and then turning those code fragments to methods. \$\endgroup\$ – Maarten Bodewes Feb 11 at 1:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.