BarclayII/shanten.py

## shanten.py
# Generic Shanten Calculator for Mahjong
# This script calculates the shanten number for a given Mahjong hand.
# It supports standard hands with different number of melds and pairs.
#
# The algorithm first tabulates the shanten of one suit only, considering different number of melds and whether a pair is present.
# Then it combines the results from all suits to get the final shanten number.
#
# Tabulation:
# Tabulation is done using dynamic programming to efficiently compute the minimum shanten.
# Let f_{m,p}(n1, n2, ..., n9) be the minimum number of tiles needed to complete m melds and p pairs from the given tile counts n1 to n9 for man, sou or pin suits, initialized with infinity.
# (f^z_{m,p}(n1, n2, ..., n7) is used for honors.)
# (m ranges from 0 to 4, p is either 0 or 1.)
# 1. We initialize the base case where the number of tiles needed is 0:
#    a. Start with 0 melds and 0 pairs
#       f_{0,0}(0, 0, ..., 0) = 0
#       Add (0, 0, ..., 0) to the processing queue and mark it as visited.
#    b. Pop the state from the queue, visit "neighboring" states by adding melds or pairs:
#       f_{m+1,p}(n1, n2, ..., n9) = min(
#           f_{m+1,p}(n1, n2, ..., n9),
#           f_{m,p}(n1 - 3, n2, ..., n9),
#           f_{m,p}(n1, n2 - 3, ..., n9),
#           ...
#           f_{m,p}(n1, n2, ..., n9 - 3), # triplets
#           f_{m,p}(n1 - 1, n2 - 1, n3 - 1, n4, ..., n9),
#           f_{m,p}(n1, n2 - 1, n3 - 1, n4 - 1, ..., n9),
#           ...
#           f_{m,p}(n1, n2, ..., n7 - 1, n8 - 1, n9 - 1), # sequences
#       )
#       f_{m,p+1}(n1, n2, ..., n9) = min(
#           f_{m,p+1}(n1, n2, ..., n9),
#           f_{m,p}(n1 - 2, n2, ..., n9),
#           f_{m,p}(n1, n2 - 2, ..., n9),
#           ...
#           f_{m,p}(n1, n2, ..., n9 - 2),
#       ) # pairs
#       Add newly visited states to the processing queue.
#       (for f^z, only consider triplets and pairs)
#    c. Repeat until the queue is empty.
# 2. After finding all f's whose values are 0, use them as "seeds" and flood-fill to find all other states: For each state in the queue, visit "neighboring" unvisited states by removing or adding a single tile.  If the unvisited state comes from adding a tile, set its value to the current state's value (as it does not impact how many tiles are needed).  If the unvisited state comes from removing a tile, set its value to the current state's value + 1 (as it increases the number of tiles needed by 1).  More specifically:
#       Maintain a processing queue initialized with all states f_{m,p}(n1, n2, ..., n9) and f^z_{m,p}(n1, n2, ..., n7) whose values are 0.
#       Pop a state from the queue, visit "neighboring" states by adding or removing a single tile:
#       f_{m,p}(n1, n2, ..., ni + 1, ..., n9) = min(
#           f_{m,p}(n1, n2, ..., ni + 1, ..., n9),
#           f_{m,p}(n1, n2, ..., ni, ..., n9)
#       )
#       f_{m,p}(n1, n2, ..., ni - 1, ..., n9) = min(
#           f_{m,p}(n1, n2, ..., ni - 1, ..., n9),
#           f_{m,p}(n1, n2, ..., ni, ..., n9) + 1
#       )
#       (same for f^z)
#       If a state got updated (i.e. its value changes from its previous value), add it to the processing queue.
#       Repeat until the queue is empty.
#
# Combining results from all suits:
# After tabulation, we get the shanten number for getting m melds and p pairs by:
# 1. Enumerate all possible distributions of melds and pairs among the suits.
# 2. For each distribution, sum up the shanten numbers from each suit.
# 3. The minimum sum across all distributions is the final shanten number.
#
# This tabulation-combination approach can also be extended to different yakus (e.g. Honitsu, Sanshoku, Sanankou, etc.) by starting from different base cases and adjusting the combination step accordingly.

"""
Shanten Calculator using BFS/Flood-fill Algorithm
Optimized version: Only computes states with <= 14 tiles total
"""

import time
from collections import deque


def precompute_suit_tables():
    """
    Precompute f_{m,p}(n1,...,n9) for suited tiles (man/pin/sou)
    Only compute states where sum(tiles) <= 14
    Returns: dict[(m, p)] -> dict[state_tuple] -> min_tiles_needed
    """
    print("Precomputing suited tile tables (max 14 tiles)...")
    start = time.time()

    tables = {}
    for m in range(5):  # 0 to 4 melds
        for p in range(2):  # 0 or 1 pair
            tables[(m, p)] = {}

    # Phase 1: Find all states with f=0 (perfect formations)
    print("  Phase 1: Finding perfect formations...")
    initial_state = (0,) * 9
    tables[(0, 0)][initial_state] = 0

    queue = deque([(0, 0, initial_state)])
    visited_phase1 = set([(0, 0, initial_state)])

    while queue:
        m, p, state = queue.popleft()

        # Try adding melds (if we haven't reached 4 melds yet)
        if m < 4:
            # Try adding triplets at each position
            for i in range(9):
                new_state = list(state)
                new_state[i] += 3
                # Check: total tiles <= 14 and each tile type <= 4
                if sum(new_state) <= 14 and new_state[i] <= 4:
                    new_state = tuple(new_state)
                    key = (m + 1, p, new_state)
                    if key not in visited_phase1:
                        visited_phase1.add(key)
                        tables[(m + 1, p)][new_state] = 0
                        queue.append((m + 1, p, new_state))

            # Try adding sequences (positions 0-6 can start a sequence)
            for i in range(7):
                new_state = list(state)
                new_state[i] += 1
                new_state[i + 1] += 1
                new_state[i + 2] += 1
                # Check: total tiles <= 14 and each tile type <= 4
                if sum(new_state) <= 14 and all(
                    new_state[j] <= 4 for j in [i, i + 1, i + 2]
                ):
                    new_state = tuple(new_state)
                    key = (m + 1, p, new_state)
                    if key not in visited_phase1:
                        visited_phase1.add(key)
                        tables[(m + 1, p)][new_state] = 0
                        queue.append((m + 1, p, new_state))

        # Try adding pairs (if we don't have a pair yet)
        if p < 1:
            for i in range(9):
                new_state = list(state)
                new_state[i] += 2
                # Check: total tiles <= 14 and each tile type <= 4
                if sum(new_state) <= 14 and new_state[i] <= 4:
                    new_state = tuple(new_state)
                    key = (m, p + 1, new_state)
                    if key not in visited_phase1:
                        visited_phase1.add(key)
                        tables[(m, p + 1)][new_state] = 0
                        queue.append((m, p + 1, new_state))

    phase1_count = sum(len(tables[(m, p)]) for m in range(5) for p in range(2))
    print(f"    Found {phase1_count} perfect states")

    # Phase 2: Flood-fill from all f=0 states
    print("  Phase 2: Flood-filling all states...")
    for m in range(5):
        for p in range(2):
            # Use BFS with cost levels
            # Start with all f=0 states
            current_level = deque()
            for state in tables[(m, p)]:
                if tables[(m, p)][state] == 0:
                    current_level.append(state)

            cost = 0
            while current_level:
                next_level = deque()

                while current_level:
                    state = current_level.popleft()

                    # Try adding a tile (cost stays the same)
                    for i in range(9):
                        new_state = list(state)
                        new_state[i] += 1
                        # Check: total tiles <= 14 and each tile type <= 4
                        if sum(new_state) <= 14 and new_state[i] <= 4:
                            new_state = tuple(new_state)
                            if new_state not in tables[(m, p)]:
                                tables[(m, p)][new_state] = cost
                                current_level.append(new_state)

                    # Try removing a tile (cost increases by 1)
                    for i in range(9):
                        if state[i] > 0:
                            new_state = list(state)
                            new_state[i] -= 1
                            new_state = tuple(new_state)
                            # No need to check sum <= 14 since we're removing
                            if new_state not in tables[(m, p)]:
                                tables[(m, p)][new_state] = cost + 1
                                next_level.append(new_state)

                current_level = next_level
                cost += 1
                if cost > 14:  # Safety limit
                    break

    elapsed = time.time() - start
    total_states = sum(len(tables[(m, p)]) for m in range(5) for p in range(2))
    print(f"  Suited tables precomputed in {elapsed:.2f}s")
    print(f"  Total states: {total_states:,} (down from ~19.5M)")
    return tables


def precompute_honor_tables():
    """
    Precompute f^z_{m,p}(n1,...,n7) for honor tiles
    Only compute states where sum(tiles) <= 14
    (Only triplets and pairs, no sequences)
    """
    print("Precomputing honor tile tables (max 14 tiles)...")
    start = time.time()

    tables = {}
    for m in range(5):
        for p in range(2):
            tables[(m, p)] = {}

    # Phase 1: Perfect formations
    initial_state = (0,) * 7
    tables[(0, 0)][initial_state] = 0

    queue = deque([(0, 0, initial_state)])
    visited_phase1 = set([(0, 0, initial_state)])

    while queue:
        m, p, state = queue.popleft()

        # Try adding triplets
        if m < 4:
            for i in range(7):
                new_state = list(state)
                new_state[i] += 3
                # Check: total tiles <= 14 and each tile type <= 4
                if sum(new_state) <= 14 and new_state[i] <= 4:
                    new_state = tuple(new_state)
                    key = (m + 1, p, new_state)
                    if key not in visited_phase1:
                        visited_phase1.add(key)
                        tables[(m + 1, p)][new_state] = 0
                        queue.append((m + 1, p, new_state))

        # Try adding pairs
        if p < 1:
            for i in range(7):
                new_state = list(state)
                new_state[i] += 2
                # Check: total tiles <= 14 and each tile type <= 4
                if sum(new_state) <= 14 and new_state[i] <= 4:
                    new_state = tuple(new_state)
                    key = (m, p + 1, new_state)
                    if key not in visited_phase1:
                        visited_phase1.add(key)
                        tables[(m, p + 1)][new_state] = 0
                        queue.append((m, p + 1, new_state))

    # Phase 2: Flood-fill
    for m in range(5):
        for p in range(2):
            current_level = deque()
            for state in tables[(m, p)]:
                if tables[(m, p)][state] == 0:
                    current_level.append(state)

            cost = 0
            while current_level:
                next_level = deque()

                while current_level:
                    state = current_level.popleft()

                    # Add a tile
                    for i in range(7):
                        new_state = list(state)
                        new_state[i] += 1
                        # Check: total tiles <= 14 and each tile type <= 4
                        if sum(new_state) <= 14 and new_state[i] <= 4:
                            new_state = tuple(new_state)
                            if new_state not in tables[(m, p)]:
                                tables[(m, p)][new_state] = cost
                                current_level.append(new_state)

                    # Remove a tile
                    for i in range(7):
                        if state[i] > 0:
                            new_state = list(state)
                            new_state[i] -= 1
                            new_state = tuple(new_state)
                            if new_state not in tables[(m, p)]:
                                tables[(m, p)][new_state] = cost + 1
                                next_level.append(new_state)

                current_level = next_level
                cost += 1
                if cost > 14:
                    break

    elapsed = time.time() - start
    total_states = sum(len(tables[(m, p)]) for m in range(5) for p in range(2))
    print(f"  Honor tables precomputed in {elapsed:.2f}s")
    print(f"  Total states: {total_states:,}")
    return tables


def calculate_shanten(hand_str, suit_tables, honor_tables):
    """
    Calculate shanten number for a given hand.
    hand_str format: "123456m1378s2256p" or with honors like "123m456p11z"
    """
    # Parse hand into tile counts
    tiles = [0] * 34
    current_suit = []

    for char in hand_str:
        if char.isdigit():
            current_suit.append(int(char))
        elif char in "mpsz":
            suit_offset = {"m": 0, "p": 9, "s": 18, "z": 27}[char]
            for num in current_suit:
                tiles[suit_offset + num - 1] += 1
            current_suit = []

    # Split into suits
    man_state = tuple(tiles[0:9])
    pin_state = tuple(tiles[9:18])
    sou_state = tuple(tiles[18:27])
    honor_state = tuple(tiles[27:34])

    # Try all distributions of melds and pairs
    min_cost = float("inf")

    # m1 + m2 + m3 + m4 = 4 (total 4 melds)
    # p1 + p2 + p3 + p4 = 1 (total 1 pair)
    for m1 in range(5):
        for m2 in range(5):
            for m3 in range(5):
                for m4 in range(5):
                    if m1 + m2 + m3 + m4 != 4:
                        continue

                    for p1 in range(2):
                        for p2 in range(2):
                            for p3 in range(2):
                                for p4 in range(2):
                                    if p1 + p2 + p3 + p4 != 1:
                                        continue

                                    # Look up costs
                                    cost1 = suit_tables[(m1, p1)].get(
                                        man_state, float("inf")
                                    )
                                    cost2 = suit_tables[(m2, p2)].get(
                                        pin_state, float("inf")
                                    )
                                    cost3 = suit_tables[(m3, p3)].get(
                                        sou_state, float("inf")
                                    )
                                    cost4 = honor_tables[(m4, p4)].get(
                                        honor_state, float("inf")
                                    )

                                    total_cost = cost1 + cost2 + cost3 + cost4
                                    min_cost = min(min_cost, total_cost)

    # Shanten = tiles_needed - 1
    shanten = min_cost - 1
    return max(-1, shanten)


# Main execution
if __name__ == "__main__":
    print("=" * 70)
    print("SHANTEN CALCULATOR - BFS with 14-tile Optimization")
    print("=" * 70)
    print()

    # Precompute tables
    suit_tables = precompute_suit_tables()
    honor_tables = precompute_honor_tables()

    print("\n" + "=" * 70)
    print("Testing shanten calculation")
    print("=" * 70)

    # Test cases
    test_hands = [
        "123456m1378s2256p",  # The original 14-tile hand
        "123456m137s2256p",  # 13-tile version
        "123m456p789s1122z",  # Different hand
        "11122233344455m",  # Many pairs
        "147m258p369s1234z",  # Scattered
        "19m19p19s1234567z",  # Kokushi attempt
        "1112345678999m",  # 13 tiles, all man
        "2258m408p134s4577z",
        "79m189p34455s1456z",
        "14m244p46s1122346z",
        "238m3446788p23s13z",
        "22679m259p1255s35z",
        "12244455677889p",
        "11122344677899p",
        "11222346688999p",
        "11222234556899p",
    ]

    for hand in test_hands:
        # Count tiles
        tile_count = sum(1 for char in hand if char.isdigit())
        shanten = calculate_shanten(hand, suit_tables, honor_tables)
        print(f"\nHand: {hand}")
        print(f"  Tiles: {tile_count}")
        print(f"  Shanten: {shanten}")
        if shanten == -1:
            print("  Status: WINNING HAND!")
        elif shanten == 0:
            print("  Status: TENPAI (ready)")
        else:
            print(f"  Status: {shanten} away from tenpai")

    print("\n" + "=" * 70)
    print("Optimization Impact:")
    print("  Previous version: ~19.5M suited states")
    print(
        f"  This version: {sum(len(suit_tables[(m, p)]) for m in range(5) for p in range(2)):,} suited states"
    )
    print(
        f"  Reduction: ~{100 * (1 - sum(len(suit_tables[(m, p)]) for m in range(5) for p in range(2)) / 19_531_250):.1f}%"
    )
    print("=" * 70)
	# Generic Shanten Calculator for Mahjong
	# This script calculates the shanten number for a given Mahjong hand.
	# It supports standard hands with different number of melds and pairs.
	#
	# The algorithm first tabulates the shanten of one suit only, considering different number of melds and whether a pair is present.
	# Then it combines the results from all suits to get the final shanten number.
	#
	# Tabulation:
	# Tabulation is done using dynamic programming to efficiently compute the minimum shanten.
	# Let f_{m,p}(n1, n2, ..., n9) be the minimum number of tiles needed to complete m melds and p pairs from the given tile counts n1 to n9 for man, sou or pin suits, initialized with infinity.
	# (f^z_{m,p}(n1, n2, ..., n7) is used for honors.)
	# (m ranges from 0 to 4, p is either 0 or 1.)
	# 1. We initialize the base case where the number of tiles needed is 0:
	# a. Start with 0 melds and 0 pairs
	# f_{0,0}(0, 0, ..., 0) = 0
	# Add (0, 0, ..., 0) to the processing queue and mark it as visited.
	# b. Pop the state from the queue, visit "neighboring" states by adding melds or pairs:
	# f_{m+1,p}(n1, n2, ..., n9) = min(
	# f_{m+1,p}(n1, n2, ..., n9),
	# f_{m,p}(n1 - 3, n2, ..., n9),
	# f_{m,p}(n1, n2 - 3, ..., n9),
	# ...
	# f_{m,p}(n1, n2, ..., n9 - 3), # triplets
	# f_{m,p}(n1 - 1, n2 - 1, n3 - 1, n4, ..., n9),
	# f_{m,p}(n1, n2 - 1, n3 - 1, n4 - 1, ..., n9),
	# ...
	# f_{m,p}(n1, n2, ..., n7 - 1, n8 - 1, n9 - 1), # sequences
	# )
	# f_{m,p+1}(n1, n2, ..., n9) = min(
	# f_{m,p+1}(n1, n2, ..., n9),
	# f_{m,p}(n1 - 2, n2, ..., n9),
	# f_{m,p}(n1, n2 - 2, ..., n9),
	# ...
	# f_{m,p}(n1, n2, ..., n9 - 2),
	# ) # pairs
	# Add newly visited states to the processing queue.
	# (for f^z, only consider triplets and pairs)
	# c. Repeat until the queue is empty.
	# 2. After finding all f's whose values are 0, use them as "seeds" and flood-fill to find all other states: For each state in the queue, visit "neighboring" unvisited states by removing or adding a single tile. If the unvisited state comes from adding a tile, set its value to the current state's value (as it does not impact how many tiles are needed). If the unvisited state comes from removing a tile, set its value to the current state's value + 1 (as it increases the number of tiles needed by 1). More specifically:
	# Maintain a processing queue initialized with all states f_{m,p}(n1, n2, ..., n9) and f^z_{m,p}(n1, n2, ..., n7) whose values are 0.
	# Pop a state from the queue, visit "neighboring" states by adding or removing a single tile:
	# f_{m,p}(n1, n2, ..., ni + 1, ..., n9) = min(
	# f_{m,p}(n1, n2, ..., ni + 1, ..., n9),
	# f_{m,p}(n1, n2, ..., ni, ..., n9)
	# )
	# f_{m,p}(n1, n2, ..., ni - 1, ..., n9) = min(
	# f_{m,p}(n1, n2, ..., ni - 1, ..., n9),
	# f_{m,p}(n1, n2, ..., ni, ..., n9) + 1
	# )
	# (same for f^z)
	# If a state got updated (i.e. its value changes from its previous value), add it to the processing queue.
	# Repeat until the queue is empty.
	#
	# Combining results from all suits:
	# After tabulation, we get the shanten number for getting m melds and p pairs by:
	# 1. Enumerate all possible distributions of melds and pairs among the suits.
	# 2. For each distribution, sum up the shanten numbers from each suit.
	# 3. The minimum sum across all distributions is the final shanten number.
	#
	# This tabulation-combination approach can also be extended to different yakus (e.g. Honitsu, Sanshoku, Sanankou, etc.) by starting from different base cases and adjusting the combination step accordingly.

	"""
	Shanten Calculator using BFS/Flood-fill Algorithm
	Optimized version: Only computes states with <= 14 tiles total
	"""

	import time
	from collections import deque


	def precompute_suit_tables():
	"""
	Precompute f_{m,p}(n1,...,n9) for suited tiles (man/pin/sou)
	Only compute states where sum(tiles) <= 14
	Returns: dict[(m, p)] -> dict[state_tuple] -> min_tiles_needed
	"""
	print("Precomputing suited tile tables (max 14 tiles)...")
	start = time.time()

	tables = {}
	for m in range(5): # 0 to 4 melds
	for p in range(2): # 0 or 1 pair
	tables[(m, p)] = {}

	# Phase 1: Find all states with f=0 (perfect formations)
	print(" Phase 1: Finding perfect formations...")
	initial_state = (0,) * 9
	tables[(0, 0)][initial_state] = 0

	queue = deque([(0, 0, initial_state)])
	visited_phase1 = set([(0, 0, initial_state)])

	while queue:
	m, p, state = queue.popleft()

	# Try adding melds (if we haven't reached 4 melds yet)
	if m < 4:
	# Try adding triplets at each position
	for i in range(9):
	new_state = list(state)
	new_state[i] += 3
	# Check: total tiles <= 14 and each tile type <= 4
	if sum(new_state) <= 14 and new_state[i] <= 4:
	new_state = tuple(new_state)
	key = (m + 1, p, new_state)
	if key not in visited_phase1:
	visited_phase1.add(key)
	tables[(m + 1, p)][new_state] = 0
	queue.append((m + 1, p, new_state))

	# Try adding sequences (positions 0-6 can start a sequence)
	for i in range(7):
	new_state = list(state)
	new_state[i] += 1
	new_state[i + 1] += 1
	new_state[i + 2] += 1
	# Check: total tiles <= 14 and each tile type <= 4
	if sum(new_state) <= 14 and all(
	new_state[j] <= 4 for j in [i, i + 1, i + 2]
	):
	new_state = tuple(new_state)
	key = (m + 1, p, new_state)
	if key not in visited_phase1:
	visited_phase1.add(key)
	tables[(m + 1, p)][new_state] = 0
	queue.append((m + 1, p, new_state))

	# Try adding pairs (if we don't have a pair yet)
	if p < 1:
	for i in range(9):
	new_state = list(state)
	new_state[i] += 2
	# Check: total tiles <= 14 and each tile type <= 4
	if sum(new_state) <= 14 and new_state[i] <= 4:
	new_state = tuple(new_state)
	key = (m, p + 1, new_state)
	if key not in visited_phase1:
	visited_phase1.add(key)
	tables[(m, p + 1)][new_state] = 0
	queue.append((m, p + 1, new_state))

	phase1_count = sum(len(tables[(m, p)]) for m in range(5) for p in range(2))
	print(f" Found {phase1_count} perfect states")

	# Phase 2: Flood-fill from all f=0 states
	print(" Phase 2: Flood-filling all states...")
	for m in range(5):
	for p in range(2):
	# Use BFS with cost levels
	# Start with all f=0 states
	current_level = deque()
	for state in tables[(m, p)]:
	if tables[(m, p)][state] == 0:
	current_level.append(state)

	cost = 0
	while current_level:
	next_level = deque()

	while current_level:
	state = current_level.popleft()

	# Try adding a tile (cost stays the same)
	for i in range(9):
	new_state = list(state)
	new_state[i] += 1
	# Check: total tiles <= 14 and each tile type <= 4
	if sum(new_state) <= 14 and new_state[i] <= 4:
	new_state = tuple(new_state)
	if new_state not in tables[(m, p)]:
	tables[(m, p)][new_state] = cost
	current_level.append(new_state)

	# Try removing a tile (cost increases by 1)
	for i in range(9):
	if state[i] > 0:
	new_state = list(state)
	new_state[i] -= 1
	new_state = tuple(new_state)
	# No need to check sum <= 14 since we're removing
	if new_state not in tables[(m, p)]:
	tables[(m, p)][new_state] = cost + 1
	next_level.append(new_state)

	current_level = next_level
	cost += 1
	if cost > 14: # Safety limit
	break

	elapsed = time.time() - start
	total_states = sum(len(tables[(m, p)]) for m in range(5) for p in range(2))
	print(f" Suited tables precomputed in {elapsed:.2f}s")
	print(f" Total states: {total_states:,} (down from ~19.5M)")
	return tables


	def precompute_honor_tables():
	"""
	Precompute f^z_{m,p}(n1,...,n7) for honor tiles
	Only compute states where sum(tiles) <= 14
	(Only triplets and pairs, no sequences)
	"""
	print("Precomputing honor tile tables (max 14 tiles)...")
	start = time.time()

	tables = {}
	for m in range(5):
	for p in range(2):
	tables[(m, p)] = {}

	# Phase 1: Perfect formations
	initial_state = (0,) * 7
	tables[(0, 0)][initial_state] = 0

	queue = deque([(0, 0, initial_state)])
	visited_phase1 = set([(0, 0, initial_state)])

	while queue:
	m, p, state = queue.popleft()

	# Try adding triplets
	if m < 4:
	for i in range(7):
	new_state = list(state)
	new_state[i] += 3
	# Check: total tiles <= 14 and each tile type <= 4
	if sum(new_state) <= 14 and new_state[i] <= 4:
	new_state = tuple(new_state)
	key = (m + 1, p, new_state)
	if key not in visited_phase1:
	visited_phase1.add(key)
	tables[(m + 1, p)][new_state] = 0
	queue.append((m + 1, p, new_state))

	# Try adding pairs
	if p < 1:
	for i in range(7):
	new_state = list(state)
	new_state[i] += 2
	# Check: total tiles <= 14 and each tile type <= 4
	if sum(new_state) <= 14 and new_state[i] <= 4:
	new_state = tuple(new_state)
	key = (m, p + 1, new_state)
	if key not in visited_phase1:
	visited_phase1.add(key)
	tables[(m, p + 1)][new_state] = 0
	queue.append((m, p + 1, new_state))

	# Phase 2: Flood-fill
	for m in range(5):
	for p in range(2):
	current_level = deque()
	for state in tables[(m, p)]:
	if tables[(m, p)][state] == 0:
	current_level.append(state)

	cost = 0
	while current_level:
	next_level = deque()

	while current_level:
	state = current_level.popleft()

	# Add a tile
	for i in range(7):
	new_state = list(state)
	new_state[i] += 1
	# Check: total tiles <= 14 and each tile type <= 4
	if sum(new_state) <= 14 and new_state[i] <= 4:
	new_state = tuple(new_state)
	if new_state not in tables[(m, p)]:
	tables[(m, p)][new_state] = cost
	current_level.append(new_state)

	# Remove a tile
	for i in range(7):
	if state[i] > 0:
	new_state = list(state)
	new_state[i] -= 1
	new_state = tuple(new_state)
	if new_state not in tables[(m, p)]:
	tables[(m, p)][new_state] = cost + 1
	next_level.append(new_state)

	current_level = next_level
	cost += 1
	if cost > 14:
	break

	elapsed = time.time() - start
	total_states = sum(len(tables[(m, p)]) for m in range(5) for p in range(2))
	print(f" Honor tables precomputed in {elapsed:.2f}s")
	print(f" Total states: {total_states:,}")
	return tables


	def calculate_shanten(hand_str, suit_tables, honor_tables):
	"""
	Calculate shanten number for a given hand.
	hand_str format: "123456m1378s2256p" or with honors like "123m456p11z"
	"""
	# Parse hand into tile counts
	tiles = [0] * 34
	current_suit = []

	for char in hand_str:
	if char.isdigit():
	current_suit.append(int(char))
	elif char in "mpsz":
	suit_offset = {"m": 0, "p": 9, "s": 18, "z": 27}[char]
	for num in current_suit:
	tiles[suit_offset + num - 1] += 1
	current_suit = []

	# Split into suits
	man_state = tuple(tiles[0:9])
	pin_state = tuple(tiles[9:18])
	sou_state = tuple(tiles[18:27])
	honor_state = tuple(tiles[27:34])

	# Try all distributions of melds and pairs
	min_cost = float("inf")

	# m1 + m2 + m3 + m4 = 4 (total 4 melds)
	# p1 + p2 + p3 + p4 = 1 (total 1 pair)
	for m1 in range(5):
	for m2 in range(5):
	for m3 in range(5):
	for m4 in range(5):
	if m1 + m2 + m3 + m4 != 4:
	continue

	for p1 in range(2):
	for p2 in range(2):
	for p3 in range(2):
	for p4 in range(2):
	if p1 + p2 + p3 + p4 != 1:
	continue

	# Look up costs
	cost1 = suit_tables[(m1, p1)].get(
	man_state, float("inf")
	)
	cost2 = suit_tables[(m2, p2)].get(
	pin_state, float("inf")
	)
	cost3 = suit_tables[(m3, p3)].get(
	sou_state, float("inf")
	)
	cost4 = honor_tables[(m4, p4)].get(
	honor_state, float("inf")
	)

	total_cost = cost1 + cost2 + cost3 + cost4
	min_cost = min(min_cost, total_cost)

	# Shanten = tiles_needed - 1
	shanten = min_cost - 1
	return max(-1, shanten)


	# Main execution
	if __name__ == "__main__":
	print("=" * 70)
	print("SHANTEN CALCULATOR - BFS with 14-tile Optimization")
	print("=" * 70)
	print()

	# Precompute tables
	suit_tables = precompute_suit_tables()
	honor_tables = precompute_honor_tables()

	print("\n" + "=" * 70)
	print("Testing shanten calculation")
	print("=" * 70)

	# Test cases
	test_hands = [
	"123456m1378s2256p", # The original 14-tile hand
	"123456m137s2256p", # 13-tile version
	"123m456p789s1122z", # Different hand
	"11122233344455m", # Many pairs
	"147m258p369s1234z", # Scattered
	"19m19p19s1234567z", # Kokushi attempt
	"1112345678999m", # 13 tiles, all man
	"2258m408p134s4577z",
	"79m189p34455s1456z",
	"14m244p46s1122346z",
	"238m3446788p23s13z",
	"22679m259p1255s35z",
	"12244455677889p",
	"11122344677899p",
	"11222346688999p",
	"11222234556899p",
	]

	for hand in test_hands:
	# Count tiles
	tile_count = sum(1 for char in hand if char.isdigit())
	shanten = calculate_shanten(hand, suit_tables, honor_tables)
	print(f"\nHand: {hand}")
	print(f" Tiles: {tile_count}")
	print(f" Shanten: {shanten}")
	if shanten == -1:
	print(" Status: WINNING HAND!")
	elif shanten == 0:
	print(" Status: TENPAI (ready)")
	else:
	print(f" Status: {shanten} away from tenpai")

	print("\n" + "=" * 70)
	print("Optimization Impact:")
	print(" Previous version: ~19.5M suited states")
	print(
	f" This version: {sum(len(suit_tables[(m, p)]) for m in range(5) for p in range(2)):,} suited states"
	)
	print(
	f" Reduction: ~{100 * (1 - sum(len(suit_tables[(m, p)]) for m in range(5) for p in range(2)) / 19_531_250):.1f}%"
	)
	print("=" * 70)
No results found