{"id":2094,"date":"2026-04-23T07:39:42","date_gmt":"2026-04-23T06:39:42","guid":{"rendered":"https:\/\/blog.univ-angers.fr\/mathsinfo\/?p=2094"},"modified":"2026-04-23T10:30:50","modified_gmt":"2026-04-23T09:30:50","slug":"algorithms-for-rpn-calculators-hp49-50g-version","status":"publish","type":"post","link":"https:\/\/blog.univ-angers.fr\/mathsinfo\/2026\/04\/23\/algorithms-for-rpn-calculators-hp49-50g-version\/","title":{"rendered":"Algorithms for RPN Calculators (HP49\/50g version)"},"content":{"rendered":"\n
On pages 62 and following of this book<\/a>, we see different combinations of the 4 XYZT elements of the stack and how to obtain them starting from the DCBA configuration.<\/pre>\n\n\n\n
We only consider the first 4 elements of the stack.<\/strong><\/p>\n\n\n\n
Input T:Z:Y:X<\/strong> (Always<\/mark>) : D:C:B:A<\/strong> (\u00ab\u00a0:\u00a0\u00bb means ENTER<\/strong>)<\/p>\n\n\n\n
D<\/strong> : Level 4 (T)
C<\/strong> : Level 3 (Z)
B<\/strong> : Level 2 (Y)
A<\/strong> : Level 1 (X)<\/p>\n\n\n\n
Example output T:Z:Y:X<\/strong>: A:A:A:A<\/mark><\/strong>
Solution : DUP \/ DUPDUP<\/strong>
Stack : D:C:B:A:A:A:A<\/mark><\/strong><\/p>\n\n\n\n
Concretely : 9 ENTER 7 ENTER 5 ENTER 3 DUP<\/strong> DUPDUP<\/strong> \u2192 9:7:5:3:3:3:3<\/mark><\/strong><\/pre>\n\n\n\n
The 256 combinations:<\/h2>\n\n\n\n
T:Z:Y:X  [cost n]  Keys <\/mark><\/strong>  \nA:A:A:A  [cost 2]  DUP DUPDUP\nB:A:A:A  [cost 1]  DUPDUP<\/strong>\nC:A:A:A  [cost 2]  NIP DUPDUP\nD:A:A:A  [cost 3]  UNROT DROP2 DUPDUP\nA:B:A:A  [cost 2]  DUP2 DUP\nB:B:A:A  [cost 2]  DUP2 ROT\nC:B:A:A  [cost 1]  DUP<\/strong>\nD:B:A:A  [cost 3]  ROT DROP DUP\nA:C:A:A  [cost 3]  ROT OVER DUP\nB:C:A:A  [cost 3]  SWAP UNROT DUP\nC:C:A:A  [cost 3]  NIP DUP2 ROT\nD:C:A:A  [cost 2]  NIP DUP\nA:D:A:A  [cost 4]  DUPDUP 6 ROLL UNROT\nB:D:A:A  [cost 4]  DUP 5 ROLL UNROT\nC:D:A:A  [cost 4]  UNROT DROP UNROT DUP\nD:D:A:A  [cost 4]  UNROT DROP2 DUP2 ROT\nA:A:B:A  [cost 3]  DUP2 3 DUPN\nB:A:B:A  [cost 1]  DUP2<\/strong>\nC:A:B:A  [cost 2]  DUP UNROT\nD:A:B:A  [cost 3]  DUP 3 UNPICK\nA:B:B:A  [cost 3]  SWAP DUP PICK3\nB:B:B:A  [cost 3]  OVER DUP ROT\nC:B:B:A  [cost 2]  OVER SWAP\nD:B:B:A  [cost 3]  OVER 3 UNPICK\nA:C:B:A  [cost 2]  3 DUPN\nB:C:B:A  [cost 3]  OVER 4 ROLLD\nC:C:B:A  [cost 2]  PICK3 UNROT\nD:C:B:A  [cost 0]  (identit\u00e9)\nA:D:B:A  [cost 4]  ROT DROP 3 DUPN\nB:D:B:A  [cost 4]  4 ROLL PICK3 ROT\nC:D:B:A  [cost 3]  ROT 4 ROLLD\nD:D:B:A  [cost 4]  4 PICK 3 UNPICK\nA:A:C:A  [cost 4]  ROT OVER 3 DUPN\nB:A:C:A  [cost 2]  ROT OVER\nC:A:C:A  [cost 2]  NIP DUP2\nD:A:C:A  [cost 3]  UNROT DROP OVER\nA:B:C:A  [cost 3]  SWAP ROT PICK3\nB:B:C:A  [cost 4]  SWAP 3 DUPN UNROT\nC:B:C:A  [cost 2]  PICK3 SWAP\nD:B:C:A  [cost 2]  SWAP UNROT\nA:C:C:A  [cost 3]  ROT DUP PICK3\nB:C:C:A  [cost 3]  ROT DUP ROT\nC:C:C:A  [cost 4]  ROT DUPDUP 4 ROLL\nD:C:C:A  [cost 3]  PICK3 2 UNPICK\nA:D:C:A  [cost 3]  NIP 3 DUPN\nB:D:C:A  [cost 3]  SWAP 4 ROLLD\nC:D:C:A  [cost 4]  NIP OVER 4 ROLLD\nD:D:C:A  [cost 3]  NIP PICK3 UNROT\nA:A:D:A  [cost 4]  DUP 5 ROLL OVER\nB:A:D:A  [cost 3]  4 ROLL OVER\nC:A:D:A  [cost 3]  NIP ROT OVER\nD:A:D:A  [cost 3]  UNROT DROP2 DUP2\nA:B:D:A  [cost 4]  SWAP 4 ROLL PICK3\nB:B:D:A  [cost 4]  OVER 5 ROLL ROT\nC:B:D:A  [cost 3]  4 ROLL SWAP\nD:B:D:A  [cost 4]  2 UNPICK PICK3 ROT\nA:C:D:A  [cost 4]  ROT 4 ROLL PICK3\nB:C:D:A  [cost 4]  ROT 4 ROLL ROT\nC:C:D:A  [cost 5]  ROT DUP2 6 ROLL ROT\nD:C:D:A  [cost 3]  NIP PICK3 SWAP\nA:D:D:A  [cost 4]  4 ROLL DUP PICK3\nB:D:D:A  [cost 4]  4 ROLL DUP ROT\nC:D:D:A  [cost 4]  NIP ROT DUP ROT\nD:D:D:A  [cost 5]  4 ROLL DUPDUP 4 ROLL\nA:A:A:B  [cost 3]  DUPDUP 4 ROLL\nB:A:A:B  [cost 2]  DUP PICK3\nC:A:A:B  [cost 2]  DUP ROT\nD:A:A:B  [cost 4]  DUP UNROT 3 UNPICK\nA:B:A:B  [cost 2]  SWAP DUP2\nB:B:A:B  [cost 3]  OVER 3 DUPN\nC:B:A:B  [cost 1]  OVER<\/strong>\nD:B:A:B  [cost 3]  ROT DROP OVER\nA:C:A:B  [cost 3]  3 DUPN SWAP\nB:C:A:B  [cost 3]  SWAP 3 DUPN\nC:C:A:B  [cost 3]  SWAP PICK3 UNROT\nD:C:A:B  [cost 1]  SWAP<\/strong>\nA:D:A:B  [cost 4]  4 DUPN 2 UNPICK\nB:D:A:B  [cost 4]  2 UNPICK 3 DUPN\nC:D:A:B  [cost 4]  SWAP ROT 4 ROLLD\nD:D:A:B  [cost 4]  2 UNPICK PICK3 UNROT\nA:A:B:B  [cost 3]  DUP ROT DUP\nB:A:B:B  [cost 2]  OVER DUP\nC:A:B:B  [cost 2]  SWAP DUP\nD:A:B:B  [cost 3]  2 UNPICK DUP\nA:B:B:B  [cost 2]  SWAP DUPDUP\nB:B:B:B  [cost 3]  SWAP DUP DUPDUP\nC:B:B:B  [cost 2]  DROP DUPDUP\nD:B:B:B  [cost 3]  DROP NIP DUPDUP\nA:C:B:B  [cost 2]  UNROT DUP\nB:C:B:B  [cost 3]  DROP DUP2 DUP\nC:C:B:B  [cost 3]  DROP DUP2 ROT\nD:C:B:B  [cost 2]  DROP DUP\nA:D:B:B  [cost 4]  4 ROLL ROT DUP\nB:D:B:B  [cost 4]  DROP ROT OVER DUP\nC:D:B:B  [cost 4]  DROP SWAP UNROT DUP\nD:D:B:B  [cost 4]  DROP NIP DUP2 ROT\nA:A:C:B  [cost 3]  3 DUPN UNROT\nB:A:C:B  [cost 2]  ROT PICK3\nC:A:C:B  [cost 2]  PICK3 ROT\nD:A:C:B  [cost 1]  UNROT<\/strong>\nA:B:C:B  [cost 3]  SWAP ROT OVER\nB:B:C:B  [cost 4]  DROP DUP2 3 DUPN\nC:B:C:B  [cost 2]  DROP DUP2\nD:B:C:B  [cost 3]  DROP DUP UNROT\nA:C:C:B  [cost 3]  UNROT OVER SWAP\nB:C:C:B  [cost 4]  SWAP ROT DUP PICK3\nC:C:C:B  [cost 4]  ROT DUPDUP 5 ROLL\nD:C:C:B  [cost 3]  DROP OVER SWAP\nA:D:C:B  [cost 2]  4 ROLLD\nB:D:C:B  [cost 3]  DROP 3 DUPN\nC:D:C:B  [cost 4]  DROP OVER 4 ROLLD\nD:D:C:B  [cost 3]  DROP PICK3 UNROT\nA:A:D:B  [cost 4]  DUP2 6 ROLL ROT\nB:A:D:B  [cost 3]  4 ROLL PICK3\nC:A:D:B  [cost 3]  4 ROLL ROT\nD:A:D:B  [cost 4]  2 UNPICK PICK3 SWAP\nA:B:D:B  [cost 4]  SWAP 4 ROLL OVER\nB:B:D:B  [cost 5]  DROP ROT OVER 3 DUPN\nC:B:D:B  [cost 3]  DROP ROT OVER\nD:B:D:B  [cost 3]  DROP NIP DUP2\nA:C:D:B  [cost 4]  ROT 4 DUPN DROP2\nB:C:D:B  [cost 4]  DROP SWAP ROT PICK3\nC:C:D:B  [cost 5]  DROP SWAP 3 DUPN UNROT\nD:C:D:B  [cost 3]  DROP PICK3 SWAP\nA:D:D:B  [cost 5]  4 ROLL DUP 4 ROLL\nB:D:D:B  [cost 4]  DROP ROT DUP PICK3\nC:D:D:B  [cost 4]  DROP ROT DUP ROT\nD:D:D:B  [cost 5]  4 ROLL DUPDUP 5 ROLL\nA:A:A:C  [cost 3]  DUPDUP 5 ROLL\nB:A:A:C  [cost 3]  DUP 4 ROLL\nC:A:A:C  [cost 3]  NIP DUP PICK3\nD:A:A:C  [cost 3]  NIP DUP ROT\nA:B:A:C  [cost 3]  DUP2 5 ROLL\nB:B:A:C  [cost 3]  ROT PICK3 UNROT\nC:B:A:C  [cost 1]  PICK3<\/strong>\nD:B:A:C  [cost 1]  ROT<\/strong>\nA:C:A:C  [cost 2]  ROT DUP2\nB:C:A:C  [cost 3]  SWAP UNROT OVER\nC:C:A:C  [cost 4]  ROT DUP2 3 DUPN\nD:C:A:C  [cost 2]  NIP OVER\nA:D:A:C  [cost 4]  NIP 3 DUPN SWAP\nB:D:A:C  [cost 3]  UNROT 4 ROLLD\nC:D:A:C  [cost 4]  UNROT DROP 3 DUPN\nD:D:A:C  [cost 4]  UNROT DROP PICK3 UNROT\nA:A:B:C  [cost 4]  DUP ROT 4 ROLL\nB:A:B:C  [cost 3]  OVER 4 ROLL\nC:A:B:C  [cost 2]  SWAP PICK3\nD:A:B:C  [cost 2]  SWAP ROT\nA:B:B:C  [cost 3]  UNROT DUP ROT\nB:B:B:C  [cost 4]  SWAP DUPDUP 5 ROLL\nC:B:B:C  [cost 3]  DROP DUP PICK3\nD:B:B:C  [cost 3]  DROP DUP ROT\nA:C:B:C  [cost 2]  UNROT OVER\nB:C:B:C  [cost 3]  SWAP ROT DUP2\nC:C:B:C  [cost 4]  DROP OVER 3 DUPN\nD:C:B:C  [cost 2]  DROP OVER\nA:D:B:C  [cost 3]  4 ROLLD SWAP\nB:D:B:C  [cost 4]  DROP 3 DUPN SWAP\nC:D:B:C  [cost 4]  DROP SWAP 3 DUPN\nD:D:B:C  [cost 4]  DROP SWAP PICK3 UNROT\nA:A:C:C  [cost 3]  ROT DUP2 ROT\nB:A:C:C  [cost 2]  ROT DUP\nC:A:C:C  [cost 3]  ROT DUP2 DUP\nD:A:C:C  [cost 3]  UNROT DROP DUP\nA:B:C:C  [cost 3]  SWAP ROT DUP\nB:B:C:C  [cost 4]  SWAP ROT DUP2 ROT\nC:B:C:C  [cost 3]  DROP OVER DUP\nD:B:C:C  [cost 3]  DROP SWAP DUP\nA:C:C:C  [cost 2]  ROT DUPDUP\nB:C:C:C  [cost 3]  SWAP ROT DUPDUP\nC:C:C:C  [cost 3]  ROT DUP DUPDUP\nD:C:C:C  [cost 2]  DROP2 DUPDUP\nA:D:C:C  [cost 3]  NIP UNROT DUP\nB:D:C:C  [cost 3]  DROP UNROT DUP\nC:D:C:C  [cost 3]  DROP2 DUP2 DUP\nD:D:C:C  [cost 3]  DROP2 DUP2 ROT\nA:A:D:C  [cost 4]  NIP 3 DUPN UNROT\nB:A:D:C  [cost 3]  4 DUPN DROP2\nC:A:D:C  [cost 3]  NIP ROT PICK3\nD:A:D:C  [cost 3]  NIP PICK3 ROT\nA:B:D:C  [cost 3]  4 ROLLD UNROT\nB:B:D:C  [cost 4]  DROP 3 DUPN UNROT\nC:B:D:C  [cost 3]  DROP ROT PICK3\nD:B:D:C  [cost 3]  DROP PICK3 ROT\nA:C:D:C  [cost 4]  ROT 4 ROLL OVER\nB:C:D:C  [cost 4]  DROP SWAP ROT OVER\nC:C:D:C  [cost 4]  DROP2 DUP2 3 DUPN\nD:C:D:C  [cost 2]  DROP2 DUP2\nA:D:D:C  [cost 4]  NIP UNROT OVER SWAP\nB:D:D:C  [cost 4]  DROP UNROT OVER SWAP\nC:D:D:C  [cost 4]  DROP2 SWAP DUP PICK3\nD:D:D:C  [cost 4]  DROP2 OVER DUP ROT\nA:A:A:D  [cost 3]  DUPDUP 6 ROLL\nB:A:A:D  [cost 3]  DUP 5 ROLL\nC:A:A:D  [cost 4]  NIP DUP 4 ROLL\nD:A:A:D  [cost 4]  UNROT DROP2 DUP PICK3\nA:B:A:D  [cost 3]  DUP2 6 ROLL\nB:B:A:D  [cost 4]  OVER SWAP 5 ROLL\nC:B:A:D  [cost 2]  4 ROLL\nD:B:A:D  [cost 3]  ROT DROP PICK3\nA:C:A:D  [cost 4]  ROT OVER 5 ROLL\nB:C:A:D  [cost 4]  SWAP UNROT 4 ROLL\nC:C:A:D  [cost 4]  NIP ROT PICK3 UNROT\nD:C:A:D  [cost 2]  NIP PICK3\nA:D:A:D  [cost 3]  4 ROLL DUP2\nB:D:A:D  [cost 4]  2 UNPICK UNROT OVER\nC:D:A:D  [cost 4]  UNROT DROP UNROT OVER\nD:D:A:D  [cost 5]  4 ROLL DUP2 3 DUPN\nA:A:B:D  [cost 4]  DUP ROT 5 ROLL\nB:A:B:D  [cost 3]  OVER 5 ROLL\nC:A:B:D  [cost 3]  SWAP 4 ROLL\nD:A:B:D  [cost 3]  2 UNPICK PICK3\nA:B:B:D  [cost 4]  SWAP DUP 5 ROLL\nB:B:B:D  [cost 4]  SWAP DUPDUP 6 ROLL\nC:B:B:D  [cost 4]  DROP DUP 4 ROLL\nD:B:B:D  [cost 4]  DROP NIP DUP PICK3\nA:C:B:D  [cost 3]  UNROT 4 ROLL\nB:C:B:D  [cost 4]  DROP DUP2 5 ROLL\nC:C:B:D  [cost 4]  DROP ROT PICK3 UNROT\nD:C:B:D  [cost 2]  DROP PICK3\nA:D:B:D  [cost 4]  4 ROLL ROT OVER\nB:D:B:D  [cost 3]  DROP ROT DUP2\nC:D:B:D  [cost 4]  DROP SWAP UNROT OVER\nD:D:B:D  [cost 5]  DROP ROT DUP2 3 DUPN\nA:A:C:D  [cost 5]  DUP 4 ROLL 5 ROLL\nB:A:C:D  [cost 3]  ROT 4 ROLL\nC:A:C:D  [cost 4]  ROT DUP2 6 ROLL\nD:A:C:D  [cost 3]  UNROT DROP PICK3\nA:B:C:D  [cost 4]  SWAP ROT 4 ROLL\nB:B:C:D  [cost 5]  DROP DUP ROT 4 ROLL\nC:B:C:D  [cost 4]  DROP OVER 4 ROLL\nD:B:C:D  [cost 3]  DROP SWAP PICK3\nA:C:C:D  [cost 4]  ROT DUP 5 ROLL\nB:C:C:D  [cost 4]  DROP UNROT DUP ROT\nC:C:C:D  [cost 4]  ROT DUPDUP 6 ROLL\nD:C:C:D  [cost 3]  DROP2 DUP PICK3\nA:D:C:D  [cost 3]  NIP UNROT OVER\nB:D:C:D  [cost 3]  DROP UNROT OVER\nC:D:C:D  [cost 3]  DROP2 SWAP DUP2\nD:D:C:D  [cost 4]  DROP2 OVER 3 DUPN\nA:A:D:D  [cost 4]  DUP 5 ROLL DUP\nB:A:D:D  [cost 3]  4 ROLL DUP\nC:A:D:D  [cost 3]  NIP ROT DUP\nD:A:D:D  [cost 4]  4 ROLL DUP2 DUP\nA:B:D:D  [cost 4]  SWAP 4 ROLL DUP\nB:B:D:D  [cost 4]  DROP ROT DUP2 ROT\nC:B:D:D  [cost 3]  DROP ROT DUP\nD:B:D:D  [cost 4]  DROP ROT DUP2 DUP\nA:C:D:D  [cost 4]  ROT 4 ROLL DUP\nB:C:D:D  [cost 4]  DROP SWAP ROT DUP\nC:C:D:D  [cost 4]  DROP2 DUP ROT DUP\nD:C:D:D  [cost 3]  DROP2 OVER DUP\nA:D:D:D  [cost 3]  4 ROLL DUPDUP\nB:D:D:D  [cost 3]  DROP ROT DUPDUP\nC:D:D:D  [cost 3]  DROP2 SWAP DUPDUP\nD:D:D:D  [cost 4]  3 DROPN DUP DUPDUP<\/code><\/pre>\n\n\n\n
Python program used : Try it here<\/a><\/h2>\n\n\n\n
\"\"\"\nhp50g_solver.py\n===============\n\"\"\"\n\nfrom itertools import product as iproduct\nimport heapq\n\ndef DUP(s):  return [s[0]] + s     if len(s) >= 1 else None\ndef DUPDUP(s):  return [s[0], s[0]] + s  if len(s) >= 1 else None\ndef SWAP(s): return [s[1], s[0]] + s[2:] if len(s) >= 2 else None\ndef DROP(s): return s[1:]       if len(s) >= 1 else None\ndef OVER(s): return [s[1]] + s     if len(s) >= 2 else None\ndef ROT(s):  return [s[2]] + s[:2] + s[3:] if len(s) >= 3 else None\ndef UNROT(s):   return s[1:3] + [s[0]] + s[3:] if len(s) >= 3 else None\ndef DUP2(s): return [s[0], s[1]] + s  if len(s) >= 2 else None\ndef DROP2(s):   return s[2:]       if len(s) >= 2 else None\ndef PICK3(s):   return [s[2]] + s     if len(s) >= 3 else None\ndef NIP(s):  return [s[0]] + s[2:]    if len(s) >= 2 else None\n\ndef make_parametric_ops(max_n: int) -> dict:\n ops = {}\n for n in range(2, max_n + 1):\n  def make_roll(n=n):\n   def f(s): return [s[n-1]] + s[:n-1] + s[n:] if len(s) >= n else None\n   f.__name__ = f\"{n} ROLL\"; return f\n  def make_rolld(n=n):\n   def f(s): return s[1:n] + [s[0]] + s[n:] if len(s) >= n else None\n   f.__name__ = f\"{n} ROLLD\"; return f\n  def make_pick(n=n):\n   def f(s): return [s[n-1]] + s if len(s) >= n else None\n   f.__name__ = f\"{n} PICK\"; return f\n  def make_unpick(n=n):\n   def f(s): return s[1:n] + [s[0]] + s[n+1:] if len(s) > n else None\n   f.__name__ = f\"{n} UNPICK\"; return f\n  def make_dupn(n=n):\n   def f(s): return s[:n] + s if len(s) >= n else None\n   f.__name__ = f\"{n} DUPN\"; return f\n  def make_dropn(n=n):\n   def f(s): return s[n:] if len(s) >= n else None\n   f.__name__ = f\"{n} DROPN\"; return f\n  def make_ndupn(n=n):\n   def f(s): return [n] + [s[0]] * n + s[1:] if len(s) >= 1 else None\n   f.__name__ = f\"{n} NDUPN\"; return f\n  ops[f\"{n} ROLL\"]   = (make_roll(),   2)\n  ops[f\"{n} ROLLD\"]  = (make_rolld(),  2)\n  ops[f\"{n} PICK\"]   = (make_pick(),   2)\n  ops[f\"{n} UNPICK\"] = (make_unpick(), 2)\n  ops[f\"{n} DUPN\"]   = (make_dupn(),   2)\n  ops[f\"{n} DROPN\"]  = (make_dropn(),  2)\n  ops[f\"{n} NDUPN\"]  = (make_ndupn(),  2)\n return ops\n\nFIXED_OPS = {\n \"DUP\": (DUP, 1), \"DUPDUP\": (DUPDUP, 1), \"SWAP\":  (SWAP,  1),\n \"DROP\":   (DROP,   1), \"OVER\":   (OVER,   1), \"ROT\":   (ROT,   1),\n \"UNROT\":  (UNROT,  1), \"DUP2\":   (DUP2,   1), \"DROP2\": (DROP2, 1),\n \"PICK3\":  (PICK3,  1), \"NIP\": (NIP, 1),\n}\nPARAM_OPS = make_parametric_ops(8)\nALL_OPS   = {**FIXED_OPS, **PARAM_OPS}\n\nINITIAL  = ('A', 'B', 'C', 'D', '_5', '_6', '_7', '_8')\nSENTINEL = frozenset({'_5', '_6', '_7', '_8'})\nLETTERS  = ('A', 'B', 'C', 'D')\n\n# \u2500\u2500 Dijkstra \u2500\u2500\u2500\u2500\u2500\n\ndef solve_all(max_cost: int = 8) -> dict:\n all_targets = set(iproduct(LETTERS, repeat=4))\n solutions   = {}\n remaining   = set(all_targets)\n dist = {INITIAL: 0}\n counter = 0\n heap = [(0, counter, INITIAL, [])]\n\n while heap and remaining:\n  cur_cost, _, stack, path = heapq.heappop(heap)\n  if dist.get(stack, float('inf')) < cur_cost: continue\n  top4 = stack[:4]\n  if top4 in remaining and not any(e in SENTINEL for e in top4):\n   solutions[top4] = (cur_cost, path)\n   remaining.discard(top4)\n\n  if cur_cost >= max_cost: continue\n\n  for name, (fn, op_cost) in ALL_OPS.items():\n   new_cost = cur_cost + op_cost\n   if new_cost > max_cost: continue\n   new_stack_list = fn(list(stack))\n   if new_stack_list is None or len(new_stack_list) < 4: continue\n   new_stack = tuple(new_stack_list)\n   if new_cost < dist.get(new_stack, float('inf')):\n    dist[new_stack] = new_cost\n    counter += 1\n    heapq.heappush(heap, (new_cost, counter, new_stack, path + [name]))\n\n return solutions\n\ndef print_table(solutions: dict):\n letters = ['A', 'B', 'C', 'D']\n combos  = list(iproduct(letters, repeat=4))\n lines = []\n for combo in combos:\n  target_str = ':'.join(combo[::-1])\n  if combo in solutions:\n   cost, path = solutions[combo]\n   seq = ' '.join(path) if path else \"(identit\u00e9)\"\n   lines.append(f\"{target_str}  [cost {cost}]  {seq}\")\n  else:\n   lines.append(f\"{target_str}  [no solution]\")\n return lines\n\n\nsolutions = solve_all(max_cost=5)\nprint(\"Research in progress...\")\nlines = print_table(solutions)\nfor l in lines: print(l)\nfound = sum(1 for c in iproduct(LETTERS, repeat=4) if c in solutions)\nprint(f\"\\n{found}\/256 targets solved.\")<\/code><\/pre>\n\n\n\n
Optimizing a sequence<\/h2>\n\n\n\n
Can a sequence be simplified? For example, can rot drop over swap<\/strong> be written more simply? The answer is YES<\/strong>, in OVER 3 UNPICK<\/strong><\/p>\n\n\n\n
S\u00e9quence > rot drop over swap\n\n  S\u00e9quence entr\u00e9e : ROT DROP OVER SWAP\n  Co\u00fbt total      : 4\n  Effet sur pile  : D : B : B : A  (niveau 1 en bas)\n\n  Recherche d'optimisations (co\u00fbt \u2264 3)...\n  \u2713 1 optimisation(s) trouv\u00e9e(s) (co\u00fbt 3, gain -1) :\n\n    [3]  OVER 3 UNPICK\n\nS\u00e9quence > swap drop swap over\n\n  S\u00e9quence entr\u00e9e : SWAP DROP SWAP OVER\n  Co\u00fbt total      : 4\n  Effet sur pile  : D : A : C : A  (niveau 1 en bas)\n\n  Recherche d'optimisations (co\u00fbt \u2264 3)...\n  \u2713 1 optimisation(s) trouv\u00e9e(s) (co\u00fbt 3, gain -1) :\n\n    [3]  UNROT DROP OVER\n\nS\u00e9quence > swap rot drop2 dup dup\n\n  S\u00e9quence entr\u00e9e : SWAP ROT DROP2 DUP DUP\n  Co\u00fbt total      : 5\n  Effet sur pile  : D : A : A : A  (niveau 1 en bas)\n\n  Recherche d'optimisations (co\u00fbt \u2264 4)...\n  \u2713 1 optimisation(s) trouv\u00e9e(s) (co\u00fbt 3, gain -2) :\n\n    [3]  UNROT DROP2 DUPDUP<\/code><\/pre>\n\n\n\n
Pyhon program<\/h2>\n\n\n\n
\"\"\"\nhp50g_optimizer.py\n==================\nTrouve une s\u00e9quence \u00e9quivalente mais plus courte (moins co\u00fbteuse) \u00e0 une\ncommande HP50g donn\u00e9e en entr\u00e9e.\n\nUsage :\n    python hp50g_optimizer.py\n    > Entrez une s\u00e9quence : SWAP OVER SWAP\n    > R\u00e9sultats...\n\"\"\"\n\nfrom itertools import product as iproduct\nimport heapq\nimport sys\n\n# \u2500\u2500 Op\u00e9rations de pile \u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\n\ndef DUP(s):    return [s[0]] + s          if len(s) >= 1 else None\ndef DUPDUP(s): return [s[0], s[0]] + s    if len(s) >= 1 else None\ndef SWAP(s):   return [s[1], s[0]] + s[2:]if len(s) >= 2 else None\ndef DROP(s):   return s[1:]               if len(s) >= 1 else None\ndef OVER(s):   return [s[1]] + s          if len(s) >= 2 else None\ndef ROT(s):    return [s[2]] + s[:2] + s[3:] if len(s) >= 3 else None\ndef UNROT(s):  return s[1:3] + [s[0]] + s[3:] if len(s) >= 3 else None\ndef DUP2(s):   return [s[0], s[1]] + s    if len(s) >= 2 else None\ndef DROP2(s):  return s[2:]               if len(s) >= 2 else None\ndef PICK3(s):  return [s[2]] + s          if len(s) >= 3 else None\ndef NIP(s):    return [s[0]] + s[2:]      if len(s) >= 2 else None\n\ndef make_parametric_ops(max_n: int) -> dict:\n    ops = {}\n    for n in range(2, max_n + 1):\n        def make_roll(n=n):\n            def f(s): return [s[n-1]] + s[:n-1] + s[n:] if len(s) >= n else None\n            f.__name__ = f\"{n} ROLL\"; return f\n        def make_rolld(n=n):\n            def f(s): return s[1:n] + [s[0]] + s[n:] if len(s) >= n else None\n            f.__name__ = f\"{n} ROLLD\"; return f\n        def make_pick(n=n):\n            def f(s): return [s[n-1]] + s if len(s) >= n else None\n            f.__name__ = f\"{n} PICK\"; return f\n        def make_unpick(n=n):\n            def f(s): return s[1:n] + [s[0]] + s[n+1:] if len(s) > n else None\n            f.__name__ = f\"{n} UNPICK\"; return f\n        def make_dupn(n=n):\n            def f(s): return s[:n] + s if len(s) >= n else None\n            f.__name__ = f\"{n} DUPN\"; return f\n        def make_dropn(n=n):\n            def f(s): return s[n:] if len(s) >= n else None\n            f.__name__ = f\"{n} DROPN\"; return f\n        def make_ndupn(n=n):\n            def f(s): return [n] + [s[0]] * n + s[1:] if len(s) >= 1 else None\n            f.__name__ = f\"{n} NDUPN\"; return f\n        ops[f\"{n} ROLL\"]   = (make_roll(),   2)\n        ops[f\"{n} ROLLD\"]  = (make_rolld(),  2)\n        ops[f\"{n} PICK\"]   = (make_pick(),   2)\n        ops[f\"{n} UNPICK\"] = (make_unpick(), 2)\n        ops[f\"{n} DUPN\"]   = (make_dupn(),   2)\n        ops[f\"{n} DROPN\"]  = (make_dropn(),  2)\n        ops[f\"{n} NDUPN\"]  = (make_ndupn(),  2)\n    return ops\n\nFIXED_OPS = {\n    \"DUP\":    (DUP,    1), \"DUPDUP\": (DUPDUP, 1), \"SWAP\":  (SWAP,  1),\n    \"DROP\":   (DROP,   1), \"OVER\":   (OVER,   1), \"ROT\":   (ROT,   1),\n    \"UNROT\":  (UNROT,  1), \"DUP2\":   (DUP2,   1), \"DROP2\": (DROP2, 1),\n    \"PICK3\":  (PICK3,  1), \"NIP\":    (NIP,    1),\n}\nPARAM_OPS = make_parametric_ops(8)\nALL_OPS   = {**FIXED_OPS, **PARAM_OPS}\n\n# \u2500\u2500 Pile initiale \u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\n\nINITIAL  = ('A', 'B', 'C', 'D', '_5', '_6', '_7', '_8')\nSENTINEL = frozenset({'_5', '_6', '_7', '_8'})\n\n# \u2500\u2500 Parsing de la s\u00e9quence entr\u00e9e \u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\n\ndef parse_sequence(raw: str) -> list[str] | None:\n    \"\"\"\n    Convertit une cha\u00eene comme \"SWAP OVER SWAP\" en liste de noms d'op\u00e9rations.\n    Retourne None si un token est inconnu.\n    Les noms sont normalis\u00e9s en majuscules.\n    \"\"\"\n    tokens = raw.upper().split()\n    result = []\n    i = 0\n    while i < len(tokens):\n        # Essai de token double : \"2 ROLL\", \"3 PICK\", etc.\n        if i + 1 < len(tokens):\n            candidate2 = tokens[i] + \" \" + tokens[i+1]\n            if candidate2 in ALL_OPS:\n                result.append(candidate2)\n                i += 2\n                continue\n        candidate1 = tokens[i]\n        if candidate1 in ALL_OPS:\n            result.append(candidate1)\n            i += 1\n        else:\n            print(f\"  \u2717 Op\u00e9ration inconnue : '{tokens[i]}'\")\n            return None\n    return result\n\ndef sequence_cost(ops: list[str]) -> int:\n    return sum(ALL_OPS[op][1] for op in ops)\n\n# \u2500\u2500 Application d'une s\u00e9quence sur une pile \u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\n\ndef apply_sequence(ops: list[str], stack: tuple) -> tuple | None:\n    s = list(stack)\n    for name in ops:\n        fn, _ = ALL_OPS[name]\n        s = fn(s)\n        if s is None:\n            return None\n    return tuple(s)\n\n# \u2500\u2500 Dijkstra : cherche toutes les s\u00e9quences <= max_cost atteignant target \u2500\u2500\u2500\u2500\u2500\n\ndef find_optimizations(target: tuple, max_cost: int, min_results: int = 1) -> list[tuple]:\n    \"\"\"\n    Retourne une liste de (cost, path) atteignant `target` depuis INITIAL,\n    avec cost <= max_cost, tri\u00e9es par co\u00fbt croissant.\n    S'arr\u00eate d\u00e8s que min_results solutions sont trouv\u00e9es au co\u00fbt minimal.\n    \"\"\"\n    solutions = []\n    best_cost = None\n\n    dist    = {INITIAL: 0}\n    counter = 0\n    heap    = [(0, counter, INITIAL, [])]\n\n    while heap:\n        cur_cost, _, stack, path = heapq.heappop(heap)\n\n        if dist.get(stack, float('inf')) < cur_cost:\n            continue\n        if best_cost is not None and cur_cost > best_cost:\n            break\n\n        # La profondeur utile est celle des \u00e9l\u00e9ments non-sentinelles\n        stack_depth = len([e for e in stack if e not in SENTINEL])\n\n        # On compare uniquement la partie \"utile\" de la pile avec la cible\n        useful = tuple(e for e in stack if e not in SENTINEL)\n        target_useful = tuple(e for e in target if e not in SENTINEL)\n\n        if useful == target_useful and cur_cost > 0:\n            solutions.append((cur_cost, path))\n            best_cost = cur_cost\n            if len(solutions) >= min_results:\n                continue   # continue \u00e0 drainer le m\u00eame niveau de co\u00fbt\n\n        if cur_cost >= max_cost:\n            continue\n\n        for name, (fn, op_cost) in ALL_OPS.items():\n            new_cost = cur_cost + op_cost\n            if new_cost > max_cost:\n                continue\n            new_stack_list = fn(list(stack))\n            if new_stack_list is None:\n                continue\n            new_stack = tuple(new_stack_list)\n            if new_cost < dist.get(new_stack, float('inf')):\n                dist[new_stack] = new_cost\n                counter += 1\n                heapq.heappush(heap, (new_cost, counter, new_stack, path + [name]))\n\n    return solutions\n\n# \u2500\u2500 Interface \u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\n\ndef main():\n    print(\"=\" * 60)\n    print(\"  HP50g Stack Sequence Optimizer\")\n    print(\"  Entrez une s\u00e9quence d'op\u00e9rations pour trouver un\")\n    print(\"  \u00e9quivalent plus court. Ex: SWAP OVER SWAP\")\n    print(\"  (op\u00e9rations param\u00e9triques : '2 ROLL', '3 PICK', ...)\")\n    print(\"  Tapez 'quitter' pour sortir.\")\n    print(\"=\" * 60)\n\n    while True:\n        print()\n        try:\n            raw = input(\"S\u00e9quence > \").strip()\n        except (EOFError, KeyboardInterrupt):\n            print(\"\\nAu revoir.\")\n            break\n\n        if raw.lower() in (\"quitter\", \"quit\", \"exit\", \"q\"):\n            print(\"Au revoir.\")\n            break\n        if not raw:\n            continue\n\n        # Parsing\n        ops = parse_sequence(raw)\n        if ops is None:\n            continue\n        if not ops:\n            print(\"  (s\u00e9quence vide)\")\n            continue\n\n        input_cost = sequence_cost(ops)\n        print(f\"\\n  S\u00e9quence entr\u00e9e : {' '.join(ops)}\")\n        print(f\"  Co\u00fbt total      : {input_cost}\")\n\n        # Application sur la pile initiale\n        target = apply_sequence(ops, INITIAL)\n        if target is None:\n            print(\"  \u2717 La s\u00e9quence \u00e9choue sur la pile initiale (pile insuffisante ?).\")\n            continue\n\n        # Pile r\u00e9sultante (partie lisible)\n        readable = [e for e in target if e not in SENTINEL]\n        print(f\"  Effet sur pile  : {' : '.join(readable[::-1])}  (niveau 1 en bas)\")\n\n        # Cas identit\u00e9\n        if tuple(e for e in target if e not in SENTINEL) == ('A', 'B', 'C', 'D'):\n            print(\"  \u26a0  La s\u00e9quence est une identit\u00e9 (ne modifie pas la pile).\")\n\n        max_search = input_cost - 1\n        if max_search <= 0:\n            print(\"  \u2713 S\u00e9quence d\u00e9j\u00e0 de co\u00fbt minimal (1), aucune optimisation possible.\")\n            continue\n\n        print(f\"\\n  Recherche d'optimisations (co\u00fbt \u2264 {max_search})...\")\n        solutions = find_optimizations(target, max_cost=max_search, min_results=5)\n\n        if not solutions:\n            print(\"  \u2713 Aucune s\u00e9quence plus courte trouv\u00e9e \u2014 d\u00e9j\u00e0 optimale !\")\n        else:\n            best = solutions[0][0]\n            gain = input_cost - best\n            print(f\"  \u2713 {len(solutions)} optimisation(s) trouv\u00e9e(s) (co\u00fbt {best}, gain -{gain}) :\\n\")\n            for cost, path in solutions:\n                seq = ' '.join(path) if path else \"(identit\u00e9 \u2014 ne rien faire)\"\n                print(f\"    [{cost}]  {seq}\")\n\nif __name__ == \"__main__\":\n    main()\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
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. … Continuer la lecture →<\/span><\/a><\/p>\n","protected":false},"author":4913,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[9],"tags":[],"class_list":["post-2094","post","type-post","status-publish","format-standard","hentry","category-hp"],"_links":{"self":[{"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/posts\/2094","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/users\/4913"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/comments?post=2094"}],"version-history":[{"count":10,"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/posts\/2094\/revisions"}],"predecessor-version":[{"id":2104,"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/posts\/2094\/revisions\/2104"}],"wp:attachment":[{"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/media?parent=2094"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/categories?post=2094"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/tags?post=2094"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}