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 DUPDUP

Python 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 DUPDUP

Pyhon 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()