Discussion :

[djibril]

Merci lolo pour ta vidéo des journées Perl sur le jeu : Bien utiliser les structures de données pour améliorer les performances

[Philou67430]

[Lolo78]

Merci à vous pour vos encouragements. Je pense qu'il y a maintenant prescription, je posterai le code de la solution au jeu de Khalou dès que j'ai le temps.

[Lolo78]

Bonsoir,

donc voilà, s'il s'agissait d'un devoir scolaire pour l'auteur du post de départ, l'échéance est forcément passée, je n'ai plus de scrupule à divulguer la solution complète. Et comme les moteurs de recherche peuvent amener des personnes intéressées sur ce fil, autant donner maintenant la solution complète que j'avais faite en février (d'autant plus que c'est l'un des trois exemples dont j'ai parlé publiquement aux Journées Perl 2013 à la mi-juin 2013, voir ci-dessus le lien donné par Djibril pour ceux que ça intéresse).

Voici donc le code du programme:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
use strict;
use warnings;
 
my @coup = qw /15 19 35 38 49 50 70 76 98 100 140 196 200 240 304 560 608 784 800 1120 1216 1568 1600 2240 3136 3200 3840 4369 4680 4864 8738 8960 9728 12544 12800 17476 17920 19456 25088 25600 33825 34952 35840 50176 51200 61440 /;
 
my (%solutions, @count, $count, @sol_count);
$solutions{0} = 0; 
$count[0] = 1;
 
foreach my $step (1..5) {
	foreach my $sol1 (keys %solutions) {
		next unless $solutions{$sol1} == ($step - 1);
		foreach my $c (@coup) {
			my $result = $sol1 ^ $c;
			next if defined $solutions{$result};
			$solutions{$result} = $step;
			$count[$step]++;
		}
	}
}
print "il y a $count[$_] positions solubles en $_ coups. \n" for (0..5);

Le code est d'une simplicité quasi biblique, et, en outre, j'ai expliqué à peu près tout dans les posts précédents, je ne vois rien à ajouter, mais me tiens à la disposition de quiconque désire des explications.

Cette version du programme ne vise qu'à répondre à la question d'origine: combien de situations de départ solubles en 1, 2, 3, 4 et 5 coups.

Moyennant deux ou trois toutes petites modifications, on peut stocker dans le hash le coup à exécuter pour chaque situation et créer, pour chaque situation de départ une sorte de liste chaînée des coups à exécuter successivement pour résoudre le problème de la meilleure façon possible.

A noter aussi que dans ce cas précis, l'index du hash est finalement un nombre compris entre 0 et 65535. L'utilisation d'un tableau serait plus efficace (à la louche, à peu près deux fois plus rapide), mais, bon, quand on résout le problème en 2 ou 3 secondes, on s'en moque un peu. Dans ce cas précis, je veux juste ma solution en un temps acceptable, je n'ai aucun besoin de faire le mieux possible. Je suis donc resté avec un hash.

Dernier point sur ce qui pourrait paraître être une incohérence dans mes propos: sur un post précédent, posté en février, j'ai parlé d'une durée d'exécution de moins de 3 secondes sur mon vieux portable. Aux Journées Perl de Nancy, je parle d'environ 1,5 seconde. La différence s'explique tout simplement par un changement d'ordinateur entre temps, et j'ai refait les mesures à zéro pour la préparation de ma présentation à Nancy.