Algorithmique

Génération aléatoire d’un labyrinthe de cavernes et de tunnels

SoC,
Comment générer aléatoirement un labyrinthe à base de tunnels et de cavernes en creusant tant qu'il est possible un surface ? Le résultat doit ressembler à cette sorte de gruyère (la partie praticable est en gris) :
Labyrinthe aléatoire avec murs droits
Continuer la lecture de "Génération aléatoire d’un labyrinthe de cavernes et de tunnels" →
Génération aléatoire d’un labyrinthe de cavernes et de tunnels

Tri aléatoire des éléments d’un tableau

SoC,
Comment tirer aléatoirement, l'un après l'autre jusqu'à épuisement, les éléments d'un tableau ? La solution qui vient spontanément à l'esprit n'est pas efficace : elle consiste à générer un indice aléatoire, vérifier si l'élément figurant à cet indice a déjà été tiré, et si tel est le cas, recommencer.
A ce petit jeu, il est probable que le temps pris pour tirer un élément s'allonge tandis que le nombre d'éléments tirés s'accroit.
Ne peut-on procéder plus efficacement ?

Continuer la lecture de "Tri aléatoire des éléments d’un tableau" →

Tri aléatoire des éléments d’un tableau

Génération aléatoire d’un nombre entier compris dans un intervalle

SoC
Comment générer aléatoirement un nombre entier compris dans un intervalle, c'est-à-dire entre des valeurs minimale et maximale ? La solution qui vient spontanément à l'esprit (min + Math.round ((max -1) * Math.random ())) n'est pas correcte, car elle n'assure pas la représentativité statistique équitable (équiprobabilité) de tous les entiers possibles.
Par exemple, la répétition de 1 000 tirages d'une valeur dans l'intervalle [3, 9] permet de dégager les probabilités d'occurrence par valeur suivantes :
Génération aléaoitre d'un entier compris dans un intervalle (mauvais)
Pourquoi ce problème, et comment y remédier ?

Continuer la lecture de "Génération aléatoire d’un nombre entier compris dans un intervalle" →

Génération aléatoire d’un nombre entier compris dans un intervalle

Inversion de contrôle pour gérer les événements

SoC, ,
Le développement d'une IHM (interface homme-machine) conduit très rapidement à associer un traitement à une séquence d'actions. Par exemple, attendre que l'utilisateur presse la touche "Suppr" pour initier la suppression d'un élément graphique, puis qu'il clique sur un élément graphique pour supprimer ce dernier. On parle ici d'un automate qui est dans un état d'attente de la pression de la touche "Suppr", puis dans un état d'attente d'un clique sur un élément avant de revenir à son état initial.
La solution qui vient à l'esprit est de s'appuyer sur la gestion des événements du système. Il s'agit d'associer un gestionnaire d'événement à chacun des événements qui entraîne un possible changement d'état de l'automate, et de gérer dans ce gestionnaire le changement d'état. Pour reprendre l'exemple, supposons qu'il s'agisse de permettre de supprimer un élément HTML d'identifiant "tagElement" en pressant la touche Suppr, puis en cliquant sur l'élément. Le code JavaScript est alors le suivant : 
var STATE_IDLE = 0;
var STATE_KEYPRESSED = 1;
var state;

function run () {
	document.body.addEventListener ("keypress", handlerKeyPress, false);
	document.getElementById ("tagElement").addEventListener ("click", handlerMouseClick, false);
	state = STATE_IDLE;
}

function handlerKeyPress (e) {
	switch (state) {
		case STATE_IDLE :
			if (e.key != "Delete")
				break;
			state = STATE_KEYPRESSED;
			document.getElementById ("tagElement").innerHTML = "Cliquez-moi maintenant";
			break;
	}
}

function handlerMouseClick (e) {
	switch (state) {
		case STATE_KEYPRESSED :
			document.getElementById ("tagElement").innerHTML = "Vous m'avez supprimé ! (pressez Suppr pour recommencer)";
			state = STATE_IDLE;
			break;
	}
}
Cliquez ici pour accéder à une page de test minimaliste. Vous pourrez visualiser le code et le récupérer pour travailler avec.
Le problème est que le code de l'automate est réparti dans les deux gestionnaires d'événement impliqués. En soi, c'est déjà compliqué. Ça le devient encore plus tandis que l'IHM s'enrichit et que les automates de ce type se multiplient et se complexifient. N'est-il pas possible de regrouper le code d'un automate dans une seule fonction spécifique ?

Continuer la lecture de "Inversion de contrôle pour gérer les événements" →

Inversion de contrôle pour gérer les événements