# 全探索: 全ての可能性を愚直に試す
# 長所: 確実に正解が得られる、実装が簡単
# 短所: 計算量が大きい
 
# 例1: パスワードの総当たり（4桁数字）
def brute_force_pin():
    """4桁のPINコードを全て試す"""
    for pin in range(10000):  # 0000-9999
        if try_pin(f"{pin:04d}"):
            return f"{pin:04d}"
    return None
# 計算量: O(10^4) = O(10000)
 
# 例2: 部分和問題
def subset_sum(nums, target):
    """numsの部分集合で合計がtargetになるものがあるか"""
    n = len(nums)
    # ビットマスクで全部分集合を列挙
    for mask in range(1 << n):  # 2^n 通り
        total = 0
        for i in range(n):
            if mask & (1 << i):
                total += nums[i]
        if total == target:
            return True
    return False
# 計算量: O(n × 2^n)
 
# 例3: 文字列のアナグラム判定（素朴な方法）
def is_anagram_brute(s1, s2):
    """s1とs2がアナグラムかを全順列で確認"""
    from itertools import permutations
    if len(s1) != len(s2):
        return False
    for perm in permutations(s1):
        if ''.join(perm) == s2:
            return True
    return False
# 計算量: O(n! × n) — 非常に非効率！
 
# 改善版: ソートで比較
def is_anagram_sort(s1, s2):
    return sorted(s1) == sorted(s2)
# 計算量: O(n log n) — 大幅に改善
 
# さらに改善: ハッシュマップで比較
from collections import Counter
def is_anagram_hash(s1, s2):
    return Counter(s1) == Counter(s2)
# 計算量: O(n) — 最適
 
# → 全探索は出発点。ここから効率の良い方法を考える。

# 分割統治法: 問題を小さく分割→各個解決→結合
# 3つのステップ: Divide → Conquer → Combine
 
# 代表例1: マージソート
def merge_sort(arr):
    """分割→ソート→結合"""
    if len(arr) <= 1:
        return arr
 
    # Divide: 半分に分割
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])    # Conquer
    right = merge_sort(arr[mid:])   # Conquer
 
    # Combine: マージ
    return merge(left, right)
 
def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result
# T(n) = 2T(n/2) + O(n) → O(n log n)
 
# 代表例2: 最近点対問題
def closest_pair(points):
    """2次元平面上のn個の点から最も近い2点を見つける
 
    全探索: O(n²) — 全ペアを調べる
    分割統治: O(n log n)
 
    1. x座標でソート
    2. 中央で左右に分割
    3. 左右それぞれで最近点対を再帰的に求める
    4. 左右にまたがるペアも確認（ストリップ領域）
    5. 最小を返す
    """
    # 詳細な実装は省略（概念の説明が目的）
    pass
 
# 代表例3: カラツバ法（高速乗算）
def karatsuba(x, y):
    """通常のO(n²)をO(n^1.585)に改善する乗算"""
    if x < 10 or y < 10:
        return x * y
 
    n = max(len(str(x)), len(str(y)))
    m = n // 2
 
    # x = a * 10^m + b
    # y = c * 10^m + d
    a, b = divmod(x, 10**m)
    c, d = divmod(y, 10**m)
 
    # 3回の再帰（通常は4回）
    ac = karatsuba(a, c)
    bd = karatsuba(b, d)
    ad_bc = karatsuba(a + b, c + d) - ac - bd
 
    return ac * 10**(2*m) + ad_bc * 10**m + bd
# T(n) = 3T(n/2) + O(n) → O(n^log₂3) ≈ O(n^1.585)
# → 4回の乗算を3回に減らしたのがポイント
 
# 分割統治が有効な条件:
# 1. 問題を同じ種類の小さい問題に分割できる
# 2. 小さい問題を独立に解ける
# 3. 部分解を効率的に結合できる
# 4. 基底ケースが自明に解ける

# 動的計画法: 部分問題の解を記憶して再利用
# 2つの条件:
# 1. 最適部分構造: 最適解が部分問題の最適解から構成される
# 2. 重複部分問題: 同じ部分問題が繰り返し現れる
 
# 典型例: フィボナッチ数列
 
# ❌ 素朴な再帰: O(2^n) — 同じ計算を何度も繰り返す
def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n-1) + fib_naive(n-2)
 
# 再帰ツリー（n=5の場合）:
#                fib(5)
#              /        \
#           fib(4)      fib(3)
#          /    \       /    \
#       fib(3) fib(2) fib(2) fib(1)
#       /  \
#    fib(2) fib(1)
# → fib(2)が3回、fib(3)が2回計算される！
 
# ✅ メモ化（トップダウンDP）: O(n)
def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]
 
# ✅ テーブル（ボトムアップDP）: O(n)
def fib_table(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]
 
# ✅ 空間最適化: O(n) 時間, O(1) 空間
def fib_optimal(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b
 
# DPの実用例: ナップサック問題
def knapsack(weights, values, capacity):
    """重さ制限内で価値を最大化する"""
    n = len(weights)
    # dp[i][w] = 最初のi個のアイテムで重さw以内の最大価値
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
 
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            # アイテムiを入れない場合
            dp[i][w] = dp[i-1][w]
            # アイテムiを入れる場合
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i][w],
                    dp[i-1][w - weights[i-1]] + values[i-1])
 
    return dp[n][capacity]
# 計算量: O(n × capacity)

# 貪欲法: 各ステップで「その時点での最善」を選ぶ
# 長所: 高速、実装が簡単
# 短所: 必ずしも最適解が得られない
 
# 貪欲法で最適解が得られる例:
 
# 1. 活動選択問題
def activity_selection(activities):
    """重ならない最大数の活動を選択
    activities = [(start, end), ...]
    """
    # 終了時刻でソート（貪欲の選択基準）
    sorted_activities = sorted(activities, key=lambda x: x[1])
 
    selected = [sorted_activities[0]]
    for activity in sorted_activities[1:]:
        if activity[0] >= selected[-1][1]:  # 重なっていない
            selected.append(activity)
 
    return selected
# 計算量: O(n log n) (ソート) + O(n) = O(n log n)
# → 貪欲法で最適解が得られることが証明されている
 
# 2. ハフマン符号化
import heapq
def huffman_encoding(freq):
    """文字の出現頻度から最適な可変長符号を生成
 
    例: {'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45}
    """
    # 最小ヒープを構築
    heap = [(f, c) for c, f in freq.items()]
    heapq.heapify(heap)
 
    while len(heap) > 1:
        # 最小の2つを取り出して結合（貪欲な選択）
        freq1, node1 = heapq.heappop(heap)
        freq2, node2 = heapq.heappop(heap)
        heapq.heappush(heap, (freq1 + freq2, (node1, node2)))
 
    return heap[0]
# → 最適な接頭符号が得られる（情報理論で証明済み）
 
# 貪欲法で最適解が得られない例:
 
# お釣り問題（特殊な硬貨体系）
# 硬貨: [1, 3, 4]、お釣り: 6
# 貪欲法: 4 + 1 + 1 = 3枚
# 最適解: 3 + 3 = 2枚！
# → この場合はDPが必要
 
# 貪欲法が使える条件:
# 1. 貪欲選択性質: 局所最適な選択が大局最適につながる
# 2. 最適部分構造: 残りの部分問題も同じ方法で解ける
# → この2つを証明する必要がある

# バックトラッキング: 探索 + 行き詰まったら戻る
# 「系統的な試行錯誤」
 
# 典型例1: N-Queens問題
def solve_n_queens(n):
    """N×Nチェスボードにn個のクイーンを互いに攻撃し合わないように配置"""
    solutions = []
    board = [-1] * n  # board[row] = col
 
    def is_safe(row, col):
        for prev_row in range(row):
            prev_col = board[prev_row]
            # 同じ列または対角線上にないか確認
            if prev_col == col or \
               abs(prev_col - col) == abs(prev_row - row):
                return False
        return True
 
    def backtrack(row):
        if row == n:
            solutions.append(board[:])
            return
 
        for col in range(n):
            if is_safe(row, col):
                board[row] = col        # 選択
                backtrack(row + 1)      # 探索
                board[row] = -1         # 元に戻す（バックトラック）
 
    backtrack(0)
    return solutions
 
# 8-Queens: 解は92通り（回転・反転を区別する場合）
# 計算量: 最悪 O(n!)、枝刈りで大幅に削減
 
# 典型例2: 数独ソルバー
def solve_sudoku(board):
    """9×9の数独を解く"""
    def find_empty():
        for i in range(9):
            for j in range(9):
                if board[i][j] == 0:
                    return (i, j)
        return None
 
    def is_valid(num, pos):
        row, col = pos
        # 行チェック
        if num in board[row]:
            return False
        # 列チェック
        if num in [board[i][col] for i in range(9)]:
            return False
        # 3×3ボックスチェック
        box_row, box_col = 3 * (row // 3), 3 * (col // 3)
        for i in range(box_row, box_row + 3):
            for j in range(box_col, box_col + 3):
                if board[i][j] == num:
                    return False
        return True
 
    empty = find_empty()
    if not empty:
        return True  # 全マス埋まった → 完成
 
    row, col = empty
    for num in range(1, 10):
        if is_valid(num, (row, col)):
            board[row][col] = num       # 選択
            if solve_sudoku(board):     # 探索
                return True
            board[row][col] = 0         # バックトラック
 
    return False  # この状態からは解なし

# 問題: 配列の中で最大の値を見つける
# 入力: 整数の配列 (空でない)
# 出力: 最大の値
 
# 方法1: 全探索（ブルートフォース）
def find_max_brute(arr):
    """全ての要素を1つずつ確認"""
    max_val = arr[0]
    for i in range(1, len(arr)):
        if arr[i] > max_val:
            max_val = arr[i]
    return max_val
# 計算量: O(n) — これ以上改善できない（全要素を見る必要がある）
 
# 方法2: 分割統治
def find_max_divide(arr, left, right):
    """配列を半分に分割して各最大値を比較"""
    if left == right:
        return arr[left]
    mid = (left + right) // 2
    left_max = find_max_divide(arr, left, mid)
    right_max = find_max_divide(arr, mid + 1, right)
    return max(left_max, right_max)
# 計算量: O(n) — 同じだが、並列化に適している
 
# 方法3: Python組み込み
max_val = max(arr)  # 内部的に方法1と同じ O(n)
 
# この問題ではO(n)が最適（下界）
# → 全ての要素を少なくとも1回は見なければ最大値は分からない
# → これを「情報理論的下界」と呼ぶ

# 問題: 配列から合計が target になる2つの要素のインデックスを返す
# 入力: nums = [2, 7, 11, 15], target = 9
# 出力: [0, 1] (nums[0] + nums[1] = 2 + 7 = 9)
 
# 方法1: 全探索 O(n²)
def two_sum_brute(nums, target):
    """全てのペアを試す"""
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []
 
# 方法2: ハッシュマップ O(n)
def two_sum_hash(nums, target):
    """見た値を記録して補数を探す"""
    seen = {}  # 値 → インデックス
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []
 
# 方法3: ソート + 二分探索 O(n log n)
def two_sum_sort(nums, target):
    """ソートして両端から探す"""
    indexed = sorted(enumerate(nums), key=lambda x: x[1])
    left, right = 0, len(indexed) - 1
    while left < right:
        total = indexed[left][1] + indexed[right][1]
        if total == target:
            return [indexed[left][0], indexed[right][0]]
        elif total < target:
            left += 1
        else:
            right -= 1
    return []
 
# 比較:
# ┌─────────────┬───────────┬───────────┬────────────────┐
# │ 方法        │ 時間      │ 空間      │ 備考            │
# ├─────────────┼───────────┼───────────┼────────────────┤
# │ 全探索      │ O(n²)    │ O(1)     │ 最も単純        │
# │ ハッシュ    │ O(n)     │ O(n)     │ 最速、空間と引替│
# │ ソート+二分 │ O(n log n)│ O(n)     │ 中間的な選択    │
# └─────────────┴───────────┴───────────┴────────────────┘
 
# → 要件に応じて最適な方法を選択する
# - 速度重視 → ハッシュマップ
# - メモリ制約 → 全探索（インデックス不要なら方法3）
# - 複数回の検索 → ソート（前処理の後、各検索はO(log n)）

# ループ不変条件（Loop Invariant）:
# ループの各反復の前に成り立つ性質
 
def insertion_sort(arr):
    """挿入ソート"""
    for i in range(1, len(arr)):
        # ループ不変条件: arr[0:i] はソート済み
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
        # ループ不変条件: arr[0:i+1] はソート済み
    # 終了時: i = len(arr) なので arr[0:len(arr)] がソート済み ✓
 
# ループ不変条件の3つの性質:
# 1. 初期化: ループ開始前に成り立つ（arr[0:1]は自明にソート済み）
# 2. 維持:   反復のたびに維持される（各ステップでソート範囲が拡大）
# 3. 終了:   ループ終了時に目的の性質が成り立つ（全体がソート済み）

# もう一つの例: 線形探索の正しさの証明
 
def linear_search(arr, target):
    """線形探索"""
    for i in range(len(arr)):
        # ループ不変条件: arr[0:i] に target は存在しない
        if arr[i] == target:
            return i
    # 終了時: arr[0:len(arr)] に target は存在しない
    return -1
 
# 証明:
# 初期化: i=0 の時、arr[0:0]（空集合）に target はない → 自明に成立 ✓
# 維持: 反復 i で arr[i] != target なら、arr[0:i+1] にも target はない
#        → 不変条件が i+1 でも成立 ✓
# 終了: i = len(arr) なら arr 全体に target がないことが証明済み
#        return -1 は正しい ✓
#        途中で arr[i] == target を見つけたら return i も正しい ✓

# 数学的帰納法によるアルゴリズムの正しさの証明
 
def factorial(n):
    """n! を再帰的に計算"""
    if n <= 1:    # 基底ケース
        return 1
    return n * factorial(n - 1)  # 再帰ケース
 
# 証明:
# 基底ケース: n=0, n=1 の時、1を返す → 0!=1, 1!=1 ✓
# 帰納ステップ:
#   factorial(k) = k! が正しいと仮定する（帰納法の仮定）
#   factorial(k+1) = (k+1) * factorial(k) = (k+1) * k! = (k+1)! ✓
# よって全ての n≥0 に対して factorial(n) = n! ✓

# より複雑な例: マージソートの正しさの証明
 
def merge_sort(arr):
    if len(arr) <= 1:
        return arr  # 基底ケース
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)
 
# 証明（強帰納法）:
#
# 命題: 長さnの任意の配列に対して、merge_sort(arr)は
#        arrと同じ要素を持つソート済み配列を返す
#
# 基底ケース: n=0 または n=1
#   → 配列はそのまま返される → 自明にソート済み ✓
#
# 帰納ステップ: n>1 として、n未満の全ての入力で正しいと仮定
#   1. arr[:mid] の長さは n/2 < n → 帰納法の仮定より left はソート済み
#   2. arr[mid:] の長さは n-n/2 < n → 帰納法の仮定より right はソート済み
#   3. merge(left, right):
#      - left, right は共にソート済み
#      - merge は各ステップで小さい方を選ぶ
#      - → 結果はソート済み ✓
#      - 要素は追加も削除もされない
#      - → 元の要素が全て含まれる ✓
#
# よって全ての n≥0 に対して merge_sort は正しい ✓

# 背理法: 仮に正しくないと仮定して矛盾を導く
 
# 例: ダイクストラ法の正しさ（概略）
#
# 命題: ダイクストラ法は非負重みグラフの最短経路を正しく求める
#
# 証明（概略）:
# 背理法として、ダイクストラ法が最初に間違った最短距離を
# 確定するノード v が存在すると仮定する
#
# d[v] = ダイクストラが求めた距離
# δ(v) = 真の最短距離
# 仮定より d[v] > δ(v)
#
# 真の最短経路 s → ... → u → v を考える
# u は v の直前のノード
#
# u は v より先に処理されているので d[u] = δ(u)（v が「最初の」間違い）
# d[v] ≤ d[u] + w(u,v)  （ダイクストラの緩和操作より）
#      = δ(u) + w(u,v)   （d[u] = δ(u) より）
#      = δ(v)            （u→v は最短経路の一部より）
#
# よって d[v] ≤ δ(v) だが、d[v] ≥ δ(v) は自明
# → d[v] = δ(v) で矛盾！
#
# よってダイクストラ法は正しい ✓

# 擬似コードをPython、Java、Go、TypeScriptに変換する例
 
# 擬似コード:
# function GCD(a, b)
#   while b ≠ 0 do
#     temp ← b
#     b ← a mod b
#     a ← temp
#   return a
 
# Python:
def gcd(a: int, b: int) -> int:
    while b != 0:
        a, b = b, a % b
    return a

// Java:
public static int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// Go:
func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a%b
    }
    return a
}

// TypeScript:
function gcd(a: number, b: number): number {
    while (b !== 0) {
        [a, b] = [b, a % b];
    }
    return a;
}

# デバッグ用ユーティリティ
import logging
import traceback
from functools import wraps
 
# ロガーの設定
logging.basicConfig(
    level=logging.DEBUG,
    format='%(asctime)s [%(levelname)s] %(name)s: %(message)s'
)
logger = logging.getLogger(__name__)
 
def debug_decorator(func):
    """関数の入出力をログ出力するデコレータ"""
    @wraps(func)
    def wrapper(*args, **kwargs):
        logger.debug(f"呼び出し: {func.__name__}(args={args}, kwargs={kwargs})")
        try:
            result = func(*args, **kwargs)
            logger.debug(f"戻り値: {func.__name__} -> {result}")
            return result
        except Exception as e:
            logger.error(f"例外発生: {func.__name__}: {e}")
            logger.error(traceback.format_exc())
            raise
    return wrapper
 
@debug_decorator
def process_data(items):
    """データ処理（デバッグ対象）"""
    if not items:
        raise ValueError("空のデータ")
    return [item * 2 for item in items]

# 設計判断の記録テンプレート
class ArchitectureDecisionRecord:
    """ADR (Architecture Decision Record) の作成"""
 
    def __init__(self, title: str):
        self.title = title
        self.context = ""
        self.decision = ""
        self.consequences = []
        self.alternatives = []
 
    def set_context(self, context: str):
        """背景と課題の記述"""
        self.context = context
        return self
 
    def set_decision(self, decision: str):
        """決定内容の記述"""
        self.decision = decision
        return self
 
    def add_consequence(self, consequence: str, positive: bool = True):
        """結果の追加"""
        self.consequences.append({
            'description': consequence,
            'type': 'positive' if positive else 'negative'
        })
        return self
 
    def add_alternative(self, name: str, reason_rejected: str):
        """却下した代替案の追加"""
        self.alternatives.append({
            'name': name,
            'reason_rejected': reason_rejected
        })
        return self
 
    def to_markdown(self) -> str:
        """Markdown形式で出力"""
        md = f"# ADR: {self.title}\n\n"
        md += f"## 背景\n{self.context}\n\n"
        md += f"## 決定\n{self.decision}\n\n"
        md += "## 結果\n"
        for c in self.consequences:
            icon = "✅" if c['type'] == 'positive' else "⚠️"
            md += f"- {icon} {c['description']}\n"
        md += "\n## 却下した代替案\n"
        for a in self.alternatives:
            md += f"- **{a['name']}**: {a['reason_rejected']}\n"
        return md

# チーム間のAPI契約定義
from dataclasses import dataclass
from typing import List, Optional
from enum import Enum
 
class Priority(Enum):
    LOW = "low"
    MEDIUM = "medium"
    HIGH = "high"
    CRITICAL = "critical"
 
@dataclass
class APIContract:
    """チーム間のAPI契約"""
    endpoint: str
    method: str
    owner_team: str
    consumers: List[str]
    sla_ms: int  # レスポンスタイムSLA
    priority: Priority
 
    def validate_sla(self, actual_ms: int) -> bool:
        """SLA準拠の確認"""
        return actual_ms <= self.sla_ms
 
    def to_openapi(self) -> dict:
        """OpenAPI形式で出力"""
        return {
            'path': self.endpoint,
            'method': self.method,
            'x-owner': self.owner_team,
            'x-consumers': self.consumers,
            'x-sla-ms': self.sla_ms
        }
 
# 使用例
contracts = [
    APIContract(
        endpoint="/api/v1/users",
        method="GET",
        owner_team="user-team",
        consumers=["order-team", "notification-team"],
        sla_ms=200,
        priority=Priority.HIGH
    ),
    APIContract(
        endpoint="/api/v1/orders",
        method="POST",
        owner_team="order-team",
        consumers=["payment-team", "inventory-team"],
        sla_ms=500,
        priority=Priority.CRITICAL
    )
]

# セキュアコーディング例
import hashlib
import secrets
import hmac
from typing import Optional
 
class SecurityUtils:
    """セキュリティユーティリティ"""
 
    @staticmethod
    def generate_token(length: int = 32) -> str:
        """暗号学的に安全なトークン生成"""
        return secrets.token_urlsafe(length)
 
    @staticmethod
    def hash_password(password: str, salt: Optional[str] = None) -> tuple:
        """パスワードのハッシュ化"""
        if salt is None:
            salt = secrets.token_hex(16)
        hashed = hashlib.pbkdf2_hmac(
            'sha256',
            password.encode('utf-8'),
            salt.encode('utf-8'),
            iterations=100000
        )
        return hashed.hex(), salt
 
    @staticmethod
    def verify_password(password: str, hashed: str, salt: str) -> bool:
        """パスワードの検証"""
        new_hash, _ = SecurityUtils.hash_password(password, salt)
        return hmac.compare_digest(new_hash, hashed)
 
    @staticmethod
    def sanitize_input(value: str) -> str:
        """入力値のサニタイズ"""
        dangerous_chars = ['<', '>', '"', "'", '&', '\\']
        result = value
        for char in dangerous_chars:
            result = result.replace(char, '')
        return result.strip()
 
# 使用例
token = SecurityUtils.generate_token()
hashed, salt = SecurityUtils.hash_password("my_password")
is_valid = SecurityUtils.verify_password("my_password", hashed, salt)

# マイグレーションスクリプトのテンプレート
import json
import logging
from pathlib import Path
from datetime import datetime
from typing import List, Dict, Callable
 
logger = logging.getLogger(__name__)
 
class MigrationRunner:
    """段階的マイグレーション実行エンジン"""
 
    def __init__(self, migration_dir: str):
        self.migration_dir = Path(migration_dir)
        self.migrations: List[Dict] = []
        self.completed: List[str] = []
 
    def register(self, version: str, description: str,
                 up: Callable, down: Callable):
        """マイグレーションの登録"""
        self.migrations.append({
            'version': version,
            'description': description,
            'up': up,
            'down': down,
            'registered_at': datetime.now().isoformat()
        })
 
    def run_up(self, target_version: str = None):
        """マイグレーションの実行（アップグレード）"""
        for migration in self.migrations:
            if migration['version'] in self.completed:
                continue
            logger.info(f"実行中: {migration['version']} - "
                       f"{migration['description']}")
            try:
                migration['up']()
                self.completed.append(migration['version'])
                logger.info(f"完了: {migration['version']}")
            except Exception as e:
                logger.error(f"失敗: {migration['version']}: {e}")
                raise
            if target_version and migration['version'] == target_version:
                break
 
    def run_down(self, target_version: str):
        """マイグレーションのロールバック"""
        for migration in reversed(self.migrations):
            if migration['version'] not in self.completed:
                continue
            if migration['version'] == target_version:
                break
            logger.info(f"ロールバック: {migration['version']}")
            migration['down']()
            self.completed.remove(migration['version'])
 
    def status(self) -> Dict:
        """マイグレーション状態の確認"""
        return {
            'total': len(self.migrations),
            'completed': len(self.completed),
            'pending': len(self.migrations) - len(self.completed),
            'versions': {
                m['version']: 'completed'
                if m['version'] in self.completed else 'pending'
                for m in self.migrations
            }
        }