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

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

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

Quelques motifs

Et on peut en inventer de nouveaux :

Exercice 1

Écrire un programme qui cherche tous les mots de 5 lettres pouvant être formés à partir de mots de 9 lettres en prenant 1 lettre sur 2, en commençant par la première lettre. Exemples :

Vous pouvez utiliser ces 2 dictionnaires (mots de 9 et 5 lettres) : https://uabox.univ-angers.fr/s/b3GotFzpTYkL4MT

Corrigé en python

with open('dictionary_9.txt', 'r') as f:
    dictionary_9 = [line.strip() for line in f]

with open('dictionary_5.txt', 'r') as f:
    dictionary_5 = set(line.strip() for line in f)

compte = 0                      # Nb de mots trouvés

for word9 in dictionary_9:
  word5 = word9[::2]            # une lettre sur deux
  if word5 in dictionary_5:     # Si le mot existe
    print(word9, word5)         # on l'affiche
    compte += 1                 # et le compteur augmente de +1
print(f"Total = {compte}")  

Résultat :

ABLATIONS ALTOS
ABLUTIONS ALTOS
ABREGEAIS ARGAS
ABROGEAIS ARGAS
ABSTIENNE ASINE
ACCONIERS ACNES
...
VIELLEUSE VELUE
VIELLIONS VELOS
VIENDRAIS VEDAS
VOILETTES VIETS
Total = 913

corrigé en javascript

Cliquez sur ce lien puis bouton droit – Inspecter – Console. Copiez-collez le code suivant :

 dictionary_9.reduce((a, m) => {
     var mot5 = m.slice(0,2)+m[4]+m.slice(-2);
     return dictionary_5.includes(mot5) ? [...a, [m, mot5]] : a 
  }, [])

Exercice 2

Identifiez tous les mots de 10 lettres qui peuvent être composés de 2 mots de 5 lettres en respectant l’ordre des lettres. Exemple : RACHIDIENS s’écrit à partir de CHIEN et RADIS

Comme il y a beaucoup de solutions, on peut créer une fonction qui admet en paramètre un mot de 5 lettres et qui renvoie tous les mots de 10 lettres contenant ce mot ainsi que l’autre mot de 5 lettres pour compléter. Exemples :

>>> trouve("CHIEN")
BANCHAIENT CHIEN BANAT
CHARMAIENT CHIEN ARMAT
CHERRAIENT CHIEN ERRAT
CHIADERENT CHIEN ADRET
CHIENDENTS CHIEN DENTS
CHTHONIENS CHIEN THONS
CHTONIENNE CHIEN TONNE
CRASHAIENT CHIEN RASAT
DOUCHAIENT CHIEN DOUAT
LOUCHAIENT CHIEN LOUAT
MATCHAIENT CHIEN MATAT
RACHIDIENS CHIEN RADIS
TOUCHAIENT CHIEN TOUAT
TRICHAIENT CHIEN TRIAT

Corrigé en python

with open('dictionary_10.txt', 'r') as f:
    dictionary_10 = [line.strip() for line in f]

with open('dictionary_5.txt', 'r') as f:
    dictionary_5 = set(line.strip() for line in f)

def is_included(word1, word2):
    positions = []
    index = 0
    for letter in word2:
        index = word1.find(letter, index)
        if index == -1: return False
        positions.append(index)
        index += 1      
    return positions

def trouve(word5):
 for word10 in dictionary_10:
  positions = is_included(word10, word5)  
  if positions:
    reste = ''.join(word10[i] for i in range(10) if i not in positions)
    if reste in dictionary_5:
       print(word10, word5, reste)

exercice 3

Ci-dessous un jeu très simple trouvé dans le journal TV Télé Z. Dans notre cas nous allons travailler avec des mots de 9 et 5 lettres.

But : créer un programme qui, à partir d’une liste de mots de 5 lettres, va rechercher autant de mots de 9 lettres les contenant.

>>> jeu(["AIDER","CAPTER","GAINE","LOGER","FILES"])
PYRAMIDER AIDER PYR-M----
CAPTERAIT CAPTER ------AIT
GRAINIERS GAINE -R---I-RS
PLONGEOIR LOGER P--N--OI-
FILONIENS FILES ---ONI-N-

corrigé en python

from random import choice

with open('dictionary_9.txt', 'r') as f:
    dictionary_9 = [line.strip() for line in f]

with open('dictionary_5.txt', 'r') as f:
    dictionary_5 = set(line.strip() for line in f)

def is_included(word1, word2):
    positions = []
    index = 0
    for letter in word2:
        index = word1.find(letter, index)
        if index == -1: return False
        positions.append(index)
        index += 1      
    return positions

def trouve(word5):
 res = []         # On cherche toutes les solutions
 for word9 in dictionary_9:
  positions = is_included(word9, word5)  
  if positions: res.append((word9, positions))
 if len(res) > 0: return choice(res)      # on renvoie une solution au hasard
 return False

def jeu(arr):
 for mot in arr:
  r = trouve(mot)
  if r:     # Si un mot de 9 lettres a été trouvé
   cache = ''.join(r[0][i] if i not in r[1] else '-' for i in range(9))
   print(r[0], mot, cache)
  else: print(f"Rien trouvé pour {mot}")    

Remarque sur les calculatrices TI : comme précisé dans la vidéo, la fonction dbd des TI-82/83/84 permet de trouver le nombre de jours entre 2 dates entre 1950 et 2049. Cependant, sur les TI-84 Plus CE cette plage a été décalée à l’intervalle 1980 – 2079.

Temps unix

import datetime
from datetime import timezone

dt = datetime.datetime(2024,8,5,14,33,17, tzinfo=timezone.utc)
>>> dt.timestamp()
1722868397.0

import time
>>> time.gmtime(1722868397.0)
time.struct_time(tm_year=2024, tm_mon=8, tm_mday=5, tm_hour=14, tm_min=33, tm_sec=17, tm_wday=0, tm_yday=218, tm_isdst=0)

>>> time.gmtime(0)
time.struct_time(tm_year=1970, tm_mon=1, tm_mday=1, tm_hour=0, tm_min=0, tm_sec=0, tm_wday=3, tm_yday=1, tm_isdst=0)

>>> time.gmtime(-2000 * 365 * 86400)
time.struct_time(tm_year=-29, tm_mon=5, tm_mday=1, tm_hour=0, tm_min=0, tm_sec=0, tm_wday=5, tm_yday=121, tm_isdst=0)

>>> time.time()
1722867076.132498

>>> datetime.datetime.now(timezone.utc).timestamp()

Date de pâques (Formule approximative !)

def paques(annee):
    cycle_lune = 29.53058853
    j_sem = 6  # Samedi 5/1/1901
    delta = nb_jours(5, 1, 1901, 21, 3, annee)
    nb_cycles = 1 + int(delta / cycle_lune)
    ajout = int(nb_cycles * cycle_lune)
    while (j_sem + ajout) % 7 != 0: ajout +=1
    nb = ajout - delta
    if nb <= 10: j, m = 21 + nb, 3
    else: j, m = nb - 10, 4
    return (m, j)

def formule(j,m,a):
    if m < 3:
        a -= 1
        m += 12
    return int(365.25 * a) + int(30.6 * (m + 1)) + j - 3

def nb_jours(j1, m1, a1, j2, m2, a2):
    return formule(j2, m2, a2) - formule(j1, m1, a1)

def dow(j,m,a): return 1 + (formule(j,m,a) % 7)

Date de pâques (formule exacte)

def easter(annee):
    a = annee % 19
    b = annee // 100
    c = annee % 100
    d = b // 4
    e = b % 4
    f = (b + 8) // 25
    g = (b - f + 1) // 3
    h = (19 * a + b - d - g + 15) % 30
    i = c // 4
    k = c % 4
    l = (32 + 2 * e + 2 * i - h - k) % 7
    m = (a + 11 * h + 22 * l) // 451
    mois = (h + l - 7 * m + 114) // 31
    jour = ((h + l - 7 * m + 114) % 31) + 1
    return (annee, mois, jour)

Pourquoi 60 ?

import math

def nb_diviseurs(n):
    count = 0
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            if n == i * i: count += 1
            else: count += 2
    return count

maxi = 0
for n in range(1, 100):
    t = nb_diviseurs(n)
    if t > maxi:
        print(f"{n} a {t} diviseurs")
        maxi = t

# Résultats :

1 a 1 diviseur
2 a 2 diviseurs
4 a 3 diviseurs
6 a 4 diviseurs
12 a 6 diviseurs
24 a 8 diviseurs
36 a 9 diviseurs
48 a 10 diviseurs
60 a 12 diviseurs

Nombre de jours entre 2 dates

mois_jours = (31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31)

def est_bissextile(annee):
    return (annee % 4 == 0 and annee % 100 != 0) or annee % 400 == 0

def jours_dans_annee(jour, mois, annee):
    jours = jour
    for m in range(1, mois):
        jours += mois_jours[m - 1]
    if mois > 2 and est_bissextile(annee): jours += 1
    return jours

def jours_entre_dates(j1, m1, a1, j2, m2, a2):
    if (a1, m1, j1) > (a2, m2, j2):
        j1, m1, a1, j2, m2, a2 = j2, m2, a2, j1, m1, a1
    jours_total = 0
    if a1 == a2:
        return jours_dans_annee(j2, m2, a2) - jours_dans_annee(j1, m1, a1)  
    jours_total += (366 if est_bissextile(a1) else 365) - jours_dans_annee(j1, m1, a1)
    jours_total += jours_dans_annee(j2, m2, a2)  
    for annee in range(a1 + 1, a2):
        jours_total += 366 if est_bissextile(annee) else 365  
    return jours_total

# Exemple

>>> jours_entre_dates(15,10,1582,4,8,2024)
161366

Programme CULMINATION pour les ti-82/83/84

Disp "JJMM.AA ?"
Input D
Disp "LONGITUDE ?"
Input L
dbd(101+fPart(D),D→N
2π(N-81)/365→B
7.678sin(B+1.374)-9.87sin(2B)→E
Disp "CULMINATION"
12+E/60-L/15▸DMS

Programme LONGITUDE pour les ti-82/83/84

Disp "CULMINATION"
Disp "HH°MM'SS''?"
Input H
getDate→L₁
100L₁(3)+L₁(2)+remainder(L₁(1),100)/100→D
dbd(101+fPart(D),D→N
2π(N-81)/365→B
7.678sin(B+1.374)-9.87sin(2B)→E
Disp "LONGITUDE :"
15*(12+E/60-H)

Réponses possibles aux 2 questions finales

ZIPSORT

cat(EXECON("CHAR(SORT({&1,&2}))",ASC(A),ASC(B)))

Exemple de déroulement avec zipsort(“oui”,”non”) :

• On transforme les 2 chaines A et B en listes de codes ASCII : {111,117,105} et {110,111,110}
• On trie les couples de lettres SORT({&1,&2}) : SORT({111,110}) -> {110,111}
• Transformation en chaine : CHAR({110,111}) -> “no”
• On obtient la liste : {“no”,”ou”,”in”}
• Concaténation finale : “noouin”

Lettres manquantes

cat(EXECON("CAS((&2≠1+&1)*char(1+&1))",ASC(T)))

Exemple de déroulement avec manque(“abcdfg”) :

• On transforme la chaine en liste ASCII : {97,98,99,100,102,103}
• Est-ce que l’élément suivant est différent de l’élément courant + 1 ?
• EXECON(“&2≠1+&1”,{97,98,99,100,102,103}) -> {0,0,0,1,0}
• La lettre manquante a comme code ASCII la lettre courante + 1 : char(1+&1)
• En multipliant le caractère par 0 on a une chaine vide, sinon on récupère le caractère manquant
• Concaténation des chaines vides + lettres manquantes
• manque(“abdefgijklmnpqrstv”) -> “chou”

Quelques challenges (proposition de solutions plus bas)

Autant de “x” que de “o”

Afficher 1 s’il y a autant de “x” que de “o” dans une chaine de caractère, sinon afficher 0.

xox("xxabcoo") -> 1
xox("xxooxoox") -> 1
xox("xaxoboxocccoox") -> 0

Au milieu

Ecrire une fonction qui prend en paramètres un caractère X et le place au milieu de Y répété N fois. Lorsque ce n’est pas possible, renvoyer X.

Exemples :

middle(10,"A","*") --> "*****A*****"  ("A" est au milieu de 10 "*")
middle(9,"A","*") --> "A"             ("A" ne peut pas être au milieu)
middle(2,"X","+") --> "+X+"

mot pur

Un mot pur est un mot dont la somme des positions dans l’alphabet de chaque lettre est divisible par la longueur totale du mot.

Par exemple, “abcb” est un mot pur car 1 + 2 + 3 + 2 = 8 et 8/4 = 2.

pure("ccc") -> 1
pure("bed") -> 0

Palindrome

Renvoyer 1 si une chaine est un palindrome, 0 sinon. La chaine pourra être écrite en minuscules et/ou majuscules.

palind("Laval") -> 1
palind("Angers") -> 0

Somme des N plus grands

Ecrire une fonction qui à partir d’une liste L et d’un entier N renvoie la somme des N entiers les plus grands de L.

sumgrand({4,9,2,3,7,1},2) --> 16    (Les 2 nombres les + grands sont 9 et 7)
sumgrand({-7,9,12,-1,-3},3) --> 20  (9 + 12 - 1 = 20)

Somme sans doublons

Ecrire une fonction qui fait la somme des éléments d’une liste, mais ignore ceux qui sont dupliqués.

Exemples : pour la liste [3, 4, 3, 6] la fonction devra renvoyer 10
et pour la liste [1, 10, 3, 10, 10] la fonction devra renvoyer 4.

Project Euler n°1

L’énoncé est ici

Exemples de solutions

Autant de “x” que de “o”

count_eq(120,ASC(T))=count_eq(111,ASC(T))

Au milieu

IFTE(N MOD 2,X,CAS(N/2*Y+X+N/2*Y))

mot pur

0=ΣLIST(ASC(T) MOD SIZE(T))

Palindrome

UPPER(T)==CHAR(revlist(ASC(UPPER(T))))

Remarquez que cette version fonctionne également (en décochant "L1") : 

revlist(sto(ASC(UPPER(T)),L1))==L1

Somme des N plus grands

ΣLIST(CAS.mid(CAS.SORT(L,"(x,y)->x>y"),1,N))

Somme sans doublons

ΣLIST(apply("x->x*(count_eq(x,L)==1)",L))

Project euler n°1

Décochez "v" :

ΣLIST(remove("x->(x MOD 3)*(x MOD 5)>0",MAKELIST(v,v,1,N)))-N

Tous les codes de la vidéo

Les collectionneurs

possede(cret,calc(hp71b,1984)).
possede(eric,ordi(zx81,1981)).
possede(ledudu,ordi(c64,1982)).
possede(eric,calc(hp41C,1979)).
possede(nicole,calc(pb100,1983)).
possede(audrey,ordi(apple2,1977)).
possede(cret,ordi(c64,1982)).
possede(ledudu,calc(ti57,1977)).
collection(P):-
 possede(P,ordi(_,_)),
 possede(P,calc(_,_)).

annee(B,H,X):-
    B > H,
    annee(H,B,X).

annee(B,H,X):-
    possede(_,calc(X,A)),
    A =< H,
    A >= B.

annee(B,H,X):-
    possede(_,ordi(X,A)),
    A =< H,
    A >= B. 

?- possede(P,ordi(_,1977)).
?- possede(P,T).
?- possede(_,calc(N,_)).
?- possede(X,calc(_,T)),T<1980.

Nombre d’or

Version 1 :

nombreOr(N, R) :- fc(N, 1, R).
fc(1, A, R) :- R = A.
fc(N, A, R) :-
    S is 1 + 1 / A,
    N1 is N - 1,
    fc(N1, S, R). 

Version 2 :

nombreOr(N, Num, Den) :- fc(N, 1, 1, Num, Den).
 
fc(1, Num, Den, Num, Den).
 
fc(N, NumP, DenP, Num, Den) :-
    N1 is N - 1,
    Num2 is NumP + DenP,
    fc(N1, Num2, NumP, Num, Den).

Taille d’une liste

length([],0).

length([H|T],N):-
    length(T,N1), N is N1+1. 

Triplets pythagoriciens

Version 1 :

valide(A, B, C) :-
    C2 is A*A + B*B,
    C*C =:= C2.

cherche(A, B, C, Max) :-
    between(1, Max, A),
    between(A, Max, B),
    between(B, Max, C),
    valide(A, B, C).

pythagore(Max, R) :-
    findall((A,B,C), cherche(A, B, C, Max), R). 

Version 2 :

entre(B, H, B).
entre(B, H, X) :-
    B < H,
    B1 is B + 1,
    entre(B1, H, X).

valide(A, B, C) :-
    C2 is A*A + B*B,
    C*C =:= C2.

cherche(A, B, C, Max) :-
    entre(1, Max, A),
    entre(A, Max, B),
    entre(B, Max, C),
    valide(A, B, C).

pythagore(Max) :-
    cherche(A, B, C, Max),
    L = [A,B,C],
    write(L), nl,
    fail.

Syracuse

Version 1 :

syr(N):- syr(N,0,N).
syr(1,T,M):- write(T),nl,write(M).
syr(N,T,M):-
 T2 is T + 1,
 suiv(N,T2,M).

suiv(N,T,M):-
 0 is N mod 2,
 N2 is N/2,
 syr(N2,T,M).

suiv(N,T,M):-
 N2 is 3*N+1,
 maxisuiv(N2,T,M).

maxisuiv(N,T,M):- N > M, syr(N,T,N).
maxisuiv(N,T,M):- syr(N,T,M). 

Version 2 :

syr(N):- syr(N,0,N).
syr(1,T,M):- write(T),nl,write(M).
syr(N,T,M):-
 T2 is T + 1,
 suiv(N,N2),
 M2 is max(N,M),
 syr(N2,T2,M2).

suiv(N, N2):-
 0 is N mod 2,
 N2 is N/2,!.

suiv(N, 3 * N + 1).

On trouve, dans certains ouvrages sur les calculatrices HP, des tables donnant les combinaisons de touches pour réordonner les éléments de la pile XYZT :

Par exemple ci-dessus, ligne n°9, si ABCD sont sur la pile XYZT, la combinaison x><y, CLX et ENTER permettra d’avoir 00AC sur la pile.

L’idée m’est venue de faire la même chose pour les calculatrices HP-48/49/50g qui ont d’autres commandes pour manipuler la pile.

A partir d’éléments (e1 au niveau 1, e2 au niveau 2 etc.), on voudrait les réordonner en utilisant les commandes de base du langage RPN : DUP, SWAP, DROP, OVER, ROT, DUP2, DROP2 et PICK3.

Exemples :

La pile contient uniquement 2 éléments e1 (niveau 1) et e2 (niveau 2)et on veut les inverser. Réponse : SWAP

La pile contient 3 éléments e1 : e2 : e3 et on veut inverser les éléments des niveaux 2 et 3 pour obtenir e1 : e3 : e2. Réponse : ROT SWAP

Je vous propose un petit programme Python qui fait une recherche brute de toutes les possibilités (en partant des combinaisons à 1 commandes, puis à 2 commandes etc. Avec répétitions, par exemple OVER OVER). Il recherche jusqu’à une combinaison de 7 commandes ce qui peut demander du temps !

Tester le programme en ligne

from itertools import *

keys = "DUP", "SWAP", "DROP", "OVER", "ROT", "DUP2", "DROP2", "PICK3"

def DUP(s): return [s[0]] + s if len(s)>0 else -1
def SWAP(s): return [s[1], s[0]] + s[2:] if len(s) > 1 else -1
def DROP(s): return s[1:] if len(s) > 0 else -1
def OVER(s): return [s[1]] + s if len(s) > 1 else -1
def ROT(s): return [s[2]] + s[:2] +s[3:] if len(s) > 2 else -1
def DUP2(s): return [s[0], s[1]] + s if len(s) > 1 else -1
def DROP2(s): return s[2:] if len(s) > 2 else -1
def PICK3(s): return [s[2]] + s if len(s) > 2 else -1

def find(target, n):
 rr = [1 + v for v in range(n)]
 tr = [int(v) for v in target]
 for n in range(1, 8):
  for op in combinations_with_replacement(keys, n):
   for p in permutations(op):
    r = rr
    for c in p:
     t = eval(c)(r)
     if t == -1: break
     r = t
    if r == tr:
     rs = ':'.join([str(v) for v in rr])
     return '{} -> {} = {}'.format(rs, ':'.join(list(target)), " / ".join(p))

 return "No solution"

# 5 levels on the stack (e1:e2:e3:e4:e5). Goal : e2:e2
>>> find("22", 5)
'1:2:3:4:5 -> 2:2 = ROT / DROP2 / SWAP / ROT / DROP2 / DUP'

# 3 levels on the stack (e1:e2:e3). Goal : e1:e2:e3:e1:e2:e3
>>> find("123123", 3)
'1:2:3 -> 1:2:3:1:2:3 = PICK3 / PICK3 / PICK3'

# 3 levels on the stack. Goal : e1:e1:e2:e2:e3:e3
>>> find("112233", 3)
'1:2:3 -> 1:1:2:2:3:3 = PICK3 / ROT / ROT / DUP2 / ROT'

# 4 levels on the stack. Goal : e2:e2:e4:e4
>>> find("2244", 4)
'1:2:3:4 -> 2:2:4:4 = ROT / DROP2 / DUP2 / ROT'

Version pour la HP-50g

Cette calculatrice a plus de commandes que les HP-48G pour manipuler la pile, j’ajoute DUPDUP, UNROT et 4 ROLL (comme ROT mais avec le niveau 4)

from itertools import *

# Version HP-50g

keys = "DUP", "DUPDUP","SWAP", "DROP", "OVER", "ROT", "UNROT", "DUP2", "DROP2", "PICK3", "_4_ROLL"

def DUP(s): return [s[0]] + s if len(s)>0 else -1
def DUPDUP(s): return [s[0], s[0]] + s if len(s)>0 else -1
def SWAP(s): return [s[1], s[0]] + s[2:] if len(s) > 1 else -1
def DROP(s): return s[1:] if len(s) > 0 else -1
def OVER(s): return [s[1]] + s if len(s) > 1 else -1
def ROT(s): return [s[2]] + s[:2] +s[3:] if len(s) > 2 else -1
def UNROT(s): return s[1:3] + [s[0]] +s[3:] if len(s) > 2 else -1
def DUP2(s): return [s[0], s[1]] + s if len(s) > 1 else -1
def DROP2(s): return s[2:] if len(s) > 2 else -1
def PICK3(s): return [s[2]] + s if len(s) > 2 else -1
def _4_ROLL(s): return [s[3]] + s[:3] +s[4:] if len(s) > 3 else -1

def find(target, n):
 rr = [1 + v for v in range(n)]
 tr = [int(v) for v in target]
 for n in range(1, 8):
  for op in combinations_with_replacement(keys, n):
   for p in permutations(op):
    r = rr
    for c in p:
     t = eval(c)(r)
     if t == -1: break
     r = t
    if r == tr:
     rs = ':'.join([str(v) for v in rr])
     return '{} -> {} = {}'.format(rs, ':'.join(list(target)), " / ".join(p))

 return "No solution"

>>> find("231", 3)
'1:2:3 -> 2:3:1 = UNROT'

>>> find("4123", 4)
'1:2:3:4 -> 4:1:2:3 = _4_ROLL'

>>> find("135", 5)
'1:2:3:4:5 -> 1:3:5 = SWAP / _4_ROLL / DROP2'

>>> find("4321", 4)
'1:2:3:4 -> 4:3:2:1 = SWAP / ROT / _4_ROLL'

Version en PROLOG (en cours de réalisation)

% Règles pour les opérations sur la pile

% SWAP : Inverse les niveaux 1 et 2
swap([A,B|T], [B,A|T]).

% DUP : Duplique le niveau 1
dup([A|T], [A,A|T]).

% DROP : Supprime le niveau 1
drop([_|T], T).

% OVER : Récupère le niveau 2 et le met au niveau 1
over([A,B|T], [B,A,B|T]).

% ROT
rot([A,B,C|T], [C,A,B|T]).


% Règle pour arrêter la récursivité lorsque la pile est déjà dans l'état voulu
trouve([], Stack, Stack).

% Règles pour trouver la séquence d'opérations 

trouve([swap|Actions], Stack, FinalState) :-
    swap(Stack, NewStack),
    trouve(Actions, NewStack, FinalState).

trouve([dup|Actions], Stack, FinalState) :-
    dup(Stack, NewStack),
    trouve(Actions, NewStack, FinalState).

trouve([drop|Actions], Stack, FinalState) :-
    drop(Stack, NewStack),
    trouve(Actions, NewStack, FinalState).

trouve([over|Actions], Stack, FinalState) :-
    over(Stack, NewStack),
    trouve(Actions, NewStack, FinalState).

trouve([rot|Actions], Stack, FinalState) :-
    rot(Stack, NewStack),
    trouve(Actions, NewStack, FinalState).

Quelques tests

rot([1,4,3],X).
Réponse : X = [3, 1, 4]

swap([1,4,3],X).
Réponse : X = [4, 1, 3]

drop([1,4,3],X).
Réponse : X = [4, 3]

over([1,4,3],X).
Réponse : X = [4, 1, 4, 3]

trouve(X, [1,4,3], [4,1,3]).
X = [swap]

Version 2 proposée par chatGPT

trouve(Actions, Stack, FinalState) :-
    trouver_sequence(Actions, [], Stack, FinalState).

% Cas où l'état actuel est l'état voulu
trouver_sequence([], _, Stack, Stack).

% Cas où l'état actuel est différent de l'état voulu, continue à chercher
trouver_sequence([Action|Actions], History, CurrentState, FinalState) :-
    \+ member(CurrentState, History), % Vérifie si l'état actuel a déjà été visité pour éviter les boucles infinies
    apply_action(Action, CurrentState, NextState),
    trouver_sequence(Actions, [CurrentState|History], NextState, FinalState).

% Applique une action sur l'état actuel de la pile
apply_action(swap, [A,B|T], [B,A|T]).
apply_action(dup, [A|T], [A,A|T]).
apply_action(drop, [_|T], T).
apply_action(over, [A,B|T], [B,A,B|T]).
apply_action(rot, [A,B,C|T], [C,A,B|T]).

Programmes à tester ici : https://tio.run/#golfscript

Programmes de la vidéo

Somme des entiers

10 .)*2/
donne 55

Syracuse version 1

27 .2%{3*)}{2/}if
donne 82

16 3*).2%6\?/
donne 8

Maximum d’un tableau

[2 5 1 3] $-1=
donne 5

Rentre Avec Tes Pieds

['RENTRE' 'AVEC' 'TES' 'PIEDS'] {[0=]}%'.'*
donne "R.A.T.P"

Fractions continues et nombre d’or

1{-1?).p}10*;

Somme des chiffres d’un entier

{0 {\.}{.10/\10%@+}while;}:sdc;

{.{.10%\10/sdc}0if+}:sdc;

Syracuse : Temps de vol

{0{\.(}{.2%\.3*)\2/if\)}while;}:syr;

{0{)\.2%\.3*)\2/if.(@\}do\;}:syr;

{{(}{3*).2%6\?/}/,}:syr;

Exemples supplémentaires (Project Euler)

P1 / Multiples de 3 ou 5 : https://projecteuler.net/problem=1

1000,.{3%},{5%},-{+}*

1000, : Création de la liste 0 à 999
. : On duplique la liste
{3%}, : On filtre ceux qui ont un reste non nul en les divisant par 3
{5%}, : Et ceux qui ont un reste non nul en les divisant par 5
- : On garde les multiples de 3 ou 5
{+}* : Réduction par la somme

P2 / Nombres de Fibonacci pairs : https://projecteuler.net/problem=2

0 1{2000.*<}{.@+}/\;.{2%},-{+}*

0 1 : On place 0 et 1 sur la pile
{2000.*<}{}/ : Tant que l'on ne dépasse pas 4 millions, ajout ds tableau
.@+ : Nombre Fibonacci suivant (a b -> a b b -> b b a -> b b+a)
\; : On garde uniquement le tableau
.{2%},- : On duplique le tableau et on ne garde que les nombres pairs
{+}* : Réduction par la somme

P6 / Sum square difference : https://projecteuler.net/problem=6

101,(;.{+}*2?\{2?}%{+}*-

101, : [0 ... 100]
( : supprime le 1er élément et le met à la fin [1 ... 100] 0
;. : supprime le 0 et duplique le tableau
{+}*2? : réduction par la somme de l'autre tableau puis carré
\{2?}%{+}* : SWAP, met chaque élément au carré puis réduction par la somme
- : Différence des 2 valeurs

Recherches personnelles

Palindrome

{.,1>{(\)@={pal}0if}1if\;}:pal;

"ABBA" pal
donne 1
"ABBCA" pal
donne 0

def grille(a, b):
    return chr(65 + (ord(a) + ord(b)) % 26)

def invGrille(a, b):
    return chr(65 + (ord(a) - ord(b)) % 26)

def chiffreAutoclaveV1(phrase:str, cle:str):
    phrase = phrase.upper()
    chiffre = ''
    for c in phrase:
        cle = grille(c, cle)
        chiffre += cle
    return chiffre

def dechiffreAutoclaveV1(chiffre:str, cle:str):
    clair = ''
    for c in chiffre:
        clair += invGrille(c, cle)
        cle = c
    return clair    
  
phrase = 'OPERATIONURGENTE'
cle = 'K'
chiffre = chiffreAutoclaveV1(phrase, cle)
print('Chiffrée :', chiffre)
print('Déchiffrée :', dechiffreAutoclaveV1(chiffre, cle))


def chiffreAutoclaveV2(phrase:str, mot:str):
    phrase = phrase.upper()
    cle = mot.upper() + phrase
    chiffre = ''
    for i, c in enumerate(phrase): chiffre += grille(c, cle[i])
    return chiffre

def dechiffreAutoclaveV2(chiffre:str, mot:str):
    clair = ''
    cle = mot
    for i, c in enumerate(chiffre):
        lettre = invGrille(c, cle[i])
        clair += lettre
        cle += lettre
    return clair

phrase = 'MESSAGEIMPORTANTPOURNESTORLAGIRAFEAUNLONGCOU'
mot = 'POIRIER'
chiffre = chiffreAutoclaveV2(phrase, mot)
print('Chiffrée :', chiffre)
print('Déchiffrée :', dechiffreAutoclaveV2(chiffre, mot))