{}
"""
hp50g_solver.py
===============
"""
from itertools import product as iproduct
import heapq
def DUP(s): return [s[0]] + s if len(s) >= 1 else None
def DUPDUP(s): return [s[0], s[0]] + s if len(s) >= 1 else None
def SWAP(s): return [s[1], s[0]] + s[2:] if len(s) >= 2 else None
def DROP(s): return s[1:] if len(s) >= 1 else None
def OVER(s): return [s[1]] + s if len(s) >= 2 else None
def ROT(s): return [s[2]] + s[:2] + s[3:] if len(s) >= 3 else None
def UNROT(s): return s[1:3] + [s[0]] + s[3:] if len(s) >= 3 else None
def DUP2(s): return [s[0], s[1]] + s if len(s) >= 2 else None
def DROP2(s): return s[2:] if len(s) >= 2 else None
def PICK3(s): return [s[2]] + s if len(s) >= 3 else None
def NIP(s): return [s[0]] + s[2:] if len(s) >= 2 else None
def make_parametric_ops(max_n: int) -> dict:
ops = {}
for n in range(2, max_n + 1):
def make_roll(n=n):
def f(s): return [s[n-1]] + s[:n-1] + s[n:] if len(s) >= n else None
f.__name__ = f"{n} ROLL"; return f
def make_rolld(n=n):
def f(s): return s[1:n] + [s[0]] + s[n:] if len(s) >= n else None
f.__name__ = f"{n} ROLLD"; return f
def make_pick(n=n):
def f(s): return [s[n-1]] + s if len(s) >= n else None
f.__name__ = f"{n} PICK"; return f
def make_unpick(n=n):
def f(s): return s[1:n] + [s[0]] + s[n+1:] if len(s) > n else None
f.__name__ = f"{n} UNPICK"; return f
def make_dupn(n=n):
def f(s): return s[:n] + s if len(s) >= n else None
f.__name__ = f"{n} DUPN"; return f
def make_dropn(n=n):
def f(s): return s[n:] if len(s) >= n else None
f.__name__ = f"{n} DROPN"; return f
def make_ndupn(n=n):
def f(s): return [n] + [s[0]] * n + s[1:] if len(s) >= 1 else None
f.__name__ = f"{n} NDUPN"; return f
ops[f"{n} ROLL"] = (make_roll(), 2)
ops[f"{n} ROLLD"] = (make_rolld(), 2)
ops[f"{n} PICK"] = (make_pick(), 2)
ops[f"{n} UNPICK"] = (make_unpick(), 2)
ops[f"{n} DUPN"] = (make_dupn(), 2)
ops[f"{n} DROPN"] = (make_dropn(), 2)
ops[f"{n} NDUPN"] = (make_ndupn(), 2)
return ops
FIXED_OPS = {
"DUP": (DUP, 1), "DUPDUP": (DUPDUP, 1), "SWAP": (SWAP, 1),
"DROP": (DROP, 1), "OVER": (OVER, 1), "ROT": (ROT, 1),
"UNROT": (UNROT, 1), "DUP2": (DUP2, 1), "DROP2": (DROP2, 1),
"PICK3": (PICK3, 1), "NIP": (NIP, 1),
}
PARAM_OPS = make_parametric_ops(8)
ALL_OPS = {**FIXED_OPS, **PARAM_OPS}
INITIAL = ('A', 'B', 'C', 'D', '_5', '_6', '_7', '_8')
SENTINEL = frozenset({'_5', '_6', '_7', '_8'})
LETTERS = ('A', 'B', 'C', 'D')
# ── Dijkstra ─────
def solve_all(max_cost: int = 8) -> dict:
all_targets = set(iproduct(LETTERS, repeat=4))
solutions = {}
remaining = set(all_targets)
dist = {INITIAL: 0}
counter = 0
heap = [(0, counter, INITIAL, [])]
while heap and remaining:
cur_cost, _, stack, path = heapq.heappop(heap)
if dist.get(stack, float('inf')) < cur_cost: continue
top4 = stack[:4]
if top4 in remaining and not any(e in SENTINEL for e in top4):
solutions[top4] = (cur_cost, path)
remaining.discard(top4)
if cur_cost >= max_cost: continue
for name, (fn, op_cost) in ALL_OPS.items():
new_cost = cur_cost + op_cost
if new_cost > max_cost: continue
new_stack_list = fn(list(stack))
if new_stack_list is None or len(new_stack_list) < 4: continue
new_stack = tuple(new_stack_list)
if new_cost < dist.get(new_stack, float('inf')):
dist[new_stack] = new_cost
counter += 1
heapq.heappush(heap, (new_cost, counter, new_stack, path + [name]))
return solutions
def print_table(solutions: dict):
letters = ['A', 'B', 'C', 'D']
combos = list(iproduct(letters, repeat=4))
lines = []
for combo in combos:
target_str = ':'.join(combo[::-1])
if combo in solutions:
cost, path = solutions[combo]
seq = ' '.join(path) if path else "(identité)"
lines.append(f"{target_str} [cost {cost}] {seq}")
else:
lines.append(f"{target_str} [no solution]")
return lines
solutions = solve_all(max_cost=5)
print("Research in progress...")
lines = print_table(solutions)
for l in lines: print(l)
found = sum(1 for c in iproduct(LETTERS, repeat=4) if c in solutions)
print(f"\n{found}/256 targets solved.")