import itertools
import math

# ==========================================
# 1. 遊戲參數與寶石計算引擎
# ==========================================
BASE_DMG = 50
BASE_DELAY = 1.0
TIME_LIMIT = 60.0
NUM_FLOORS = 81

def calculate_weapon_stats(combo_string):
    """
    根據寶石順序，計算最終的神劍屬性
    combo_string: 類似 'RRES', 'EEES' 的 4 字元字串
    """
    dmg = BASE_DMG
    delay = BASE_DELAY
    
    for gem in combo_string:
        if gem == 'R':
            dmg += 200
        elif gem == 'E':
            dmg *= 1.8
            delay += 0.2
        elif gem == 'S':
            delay *= 0.6
            dmg -= 50
            if dmg < 10: 
                dmg = 10
                
    # 避免極端情況浮點數誤差，攻速最低限制為 0.01 秒
    delay = max(0.01, delay) 
    return dmg, delay

def can_beat_boss(dmg, delay, floor_k):
    """判斷特定的武器屬性是否能在 60 秒內擊殺第 K 層的 Boss"""
    boss_hp = 5000 + (1000 * floor_k)
    boss_armor = 10 * floor_k
    
    hits = math.floor(TIME_LIMIT / delay) + 1
    actual_dmg_per_hit = max(1, dmg - boss_armor)
    
    total_damage = hits * actual_dmg_per_hit
    return total_damage >= boss_hp

# ==========================================
# 2. 模擬與建圖 (Graph Construction)
# ==========================================
def build_bipartite_graph():
    # 產生 3^4 = 81 種寶石鑲嵌組合
    gems = ['R', 'E', 'S']
    all_combos = [''.join(c) for c in itertools.product(gems, repeat=4)]
    
    print(f"✅ 成功生成 {len(all_combos)} 種獨特的寶石配裝方案。")
    
    # 建立二分圖的 Adjacency List
    # graph[combo] = [能擊殺的樓層 list]
    graph = {}
    for combo in all_combos:
        dmg, delay = calculate_weapon_stats(combo)
        beatable_floors = []
        for floor in range(1, NUM_FLOORS + 1):
            if can_beat_boss(dmg, delay, floor):
                beatable_floors.append(floor)
        graph[combo] = beatable_floors
        
    return graph, all_combos

# ==========================================
# 3. 核心演算法：最大二分圖匹配 (Kuhn's Algorithm)
# ==========================================
def max_bipartite_matching(graph, combos):
    """
    使用 DFS 尋找增廣路徑 (Augmenting Path)
    來解出最多能通關多少層樓。
    """
    # 紀錄某個樓層目前是被哪個 combo 佔用
    floor_assignment = {} 
    
    def dfs_match(combo, visited):
        # 遍歷這個配裝能打贏的所有樓層
        for floor in graph[combo]:
            if floor not in visited:
                visited.add(floor)
                # 如果該樓層還沒有分配配裝，或者佔用該樓層的配裝可以被挪去打別層(遞迴尋找增廣路)
                if floor not in floor_assignment or dfs_match(floor_assignment[floor], visited):
                    floor_assignment[floor] = combo
                    return True
        return False

    matches = 0
    # 對每一種配裝嘗試進行匹配
    for combo in combos:
        visited = set()
        if dfs_match(combo, visited):
            matches += 1
            
    return matches, floor_assignment

# ==========================================
# 4. 執行主程式
# ==========================================
def main():
    print("⚔️ 啟動 Stick Ranger 無盡之塔 81 層模擬器...\n")
    
    # 1. 建立圖形
    graph, combos = build_bipartite_graph()
    
    # 2. 跑圖論匹配演算法
    max_wins, final_assignments = max_bipartite_matching(graph, combos)
    
    # 3. 輸出結果分析
    print(f"🏆 在 81 層中，不重複使用配裝的情況下，極限能通關: 【 {max_wins} 】層！\n")
    
    print("--- ⚔️ 部分精選通關樓層配裝報告 ⚔️ ---")
    
    # 反轉 dict 以樓層來排序輸出
    floor_to_combo = {k: v for k, v in final_assignments.items()}
    
    # 顯示前 5 樓、中間樓層、以及挑戰成功的最高樓層
    floors_to_show = [1, 2, 3, 4, 5, 40, max(floor_to_combo.keys())]
    
    for floor in sorted(list(set(floors_to_show))):
        if floor in floor_to_combo:
            combo = floor_to_combo[floor]
            dmg, delay = calculate_weapon_stats(combo)
            boss_hp = 5000 + (1000 * floor)
            boss_armor = 10 * floor
            
            print(f"🏢 第 {floor:02d} 層 | Boss [HP:{boss_hp:6d}, 甲:{boss_armor:3d}] "
                  f"| 配裝: {combo} (傷:{dmg:6.1f}, 攻速:{delay:.2f}s)")
            
    # 尋找最強破甲與最高秒傷配裝
    print("\n--- 🔬 神劍資料科學分析 ---")
    best_dmg_combo = max(combos, key=lambda c: calculate_weapon_stats(c)[0])
    fastest_combo = min(combos, key=lambda c: calculate_weapon_stats(c)[1])
    
    print(f"🔥 最高單發傷害配裝: {best_dmg_combo} (傷害: {calculate_weapon_stats(best_dmg_combo)[0]:.1f})")
    print(f"⚡ 最高攻擊速度配裝: {fastest_combo} (間隔: {calculate_weapon_stats(fastest_combo)[1]:.3f}s)")

if __name__ == '__main__':
    main()