Challenge n°3 : Algorithme de la goutte díeau

1. description

Le but de ce challenge est de déterminer les coordonnées du point díarrivé díune goutte díeau ( ou autre liquide ) " glissant " sur un terrain.
Ce défi reprend la définition du terrain donné dans le HoPsy n°1. Afin de ne pas défavoriser ceux qui ne sont pas abonné à HoPsy, je vais rappeler ce quíest un terrain :

Le terrain est représenté par un quadrillage. A chaque case correspond une altitude, qui a pour valeur un chiffre hexadécimal.

Version RPL : Le terrain est codé par une liste de listes díentiers binaires en hexadécimal de taille 64 bits. Chaque sous-liste représente une ligne de terrain et le 1^er entier de la liste le nombre de colonnes.
Exemple : { 2 { # DAh } { # 4h}}

Version RPL-Système et Assembleur : Le terrain est codé par une seule liste díentier binaire en hexadécimal de taille 4n, où n est le nombre de colonne du terrain. Chaque sous-liste représente une ligne du terrain.
Exemple : { { # DAh } { # 4h}}

2. Règles

La position de la goutte est déterminée par ses coordonnées { colonne ligne }. A chaque tour, la goutte glisse en fonction de la pente. Les règles à suivre dans líordre décroissantes sont :

Vers la case à plus forte pente
En cas díégalité au 1, choix de la case ou le changement díangle est le moins violent.
En cas díégalité au 2, le choix se fait dans le sens contraire des aiguilles díune montre ( sens trigonométrique, cíest aussi le sens dans laquelle tourne líeau dans un tourbillon dans líhémisphère nord, enfin jíespère que je ne me trompe pas )
Arrêt de la goutte dés quíil níy a pas de case plus basse que celle où se situe la goutte. Les bords du terrain sont considérés comme ayant une valeur strictement supérieure à # Fh.

3. Exemple

 3.1 Terrain et coordonnées

Colonne ligne	1	2	3	4	5	Position díorigine { 3 1 } Tour 1 { 4 2 } Tour 2 { 4 3 } Tour 3 { 3 4 } Position finale { 2 4 }
1	F	B	A	8	E
2	C	7	8	6	6
3	8	8	5	5	6
4	3	3	4	5	4

3.2 Explications

Tour 1 : plus forte pente { 4 2 }
Tour 2 : angle le moins violent : calcul

tour 0 { 3 1 }
tour 1 { 4 2 }

a) arrivée possible (2) { 4 3 } angle : 135°
b) arrivée possible (2) { 3 3 } angle : 90°
f choix : angle a) > angle b) : { 4 3 }

Tour 3 : sens trigonométrique : calcul

tour 1 { 4 2 }
tour 2 { 4 3 }
a) arrivée possible (3) { 3 4 } angle :135°
b) arrivée possible (3) { 5 4 } angle :135°
f égalité d'angle : la case { 5 4 } est la première case si on tourne autour de la case d'origine { 4 3 } dans le sens trigonométrique : { 5 4 }

Tour 4 : plus forte pente { 2 4 }
Tour 5 : Arrêt ( pas de case plus basse ) { 2 4 }

4. Le programme

Le programme à réaliser devra prendre comme argument au niveau 2 de la pile une liste représentant le terrain et au niveau 1 une liste de deux entiers représentant les coordonnées díorigine de la goutte. Il rendra comme résultat au niveau 1 de la pile une liste correspondant à la position finale de la goutte.

Le programme ne doit en aucun cas modifier le reste de la pile (niveau 3 et supérieurs).

5. Exemple en RPL

6. Gagnant

Le gagnant sera le programme dont la taille (en octet) multipliée par la vitesse díexécution (en seconde) sera la plus petite (mesuré avec TK.EXT, CF. HoPsy n°0). Actuellement il níy a aucun programme de référence.

La date limite de participation est fixée à 15 jours après la parution le HoPsy n°3.

Bonne algorithme et bonne course !

P.S.: Si vous pensez qu'un terrain à des caractéristiques intéressantes dans le cas de cet algorithme, envoyer le nous avec votre source.