Last week, I began my first-ever programming project. I also explained the basics of the Hong Kong Mahjong scoring system.
To win a game, you must be the first to collect various Chows (3 sequential suited tiles) and Pongs (3 identical tiles), along with a pair of Eyes (a pair of identical tiles). This is the fundamental part of Faan calculation.
Checkout the basics in my last aricle if you haven’t!
Given a list of the tiles,
I want to group the tiles into melds that meet the requirements,
So that I could deduce the Winning Hand according to various combinations of melds.
To simplify the problem, I assumed the winning condition is Win from Wall, i.e., the entire hand remains concealed until the winning tile was drawn or stolen. I chose Chow determination as the starting point because determining Pong is so straightforward that it doesn’t offer much insight into data structure design.
The Common Hand consists of 4 melds of Chows and a pair of Eyes.
The problem was further simplified as follows:
Given a set of 13 tiles. Return 1 if it can form the Common Hand. Return 0 otherwise.
Example 1:
Input: tiles = 🀗🀑🀒🀕🀒🀘🀖🀐🀑🀔🀐🀗🀖🀔
Output: 1
Explanation
The tiles can be reorganised as 🀐🀑🀒 🀐🀑🀒 🀕🀖🀗 🀖🀗🀘 🀔🀔, which is the Common Hand.Example 2:
Input: tiles = 🀐🀑🀑🀑🀒🀒🀒🀓🀕🀕🀘🀘🀗🀗
Output: 0
Explanation
Nothing valid can be constructed.Example 2:
Input: tiles = 🀑🀑🀑🀒🀒🀒🀕🀕🀕🀗🀗🀗🀘🀘
Output: 0
Explanation
This is an All in Triplets, not a Common Hand.
I’ve rarely been good at Backtracking, but unexpectedly, my first intuition was to use backtracking to solve this problem.
Take 🀗🀑🀒🀕🀒🀘🀖🀐🀑🀔🀐🀗🀖🀔 as an example. First, sort the tiles in non-descending order. It becomes 🀐🀐🀑🀑🀒🀒🀔🀔🀕🀖🀖🀗🀗🀘. For each tile, there are 2 possibilities:
- Include the current tile in the subset and recur for the remaining tiles if they are consecutive.
- Exclude the current tile and recur for the remaining tiles.
When a Chow is formed, it will be included in the final results. The Eyes can be identified later by checking the remaining tiles.
While this approach correctly forms Chows and identifies Eyes, its complexity is O(2N) because it may explore all subsets of the given sets in the worst case. This algorithm is inefficient. In fact, we don’t need to check all subsets since we only care about consecutive tiles. Checking groups like 🀐🀑🀔 is redundant.
Reflecting on the LeetCode problems I’ve solved recently, I realised the problem could be simplified with arrays. First, create an array tileCounts
where tileCounts[i]
represents the number of tile i. Then count all the tiles. Looping through i from 1 to 7, find minRemaining
, the minimum count of the i-th, (i+1)-th, and (i+2)-th tiles. Add minRemaining
of this set to the solution and reduce the count of the tiles accordingly.
var tileCounts = new int[10];
for (var tile : tiles) {
tileCounts[tile.charAt(1) - '0']++;
}
var chows = new ArrayList<List<Integer>>();
for (var i = 1; i <= 7; i++) {
var minRemaining = Math.min(tileCounts[i], Math.min(tileCounts[i + 1], tileCounts[i + 2]));
for (var j = 0; j < minRemaining; j++) {
chows.add(List.of(i, i + 1, i + 2));
}
tileCounts[i] -= minRemaining;
tileCounts[i + 1] -= minRemaining;
tileCounts[i + 2] -= minRemaining;
}
var eye = -1;
for (var i = 1; i < tileCounts.length; i++) {
if (tileCounts[i] == 2) {
eye = i;
tileCounts[i] = 0;
break;
}
}
The Eye can then be found easily in the tileCounts
array, where the value is larger or equal to 2.
This is the simplest approach I’ve come up with so far, drastically reducing the time complexity from exponential to linear.
Here comes 2 post-reading questions!
- Given tiles = 🀐🀑🀑🀑🀒🀒🀓🀔🀖🀖🀗🀗🀘🀘, the algorithm returns 🀐🀑🀒 🀑🀒🀓 🀖🀗🀘 🀖🀗🀘, leaving 🀑 and 🀔 unused. How can we refine the algorithm to return 🀐🀑🀒 🀒🀓🀔 🀖🀗🀘 🀖🀗🀘 🀑🀑 instead?
- If Pong determination is added and tiles = 🀐🀐🀐🀑🀑🀑🀒🀒🀒🀚🀚🀇🀇🀇, how can the algorithm be refined to return All in Triplets 🀐🀐🀐 🀑🀑🀑 🀒🀒🀒 🀇🀇🀇 🀚🀚, where every meld is a Pong, instead of a Chicken Hand 🀐🀑🀒 🀐🀑🀒 🀐🀑🀒 🀇🀇🀇 🀚🀚, which mixes Pongs and Chows?
When I first learned Java 8 and Stream API years ago, I was so fixated on using Stream API everywhere in my codebase. I also avoided variables, relying only on constants. You wouldn’t find continue
, break
, while
or for
in my code. I once belived Stream API was a silver bullet for all looping problems and saw variable reassignment as a bad pracice. However, practising LeetCode challenges help me unlearn those mindsets and relearn from scratch. Using only Stream API and ditching variable reassignment could be the enabling constraints for learning some coding practices, but that doesn’t mean we should avoid other techniques to solve a problem. Now, I know how to adapt my approach depending on the situation.
As of now, I’ve implemented all the winning hands under Win from Wall condition. In the coming week, I’ll explore an area I’ve never touched before – the front-end development.
Stay tuned!