Misez p'tit Optimisez en version APL

Vous ne possédez pas l'original ? Découvrez la machine via l'émulation !

Modérateur : Politburo

Avatar du membre
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 499
Enregistré le : 05 mars 2020 20:45
Contact :

MPO111 - Misez p'tit Optimisez en version APL

Message par Schraf »

Enoncé du MPO n°111
Trouver les nombres triangulaires qui diminués de 1, sont la somme de deux nombres triangulaires.
Les nombres triangulaires T(n) sont de la forme 1 + 2 + ... + n = n * (n + 1) / 2, les premiers étant 1, 3, 6, 10, 15 etc. On peut les générer en APL par :

Code : Tout sélectionner

      ⍳10			⍝ Entiers entre 1 et 10
1 2 3 4 5 6 7 8 9 10

      +\ ⍳10			⍝ Utilisation d'un scan 1, 1+2, 1+2+3 etc.
1 3 6 10 15 21 28 36 45 55
Cherchons toutes les combinaisons des sommes de ces nombres triangulaires et ajoutons 1. C'est-à-dire T(a) + T(b) + 1 pour a et b entre 1 et 10 :

Code : Tout sélectionner

      1 + u ∘.+ u ← +\ ⍳10
 3  5  8 12 17 23 30 38  47  57
 5  7 10 14 19 25 32 40  49  59
 8 10 13 17 22 28 35 43  52  62
12 14 17 21 26 32 39 47  56  66
17 19 22 26 31 37 44 52  61  71
23 25 28 32 37 43 50 58  67  77
30 32 35 39 44 50 57 65  74  84
38 40 43 47 52 58 65 73  82  92
47 49 52 56 61 67 74 82  91 101
57 59 62 66 71 77 84 92 101 111
Finalement, on cherche les nombres triangulaires qui sont dans cette matrice. On transforme la matrice en un vecteur (avec ',') et on prend l'intersection entre u et ce vecteur :

Code : Tout sélectionner

      u ∩ , 1 + u ∘.+ u ← +\ ⍳10
3 10 21 28
Avec un nombre de départ plus grand :

Code : Tout sélectionner

      u ∩ , 1 + u ∘.+ u ← +\ ⍳100
3 10 21 28 66 91 120 136 190 253 325 406 435 595 703 820 903 1081 1596 1711 1891 2080 2145 2278 2415 2775 2926 3081 3160 3486 3916 4186 4278 4656 4753
Remarquons que l'on n'a pas tous les nombres triangulaires, par exemple dans la matrice 10x10 notre code s'arrête à 28 alors qu'il y aurait 66 et 91 également de présents. On doit en fait chercher les nombres triangulaires n * (n + 1) / 2 inférieurs au max M de la matrice. L'équation du second degré n * n + n - 2 * M = 0 montre que n doit être inférieur à environ 2*√M. Ce qui nous amène à cette version finale que vous pouvez tester ici :

Code : Tout sélectionner

      MPO111 ← {(+\ ⍳⌈2 × .5 *⍨ ⌈/ v) ∩ v ← , 1 + u ∘.+ u ← +\ ⍳⍵}
      MPO111 10
3 10 21 28 66 91

      MPO111 100
3 10 21 28 66 91 120 136 190 253 325 406 435 595 703 820 903 1081 1596 1711 1891 2080 2145 2278 2415 2775 2926 3081 3160 3486 3916 4186 4278 4656 4753 5565 6105 7626
Avatar du membre
gege
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 7141
Enregistré le : 31 janv. 2008 14:24
Localisation : Banlieue Paârisienne
Contact :

Re: Misez p'tit Optimisez en version APL

Message par gege »

Bonjour,
Sympa mais me trompes-je en disant que tu manipules ici une matrice 100 x 100 ?
Ouch !!
...mais sympa !
G.E.
Avatar du membre
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 499
Enregistré le : 05 mars 2020 20:45
Contact :

Re: Misez p'tit Optimisez en version APL

Message par Schraf »

@gege : Oui ! En installant Dyalog APL (qui est moins limité que la version en ligne tryapl.org), le résultat pour une matrice 4000*4000 est instantané. Mais on peut aussi saturer la mémoire avec un nombre un peu plus grand...
⍴ MPO111 4000 ⍝ Nombre de réponses trouvées
1213

⍴MPO111 5000
WS FULL
Il est possible bien sûr de faire des programmes plus conventionnels avec boucles, tests...
Avatar du membre
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 499
Enregistré le : 05 mars 2020 20:45
Contact :

Re: Misez p'tit Optimisez en version APL

Message par Schraf »

Je vous ai beaucoup parlé d'APL ici sur Silicium 😄

Un tweeter (Yann Le Du) m'a fait découvrir K (créé en 1993) qui est largement inspiré d'APL mais avec des caractères "normaux". Certes il existe aussi J (par Iverson le créateur d'APL) mais personnellement je n'ai jamais accroché à sa syntaxe.

J'en parle dans cette section car il y a 6-7 ans John Earnest a fait une version de K pour les mobiles (ou tablettes ou ordinateurs). Il s'agit d'une page HTML + JavaScript et le tout pour moins de 200 ko (voir uniquement 56 ko si on ne veut pas faire de graphique).

Les fans du RPN devraient tester, je trouve cela assez formidable ! Je vous mets le lien vers mon tuto (qui est un peu en état de brouillon car je découvre aussi ce langage) et vers le simulateur mais l'histoire de vous mettre l'eau à la bouche, voici la version de Syracuse avec un graphique :

Code : Tout sélectionner

 syr:{x>1}{$[2!x;1+3*x;x%2]}\

 syr 35
35 106 53 160 80 40 20 10 5 16 8 4 2 1

stats:{(#1_x),|/x}

stats syr 27
111 9232

r:syr 27
pl[#r;r]
Image
Avatar du membre
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 499
Enregistré le : 05 mars 2020 20:45
Contact :

Re: Misez p'tit Optimisez en version APL

Message par Schraf »

Enoncé du MPO n°116

Voici une suggestion en APL :

Code : Tout sélectionner

MPO116 ← ⌈⌿ ({ (⍎⍺) × r × 2 < r ← ⍴⍵ } ⌸ '0', ⊢)
⌸ permet de faire des statistiques sur un vecteur ou une chaine :

Code : Tout sélectionner

      {⍺, ⍴⍵}⌸'SUPERCETRUC'
S 1		⍝ le 'S' apparaît 1 fois
U 2		⍝ le 'U' apparaît 2 fois
P 1
E 2
R 2
C 2
T 1
Il faut au moins 2 éléments, d'où le '0', ⊢ pour ajouter un '0' à gauche:

Code : Tout sélectionner

      {⍺,⍴⍵}⌸'4'
RANK ERROR

      {⍺,⍴⍵}⌸'04'
0 1
4 1
On teste si l'effectif est > 2 (ce qui donne 0 ou 1) et on multiplie par la valeur testée. Mais comme cette valeur est un caractère et pas un nombre, on transforme la chaine en nombre avec ⍎ :

Code : Tout sélectionner

      3 × '123'
DOMAIN ERROR

      3 × ⍎'123'
369
Ainsi, la première partie du programme donne les différents scores possibles :

Code : Tout sélectionner

      {(⍎⍺) × r × 2 < r ← ⍴⍵}⌸ '0111555555'
 0	⍝ Score pour 0 = 0
 3	⍝ Score pour 1 = 3
30	⍝ Score pour 5 = 30
Et finalement on prend le max de ce vecteur colonne (⌈⌿)
Avatar du membre
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 499
Enregistré le : 05 mars 2020 20:45
Contact :

Re: Misez p'tit Optimisez en version APL

Message par Schraf »

Voici une autre version pour le MPO116 qui évite d'ajouter le '0' :

Code : Tout sélectionner

MPO116 ← ⌈/n × (⍎¨∪) × 2 < n ← +⌿ ⊢∘.= ∪
La première partie calcule les effectifs :

Code : Tout sélectionner

      ∪ '4444999'
49		⍝ Chaine avec les uniques caractères présents

      (⊢∘.=∪) '4444999'
1 0
1 0
1 0
1 0
0 1
0 1
0 1
      (+⌿⊢∘.=∪) '4444999'
4 3		⍝ Somme des colonnes
On teste s'il y a au moins 3 chiffres :

Code : Tout sélectionner

      2 < (n ← +⌿ ⊢∘.= ∪) '4444999'
1 1		⍝ C'est vrai pour 4 et 9
      2 < (n ← +⌿ ⊢∘.= ∪) '444499'
1 0		⍝  C'est faux pour 9
La dernière partie transforme la chaine en vecteur de chiffres et on effectue la multiplication des vecteurs (terme à terme) :

Code : Tout sélectionner

      (⍎¨∪) '4444999'
4 9		⍝ Vecteur de chiffres

      4 3 × 4 9 × 1 1
16 27		⍝ 4 fois le 4 et 3 fois le 9
      4 2 × 4 9 × 1 0
16 0		⍝ 4 fois le 4 et 2 fois le 9 que l'on ne comptera pas
Et finalement ⌈/ pour prendre la plus grande valeur.

Code : Tout sélectionner

      MPO116 ← ⌈/n × (⍎¨∪) × 2 < n ← +⌿ ⊢∘.= ∪

      MPO116¨ '84884284' '123456' '444444999' '44499' '11' '111' '1'
32 0 27 12 0 3 0
Avatar du membre
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 499
Enregistré le : 05 mars 2020 20:45
Contact :

Re: Misez p'tit Optimisez en version APL

Message par Schraf »

Traduction en K :

Code : Tout sélectionner

 MPO116 : {|/(u[] * 2 < u[]) * .' ! u:#' = "0", x}

 MPO116' ("84884284";"123456";"444444999";"44499";"11";"111";"1")
32 0 27 12 0 3 0
Testez le code ici

Quelques explications :

Code : Tout sélectionner

 ="4444999"	/ Dictionnaire avec clés et positions
4|0 1 2 3
9|4 5 6  

 u:#'="4444999"	/ Nombre d'éléments pour chaque clé
 u
4|4
9|3

 !u		/ Les clés
"49"

 .'!u		/ Valeurs numériques des clés
4 9

 u[]		/ Valeurs du dictionnaire
4 3

 |/ 16 27
 27		/ Maximum d'un vecteur
Avatar du membre
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 499
Enregistré le : 05 mars 2020 20:45
Contact :

Re: Misez p'tit Optimisez en version APL

Message par Schraf »

Finalement une 3e version, cette fois-ci en testant les chiffres de 1 à 9 :

Code : Tout sélectionner

      MPO116 ← ⌈/ n × u × 2 < u ← +/ (n ← ⍳9) ∘.= ⍎¨

      MPO116¨ '84884284' '123456' '444444999' '44499' '11' '111' '1'
32 0 27 12 0 3 0
Avatar du membre
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 499
Enregistré le : 05 mars 2020 20:45
Contact :

Re: Misez p'tit Optimisez en version APL

Message par Schraf »

N°57 : Palindromes par zPalm version APL

Page 2 de ce fil j'ai donné une version de ce MPO en APL classique en ajoutant "en fait je suis incapable de résoudre ce problème en une seule ligne", ce que je démens aujourd'hui :

Code : Tout sélectionner

MPO57 ← {⍵ = a ← ⍎∘⌽⍕ ⍵ : a ⋄ ∇ ⍵ + a} 

      MPO57 167
88555588
C'est juste de la récursivité :

Code : Tout sélectionner

⍕ 167 --> '167'		⍝ Chaine de caractères
⌽⍕ 167 --> '761'	⍝ Inversion
⍎∘⌽⍕ 167 --> 761	⍝ Conversion en nombre
a ←			⍝ On mémorise dans "a"
⍵ = a			⍝ On teste si le nombre est son symétrique sont égaux
a			⍝ Si oui on renvoie "a"
⋄ ∇ ⍵ + a		⍝ Sinon on recommence avec le nombre + son symétrique
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

Re: Misez p'tit Optimisez en version APL

Message par Gilles59 »

j'étais passé à coté de cet article ... Après avoir lu les premiers posts et quelques vidéos d'initiations, je pense qu'il y a besoin de quelques heures pour déchiffrer ces hiéroglyphes mais j'ai trouvé ma Pierre de Rosette ;D
Casio FX-502P /602P / 603P / FX180P+ / FX4000P / TI57 / TI66 / TI74 Basicalc / TI95 Procalc / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49g+ / 50G / 50G NewRPL / HP Prime / Oric 1 / Amstrad CPC 6128+ CM14 et MM12 / Alice 32
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

Re: Misez p'tit Optimisez en version APL

Message par Gilles59 »

Schraf a écrit : 22 mai 2023 19:25 N°57 : Palindromes par zPalm version APL

Page 2 de ce fil j'ai donné une version de ce MPO en APL classique en ajoutant "en fait je suis incapable de résoudre ce problème en une seule ligne", ce que je démens aujourd'hui :

Code : Tout sélectionner

MPO57 ← {⍵ = a ← ⍎∘⌽⍕ ⍵ : a ⋄ ∇ ⍵ + a} 

      MPO57 167
88555588
:O Je ne comprends (encore) rien mais j'adore :D
Casio FX-502P /602P / 603P / FX180P+ / FX4000P / TI57 / TI66 / TI74 Basicalc / TI95 Procalc / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49g+ / 50G / 50G NewRPL / HP Prime / Oric 1 / Amstrad CPC 6128+ CM14 et MM12 / Alice 32
Avatar du membre
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 499
Enregistré le : 05 mars 2020 20:45
Contact :

Re: Misez p'tit Optimisez en version APL

Message par Schraf »

@Gilles59 : "Je ne comprends (encore) rien mais j'adore", oui ça fait ça au début et... euh... pareil après ! 😆😅

@FLISZT m'avait lancé sur une piste intéressante entre calculatrices HP et APL, j'en avais fait un petit tuto sur mon blog.

Sinon, il y a aussi les quelques challenges que j'ai proposés cette année sur le groupe Facebook "HP Calculator Fan Club" où j'ai mis les corrections en RPL, APL et parfois Python.
Si toi ou d'autres de ce forum trouvez des solutions meilleures, bien entendu je les ajouterai.
Avatar du membre
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 499
Enregistré le : 05 mars 2020 20:45
Contact :

Re: Misez p'tit Optimisez en version APL

Message par Schraf »

Proposition de code en APL pour le Misez P'tit, Optimisez - N°119 : Le Lièvre et la Tortue

Définition de la fonction f :

La fonction sinus s'écrit 1∘○ en APL et travaille en radians. On doit donc dans un premier temps transformer les degrés en radians, j'ai utilisé le code trouvé sur aplcart.info :

Code : Tout sélectionner

      (180÷⍨○) 90
1.570796327
      (180÷⍨○) 180
3.141592654
La fonction f proposée dans le MPO s'écrit :

Code : Tout sélectionner

sin ← 1∘○(180÷⍨○)
f ← {⌊193.5 - 89 × sin 77 × ⍵}
Code qui cherche récursivement la boucle :

Code : Tout sélectionner

s ← {⍵ ∊ ⍺ : ⍵,(|t-⍴⍺),t←⍺⍳⍵ ⋄ (⍵,⍺) s f ⍵} 
qui se traduit par : Si ⍵ est dans la liste des valeurs précédentes ⍺, afficher ⍵, la position de ⍵ dans ⍺ (qui s'écrit ⍺⍳⍵) et calculer "taille de ⍺ - position du ⍵" (qui s'écrit |t-⍴⍺). Sinon ajouter ⍵ à la liste ⍺ (qui s'écrit ⍵,⍺) et chercher si f ⍵ est dans cette nouvelle liste.

Code : Tout sélectionner

      ⍬ s 94	⍝ ⍬ est le vecteur nul
139 12 2
Pour éviter d'avoir à ajouter ⍬, voici le programme final :

Code : Tout sélectionner

mpo119 ← ⍬ s ⊢

      mpo119 243
243 0 11
      mpo119 811
272 6 9
      mpo119 1265
231 1 3
Le programme est à tester ici.
Avatar du membre
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 499
Enregistré le : 05 mars 2020 20:45
Contact :

Re: Misez p'tit Optimisez en version APL

Message par Schraf »

Proposition de code en APL pour le Misez P'tit, Optimisez - N°121 : Retournez à vos places ! Si quelqu'un voit plus court... 😅

Code : Tout sélectionner

mpo121 ← ⍋


	mpo121 5 1 4 2 3
2 4 5 3 1

	mpo121 12 7 5 6 2 3 1 9 13 4 8 10 11
7 5 6 10 3 4 2 11 8 12 13 1 9
A tester ici
Avatar du membre
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 499
Enregistré le : 05 mars 2020 20:45
Contact :

Re: Misez p'tit Optimisez en version APL

Message par Schraf »

Proposition de code en APL pour le M.P.O. n°118 : Discussion à Colney Hatch

Code : Tout sélectionner

	(n = +/¨ (⍎¨⍕)¨ u) / u ← (n ← 0,⍳54) * 3
0 1 512 4913 5832 17576 19683

Version similaire :

	∊(n = +/∘(⍎¨⍕)¨u) ⊆ u ← 3 *⍨ n ← 0,⍳54
Quelques explications :

* signifie "puissance" en APL

Code : Tout sélectionner

      2 * 3
8
On mémorise dans n les entiers de 0 à 54 et les puissances dans u.
Pour trouver la somme des chiffres, on transforme le nombre en chaine (⍕) et on convertit chaque (¨) caractère en chiffre (⍎), ce qui donne le ⍎¨

Code : Tout sélectionner

      (⍎¨⍕)¨ u ← (n ← 0,⍳10) * 3
┌─┬─┬─┬───┬───┬─────┬─────┬─────┬─────┬─────┬───────┐
│0│1│8│2 7│6 4│1 2 5│2 1 6│3 4 3│5 1 2│7 2 9│1 0 0 0│
└─┴─┴─┴───┴───┴─────┴─────┴─────┴─────┴─────┴───────┘
On fait maintenant les sommes des chiffres pour chaque case +/¨

Code : Tout sélectionner

      +/¨ (⍎¨⍕)¨ u ← (n ← 0,⍳10) * 3
0 1 8 9 10 8 9 10 8 18 1
On teste quelles valeurs sont égales à leur rang (0 et 1 sont bien aux positions 0 et 1, ainsi que le 8 avant le 18)

Code : Tout sélectionner

      n = +/¨ (⍎¨⍕)¨ u ← (n ← 0,⍳10) * 3
1 1 0 0 0 0 0 0 1 0 0
Ce qui permet de filtrer (/) les puissances et de ne conserver que celles qui répondent à la question.

A tester ici
Répondre

Retourner vers « Emulateurs »