0
$\begingroup$

I was on a interview with an algorithm problem, which I cannot seem to solve nor find a solution already for it, but I'm really curious how it can be solved.

Here is the problem.

You’re working on making some mini-games, and you’ve decided to make a simpler variant of the game Mahjong. In this variant, players have a number of tiles, each marked 0-9. The tiles can be grouped into pairs or triples of the same tile. A “complete hand” is defined as a collection of tiles where all the tiles can be grouped into any number of triples (zero or more) and exactly one pair, and each tile is used in exactly one triple or pair. Write a function that takes a string representing a player’s tiles in no particular order, and returns the string “COMPLETE” if the hand is complete, and “NOT COMPLETE” if it is not. Each tile may only be used in a single group (either a pair or a triple). All tiles must be used to complete a hand. There may be a pair and triples of the same tile. A single pair with no triples (ex: 99) is a valid hand. The input will only consist of characters 0-9.

Examples

These three hands would all return “COMPLETE”:
33344466 -> 333 444 66 This hand can be grouped into a triple of 3s and 4s, and a pair of 6s
55555555 -> 555 555 55 This hand can be grouped into two triples of 5s and a pair of 5s
22 -> 22 This hand is a single pair of 2s (no triples are required)

These three hands would all return “NOT COMPLETE”:
1357 This hand has tiles which cannot be formed into pairs or triples
335577 This hand has three pairs, a complete hand must have exactly one pair
666888 This hand has two triples, but no pairs.

Is this related to some math formula or some already know algorithm?

$\endgroup$
1
  • $\begingroup$ We require you to credit the original source of all material copied from elsewhere or originally written by someone else: cs.stackexchange.com/help/referencing $\endgroup$
    – D.W.
    Feb 1, 2022 at 21:45

2 Answers 2

2
$\begingroup$

I don't know if this is really suited for computer science SE, perhaps better at Stackoverflow.

Just write a simple function that counts modulo 3 and then goes through all values:

from collections import defaultdict


def expressingx(game):
    counter = defaultdict(int)
    for e in game:
        counter[e] = (counter[e] + 1) % 3
    pairs = 0
    for k, v in counter.items():
        if v == 1:
            return "NOT COMPLETE"
        if v == 2:
            pairs += 1
    return "COMPLETE" if pairs == 1 else "NOT COMPLETE"
$\endgroup$
0
$\begingroup$

Yes, there is a simple algorithm.

  1. Count the frequencies of characters 0-9 in that string.
  2. Check whether all frequencies are divisible by 3 except exactly one frequency, which must have a remainder of 3 when divided by 2.
    • If yes, return "COMPLETE".
    • Otherwise, return "NOT COMPLETE".

For example, given "33344466", the frequencies are 3, 3, and 2. Return "COMPLETE".

For example, given "88888888", the only frequency is 8. Return "COMPLETE".

For example, given "335577", the frequencies are 2, 2, and 2. There are more than one frequency that have a remainder of 3 when divided by 2. Return "NOT COMPLETE"


Here is an implementation in C#.

StackExchange.CS148876.BatchTest();

namespace StackExchange {
    class CS148876 {
        public static bool IsCompleteHand(String tiles) {
            var counter = new int[10];
            foreach(char c in tiles) {
                counter[c - '0'] += 1;
            }

            var hasOnePair = false;
            foreach(var c in counter) {
                if (c % 3 == 1) return false;
                if (c % 3 == 2) {
                    if (hasOnePair) {
                        return false;
                    } else {
                        hasOnePair = true;
                    }
                }
            }
            return hasOnePair;
        }

        public static void Test(String tiles) {
            Console.WriteLine(tiles + ": " + (IsCompleteHand(tiles) ? "COMPLETE" : "NOT COMPLETE"));
        }

        public static void BatchTest() {
            Test("44433344466");
            Test("88888888");
            Test("22");
            Test("1357");
            Test("335577");
            Test("666888");
        }
    }
}
$\endgroup$
2
  • $\begingroup$ What if we have '88888888', this is still valid input. $\endgroup$ Feb 1, 2022 at 19:51
  • $\begingroup$ @Expressingx the collection of frequencies is (8). So, all frequencies are divisible by 3 except that 8, which has a remainder of 3 when divided by 2. So, return "COMPLETE". (By the way, '8', '88', '888', '88888888', etc. are valid input. I guess you wanted to say '88888888' is a complete hand.) $\endgroup$
    – John L.
    Feb 1, 2022 at 20:34

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.