On pages 62 and following of this book, we see different combinations of the 4 XYZT elements of the stack and how to obtain them starting from the DCBA configuration.
We only consider the first 4 elements of the stack.
Input T:Z:Y:X (Always) : D:C:B:A (« : » means ENTER)
D : Level 4 (T)
C : Level 3 (Z)
B : Level 2 (Y)
A : Level 1 (X)
Example output T:Z:Y:X: A:A:A:A
Solution : DUP / DUPDUP
Stack : D:C:B:A:A:A:A
Concretely : 9 ENTER 7 ENTER 5 ENTER 3 DUP DUPDUP → 9:7:5:3:3:3:3
The 256 combinations:
T:Z:Y:X [cost n] Keys
A:A:A:A [cost 2] DUP DUPDUP
B:A:A:A [cost 1] DUPDUP
C:A:A:A [cost 2] NIP DUPDUP
D:A:A:A [cost 3] UNROT DROP2 DUPDUP
A:B:A:A [cost 2] DUP2 DUP
B:B:A:A [cost 2] DUP2 ROT
C:B:A:A [cost 1] DUP
D:B:A:A [cost 3] ROT DROP DUP
A:C:A:A [cost 3] ROT OVER DUP
B:C:A:A [cost 3] SWAP UNROT DUP
C:C:A:A [cost 3] NIP DUP2 ROT
D:C:A:A [cost 2] NIP DUP
A:D:A:A [cost 4] DUPDUP 6 ROLL UNROT
B:D:A:A [cost 4] DUP 5 ROLL UNROT
C:D:A:A [cost 4] UNROT DROP UNROT DUP
D:D:A:A [cost 4] UNROT DROP2 DUP2 ROT
A:A:B:A [cost 3] DUP2 3 DUPN
B:A:B:A [cost 1] DUP2
C:A:B:A [cost 2] DUP UNROT
D:A:B:A [cost 3] DUP 3 UNPICK
A:B:B:A [cost 3] SWAP DUP PICK3
B:B:B:A [cost 3] OVER DUP ROT
C:B:B:A [cost 2] OVER SWAP
D:B:B:A [cost 3] OVER 3 UNPICK
A:C:B:A [cost 2] 3 DUPN
B:C:B:A [cost 3] OVER 4 ROLLD
C:C:B:A [cost 2] PICK3 UNROT
D:C:B:A [cost 0] (identité)
A:D:B:A [cost 4] ROT DROP 3 DUPN
B:D:B:A [cost 4] 4 ROLL PICK3 ROT
C:D:B:A [cost 3] ROT 4 ROLLD
D:D:B:A [cost 4] 4 PICK 3 UNPICK
A:A:C:A [cost 4] ROT OVER 3 DUPN
B:A:C:A [cost 2] ROT OVER
C:A:C:A [cost 2] NIP DUP2
D:A:C:A [cost 3] UNROT DROP OVER
A:B:C:A [cost 3] SWAP ROT PICK3
B:B:C:A [cost 4] SWAP 3 DUPN UNROT
C:B:C:A [cost 2] PICK3 SWAP
D:B:C:A [cost 2] SWAP UNROT
A:C:C:A [cost 3] ROT DUP PICK3
B:C:C:A [cost 3] ROT DUP ROT
C:C:C:A [cost 4] ROT DUPDUP 4 ROLL
D:C:C:A [cost 3] PICK3 2 UNPICK
A:D:C:A [cost 3] NIP 3 DUPN
B:D:C:A [cost 3] SWAP 4 ROLLD
C:D:C:A [cost 4] NIP OVER 4 ROLLD
D:D:C:A [cost 3] NIP PICK3 UNROT
A:A:D:A [cost 4] DUP 5 ROLL OVER
B:A:D:A [cost 3] 4 ROLL OVER
C:A:D:A [cost 3] NIP ROT OVER
D:A:D:A [cost 3] UNROT DROP2 DUP2
A:B:D:A [cost 4] SWAP 4 ROLL PICK3
B:B:D:A [cost 4] OVER 5 ROLL ROT
C:B:D:A [cost 3] 4 ROLL SWAP
D:B:D:A [cost 4] 2 UNPICK PICK3 ROT
A:C:D:A [cost 4] ROT 4 ROLL PICK3
B:C:D:A [cost 4] ROT 4 ROLL ROT
C:C:D:A [cost 5] ROT DUP2 6 ROLL ROT
D:C:D:A [cost 3] NIP PICK3 SWAP
A:D:D:A [cost 4] 4 ROLL DUP PICK3
B:D:D:A [cost 4] 4 ROLL DUP ROT
C:D:D:A [cost 4] NIP ROT DUP ROT
D:D:D:A [cost 5] 4 ROLL DUPDUP 4 ROLL
A:A:A:B [cost 3] DUPDUP 4 ROLL
B:A:A:B [cost 2] DUP PICK3
C:A:A:B [cost 2] DUP ROT
D:A:A:B [cost 4] DUP UNROT 3 UNPICK
A:B:A:B [cost 2] SWAP DUP2
B:B:A:B [cost 3] OVER 3 DUPN
C:B:A:B [cost 1] OVER
D:B:A:B [cost 3] ROT DROP OVER
A:C:A:B [cost 3] 3 DUPN SWAP
B:C:A:B [cost 3] SWAP 3 DUPN
C:C:A:B [cost 3] SWAP PICK3 UNROT
D:C:A:B [cost 1] SWAP
A:D:A:B [cost 4] 4 DUPN 2 UNPICK
B:D:A:B [cost 4] 2 UNPICK 3 DUPN
C:D:A:B [cost 4] SWAP ROT 4 ROLLD
D:D:A:B [cost 4] 2 UNPICK PICK3 UNROT
A:A:B:B [cost 3] DUP ROT DUP
B:A:B:B [cost 2] OVER DUP
C:A:B:B [cost 2] SWAP DUP
D:A:B:B [cost 3] 2 UNPICK DUP
A:B:B:B [cost 2] SWAP DUPDUP
B:B:B:B [cost 3] SWAP DUP DUPDUP
C:B:B:B [cost 2] DROP DUPDUP
D:B:B:B [cost 3] DROP NIP DUPDUP
A:C:B:B [cost 2] UNROT DUP
B:C:B:B [cost 3] DROP DUP2 DUP
C:C:B:B [cost 3] DROP DUP2 ROT
D:C:B:B [cost 2] DROP DUP
A:D:B:B [cost 4] 4 ROLL ROT DUP
B:D:B:B [cost 4] DROP ROT OVER DUP
C:D:B:B [cost 4] DROP SWAP UNROT DUP
D:D:B:B [cost 4] DROP NIP DUP2 ROT
A:A:C:B [cost 3] 3 DUPN UNROT
B:A:C:B [cost 2] ROT PICK3
C:A:C:B [cost 2] PICK3 ROT
D:A:C:B [cost 1] UNROT
A:B:C:B [cost 3] SWAP ROT OVER
B:B:C:B [cost 4] DROP DUP2 3 DUPN
C:B:C:B [cost 2] DROP DUP2
D:B:C:B [cost 3] DROP DUP UNROT
A:C:C:B [cost 3] UNROT OVER SWAP
B:C:C:B [cost 4] SWAP ROT DUP PICK3
C:C:C:B [cost 4] ROT DUPDUP 5 ROLL
D:C:C:B [cost 3] DROP OVER SWAP
A:D:C:B [cost 2] 4 ROLLD
B:D:C:B [cost 3] DROP 3 DUPN
C:D:C:B [cost 4] DROP OVER 4 ROLLD
D:D:C:B [cost 3] DROP PICK3 UNROT
A:A:D:B [cost 4] DUP2 6 ROLL ROT
B:A:D:B [cost 3] 4 ROLL PICK3
C:A:D:B [cost 3] 4 ROLL ROT
D:A:D:B [cost 4] 2 UNPICK PICK3 SWAP
A:B:D:B [cost 4] SWAP 4 ROLL OVER
B:B:D:B [cost 5] DROP ROT OVER 3 DUPN
C:B:D:B [cost 3] DROP ROT OVER
D:B:D:B [cost 3] DROP NIP DUP2
A:C:D:B [cost 4] ROT 4 DUPN DROP2
B:C:D:B [cost 4] DROP SWAP ROT PICK3
C:C:D:B [cost 5] DROP SWAP 3 DUPN UNROT
D:C:D:B [cost 3] DROP PICK3 SWAP
A:D:D:B [cost 5] 4 ROLL DUP 4 ROLL
B:D:D:B [cost 4] DROP ROT DUP PICK3
C:D:D:B [cost 4] DROP ROT DUP ROT
D:D:D:B [cost 5] 4 ROLL DUPDUP 5 ROLL
A:A:A:C [cost 3] DUPDUP 5 ROLL
B:A:A:C [cost 3] DUP 4 ROLL
C:A:A:C [cost 3] NIP DUP PICK3
D:A:A:C [cost 3] NIP DUP ROT
A:B:A:C [cost 3] DUP2 5 ROLL
B:B:A:C [cost 3] ROT PICK3 UNROT
C:B:A:C [cost 1] PICK3
D:B:A:C [cost 1] ROT
A:C:A:C [cost 2] ROT DUP2
B:C:A:C [cost 3] SWAP UNROT OVER
C:C:A:C [cost 4] ROT DUP2 3 DUPN
D:C:A:C [cost 2] NIP OVER
A:D:A:C [cost 4] NIP 3 DUPN SWAP
B:D:A:C [cost 3] UNROT 4 ROLLD
C:D:A:C [cost 4] UNROT DROP 3 DUPN
D:D:A:C [cost 4] UNROT DROP PICK3 UNROT
A:A:B:C [cost 4] DUP ROT 4 ROLL
B:A:B:C [cost 3] OVER 4 ROLL
C:A:B:C [cost 2] SWAP PICK3
D:A:B:C [cost 2] SWAP ROT
A:B:B:C [cost 3] UNROT DUP ROT
B:B:B:C [cost 4] SWAP DUPDUP 5 ROLL
C:B:B:C [cost 3] DROP DUP PICK3
D:B:B:C [cost 3] DROP DUP ROT
A:C:B:C [cost 2] UNROT OVER
B:C:B:C [cost 3] SWAP ROT DUP2
C:C:B:C [cost 4] DROP OVER 3 DUPN
D:C:B:C [cost 2] DROP OVER
A:D:B:C [cost 3] 4 ROLLD SWAP
B:D:B:C [cost 4] DROP 3 DUPN SWAP
C:D:B:C [cost 4] DROP SWAP 3 DUPN
D:D:B:C [cost 4] DROP SWAP PICK3 UNROT
A:A:C:C [cost 3] ROT DUP2 ROT
B:A:C:C [cost 2] ROT DUP
C:A:C:C [cost 3] ROT DUP2 DUP
D:A:C:C [cost 3] UNROT DROP DUP
A:B:C:C [cost 3] SWAP ROT DUP
B:B:C:C [cost 4] SWAP ROT DUP2 ROT
C:B:C:C [cost 3] DROP OVER DUP
D:B:C:C [cost 3] DROP SWAP DUP
A:C:C:C [cost 2] ROT DUPDUP
B:C:C:C [cost 3] SWAP ROT DUPDUP
C:C:C:C [cost 3] ROT DUP DUPDUP
D:C:C:C [cost 2] DROP2 DUPDUP
A:D:C:C [cost 3] NIP UNROT DUP
B:D:C:C [cost 3] DROP UNROT DUP
C:D:C:C [cost 3] DROP2 DUP2 DUP
D:D:C:C [cost 3] DROP2 DUP2 ROT
A:A:D:C [cost 4] NIP 3 DUPN UNROT
B:A:D:C [cost 3] 4 DUPN DROP2
C:A:D:C [cost 3] NIP ROT PICK3
D:A:D:C [cost 3] NIP PICK3 ROT
A:B:D:C [cost 3] 4 ROLLD UNROT
B:B:D:C [cost 4] DROP 3 DUPN UNROT
C:B:D:C [cost 3] DROP ROT PICK3
D:B:D:C [cost 3] DROP PICK3 ROT
A:C:D:C [cost 4] ROT 4 ROLL OVER
B:C:D:C [cost 4] DROP SWAP ROT OVER
C:C:D:C [cost 4] DROP2 DUP2 3 DUPN
D:C:D:C [cost 2] DROP2 DUP2
A:D:D:C [cost 4] NIP UNROT OVER SWAP
B:D:D:C [cost 4] DROP UNROT OVER SWAP
C:D:D:C [cost 4] DROP2 SWAP DUP PICK3
D:D:D:C [cost 4] DROP2 OVER DUP ROT
A:A:A:D [cost 3] DUPDUP 6 ROLL
B:A:A:D [cost 3] DUP 5 ROLL
C:A:A:D [cost 4] NIP DUP 4 ROLL
D:A:A:D [cost 4] UNROT DROP2 DUP PICK3
A:B:A:D [cost 3] DUP2 6 ROLL
B:B:A:D [cost 4] OVER SWAP 5 ROLL
C:B:A:D [cost 2] 4 ROLL
D:B:A:D [cost 3] ROT DROP PICK3
A:C:A:D [cost 4] ROT OVER 5 ROLL
B:C:A:D [cost 4] SWAP UNROT 4 ROLL
C:C:A:D [cost 4] NIP ROT PICK3 UNROT
D:C:A:D [cost 2] NIP PICK3
A:D:A:D [cost 3] 4 ROLL DUP2
B:D:A:D [cost 4] 2 UNPICK UNROT OVER
C:D:A:D [cost 4] UNROT DROP UNROT OVER
D:D:A:D [cost 5] 4 ROLL DUP2 3 DUPN
A:A:B:D [cost 4] DUP ROT 5 ROLL
B:A:B:D [cost 3] OVER 5 ROLL
C:A:B:D [cost 3] SWAP 4 ROLL
D:A:B:D [cost 3] 2 UNPICK PICK3
A:B:B:D [cost 4] SWAP DUP 5 ROLL
B:B:B:D [cost 4] SWAP DUPDUP 6 ROLL
C:B:B:D [cost 4] DROP DUP 4 ROLL
D:B:B:D [cost 4] DROP NIP DUP PICK3
A:C:B:D [cost 3] UNROT 4 ROLL
B:C:B:D [cost 4] DROP DUP2 5 ROLL
C:C:B:D [cost 4] DROP ROT PICK3 UNROT
D:C:B:D [cost 2] DROP PICK3
A:D:B:D [cost 4] 4 ROLL ROT OVER
B:D:B:D [cost 3] DROP ROT DUP2
C:D:B:D [cost 4] DROP SWAP UNROT OVER
D:D:B:D [cost 5] DROP ROT DUP2 3 DUPN
A:A:C:D [cost 5] DUP 4 ROLL 5 ROLL
B:A:C:D [cost 3] ROT 4 ROLL
C:A:C:D [cost 4] ROT DUP2 6 ROLL
D:A:C:D [cost 3] UNROT DROP PICK3
A:B:C:D [cost 4] SWAP ROT 4 ROLL
B:B:C:D [cost 5] DROP DUP ROT 4 ROLL
C:B:C:D [cost 4] DROP OVER 4 ROLL
D:B:C:D [cost 3] DROP SWAP PICK3
A:C:C:D [cost 4] ROT DUP 5 ROLL
B:C:C:D [cost 4] DROP UNROT DUP ROT
C:C:C:D [cost 4] ROT DUPDUP 6 ROLL
D:C:C:D [cost 3] DROP2 DUP PICK3
A:D:C:D [cost 3] NIP UNROT OVER
B:D:C:D [cost 3] DROP UNROT OVER
C:D:C:D [cost 3] DROP2 SWAP DUP2
D:D:C:D [cost 4] DROP2 OVER 3 DUPN
A:A:D:D [cost 4] DUP 5 ROLL DUP
B:A:D:D [cost 3] 4 ROLL DUP
C:A:D:D [cost 3] NIP ROT DUP
D:A:D:D [cost 4] 4 ROLL DUP2 DUP
A:B:D:D [cost 4] SWAP 4 ROLL DUP
B:B:D:D [cost 4] DROP ROT DUP2 ROT
C:B:D:D [cost 3] DROP ROT DUP
D:B:D:D [cost 4] DROP ROT DUP2 DUP
A:C:D:D [cost 4] ROT 4 ROLL DUP
B:C:D:D [cost 4] DROP SWAP ROT DUP
C:C:D:D [cost 4] DROP2 DUP ROT DUP
D:C:D:D [cost 3] DROP2 OVER DUP
A:D:D:D [cost 3] 4 ROLL DUPDUP
B:D:D:D [cost 3] DROP ROT DUPDUP
C:D:D:D [cost 3] DROP2 SWAP DUPDUP
D:D:D:D [cost 4] 3 DROPN DUP DUPDUPPython program used : Try it here
"""
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.")Optimizing a sequence
Can a sequence be simplified? For example, can rot drop over swap be written more simply? The answer is YES, in OVER 3 UNPICK
Séquence > rot drop over swap
Séquence entrée : ROT DROP OVER SWAP
Coût total : 4
Effet sur pile : D : B : B : A (niveau 1 en bas)
Recherche d'optimisations (coût ≤ 3)...
✓ 1 optimisation(s) trouvée(s) (coût 3, gain -1) :
[3] OVER 3 UNPICK
Séquence > swap drop swap over
Séquence entrée : SWAP DROP SWAP OVER
Coût total : 4
Effet sur pile : D : A : C : A (niveau 1 en bas)
Recherche d'optimisations (coût ≤ 3)...
✓ 1 optimisation(s) trouvée(s) (coût 3, gain -1) :
[3] UNROT DROP OVER
Séquence > swap rot drop2 dup dup
Séquence entrée : SWAP ROT DROP2 DUP DUP
Coût total : 5
Effet sur pile : D : A : A : A (niveau 1 en bas)
Recherche d'optimisations (coût ≤ 4)...
✓ 1 optimisation(s) trouvée(s) (coût 3, gain -2) :
[3] UNROT DROP2 DUPDUPPyhon program
"""
hp50g_optimizer.py
==================
Trouve une séquence équivalente mais plus courte (moins coûteuse) à une
commande HP50g donnée en entrée.
Usage :
python hp50g_optimizer.py
> Entrez une séquence : SWAP OVER SWAP
> Résultats...
"""
from itertools import product as iproduct
import heapq
import sys
# ── Opérations de pile ────────────────────────────────────────────────────────
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}
# ── Pile initiale ─────────────────────────────────────────────────────────────
INITIAL = ('A', 'B', 'C', 'D', '_5', '_6', '_7', '_8')
SENTINEL = frozenset({'_5', '_6', '_7', '_8'})
# ── Parsing de la séquence entrée ─────────────────────────────────────────────
def parse_sequence(raw: str) -> list[str] | None:
"""
Convertit une chaîne comme "SWAP OVER SWAP" en liste de noms d'opérations.
Retourne None si un token est inconnu.
Les noms sont normalisés en majuscules.
"""
tokens = raw.upper().split()
result = []
i = 0
while i < len(tokens):
# Essai de token double : "2 ROLL", "3 PICK", etc.
if i + 1 < len(tokens):
candidate2 = tokens[i] + " " + tokens[i+1]
if candidate2 in ALL_OPS:
result.append(candidate2)
i += 2
continue
candidate1 = tokens[i]
if candidate1 in ALL_OPS:
result.append(candidate1)
i += 1
else:
print(f" ✗ Opération inconnue : '{tokens[i]}'")
return None
return result
def sequence_cost(ops: list[str]) -> int:
return sum(ALL_OPS[op][1] for op in ops)
# ── Application d'une séquence sur une pile ───────────────────────────────────
def apply_sequence(ops: list[str], stack: tuple) -> tuple | None:
s = list(stack)
for name in ops:
fn, _ = ALL_OPS[name]
s = fn(s)
if s is None:
return None
return tuple(s)
# ── Dijkstra : cherche toutes les séquences <= max_cost atteignant target ─────
def find_optimizations(target: tuple, max_cost: int, min_results: int = 1) -> list[tuple]:
"""
Retourne une liste de (cost, path) atteignant `target` depuis INITIAL,
avec cost <= max_cost, triées par coût croissant.
S'arrête dès que min_results solutions sont trouvées au coût minimal.
"""
solutions = []
best_cost = None
dist = {INITIAL: 0}
counter = 0
heap = [(0, counter, INITIAL, [])]
while heap:
cur_cost, _, stack, path = heapq.heappop(heap)
if dist.get(stack, float('inf')) < cur_cost:
continue
if best_cost is not None and cur_cost > best_cost:
break
# La profondeur utile est celle des éléments non-sentinelles
stack_depth = len([e for e in stack if e not in SENTINEL])
# On compare uniquement la partie "utile" de la pile avec la cible
useful = tuple(e for e in stack if e not in SENTINEL)
target_useful = tuple(e for e in target if e not in SENTINEL)
if useful == target_useful and cur_cost > 0:
solutions.append((cur_cost, path))
best_cost = cur_cost
if len(solutions) >= min_results:
continue # continue à drainer le même niveau de coût
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:
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
# ── Interface ─────────────────────────────────────────────────────────────────
def main():
print("=" * 60)
print(" HP50g Stack Sequence Optimizer")
print(" Entrez une séquence d'opérations pour trouver un")
print(" équivalent plus court. Ex: SWAP OVER SWAP")
print(" (opérations paramétriques : '2 ROLL', '3 PICK', ...)")
print(" Tapez 'quitter' pour sortir.")
print("=" * 60)
while True:
print()
try:
raw = input("Séquence > ").strip()
except (EOFError, KeyboardInterrupt):
print("\nAu revoir.")
break
if raw.lower() in ("quitter", "quit", "exit", "q"):
print("Au revoir.")
break
if not raw:
continue
# Parsing
ops = parse_sequence(raw)
if ops is None:
continue
if not ops:
print(" (séquence vide)")
continue
input_cost = sequence_cost(ops)
print(f"\n Séquence entrée : {' '.join(ops)}")
print(f" Coût total : {input_cost}")
# Application sur la pile initiale
target = apply_sequence(ops, INITIAL)
if target is None:
print(" ✗ La séquence échoue sur la pile initiale (pile insuffisante ?).")
continue
# Pile résultante (partie lisible)
readable = [e for e in target if e not in SENTINEL]
print(f" Effet sur pile : {' : '.join(readable[::-1])} (niveau 1 en bas)")
# Cas identité
if tuple(e for e in target if e not in SENTINEL) == ('A', 'B', 'C', 'D'):
print(" ⚠ La séquence est une identité (ne modifie pas la pile).")
max_search = input_cost - 1
if max_search <= 0:
print(" ✓ Séquence déjà de coût minimal (1), aucune optimisation possible.")
continue
print(f"\n Recherche d'optimisations (coût ≤ {max_search})...")
solutions = find_optimizations(target, max_cost=max_search, min_results=5)
if not solutions:
print(" ✓ Aucune séquence plus courte trouvée — déjà optimale !")
else:
best = solutions[0][0]
gain = input_cost - best
print(f" ✓ {len(solutions)} optimisation(s) trouvée(s) (coût {best}, gain -{gain}) :\n")
for cost, path in solutions:
seq = ' '.join(path) if path else "(identité — ne rien faire)"
print(f" [{cost}] {seq}")
if __name__ == "__main__":
main()