Algorithms for RPN Calculators (HP49/50g version)

Publié le par 
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()
Publié dans HP

Jouons avec les dictionnaires

Publié le par

Voici quelques jeux de mots originaux inspirés du fil de Adam Aaronson sur X. Le principe : appliquer des critères mathématiques ou visuels à des listes de mots français classés par longueur (de 2 à 15 lettres) pour trouver des champions inattendus.

Nous aurons besoin de dictionnaires (mots de 2 lettres à 15 lettres), les voici de façon séparés.

Mot qui parcourt la plus longue distance dans l’alphabet

En parcourant un mot lettre à lettre, on mesure la distance alphabétique entre chaque paire de lettres consécutives. Plus les lettres sautent loin dans l’alphabet, plus le score est élevé.

Exemple : « AXA » — de A à X, il y a 23 pas, puis 23 de retour de X à A, soit une distance totale de 46.
Objectif : trouver, pour chaque longueur, le mot cumulant la plus grande distance alphabétique.

Vous devriez trouver :

2 : AY (24)
3 : AXA (46)
4 : AXAT (65)
5 : RAYAT (84)
6 : ZEZAYA (115)
7 : ZEZAYAT (134)
8 : ZEZAYANT (134)
9 : ZEZAYATES (163)
10 : ZEZAYASSES (161)
11 : ZEZAYASSIEZ (168)
12 : REHYDRATATES (171)
13 : PARAPHRASATES (183)
14 : REVASCULARISAT (196)
15 : REVASCULARISERA (203)

La famille des « zézayer » (parler en substituant des « z » aux « j » ou « s ») domine largement les mots courts grâce à l’alternance entre Z, la dernière lettre, et des lettres du début de l’alphabet.

def score(mot):
    return sum(abs(ord(b) - ord(a)) for a, b in zip(mot, mot[1:]))

for i in range(2, 16):
    with open(f"dic{i}.txt") as f:
        mots = [line.strip() for line in f if line.strip()]

    solution = max(mots, key=score)

    print(f"{len(solution)} : {solution} ({score(solution)})")

Mots les plus étroits

Tous les caractères n’ont pas la même largeur à l’écran. En police Arial 16 px, un « i » ou un « l » occupe bien moins d’espace qu’un « m » ou un « w ». Quel mot, pour chaque longueur, tient dans le moins de pixels possible ?
Exemple : « il » écrit en Arial prend moins de place que « ma ».
Objectif : trouver, pour chaque longueur, le mot le plus étroit.

Vous devriez trouver :

2 : il (7.1)
3 : fil (11.55)
4 : fifi (16.0)
5 : flirt (21.33)
6 : rififi (24.88)
7 : jaillit (31.1)
8 : titiller (37.33)
9 : titillait (40.0)
10 : liliiflore (48.88)
11 : titillerait (54.23)
12 : illisibilite (58.65)
13 : illisibilites (66.65)
14 : infaillibilite (72.9)
15 : infaillibiliste (80.9)

Les lettres i, l, f et t sont les grandes gagnantes — et il n’est pas surprenant qu’« illisibilité » apparaisse dans le palmarès, un mot presque fait sur mesure pour ce défi !

Largeurs des lettres en Arial 16px : 

# poids des lettres a → z
w = [8.9, 8.9, 8.0, 8.9, 8.9, 4.45, 8.9, 8.9, 3.55, 3.55,
     8.0, 3.55, 13.3, 8.9, 8.9, 8.9, 8.9, 5.33, 8.0, 4.45,
     8.9, 8.0, 11.6, 8.0, 8.0, 8.0]

# fonction de score d’un mot
def score(mot):
    return sum(w[ord(c) - 65] for c in mot)  # A=65

# parcours des fichiers
for i in range(2, 16):
    with open(f"dic{i}.txt") as f:
        mots = [line.strip() for line in f if line.strip()]

    # mot avec score minimal
    solution = min(mots, key=score)

    print(f"{len(solution)} : {solution.lower()} ({score(solution)})")

Mots avec les lettres les plus éloignées dans l’alphabet

Cette fois, on s’intéresse non plus aux sauts entre lettres consécutives, mais à la position absolue de chaque lettre dans l’alphabet. Z vaut 26, A vaut 1. Quel mot affiche la moyenne de position la plus haute ?
Exemple : « ZUT » → Z (26) + U (21) + T (20) = 67, moyenne = 22,33.
Objectif : trouver, pour chaque longueur, le mot dont les lettres occupent en moyenne la position la plus haute dans l’alphabet.

Vous devriez trouver :

2 : WU (22.00)
3 : ZUT (22.33)
4 : YUZU (23.25)
5 : TUTUS (20.20)
6 : YOUYOU (20.33)
7 : YOUYOUS (20.14)
8 : SURTOUTS (19.12)
9 : TURLUTUTU (19.33)
10 : VOUSSOYONS (18.40)
11 : YOUYOUTIONS (18.09)
12 : YOUYOUTERONT (17.83)
13 : YOUYOUTERIONS (17.08)
14 : YOUYOUTASSIONS (17.00)
15 : POURSUIVISSIONS (16.33)

Le youyou (petit canot à rames) et ses conjugaisons s’imposent dans presque toutes les longueurs — preuve que Y, U et O sont redoutables à ce jeu-là.

def score(mot):
    return sum(ord(c) - 64 for c in mot)

for i in range(2, 16):
    with open(f"dic{i}.txt") as f:
        mots = [line.strip() for line in f if line.strip()]

    solution = max(mots, key=score)
    moyenne = score(solution) / i

    print(f"{len(solution)} : {solution} ({moyenne:.2f})")

Mots écrits avec les n premières lettres de l’alphabet

Nouveau défi : construire des mots en se limitant à un sous-ensemble restreint de l’alphabet. On part des deux premières lettres — A et B — et on en ajoute une à chaque étape jusqu’à la quatorzième. La question est simple : quel est le mot le plus long que l’on peut écrire en n’utilisant que ces lettres-là ?

Avec seulement A et B, on est vite à court d’options : « baba » fait figure de champion avec ses quatre lettres. En ajoutant le C, « cacaba » s’impose avec six lettres. Mais attention — élargir le répertoire ne garantit pas toujours un mot plus long : « cacaba » résiste aussi à l’arrivée du D, et « dédicacée » règne sans partage sur les niveaux 9, 10 et 11.

Les vrais coups de théâtre arrivent plus tard. À 13 lettres disponibles, le lauréat inattendu est « hamamelidacée » — l’hamamélis, cet arbuste aux fleurs d’hiver — avec 13 lettres. Et à 14 lettres, « magdalénienne » lui fait jeu égal.

Vous devriez trouver :

2 (AB) : baba (4)
3 (ABC) : cacaba (6)
4 (ABCD) : cacaba (6)
5 (ABCDE) : abcedee (7)
6 (ABCDEF) : abcedee (7)
7 (ABCDEFG) : affeagee (8)
8 (ABCDEFGH) : debachage (9)
9 (ABCDEFGHI) : acidifiai (9)
10 (ABCDEFGHIJ) : acidifiai (9)
11 (ABCDEFGHIJK) : acidifiai (9)
12 (ABCDEFGHIJKL) : acidifiable (11)
13 (ABCDEFGHIJKLM) : hamamelidacee (13)
14 (ABCDEFGHIJKLMN) : academicienne (13)

def score(mot, n):
    lettres_autorisees = set("abcdefghijklmnopqrstuvwxyz"[:n])
    return all(c in lettres_autorisees for c in mot.lower())

for n in range(2, 15):
    meilleur = ""
    for i in range(2, 16):
        with open(f"dic{i}.txt") as f:
            mots = [line.strip() for line in f if line.strip()]

        candidats = [m for m in mots if score(m, n)]
        if candidats:
            plus_long = max(candidats, key=len)
            if len(plus_long) > len(meilleur):
                meilleur = plus_long

    lettres = "abcdefghijklmnopqrstuvwxyz"[:n].upper()
    print(f"{n} ({lettres}) : {meilleur.lower()} ({len(meilleur)})")

Mot avec le moins de lettres différentes, pour chaque longueur

Écrire long en variant peu : c’est le défi de ce nouveau challenge. Pour chaque longueur de mot, on cherche celui qui se contente du plus petit alphabet personnel — autrement dit, celui dont les lettres se répètent le plus.

Avec deux lettres, « AA » n’en utilise qu’une seule. Avec trois, « MMM » fait pareil. Mais à partir de quatre lettres, l’exercice se complique : difficile de faire un vrai mot français avec une seule lettre répétée quatre fois. « ALLA » et « ERRER » s’en tirent avec deux lettres distinctes seulement.

La résistance dure longtemps : il faut atteindre les mots de onze lettres pour qu’une quatrième lettre s’invite enfin dans le palmarès. Et même à quinze lettres, « assassinassions » n’en mobilise que cinq — une économie remarquable pour un mot aussi long.

Vous devriez trouver :

2 : AA (1)
3 : MMM (1)
4 : ALLA (2)
5 : ERRER (2)
6 : ETETEE (2)
7 : AMASSAS (3)
8 : GNANGNAN (3)
9 : BLABLABLA (3)
10 : RESSERREES (3)
11 : ASSAGISSAIS (4)
12 : ASSAINISSAIS (4)
13 : ARRERAGEASSES (5)
14 : EINSTEINIENNES (5)
15 : ASSASSINASSIONS (5)

def score(mot):
    return len(set(mot))

for i in range(2, 16):
    with open(f"dic{i}.txt") as f:
        mots = [line.strip() for line in f if line.strip()]

    solution = min(mots, key=score)

    print(f"{i} : {solution} ({score(solution)})")

Quelques visuels basés sur le Kezako n°7 (forum Silicium)

Publié le par

Dans les automates élémentaires de Wolfram on ne considère que 3 cases et non pas 5 comme dans le post de @Marge. Avec 3 cases on a 8 combinaisons 111,110,101,100,011,010,001,000 et pour chacune de ces combinaisons on décide si la case centrale (par exemple 111) sera en vie ou morte à l’étape suivante. Ca fait 28 = 256 possibilités. Avec 5 cases, si on ne regarde plus seulement le nombre de voisins vivants mais toutes les combinaisons possibles 11111,11110,…, 00010,00001 soit 32 combinaisons et que l’on décide pour chacune ce que devient la cellule centrale (par exemple 11100) à l’étape suivante, ça fait 232= 4294967296 combinaisons ! Donc il y a certainement plein de motifs intéressants à découvrir si on ne se borne pas à juste compter les voisins vivants

Le cas particulier de @Marge parmi les 4294967296 combinaisons correspond au nombre 393113224 :

from kandinsky import *
from random import randint

T = 2

def go(r = 393113224):
  lig = 220 // T
  col = 320 // T
  
  # première ligne aléatoire
  for x in range(col):
    if randint(0,1) == 1:
      fill_rect(T*x,0,T,T,(0,0,0))
  
  rb = "0"*32 + bin(r)[2:]       # règle binaire (32 bits)

  for y in range(lig):
    for x in range(2,col-2):

      n = (
      16*ecran(x-2,y) +
       8*ecran(x-1,y) +
       4*ecran(x,y) +
       2*ecran(x+1,y) +
         ecran(x+2,y)
      )

      if rb[-1-n] == "1":
        fill_rect(T*x, T*(y+1), T, T, (0,0,0))


def ecran(x,y):
  v = sum(get_pixel(T*x,T*y))
  return 1 if v == 0 else 0

go()

Voici quelques visuels supplémentaires à ceux donnés sur le forum :

go(972801)
go(830575)
go(230954)
go(826660)
go(816895)
go(522517)

Quelques visuels en Uiua

Publié le par

Il y a quelques années j’avais fait ce programme Python donnant quelques visuels sympas : https://my.numworks.com/python/schraf/cmplx

En recherchant sur le web, je suis tombé sur https://jcmorrow.com/mandelbrot/ qui propose une écriture en Uiua de la célèbre fractale. Cela m’a permis de créer la fractale Julia et aidé à la traduction du programme Python : 

Phase! ← ◿₁÷π∠°ℂ^⊞ℂ∩⌞+×÷⟜⇡600

Exemple 1 : f(z) = z / (1 – z)

Phase!(÷⊸˜-1) 1.4 ¯0.8 ¯0.2

Exemple 2 : f(z) = (z – 1) / (z ** 2 + z + 1)

Phase!(÷⊃(+˙×⤙+1|-1)) 4 ¯2 ¯1

Challenges en langage Uiua (D’après les MPO du forum Silicium)

Publié le par

Initiation au langage Uiua

🧩 Challenge 4 : Périmètre et surface d’un rectangle

🎯 Énoncé

Soit un rectangle de côté a et b.

Avec a et b respectivement sur la pile, faire un programme qui sort le Périmètre du rectangle et la Surface du rectangle.

Les formules utilisées sont :

  • Périmètre : P = 2(a+b)
  • Surface : S = a × b

🔑 Mots-clés Uiua

⊃ – Appeler deux fonctions sur une même valeur
×₂ – Multiplier par 2

🧠 Solution Uiua

CHA₄ ← ×₂⊃+×

🔍 Explications

La fonction CHA₄ est conçue pour calculer à la fois la surface et le périmètre d’un rectangle à partir des longueurs de ses côtés, en laissant les deux résultats sur la pile.

L’opérateur ⊃ permet d’appliquer les deux calculs et de conserver la Surface et le Périmètre sur la pile dans l’ordre requis par l’énoncé.

  1. Calcul de la Surface : L’opérateur × (multiplication) calcule la surface (S=a×b).
  2. Calcul du Périmètre : L’opérateur + (addition) calcule d’abord la somme des côtés (a+b), puis le résultat est multiplié par 2 (×₂).

🧾 Exemples

Pour les entrées 3 et 4, la fonction donne les résultats suivants :

CHA₄ 3 4

Résultats :
12 # Surface
14 # Périmètre

🧩 Challenge 8 : Chaîne

🎯 Énoncé

Faire un programme qui inverse l’ordre des caractères d’une chaine et qui, en plus, transforme l’ensemble en minuscules.

Exemple : « sILiCIuM » donne « muicilis ».

🔑 Mots-clés Uiua

⇌ – Inverser la chaine, un vecteur ou les lignes d’un tableau
⌵ – Mettre en majuscules
¯ – Inverser la casse

🧠 Solution Uiua

CHA₈ ← ¯⌵⇌

🔍 Explications

Le programme inverse d’abord la chaîne (⇌), la met ensuite entièrement en majuscules (⌵), puis utilise l’opérateur d’inversion de casse (¯). L’inversion de casse (¯) permet de transformer toutes les majuscules résultantes en minuscules.

🧾 Exemples

CHA₈ "sILiCIuM"
→ "muicilis"

🧩 Challenge N°9 : Somme des chiffres d’un nombre

🎯 Énoncé

Soit un nombre entier positif sur la pile. Le programme doit calculer la somme de ses chiffres.

Exemple : 352791 doit retourner 27.

🔑 Mots-clés Uiua

⊥₁₀ – Décomposition du nombre en chiffres
/+ – Addition/Somme des éléments d’un vecteur

🧠 Solution Uiua

CHA₉ ← /+⊥₁₀

🔍 Explications

La fonction CHA₉ est conçue pour réaliser la somme des chiffres d’un nombre.

  1. Décomposition : L’opérateur ⊥₁₀ prend le nombre entier positif en entrée et réalise sa décomposition en chiffres (base 10).
  2. Sommation : L’opérateur /+ est ensuite appliqué pour effectuer la somme de tous les chiffres obtenus dans la liste (réduction par l’addition).

🧾 Exemple

Pour le nombre 352791, la fonction donne le résultat suivant :

CHA₉ 352791

Résultat : 27

🧩 Challenge 13 : Aire d’un triangle

🎯 Énoncé

Écrire un programme qui permet de calculer la surface d’un triangle quelconque.

Le calcul de l’aire S d’un triangle quelconque, en ne connaissant que les longueurs a, b et c de ses trois côtés, est permis par la formule de Héron.

La formule est vue comme √(s(s-a)(s-b)(s-c)), où s est la demi-somme des côtés.

🔑 Mots-clés Uiua

÷₂ – Diviser par 2
⊂ – Joindre 2 éléments (scalaires, vecteurs…)
/× – Produit des éléments d’un vecteur

🧠 Solution Uiua

CHA₁₃ ← √/×-⊂0⟜(÷₂/+)

🔍 Explications

La solution implémente la formule de Héron, qui est exprimée dans les sources comme \sqrt{(s-a)(s-b)(s-c)(s-0)}

La fonction se décompose comme suit :

  1. Calcul du demi-périmètre (s): La partie (÷₂/+) calcule la demi-somme (s) des longueurs des côtés a, b, et c.
  2. Préparation du vecteur pour la soustraction: L’opération ⊂0⟜ maintient le vecteur initial des côtés (a,b,c) (⟜) et lui ajoute le nombre 0 (⊂0).
  3. Soustraction et création des termes: L’opérateur – (soustraction) est ensuite appliqué pour créer les termes (a−s),(b−s),(c−s) et (0−s).
  4. Calcul final de l’aire: Enfin, l’opération √/× réalise le produit des quatre termes et applique la racine carrée au résultat.

🧾 Exemples

Pour les entrées 4_5_6 et 3_4_5, la fonction donne les résultats suivants :

∩CHA₁₃ 4_5_6 3_4_5

Résultats :
• 6 (pour un triangle de côtés 3, 4, 5)
• 9.921567416492215 (pour un triangle de côtés 4, 5, 6)

🧩 Challenge 57 : Inversion–Addition

🎯 Énoncé

À partir d’un entier, inverse ses chiffres, additionne les deux nombres, puis recommence jusqu’à obtenir un palindrome (un nombre identique à l’envers).
Affiche le palindrome obtenu.

➡️ Bonus : trouver le premier nombre (le plus petit) qui ne génère jamais de palindrome — c’est un nombre de Lychrel.

Exemple
78 → 78 + 87 = 165
165 + 561 = 726
726 + 627 = 1353
1353 + 3531 = 4884 ✅ (palindrome)

🔑 Mots-clés Uiua

⊥₁₀ – convertir un nombres en chiffres décimaux
⍜ f g – effectuer l’opération f sur un tableau, puis g puis inverse la transformation f
⊸ – garder la valeur initiale sur la pile
⍢(action|test) – boucle : répéter une action tant qu’un test est vrai

🧠 Solution Uiua

Rev   ← ⊸⍜⊥₁₀⇌
CHA₅₇ ← ⍢(+Rev|≠Rev)

🔍 Explications

⊥₁₀ : convertit un nombre en liste de chiffres
⇌ : inverse la liste
⍜ ⊥₁₀ ⇌ : transformation ⊥₁₀ puis ⇌ et enfin transformation inverse de ⊥₁₀ (Chiffres en nombre)
⊸ : conserve le nombre d’origine
⍢(+Rev|≠Rev) : additionne avec l’inverse tant qu’on n’a pas de palindrome

🧾 Exemples

≡CHA₅₇ 165_59_89
→ [4884 1111 8813200023188]

CHA₅₇ 196
→ Error: Cannot take base of ∞

🧩 Challenge N°74 : Cubes en folie

🎯 Énoncé

Trouver tous les nombres taxi (taxicab number) inférieurs à 40000 [1].

L’origine de ce défi est célèbre : En 1919, G.H. Hardy a mentionné à Srinivasa Ramanujan que le numéro de son taxi, 1729, lui semblait banal. Ramanujan répondit qu’il s’agissait au contraire du plus petit nombre exprimable comme somme de deux cubes de deux façons .

Exemple célèbre

1729 = 1³ + 12³ = 9³ + 10³

🔑 Mots-clés Uiua

ⁿ3 ou ⁿ₃ – Calculer la puissance 3 (au cube)
⇡₁ – Générer un intervalle d’entiers, de 1 à N
˙⊞+ – Opérateur qui gère la duplication et la construction de la table de toutes les additions possibles des différents couples.
⊛♭ – Opérateur qui aplatit le tableau et assigne un index unique à chaque valeur
⊸ – Garder la valeur initiale sur la pile
⊕(>2⧻) – Grouper les éléments par leurs index, puis pour chaque groupe, compter (⧻) le nombre d’occurrences et tester s’il y en a plus que 2 (>2)
▽ – Garder (filtrer) les valeurs concernées

🧠 Solution Uiua

CHA₇₄ ← ▽⊕(>2⧻)⊸⊸⊛♭˙⊞+ⁿ₃⇡₁

🔍 Explications

La fonction CHA₇₄ est conçue pour identifier les nombres qui apparaissent au moins deux fois comme somme de deux cubes, en limitant la recherche par le paramètre N (dans l’exemple, N=35 permet de trouver les nombres taxi sous 40000).

  • ⁿ₃⇡₁ N : Cette partie calcule les puissances 3 des entiers allant de 1 jusqu’à N.
  • ˙⊞+ : Elle génère un tableau de toutes les sommes possibles en additionnant les couples de cubes obtenus.
  • ⊛♭ : L’opérateur .♭ aplatit ce tableau de sommes, et l’opérateur ⊛ assigne ensuite un index unique à chaque valeur.
  • ⊕(>2⧻) : C’est le cœur de la détection : les nombres sont groupés (⊕) selon leur index.

🧩 Challenge N°116 : Le défi du Rami en chiffres

🎯 Énoncé

Dans ce mini-jeu nommé RamiSum, les seules combinaisons valables sont celles avec au moins 3 nombres identiques .

Mission :

  • En entrée : Un nombre composé de chiffres entre 1 et 9, de taille arbitraire.
  • En sortie : Le score maximum que l’on peut obtenir, ou 0 si aucun coup n’est possible.

Exemples de combinaisons valables :

  • Pour le tirage 84884284, les combinaisons valables sont 888, 8888 et 444.
  • Pour le tirage 123456, on ne peut pas jouer.

🔑 Mots-clés Uiua

⊛ – Opérateur qui assigne des index uniques aux valeurs d’un tableau.
⊕ – Grouper les éléments.
⧻ – Compter le nombre d’occurrences ou la longueur d’un groupe.
⊢ – Garder le premier élément d’un vecteur.
>₂ – Tester si la valeur est supérieure à 2.
/↥ – Récupérer le maximum des éléments.

🧠 Solution Uiua

CHA₁₁₆ ← /↥××⊸>₂⊕⊃⧻⊢⊸⊛⊥₁₀

🔍 Explications

La fonction CHA₁₁₆ calcule le score maximum en identifiant les chiffres répétés au moins trois fois, puis en multipliant leur valeur par le nombre de fois où ils peuvent.

⊸⊛⊥₁₀ 84884284
[4 8 2 4 8 8 4 8]
[0 1 2 0 1 1 0 1]		# Il y a 3 chiffres différents (4, 8, 2) indexés par 0, 1 et 2

⊕⊃⧻⊢⊸⊛⊥₁₀ 84884284

[4 8 2]
[3 4 1]	# il y a 3 fois "4", 4 fois "8" et 1 fois "2"

⊸>₂⊕⊃⧻⊢⊸⊛⊥₁₀ 84884284
[4 8 2]	# il n'y a que des 4, 8 et 2
[3 4 1]	# 3 fois le "4", 4 fois le "8", 1 fois le "2"
[1 1 0]	# On ne garde que 3 et 4 car 1 < 3

On multiplie les 3 vecteurs pour obtenir les scores (××) et on récupère le maximum (/↥).

🧩 Challenge 142 : Nombres de Diophante

🎯 Énoncé

Trouver quatre nombres entiers tels que le produit de deux quelconques de ces nombres soit un carré moins un .

Il y a une infinité de quadruplets (a, b, c, d) tels que ab+1, ac+1, ad+1, bc+1 et cd+1 soient des carrés parfaits.

En particulier, cette condition est remplie par le quadruplet paramétrique (k-1, k+1, 4k, 4k(4k²-1)) pour tout k > 1.

🔑 Mots-clés Uiua

⇡₂ – Ajouter 2 à l’intervalle de base (décalage)
⊃ – Appeler 2 fonctions sur une même valeur
⟜ – Garder la valeur initiale en haut de la pile
⊸⊸∘ – Double duplication
⊟₄ – Combiner 4 vecteurs en une matrice
× – Multiplication
⍉ – Transposée
⇌ – Inverser l’ordre des lignes

🧠 Solution Uiua

CHA₁₄₂ ← ⍉⇌⊟₄ ×-1×⟜(⊸⊸∘⊃(×4|⊃+-1))⇡₂

🔍 Explications

Le code Uiua est conçu pour générer la série de quadruplets (k−1,k+1,4k,4k(4k² −1)).
• ⇡₂ N : Cette fonction prend N en entrée et génère un intervalle auquel elle ajoute 2, produisant la liste [2,3,4,…,N+1].
• ⊃(×4|⊃+-1) : Cet opérateur structuré est utilisé pour appliquer deux actions distinctes : la multiplication par 4 (×4), et les opérations d’ajout et soustraction de 1 (⊃+-1).
• ⟜(⊸⊸∘⊃(×4|⊃+-1))⇡₂ : On duplique deux fois l’opération de multiplication par 4. L’opérateur ⟜ maintient l’intervalle généré par ⇡₂ en haut de la pile.
• ⊟₄ : Combine les quatre vecteurs situés en haut de la pile pour former une matrice.
• ⍉⇌ : Inverse l’ordre des lignes (⇌) puis transpose (⍉) la matrice pour obtenir le format de sortie désiré.

🧾 Exemples

Pour N=20, la fonction génère les 20 premiers quadruplets.

CHA₁₄₂ 20

╭─
╷ 1 3 8 120
2 4 12 420
3 5 16 1008
4 6 20 1980
5 7 24 3432
6 8 28 5460
7 9 32 8160
8 10 36 11628
9 11 40 15960
10 12 44 21252
11 13 48 27600
12 14 52 35100
13 15 56 43848
14 16 60 53940
15 17 64 65472
16 18 68 78540
17 19 72 93240
18 20 76 109668
19 21 80 127920
20 22 84 148092
╯

Vérification

Pour le quadruplet (3,5,16,1008), on peut vérifier que les produits plus un sont bien des carrés parfaits :
• 3×5+1=16=4²
• 3×16+1=49=7²
• 3×1008+1=3025=55²
• 5×16+1=81=9²
• 16×1008+1=16129=127²

Jeu « Color Water Sort » pour HP-Prime

Publié le par
Exemple de début de partie
Exemple de milieu de partie
Exemple de fin de partie

Voici une adaptation tactile du célèbre jeu de logique WaterSort Puzzle, spécialement conçue pour la calculatrice HP Prime en langage Python. Le principe est simple, mais diaboliquement addictif : vous devez verser les couleurs d’un tube à l’autre pour que chaque tube contienne qu’une seule couleur.

Au départ, les couleurs sont mélangées dans plusieurs tubes. À chaque tour, vous pouvez déplacer un empilement de couleur d’un tube vers un autre, à condition que la couleur soit identique ou que le tube soit vide. L’objectif est de reconstituer les couleurs uniformément dans chaque tube, sans déborder.

💡 Ce jeu fait appel à la logique, à l’anticipation… et un peu à votre patience !

Fonctionnalités :

  • Interface graphique simple et intuitive adaptée à l’écran de la HP Prime
  • Affichage coloré dynamique (jusqu’à 8 couleurs différentes)
  • Bouton ® pour recommencer le niveau si vous êtes bloqué
  • Détection automatique de victoire

Vous trouverez ci-dessous le code source complet ainsi que le fichier watercolor.hpprgm (fonctionne avec la version 2.1 du 13/04/2023 et les suivantes) :

#python jeu
from hpprime import *
from urandom import choice

couleurs_rgb = {
    "a": 0x845ec2,
    "b": 0xd65db1,
    "c": 0xff6f91,
    "d": 0xff9671,
    "e": 0xffc75f,
    "f": 0xf9f871,
    "g": 0x9bde7e,
    "h": 0x4bbc8e
}
liste_couleurs = list(couleurs_rgb.keys())

LARGEUR_TUBE = 20
HAUTEUR_TUBE = 60
ESPACEMENT_X = 80
ESPACEMENT_Y = 74
MARGE_X = 45
MARGE_Y = 20
COLONNES = 3
LIGNES = 3
TOTAL_COULEURS = 7
NOIR = 0x000000
BLANC = 0xFFFFFF
BG = 0x03132C

def position_tube(index):
    col = index % COLONNES
    lig = index // COLONNES
    x = MARGE_X + col * ESPACEMENT_X
    y = MARGE_Y + lig * ESPACEMENT_Y
    return x, y

def attendre_clic():
    while True:
        f1, _ = eval('mouse')
        if f1:
            while eval('mouse')[0]: pass
            return f1[:2]

def tube_clique(x, y):
    for i in range(9):
        tx, ty = position_tube(i)
        if tx - ESPACEMENT_X / 2 < x < tx + LARGEUR_TUBE + ESPACEMENT_X / 2 and ty <= y <= ty + HAUTEUR_TUBE:
            return i
    return None

def dessiner_tubes(tubes, selectionne=None):
    fillrect(0, 0, 0, 320, 240, BG, BG)
    for i, tube in enumerate(tubes):
        x, y = position_tube(i)
        bordure = 0x00FF00 if i == selectionne else BLANC
        rect(0, x-2, y-2, LARGEUR_TUBE+4, HAUTEUR_TUBE+4, bordure)
        rect(0, x-3, y-3, LARGEUR_TUBE+6, HAUTEUR_TUBE+6, bordure)
        fillrect(0, x, y-3, LARGEUR_TUBE, 3, BG, BG)
        h = HAUTEUR_TUBE // 4
        for j, couleur in enumerate(tube):
            c = couleurs_rgb.get(couleur)
            fillrect(0, x, y + HAUTEUR_TUBE - (j + 1)*h, LARGEUR_TUBE, h, c, c)
    # Bouton recommencer
    textout(0, 270, 110, chr(174), BLANC)

def sommet_identique(tube):
    if not tube: return None, 0
    sommet = tube[-1]
    compteur = 1
    for i in range(len(tube)-2, -1, -1):
        if tube[i] == sommet: compteur += 1
        else: break
    return sommet, compteur

def peut_verser(depuis, vers):
    if not depuis or len(vers) >= 4:
        return False
    couleur, nb = sommet_identique(depuis)
    if not vers: return True
    return vers[-1] == couleur

def verser(depuis, vers):
    if not peut_verser(depuis, vers): return
    couleur, nb = sommet_identique(depuis)
    espace = 4 - len(vers)
    a_verser = min(nb, espace)
    for _ in range(a_verser):
        vers.append(depuis.pop())

def generer_tubes():
    couleurs = []
    for couleur in liste_couleurs[:TOTAL_COULEURS]:
        couleurs += [couleur]*4
    melange = []
    while couleurs:
        c = choice(couleurs)
        couleurs.remove(c)
        melange.append(c)
    tubes = [melange[i*4:(i+1)*4] for i in range(TOTAL_COULEURS)]
    tubes += [[] for _ in range(9 - TOTAL_COULEURS)]
    return tubes

def a_gagne(tubes):
    for tube in tubes:
        if not tube: continue
        if len(tube) != 4: return False
        if any(c != tube[0] for c in tube): return False
    return True

def afficher_message_gagne():
    fillrect(0, 50, 90, 220, 60, BLANC, couleurs_rgb["d"])
    textout(0, 85, 105, "Bravo ! Vous avez gagné", NOIR)
    fillrect(0, 110, 130, 100, 25, BLANC, couleurs_rgb["g"])
    textout(0, 130, 135, "REJOUER", NOIR)

def attendre_redemarrage():
    while True:
        x, y = attendre_clic()
        if 110 <= x <= 210 and 130 <= y <= 155: return

def bouton_redemarrer(x, y):
    return 260 <= x <= 300 and 80 <= y <= 130

def main():
    while True:
        tubes = generer_tubes()
        tubes_depart = [tube[:] for tube in tubes]
        selection = None
        while True:
            dessiner_tubes(tubes, selection)
            if a_gagne(tubes):
                afficher_message_gagne()
                attendre_redemarrage()
                break
            x, y = attendre_clic()
            if bouton_redemarrer(x, y):
                tubes = [tube[:] for tube in tubes_depart]
                selection = None
                continue
            index = tube_clique(x, y)
            if index is None:
                selection = None
                continue
            if selection is None:
                if tubes[index]: selection = index
            elif selection == index:
                selection = None
            else:
                verser(tubes[selection], tubes[index])
                selection = None

main()
#end

EXPORT watercolor()
BEGIN
  wait(.3);
  python(jeu);
END;

Cahiers de vacances (1976 et 1977)

Publié le par

Collectionneur de manuels de mathématiques des années 70, je vous propose quelques exercices de 1976 tirés du cahier de vacances PASSEPORT POUR LE CE1.

Exercice sur les bases

Relation d’ordre

Cryptographie

Algorithmique

Compréhension, classement

Cahier PASSERELLE CM2 (1977)

Enveloppe d’une famille de droites

Publié le par

En parcourant le livre « Mathematiques et graphismes » de 1985, j’ai trouvé page 41 un programme intéressant en BASIC (pour TO7/Apple/Commodore 64/Oric etc) permettant de tracer une enveloppe de droites (de la forme ax+by+c = 0). En faisant varier a,b et c en fonction d’un paramètre (noté t dans le programme), on obtient des visuels sympathiques :

Traduction en Python (avec 18 exemples)

Version pour la NUMWORKS ici.

import turtle
from math import *
from time import sleep

t = turtle.Turtle()
t.hideturtle()
t.pensize(2)

w, h = 800, 600

wn = turtle.Screen()

wn.colormode(255)
t.pencolor(255, 255, 0)


def ex0():
    def g(t):
        return 2 - t * t, -2 * t, t**3

    return g, -5, 5, -2, 1.5, -3, 3


def ex1():
    def g(t):
        return cos(3 * t), sin(3 * t), sin(t) ** 2

    return g, -1, 1, -1.1, 1.1, 0, 2 * pi


def ex2():
    def g(t):
        return cos(3 * t), sin(3 * t), cos(t)

    return g, -1.2, 0.8, -1.2, 1.2, -pi / 2, pi / 2


def ex3():
    def g(t):
        return cos(t), sin(t), exp(-exp(-t / 5))

    return g, -2, 2, -2, 3, -5, 10


def ex4():
    def g(t):
        return cos(t), sin(t), -sin(t) / t

    return g, -0.3, 1.2, -0.9, 0.9, -5, 5


def ex5():
    def g(t):
        return cos(t), sin(t), -1 - int(t / 2 / pi)

    return g, -6, 6, -6, 6, 0, 10 * pi


def ex6():
    def g(t):
        return cos(t), sin(t), 1 / t

    return g, -2, 2, -1, 0.5, -10, 10


def ex7():
    def g(t):
        return cos(t), sin(t), log10(t)

    return g, -4, 4, -4, 4, 0.2, 20


def ex8():
    def g(t):
        return cos(t), sin(t), t * t * sin(t)

    return g, -4, 4, -10, 3, -pi, pi


def ex9():
    def g(t):
        return cos(t), sin(t), t * t / (1 + t * t)

    return g, -1, 1, -1, 1, -2 * pi, 2 * pi


def ex10():
    def g(t):
        return cos(t), sin(t), (1 - t * t) / (1 + t * t)

    return g, -1.5, 1.5, -1.5, 1.5, -2 * pi, 2 * pi


def ex11():
    def g(t):
        return cos(t), sin(t), sqrt(abs(t))

    return g, -4, 4, -4, 4, -10, 10


def ex12():
    def g(t):
        return cos(t), sin(t), t / (1 + t)

    return g, -3, 3, -3, 3, -10, 10


def ex13():
    def g(t):
        return cos(t), sin(t), 2 + cos(t / 2)

    return g, -4, 4, -4, 4, -2 * pi, 2 * pi


def ex14():
    def g(t):
        return cos(t), sin(t), -0.5 + cos(t / 2)

    return g, -2, 2, -2, 2, -2 * pi, 2 * pi


def ex15():
    def g(t):
        return cos(t), sin(t), t * t * sin(t)

    return g, -4, 4, -10, 3, -pi, pi


def ex16():
    def g(t):
        return cos(t), sin(t), t * t / (1 - t * t)

    return g, -1.5, 2, -2, 2, -2 * pi, 2 * pi


def ex17():
    def g(t):
        return cos(t), sin(t), sin(t) + sin(t) ** 2 / 2 + sin(t) ** 3 / 3

    return g, -2, 2, -3, 0, -pi, pi


def tracer(x, y):
    global f, pts
    if x < xi or x > xs or y < yi or y > ys:
        return
    f += 1
    pts[f] = [
        -w / 2 + ceil(w * (x - xi) / (xs - xi)),
        -h / 2 + ceil(h * (y - yi) / (ys - yi)),
    ]
    if f == 1 and pts[0] == pts[1]:
        f = -1
    elif f == 1:
        t.penup()
        t.goto(pts[0])
        t.pendown()
        t.goto(pts[1])


t.hideturtle()
for k in range(18):
    turtle.Screen().bgcolor(0, 0, 0)
    t.clear()
    wn.tracer(0)
    g, xi, xs, yi, ys, ti, ts = eval("ex" + str(k) + "()")
    pts = [[0, 0], [0, 0]]
    n = 200
    th = (ts - ti) / (n - 1)
    for i in range(n):
        try: a, b, c = g(ti + i * th)
        except: continue
        f = -1
        if b != 0:
            tracer(xi, -(c + a * xi) / b)
            tracer(xs, -(c + a * xs) / b)
        if a != 0:
            tracer(-(c + b * yi) / a, yi)
            tracer(-(c + b * ys) / a, ys)
    wn.update()
    sleep(2)

Initiation à l’assembleur 8080 sur ALTAIR 8800

Publié le par

Outils

Simulateur 8080 : https://www.sim8085.com

Création d’un fichier binaire : https://www.asm80.com/

Simulateur ALTAIR 8800 : https://s2js.com/altair/sim.html

Tous les codes (00.MEM = 3n+1, 01.MEM = n/2, 02.MEM = pair/impair + saut, 03.MEM = avec temps de vol, 04.MEM = avec maximum, 16bits.bin = version 16 bits) : https://uabox.univ-angers.fr/s/o96B5MEfeQAcXLA

Chargement d’une bande perforée : https://youtu.be/qv5b1Xowxdk?feature=shared&t=235

Calcul de 3n+1

Mettre une valeur N en 80h puis lancer le programme ci-dessous
Lire en 80h la valeur 3N+1 (modulo 256)

HEXA : 3A80004787803C32800076

Programme source :

LDA 80h
MOV B, A
ADD A
ADD B
INR A
STA 80h
HLT

Programme objet :

3A 80 00   LDA 80h
47         MOV B, A
87         ADD A
80         ADD B
3C         INR A
32 80 00   STA 80h
76         HLT

Division par 2

Mettre une valeur N en 80h puis lancer le programme ci-dessous
Lire en 80h la valeur ENT(N/2)

HEXA : 373F3E1B1F32800076

Programme source :

STC
CMC
MVI A, 27
RAR
STA 80h
HLT

Sauts avec tests pair ou impair

HEXA : 3A800047FE01CA2100E60178CA180087803C328000C30000373F1F328000C3000076

Programme source :

loop: 	LDA 80h
	MOV B, A
        CPI 1
	JZ fin
	ANI 1
	MOV A, B
	JZ pair
	ADD A
	ADD B
	INR A
	STA 80h
	JMP loop
pair:	STC
	CMC
	RAR
	STA 80h
	JMP loop
fin:	HLT

Version 1 avec temps de vol uniquement

HEXA : 3E003281 003A8000 47FE01CA 2E003A81 003C3281 0078E601 78CA2500 87803C32 8000C305 00373F1F 328000C3 050076

Programme source :

MVI A, 0
STA 81h
loop: 	LDA 80h
	MOV B, A
CPI 1
	JZ fin
	LDA 81h
	INR A
	STA 81h
	MOV A, B
	ANI 1
	MOV A, B
	JZ pair
	ADD A
	ADD B
	INR A
	STA 80h
	JMP loop
pair:	STC
	CMC
	RAR
	STA 80h
	JMP loop
fin:	HLT

Version 2 avec temps de vol et maximum

HEXA : 3E003281 003A8000 3282003A 800047FE 01CA4000 3A81003C 32810078 E60178CA 37008780 3C328000 473A8200 B8D20B00 78328200 C30B0037 3F1F3280 00C30B00 76

Programme source :

MVI A, 0
STA 81h
LDA 80h
STA 82h

loop: 	LDA 80h
	MOV B, A
        CPI 1
	JZ fin
	LDA 81h
	INR A
	STA 81h
	MOV A, B
	ANI 1
	MOV A, B
	JZ pair
	ADD A
	ADD B
	INR A
	STA 80h
	MOV B, A
    	LDA 82h
    	CMP B
    	JNC loop
    	MOV A, B
    	STA 82h
	JMP loop
pair:	STC
	CMC
	RAR
	STA 80h
	JMP loop
fin:	HLT

Version 16 bits

Mettre la partie basse de N en 80h et la partie haute en 81h. Par exemple pour 27 : 00 011 011 en 80h et 00 000 000 en 81h

Lire le temps de vol en 84h et le maximum aux adresses 82h (partie basse) et 83h (partie haute)

2A 80 00	LHLD 80H 	; Initialisation des mémoires 82h à 84h
22 82 00	SHLD 82H 	; copie de 80-81h vers 82-83h
21 84 00	LXI H, 84H	;
36 00		MVI M, 0 	; Temps de vol = 0
21 81 00 collatz: LXI H, 81H	
7E		MOV A, M  	; Si la valeur haute
B7		ORA A     	; n'est pas nulle
C2 1A 00	JNZ parity 	; On va tester la parité 
2B		DCX H       	; sinon,
7E		MOV A, M	; Si la valeur basse
FE 01		CPI 1       	;  vaut 1
CA 5D 00	JZ fin	        ; on arrête le programme
21 84 00 parity:LXI H, 84H	
34		INR M     	; temps de vol augmente de +1
21 80 00	LXI H, 80H	
7E		MOV A, M	
5F		MOV E, A    	; que l'on stocke dans E
E6 01		ANI 1       	; Si Z = 0
CA 3A 00	JZ pair     	; C'est un nombre pair
23		INX H	
56		MOV D, M	
D5		PUSH D	
E1		POP H	        ; HL = DE
29		DAD H	        ; HL = 2HL
19		DAD D	        ; HL = 3HL
23		INX H	        ; HL = 3HL + 1
22 80 00	SHLD 80h    	; Nouvelle valeur en 80h
E5		PUSH H	
D1		POP D    	; On la stocke dans DE
CD 46 00	CALL maxi	; Sous-routine maxi
C3 0B 00	JMP collatz 	; Retour à collatz
23	  pair: INX H  	        ; Si le nombre est pair
AF		XRA A         	; Carry = 0
7E		MOV A, M      	; Division par 2
1F		RAR           	; de la partie haute
77		MOV M, A	
2B		DCX H	
7E		MOV A, M      	; division par 2 de la partie basse
1F		RAR           	; avec ajout éventuel de C à gauche
77		MOV M, A	;
C3 0B 00	JMP collatz   	; Retour à collatz
2A 82 00  maxi:	LHLD 82H	;
7A		MOV A, D      	; Récup partie haute du max
BC		CMP H         	; si égalité des parties hautes
CA 52 00	JZ unite      	; tester les unités
D2 58 00	JNC change    	; si retenue le max a été dépassé
C9		RET           	; sinon ne rien faire
7B	unite:	MOV A, E   	; test des unités
BD		CMP L           ; si une retenue
DA 58 00	JC change     	; le max est dépassé
C9		RET           	; retour
EB	change:	XCHG  	        ; HL = DE
22 82 00	SHLD 82H	; que l'on place en 82h
C9		RET	
76	fin:	HLT

Résultats à obtenir aux adresses 82-83h et 84h

00 010 000 en 82h (partie basse) et 00 100 100 en 83h (haut) 

parseInt('0010010000010000',2)
9232

01 101 111 à l'adresse 84h : 

parseInt('01101111',2)
111

Résultats pour N = 639

>>> bin(639)
'0b1001111111'

Il faut donc mettre 01 111 111 à l'adresse 80h et 10 à l'adresse 81h

On lance le programme et on trouve :

Adresse 82h : 00 110 100
Adresse 83h : 10 100 010

Le maximum vaut donc :

>>> int('1010001000110100',2)
41524

Et le temps de vol est à l'adresse 84h : 10 000 011

>>> int('10000011',2)
131

Fractales

Publié le par

Sur cette page de Wolfram, on peut voir différentes fractales :

Et en bas de cette même page les algorithmes utilisés pour transformer les cases :

Ci-dessous un programme Python qui permet d’appliquer le motif voulu, il suffit d’indiquer les coordonnées des cases blanches. Par exemple pour le (a), la seule case blanche est au milieu (coordonnées (1,1))

La case blanche en (1,1)
from PIL import Image, ImageDraw
import numpy as np

# Dimensions de l'image finale (à modifier comme vous le voulez)
source = Image.new("RGB", (600, 600), color="white")
draw = ImageDraw.Draw(source)

# Recherche s'il y a une case blanche
def has_common(str1, str2, pattern):
    min_len = min(len(str1), len(str2))
    for i in range(1, min_len + 1):
        for p in pattern:
            # Ne pas afficher si on trouve une case blanche
            if str1[-i] == p[0] and str2[-i] == p[1]:
                return False
    # Sinon case noire
    return True

# Construction de la fractale
def fractal(pattern):
    # On parcourt les colonnes
    for c in range(600):
        # Convertir 'c' en base 3 (ici à l'aide de numpy)
        t1 = np.base_repr(c, base=3)
        # On parcourt les lignes
        for l in range(600):
            t2 = np.base_repr(l, base=3)
            # Si pas de case blanche, afficher le point
            if has_common(t1, t2, pattern):
                draw.point((c, l), fill=(0, 0, 0))

# Exemple avec le tapis de Sierpiński
fractal(["11"])
source.show()
Motif (a) = case blanche en (1,1)

Quelques motifs

(b) = fractal([’00’,’02’,’20’,’22’])
(d) = fractal([’10’,’20’,’21’])
(e) = fractal([’00’,’02’,’11’,’20’,’22’])
(g) = fractal([’11’,’20’])
(h) = fractal([’02’,’11’,’20’])

Et on peut en inventer de nouveaux :

fractal([’02’,’10’,’20’])