Introduction to Mahjong tiles

Mahjong (้บป้›€) is a board game that originates from China. Mahjong tiles used in this challenge are in Unicode points U+1F000 โ€“ U+1F021:

๐Ÿ€€๐Ÿ€๐Ÿ€‚๐Ÿ€ƒ๐Ÿ€„๐Ÿ€…๐Ÿ€†๐Ÿ€‡๐Ÿ€ˆ๐Ÿ€‰๐Ÿ€Š๐Ÿ€‹๐Ÿ€Œ๐Ÿ€๐Ÿ€Ž๐Ÿ€๐Ÿ€๐Ÿ€‘๐Ÿ€’๐Ÿ€“๐Ÿ€”๐Ÿ€•๐Ÿ€–๐Ÿ€—๐Ÿ€˜๐Ÿ€™๐Ÿ€š๐Ÿ€›๐Ÿ€œ๐Ÿ€๐Ÿ€ž๐Ÿ€Ÿ๐Ÿ€ ๐Ÿ€ก

They are categorized as:

  • Winds (้ขจ็‰Œ): ๐Ÿ€€(East Wind), ๐Ÿ€(South Wind), ๐Ÿ€‚(West Wind), ๐Ÿ€ƒ(North Wind)

  • Dragons (ไธ‰ๅ…ƒ็‰Œ): ๐Ÿ€„(Red Dragon), ๐Ÿ€…(Green Dragon), ๐Ÿ€†(White Dragon)

  • Ten Thousands (่ฌๅญ): ๐Ÿ€‡(One of the Ten Thousands) through ๐Ÿ€(Nine of the Ten Thousands)

  • Bamboos (็ดขๅญ): ๐Ÿ€(One of the Bamboos; note that it depicts a bird) through ๐Ÿ€˜(Nine of the Bamboos)

  • Circles (็ญ’ๅญ): ๐Ÿ€™(One of the Circles) through ๐Ÿ€ก(Nine of the Circles)

  • Winds and Dragons are together called Honors (ๅญ—็‰Œ).

  • Ten Thousands, Bamboos and Circles are each called a suit and together called Numbers (ๆ•ฐ็‰Œ). They have ranks from 1 to 9.

  • Among Numbers, the Ones and the Nines are called Terminals (่€้ ญ็‰Œ). The Twos through the Eights are called Simples (ไธญๅผต็‰Œ).

  • Honors and Terminals are together called Orphans (ๅนบไน็‰Œ).

Every Mahjong tiles have 4 copies of themselves.

Mahjong Hand

A legal Hand consists of:

  • A Head (ๅฏพๅญ), which is 2 identical tiles.

  • 4 Bodies (้ขๅญ), each which is either:

    • A Sequence (้ †ๅญ), which is 3 consecutive Numbers with same suit.

    • A Triplet (ๅˆปๅญ), which is 3 identical tiles.

Hence, a Hand consists of 14 tiles.

There are exceptional valid Hands. Seven Heads (ไธƒๅฏพๅญ), which is 7 distinct Heads, and Thirteen Orphans (ๅ›ฝๅฃซ็„กๅŒ), which collects all 13 Orphans with an additional Orphan.

Tenpais and Shantens

13 Mahjong tiles will be given as the input. If an additional tile would make a valid Hand, this is called Tenpai (่ฝ็‰Œ). Tenpai is zero Shantens.

If a tile must be exchanged to be Tenpai, this is 1-Shanten (1ๅ‘่ด).

If a tile must be exchanged to be 1-Shanten, this is 2-Shantens, and so on.

The objective is to output the number of Shantens.


๐Ÿ€‡๐Ÿ€‡๐Ÿ€‡๐Ÿ€Ž๐Ÿ€Ž๐Ÿ€Ž๐Ÿ€“๐Ÿ€“๐Ÿ€™๐Ÿ€š๐Ÿ€›๐Ÿ€Ÿ๐Ÿ€  : Tenpai waiting for ๐Ÿ€ž or ๐Ÿ€ก to make a Sequence. An example of Two-sided Wait (ๅ…ฉ้ขๅพ…ๆฉŸ).

๐Ÿ€€๐Ÿ€€๐Ÿ€‡๐Ÿ€‡๐Ÿ€๐Ÿ€Ž๐Ÿ€๐Ÿ€•๐Ÿ€–๐Ÿ€—๐Ÿ€œ๐Ÿ€๐Ÿ€ž : Tenpai waiting for ๐Ÿ€€ or ๐Ÿ€‡ to make a Triplet. An example of Wait for a Triplet (ๅŒ็ขฐๅพ…ๆฉŸ).

๐Ÿ€Š๐Ÿ€‹๐Ÿ€Œ๐Ÿ€๐Ÿ€Ž๐Ÿ€๐Ÿ€๐Ÿ€‘๐Ÿ€˜๐Ÿ€˜๐Ÿ€˜๐Ÿ€š๐Ÿ€š : Tenpai waiting for ๐Ÿ€’ to make a Sequence. An example of One-sided Wait (้‚Šๅผตๅพ…ๆฉŸ).

๐Ÿ€…๐Ÿ€…๐Ÿ€‡๐Ÿ€ˆ๐Ÿ€‰๐Ÿ€“๐Ÿ€“๐Ÿ€“๐Ÿ€™๐Ÿ€š๐Ÿ€›๐Ÿ€œ๐Ÿ€ž : Tenpai waiting for ๐Ÿ€ to make a Sequence. An example of Wait for the Middle (ๅŽๅผตๅพ…ๆฉŸ).

๐Ÿ€‡๐Ÿ€‡๐Ÿ€‡๐Ÿ€Œ๐Ÿ€๐Ÿ€Ž๐Ÿ€“๐Ÿ€–๐Ÿ€—๐Ÿ€˜๐Ÿ€๐Ÿ€ž๐Ÿ€Ÿ : Tenpai waiting for ๐Ÿ€“ to make a Head. An example of Wait for a Head (ๅ–ฎ้จŽๅพ…ๆฉŸ).

๐Ÿ€‡๐Ÿ€ˆ๐Ÿ€‰๐Ÿ€‰๐Ÿ€Š๐Ÿ€‹๐Ÿ€Œ๐Ÿ€๐Ÿ€๐Ÿ€๐Ÿ€“๐Ÿ€”๐Ÿ€• : Tenpai waiting for ๐Ÿ€ˆ, ๐Ÿ€‹, or ๐Ÿ€Ž. This example demonstrates how multiple ways of waiting can be combined.

๐Ÿ€‡๐Ÿ€‡๐Ÿ€‡๐Ÿ€ˆ๐Ÿ€‰๐Ÿ€Š๐Ÿ€‹๐Ÿ€Œ๐Ÿ€๐Ÿ€Ž๐Ÿ€๐Ÿ€๐Ÿ€ : Tenpai waiting for any of Ten Thousands. This is called Nine Gates (ไน่“ฎๅฎ็‡ˆ), and has the highest possible number of tiles to wait for to be a "normal" Hand.

๐Ÿ€„๐Ÿ€ˆ๐Ÿ€ˆ๐Ÿ€Š๐Ÿ€Š๐Ÿ€Œ๐Ÿ€Œ๐Ÿ€๐Ÿ€๐Ÿ€‘๐Ÿ€‘๐Ÿ€๐Ÿ€ : Tenpai waiting for ๐Ÿ€„ to make a Head. An example of Seven Heads.

๐Ÿ€€๐Ÿ€€๐Ÿ€๐Ÿ€‚๐Ÿ€ƒ๐Ÿ€„๐Ÿ€…๐Ÿ€†๐Ÿ€‡๐Ÿ€๐Ÿ€๐Ÿ€˜๐Ÿ€™ : Tenpai waiting for ๐Ÿ€ก. An example of Thirteen Orphans.

๐Ÿ€€๐Ÿ€๐Ÿ€‚๐Ÿ€ƒ๐Ÿ€„๐Ÿ€…๐Ÿ€†๐Ÿ€‡๐Ÿ€๐Ÿ€๐Ÿ€˜๐Ÿ€™๐Ÿ€ก : Tenpai waiting for any of Orphans. Another example of Thirteen Orphans.

๐Ÿ€€๐Ÿ€€๐Ÿ€€๐Ÿ€๐Ÿ€๐Ÿ€๐Ÿ€‚๐Ÿ€‚๐Ÿ€‚๐Ÿ€ƒ๐Ÿ€ƒ๐Ÿ€ƒ๐Ÿ€ƒ : 1-Shanten. Note that this is not Tenpai waiting for ๐Ÿ€ƒ because it would be a fifth ๐Ÿ€ƒ.

๐Ÿ€ˆ๐Ÿ€ˆ๐Ÿ€ˆ๐Ÿ€Š๐Ÿ€Š๐Ÿ€Œ๐Ÿ€Œ๐Ÿ€๐Ÿ€๐Ÿ€‘๐Ÿ€‘๐Ÿ€๐Ÿ€ : 1-Shanten. Note that this is not Tenpai for Seven Heads because getting ๐Ÿ€ˆ will result in a duplicated Head.

๐Ÿ€๐Ÿ€๐Ÿ€ƒ๐Ÿ€ƒ๐Ÿ€„๐Ÿ€„๐Ÿ€‰๐Ÿ€‰๐Ÿ€‹๐Ÿ€๐Ÿ€“๐Ÿ€—๐Ÿ€ž : 2-Shantens.

๐Ÿ€€๐Ÿ€๐Ÿ€‚๐Ÿ€ƒ๐Ÿ€ˆ๐Ÿ€‹๐Ÿ€Ž๐Ÿ€‘๐Ÿ€”๐Ÿ€—๐Ÿ€š๐Ÿ€๐Ÿ€  : 6-Shantens. This is the highest possible number of Shantens.

You can demonstrate arbitrary examples here. (for 13 or 14 tiles)

Rules about code golf

  • Input type and format doesn't matter, but it must consist of the Unicode characters above. In C++, valid examples include std::u8string (sorted or not) , u32char_t[13], and std::multiset<u32char_t>.

  • Output type and format doesn't matter either.

  • Invalid input (not exactly 13 tiles, contains 5 copies of the same tile, contains a character not in U+1F000 โ€“ U+1F021, etc) falls into don't care situation.

  • 1
    \$\begingroup\$ @KevinCruijssen Thanks. Since I want to see how golfing languages handle Unicode, I removed that rule. \$\endgroup\$ Feb 10, 2020 at 9:01
  • \$\begingroup\$ FYI: for some reason, the Mahjong tile characters are hard to read on (my version of) Firefox which alternates between small monochrome characters and larger color characters. Weirdly enough, the monochrome and color versions of the same character are both used depending on its position in the post. No problem on Chrome on the same laptop. \$\endgroup\$
    – Arnauld
    Feb 10, 2020 at 10:23
  • \$\begingroup\$ @Arnauld Really? I'm using Firefox on Ubuntu, and to me, only ๐Ÿ€„ is displayed as emoji, and all other tiles are displayed as monochrome characters. I'm afraid I don't know a solution. \$\endgroup\$ Feb 10, 2020 at 10:26
  • \$\begingroup\$ It is quite painful to convert from Unicode to the mpsz notation used by the tool linked in the challenge, or the other way around. So ... \$\endgroup\$
    – Arnauld
    Feb 11, 2020 at 2:21
  • 1
    \$\begingroup\$ Also, I think we need more non-tenpai test cases, especially some tricky ones where it's not obvious to decide which groups should be removed or completed to get the optimal N-shantens. \$\endgroup\$
    – Arnauld
    Feb 11, 2020 at 2:27

1 Answer 1


05AB1E, 80 77 73 72 77 74 bytes

โ‚‚ร8+3รคโ‚ฌรผ3โ‚ฌ`4ะธML3ฮดะธยฉยซ4รฃยฎโ‚ฌยฆยฉรขส’หœDยขร 5โ€น}ยฎ7.ร†ยซ8Lโ€ข1ยซรพรฏโ€ขโ‚†ะฒยซDยธรขยซฮตหœโ€ข1รณรฑโ€ข+รงJล“Iล“ฮด.L}W<

-5 bytes thanks to @Grimmy, and also for teaching me about a hidden builtin
+5 bytes to fix two bugs

Brute-force approach that's extremely slow, so obviously no TIO with test cases.

Although TIO is too slow for the entire solution, I've added a TIO after each section so you can verify the individual parts work as intended. Note that the final TIO-link only uses a portion of each hand (including the input).

General explanation:

  1. Generate a list of all valid 14-tile hands
  2. Get every possible permutation of every 14-tile hand
  3. Get the input-hand and get all its permutations as well
  4. Get the Levenshtein distance between every input-hand permutation and every valid 14-tile hand permutation
  5. Keep the lowest Levenshtein distance across all these checks, and decrease it by 1 to get the number of Shantens

Code explanation:

Create a list of all overlapping consecutive triplets of the Numbers:

โ‚‚ร                # Push a list in the range [0,26]
  8+              # Add 8 to each to make the range [8,34]
    3รค            # Split it into 3 equal-sized parts: [[8,16],[17,25],[26,34]]
      โ‚ฌ           # For each inner list:
       รผ3         #  Create all overlapping triplets of this list
                  #   [a,b,c,d,e,...] โ†’ [[a,b,c],[b,c,d],[c,d,e],...]
         โ‚ฌ`       # Then flatten one level down to have a list of triplets
           4ะธ     # And repeat each consecutive triplet 4 times in the list

Try it online.

Create a list of all possible triplets of all tiles:

M                 # Push the largest value on the stack thus far (including inner lists),
                  # which is 34
 L                # Pop and push a list in the range [1,34]
   ฮด              # For each value in this list,
  3 ะธ             #  Repeat it 3 times as list
     ยฉ            # Store the list of identical triplets in variable `ยฎ` (without popping)

Try it online.


ยซ                 # Merge the two lists together
 4รฃ               # And take the cartesian product of 4 with this list

Which results in all possible combinations of 4 Bodies: Try it online.

Then we'll generate all possible Heads:

ยฎ                 # Push the list of identical triplets from variable `ยฎ`
 โ‚ฌยฆ               # Remove one value from each so we have identical pairs (Heads) instead
   ยฉ              # Store that as new variable `ยฎ` (without popping)

Try it online.

And create every possible combination of these 1 Heads + 4 Bodies:

รข                 # By taking the cartesian product of the two lists
 ส’      }         # And then filtering it so we won't use more than 4 of the same tile:
  หœ               #  Flatten the pairs/triplets to a single list
   Dยข             #  Duplicate it, and count for each item how much it occurs
     ร             #  Get the maximum for the tile that occurs the most
      5โ€น          #  And check that this it smaller than 5

Now we have all possible regular 14-tile hands: Try it online.

Next we'll also create the special type of 14-tile heads, starting with the 7 Heads:

ยฎ                 # Push the list of identical pairs (Heads) from variable `ยฎ` again
 7.ร†              # Get all 7-element combinations of these distinct heads
    ยซ             # And merge it to the earlier created valid 14-tile hands

Try it online.

And the final valid 14-tile hands are the 13+1 Orphans:

8L                # Push a list in the range [1,8] (4 Winds, 3 Dragons, and One of the Ten Thousands)
  โ€ข1ยซรพรฏโ€ข          # Push compressed integer 27700378
        โ‚†ะฒ        # Convert it to base-36 as list: [16,17,25,26,34] (Nine of the Ten Thousands,
                  #  One & Nine of the Bamboos, One & Nine of the Circles)
          ยซ       # Merge those together
           Dยธ     # Duplicate this list of 13 Orphans, and wrap it into a list
             รข    # And take the cartesian product of the two
              ยซ   # And also merge those to the earlier created valid 14-tile hands

Try it online.

Now that we finally have all our valid 14-tile hands, we're going to get all their permutations as well as the permutations of the input, and check the Levenshtein-distance between each possible combination. After which the lowest Levenshtein-distance across all permutation-comparisons minus 1 is our number of Shatens:

ฮต                 # Map over each valid 14-tile hand:
 หœ                #  Flatten the pairs/triplets to a single 14-length list
  โ€ข1รณรฑโ€ข           #  Push compressed integer 126975
       +          #  Add it to each value in the list
        รง         #  Convert each from integer to their unicode character
         J        #  And join it together to a single string
          ล“       #  Get all permutations of this hand
 Iล“               #  Then push the input, and get all its permutations as well
 ฮด                #  And then check for every possible combination of the permutations:
  .L              #   What the Levenshtein-distance is between the two

And finally get the (flattened) lowest one to calculate the number of Shantens:

}W                # After the map: push the flattened lowest Levenshtein-distance
  <               # And subtract it by 1 to get the number of Shantens
                  # (after which this is output implicitly as result)

Try it online with just a portion of the valid hands, each cut into a smaller hand, and with added debug-lines.

See this 05AB1E tip of mine (sections How to compress large integers? and How to compress integer lists?) to understand why โ€ข1ยซรพรฏโ€ข is 27700378; โ€ข1ยซรพรฏโ€ขโ‚†ะฒ is [16,17,25,26,34]; and โ€ข1รณรฑโ€ข is 126975.

How slow?

To give you an idea of how slow this approach is, here are some numbers:

Regular hands: \$34ร—118^4-X\$

  • There are \$118\$ valid Bodies (including duplicated subsequent triplets for the Numbers, which each occur four time), and thus \$118^4\$ combinations of 4 Bodies (yes, this includes duplicated combinations due to the duplicated subsequent Number triplets).
  • There are \$34\$ valid Heads, and thus \$34ร—118^4\$ combinations of 1 Head + 4 Bodies.
  • After which \$X\$ (TODO: do the math..) combinations are removed, because they contain a certain tile more than four times.

Special hands: \$\binom{34}{7} + 13\$

  • There are again \$34\$ valid Heads, and thus \$\binom{34}{7}\$ combinations of 7 distinct Heads.
  • There are \$13\$ Orphans (\$4\$ Winds + \$3\$ Dragons + \$3\$ Ones + \$3\$ Nines), and thus \$13\$ valid Orphan hands.

There are therefore a total of \$34ร—118^4-X + \binom{34}{7} + 13 = 6597224013-X\$ valid 14-tile hands.

Comparing the input-hand and a single valid-hand: \$14!ร—13!\$

  • Getting all permutations of the 14-tile hands means there are \$14!\$ permutations.
  • Getting all permutations of the 13-tile input-hand means there are \$13!\$ permutations.
  • Checking each permutation of a valid 14-tile hand with each permutation of the input-hand are therefore \$14!ร—13! = 542861032610856960000\$ valid permutation-pairs.

So in conclusion:

Assuming a standard Levenshtein algorithm is used in the .L builtin, the complexity is in general about \$O(n^2)\$ (\$n\$ being the length of the string). Which in this case would be complexity \$O(14^2) = O(196)\$ for each of the \$14!ร—13! ร— (34ร—118^4-X + \binom{34}{7} + 13) = \$\$3581375840062321621020180480000 - 542861032610856960000ร—X\$ permutation-combinations across all valid hands (after which we still have to get the flattened \$minimum-1\$).
Safe to say: way too slow for a TIO link for even a single test case, let alone a test suite of all test cases. ;)

  • 2
    \$\begingroup\$ üโ€šü«โ‚ฌÙ is the built-in ü3: TIO. \$\endgroup\$
    – Grimmy
    Feb 10, 2020 at 13:17
  • \$\begingroup\$ @Grimmy Huh, since when is that a thing?! o.Ô \$\endgroup\$ Feb 10, 2020 at 13:18
  • \$\begingroup\$ Probably since non-legacy 05AB1E. Also, that literal 34 can be M. \$\endgroup\$
    – Grimmy
    Feb 10, 2020 at 13:20
  • \$\begingroup\$ If anyone knows the math for the \$X\$, let me know. \$\endgroup\$ Feb 11, 2020 at 12:09
  • \$\begingroup\$ Winning hands => permutations of each => drop last from each => levenshtein distance of each with the current hand would also work, saving a 13! execution time factor and probably a few bytes. \$\endgroup\$
    – Grimmy
    Feb 11, 2020 at 12:44

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.