Mahjong Tenpai
InterviewTime limit2sMemory limit1024 MB
Given 13 mahjong tiles, check whether the hand is in tenpai and list every tile kind that completes a valid 14-tile win.
- Level
Medium5 of 10
- Topics
- Brute force, Backtracking, Implementation
- Solved
- No attempts yet
Problem
The mahjong in this problem may differ from real mahjong.
Mahjong is a game from China. Players repeatedly draw and discard tiles to form a specific shape. There are two kinds of tiles: number tiles and honor tiles. A number tile has a suit and a number. The suit is one of three kinds: sak, tong, or man. The number is from 1 to 9, so there are 27 kinds of number tiles. An honor tile has no number. Its kind is one of seven: East, South, West, North, White, Green, or Red. Each tile kind has 4 copies. So the game uses 136 tiles: 4 copies each of 1 to 9 sak, 1 to 9 tong, 1 to 9 man, East, South, West, North, White, Green, and Red.
At the start, a player holds 13 of the 136 tiles. When the player draws one of the remaining tiles and the 14 tiles form a valid combination, the player declares "tsumo" and wins. If the player cannot declare tsumo, the player discards a tile of choice, draws a new one, and repeats. A hand of 13 tiles is in the "tenpai" state if adding one more tile lets the player declare tsumo.
A valid set of 14 tiles splits into 1 pair and 4 sets. The pair is 2 identical tiles. Each set has 3 tiles and is either a "shuntsu" or a "kotsu". A shuntsu is 3 consecutive number tiles of the same suit. Honor tiles have no numbers, so they cannot form a shuntsu. A kotsu is 3 identical tiles.
There are two special valid combinations. "Chiitoitsu" is 7 pairs among the 14 tiles. A hand with 4 identical tiles does not count as chiitoitsu. "Kokushi musou" is made of 13 tiles: 1 and 9 of sak, 1 and 9 of man, 1 and 9 of tong, and all 7 honor tiles. The 14th tile is a duplicate of one of these 13 tiles.
Given 13 tiles in the tenpai state, find which tile kinds can be the last tile that completes the hand for tsumo.
Input
13 tiles are given, separated by spaces.
Sak tiles are written as s, tong tiles as t, and man tiles as m. The number is written before the letter. East is e, South is s, West is w, North is n, White is h, Green is b, and Red is j.
Output
If the given tiles are in the tenpai state, print tenpai on the first line. On the second line, print the number of tile kinds that complete the hand for tsumo. On the third line, print those tile kinds in lexicographic order, separated by spaces.
If the given tiles are not in the tenpai state, print no tenpai on the first line.
Hint
The lexicographic order is defined as follows.
If two strings have different lengths, append a special character that is smaller than every character to the end of the shorter string until the lengths are equal. If the lengths are equal, compare the characters from the first one. Skip equal characters. At the first different character, the string with the smaller character is smaller in lexicographic order.