# from math import abs
from collections import defaultdict

max_num = 16
initial_nums = list(range(1, max_num + 1))
initial_nums.remove(10)

# end number -> list of steps to get here which are
#     (prev_number, operation description)

target = 7387

upper_bound = target * max_num
ops = []
for n in initial_nums:
    ops.append((lambda x, n=n: x + n, f"+{n}"))
    ops.append((lambda x, n=n: abs(x - n), f"-{n}"))
    ops.append((lambda x, n=n: x * n, f"*{n}"))
    ops.append((lambda x, n=n: x // n if x and x % n == 0 else x, f"/{n}"))
    ops.append((lambda x, n=n: x**n if x**2 < upper_bound else x, f"**{n}"))


seen = {n: [] for n in initial_nums}
recent = seen.keys()

while target not in seen:
    news = defaultdict(list)
    for n in recent:
        for op, description in ops:
            new = op(n)
            if new > upper_bound:
                continue
            if new in seen:
                continue
            news[new].append((n, description))
    seen.update(news)
    recent = sorted(news.keys())
    if not news:
        assert False

    print(f"progress: {len(seen)=}")


pickers = [
    lambda l: l[0],
    lambda l: l[len(l) // 2],
    lambda l: l[-1],
]
for picker in pickers:
    steps = [target]
    picks = []
    while prevs := seen[steps[-1]]:
        pick = picker(prevs)
        picks.append(pick)
        steps.append(pick[0])

    print(f"{steps[-1]:>3}", end=" ")
    for pick in reversed(picks):
        print(f"{pick[1]:>4}", end=" ")
    print(f" = {target}")