"""BTVN: ba cách mô tả lời giải Tháp Hà Nội và hàm đếm.

Python 3, ví dụ:
  python3 g11-cs-thap-ha-noi.py 3
  python3 g11-cs-thap-ha-noi.py 2 --names A C B
  python3 g11-cs-thap-ha-noi.py 64 --count-only
--names: tên cọc nguồn, cọc đích, cọc trung gian (theo thứ tự đó).
Mẫu chỉ liệt kê 1–10 đĩa; chế độ chỉ đếm nhận 1–512 để giữ thử nghiệm nhỏ.
"""
import argparse


def Hanoi(n, i, j, k):
    # n >= 1; i, j, k là ba tên cọc khác nhau.
    if n == 1:
        print(f'Đĩa {n}: {i} -> {j}')
    else:
        Hanoi(n - 1, i, k, j)
        print(f'Đĩa {n}: {i} -> {j}')
        Hanoi(n - 1, k, j, i)


def Hanoi_zero(n, i, j, k):
    # n >= 0; không có đĩa thì không in lần chuyển nào.
    if n > 0:
        Hanoi_zero(n - 1, i, k, j)
        print(f'Đĩa {n}: {i} -> {j}')
        Hanoi_zero(n - 1, k, j, i)


def Hanoi_list(n, i, j, k):
    # n >= 0; mỗi bộ ba là (số đĩa, nguồn, đích).
    if n == 0:
        return []
    first = Hanoi_list(n - 1, i, k, j)
    last = Hanoi_list(n - 1, k, j, i)
    return first + [(n, i, j)] + last


def H(n):
    # n >= 1; chỉ tính số lần chuyển, không tạo danh sách.
    if n == 1:
        return 1
    return 2 * H(n - 1) + 1


def main():
    parser = argparse.ArgumentParser(description=__doc__)
    parser.add_argument('n', type=int)
    parser.add_argument('--names', nargs=3, default=['1', '3', '2'],
                        metavar=('NGUON', 'DICH', 'TRUNG_GIAN'))
    parser.add_argument('--count-only', action='store_true')
    args = parser.parse_args()
    if len(set(args.names)) != 3 or any(not s.strip() for s in args.names):
        parser.error('Ba tên cọc phải khác nhau và không rỗng.')
    limit = 512 if args.count_only else 10
    if not 1 <= args.n <= limit:
        parser.error(f'Mẫu thử này nhận n từ 1 đến {limit}.')
    print(f'H({args.n}) = {H(args.n)}')
    if not args.count_only:
        for d, source, target in Hanoi_list(args.n, *args.names):
            print(f'Đĩa {d}: {source} -> {target}')


if __name__ == '__main__':
    main()