Lernzettel: Optimisation des Suites de Déplacements

📋 Plan du Cours

1. Objectif de la version 2
2. Fonctionnement attendu du programme
3. Bilan et sauvegarde de la suite
4. Déplacements non joués et séquences inutiles

📖 1. Objectif de la version 2

🔑 Notions clés & Définitions

• Version 2 : Version 2 désigne l’amélioration du programme qui réduit une suite de déplacements en supprimant ce qui ne change pas réellement l’état du jeu.
• Suite de déplacements : Une suite de déplacements est une liste de caractères lue depuis un fichier .dep et destinée à être jouée sur une partie définie par un fichier .sok.

📝 Points essentiels

• La version 2 complète la version 1 en supprimant de la suite tout déplacement non joué et toute séquence inutile avant d’évaluer la solution.
• Le programme doit comparer la longueur de la suite initiale et la longueur de la suite après optimisation, quand la suite optimisée est une solution pour la partie.

📖 2. Fonctionnement attendu du programme

🔑 Notions clés & Définitions

• Fichier .sok : Le fichier .sok contient la description de la partie à jouer par le programme.
• Fichier .dep : Le fichier .dep contient la suite de déplacements à exécuter, sous forme de caractères.
• Bilan : Le bilan est l’affichage final indiquant si la suite (optimisée) constitue une solution ou non pour la partie choisie.

📝 Points essentiels

• Le programme doit demander à l’utilisateur le nom d’une partie au format .sok, puis le nom d’une suite au format .dep.
• Pendant le jeu, chaque déplacement doit être visible à l’écran et une pause doit séparer deux déplacements pour permettre le suivi.
• Le programme doit toujours afficher si la suite constitue une solution ou non pour la partie choisie.
• Si la suite est une solution, il affiche d’abord la longueur de la suite initiale, puis la longueur après optimisation en supprimant les déplacements non joués et les séquences inutiles.
• Après le bilan, le programme demande à l’utilisateur s’il souhaite enregistrer la suite optimisée avec une réponse O/N.

📖 3. Bilan et sauvegarde de la suite

🔑 Notions clés & Définitions

• Longueur de la suite initiale : La longueur de la suite initiale est le nombre de caractères du fichier .dep.
• Longueur après optimisation : La longueur après optimisation est le nombre de caractères de la suite une fois supprimés les déplacements non joués et les séquences inutiles.
• Enregistrement de la suite optimisée : L’enregistrement de la suite optimisée correspond au fait de stocker la suite après réduction, sur demande de l’utilisateur.

📝 Points essentiels

• Dans l’exemple 1, la suite a une longueur initiale de 999 caractères et reste de 999 après optimisation car aucune réduction n’est applicable.
• Dans l’exemple 1, le programme propose l’enregistrement et la réponse donnée est O.
• Dans l’exemple 2, la suite n’est pas une solution, donc l’optimisation ne peut pas être validée comme solution pour la partie concernée.

📖 4. Déplacements non joués et séquences inutiles

🔑 Notions clés & Définitions

• Déplacement non joué : Un déplacement non joué est un caractère de la suite qui ne provoque aucun changement effectif sur le plateau lorsqu’il est tenté.
• Séquence inutile : Une séquence inutile est une suite de déplacements où aucune caisse n’est déplacée et où Sokoban revient exactement à sa position de départ.
• Exemple d’élimination d’un déplacement non joué : Un exemple de déplacement non joué est un mouvement vers un mur, qui échoue donc sans déplacer Sokoban sur le plateau.

📝 Points essentiels

• Un déplacement non joué correspond à une tentative qui ne peut pas être jouée, par exemple un déplacement vers la droite s’il y a un mur à droite.
• Une séquence inutile ne progresse pas vers la victoire car l’état du jeu avant la séquence est identique à l’état après la séquence.
• Dans l’exemple dDhhdgDb, la sous-séquence dg est une séquence inutile car elle ramène Sokoban au point de départ après exécution complète correspondante dDhhDb.

⚠️ Pièges & confusions fréquents

1. Confondre déplacement non joué et séquence inutile : un non joué concerne un caractère qui n’a aucun effet, tandis qu’une séquence inutile peut revenir au point de départ sans déplacer de caisses.
2. Croire qu’une séquence inutile peut déplacer des caisses : elle doit au contraire contenir aucun déplacement de caisse.
3. Penser qu’une séquence inutile doit forcément être de longueur 2 : l’exemple montre dg, mais la définition ne limite pas la taille.
4. Réduire la suite sans re-vérifier la solution : le bilan doit rester exact, même si la longueur change après optimisation.
5. Oublier de compter correctement la longueur après optimisation : c’est la longueur de la suite réellement obtenue après suppressions, pas la longueur initiale.
6. Confondre l’enregistrement O/N avec le test de solution : l’enregistrement ne remplace pas l’affichage du résultat de solvabilité.

✅ Checklist Examen

1. Identifier les deux fichiers demandés : nom de partie en .sok puis nom de suite en .dep.
2. Expliquer ce qu’est un déplacement non joué et donner une cause typique (mouvement bloqué sans effet sur le plateau).
3. Expliquer ce qu’est une séquence inutile en respectant ses deux conditions : aucune caisse déplacée et retour exact à la position de départ.
4. Décrire la logique d’optimisation attendue : supprimer les déplacements non joués puis supprimer les séquences inutiles de la suite.
5. Indiquer ce que le programme affiche quand la suite n’est pas une solution : il doit toujours annoncer non-solvable pour cette partie.
6. Indiquer ce que le programme affiche quand la suite est une solution : longueur initiale puis longueur après optimisation.
7. Préciser que la longueur initiale correspond au nombre de caractères du fichier .dep.
8. Préciser que le jeu doit être visible pas à pas : affichage de chaque déplacement et pause suffisante entre deux déplacements.
9. Mentionner que le programme demande ensuite l’utilisateur pour enregistrer la suite optimisée avec une réponse O/N.
10. Savoir associer les exemples aux notions : exemple 1 où la longueur ne change pas (999), et exemple 2 où la suite n’est pas une solution.