Travaux : Php
Générateur et solveur de labyrinthes (dans Php, le 02/01/2010 à 19h 17min)
Je vais vous présenter ici le script que j'ai écrit dans le cadre du concours PHP organisé sur le Site du Zér0. L'énoncé ainsi que le topic du concours se trouve ici : sujet du concours.
Pour la petite histoire, j'ai fini 1er ex-æquo de ce concours. :)
Le compte-rendu est disponible ici : résultat sur le SdZ.
Exemple de rendu
La suite de l'article explique le principe de génération, et montre le script en action.
Je vais vous présenter ici le script que j'ai écrit dans le cadre du concours PHP organisé sur le Site du Zér0. L'énoncé ainsi que le topic du concours se trouve ici : sujet du concours.
Pour la petite histoire, j'ai fini 1er ex-æquo de ce concours. :)
Le compte-rendu est disponible ici : résultat sur le SdZ.
Exemple de rendu
La suite de l'article explique le principe de génération, et montre le script en action.
Résolveur de sudoku en PHP (dans Php, le 29/12/2009 à 22h 56min)
Petit retour dans le temps avec ce script retrouvé au fond de mon disque dur, et datant de Mars 2006. C'est mes premiers pas dans l'algorithmique, et dans l'utilisation du brute-force pour résoudre un problème : on test toutes les possibilités, jusqu'à ce qu'on trouve la solution.
Bien sûr, on respecte tout le temps les règles du sudoku, ce qui nous permet de largement limiter les essais. Cependant, il arrive souvent que l'on se retrouve dans une configuration où l'on ne peut plus rajouter de chiffre sans violer une des règles; dans ce cas, le sudoku est bloqué, il faut alors revenir en arrière et essayer une autre possibilité. On peut donc assimiler la recherche de la solution au parcours d'un arbre de possibilités en profondeur.
Avec le recul, je me dis qu'il faudrait reprendre au moins la moitié de ce script, qui me semble maintenant bien compliqué et bien mal pensé (surtout au niveau de la représentation des données et de l'organisation de l'algorithme; je pense qu'il y a beaucoup de calculs redondants), mais je n'ai pas forcément le temps ni l'envie.
Vous pourrez trouver ici :
Voilà, vous pourrez maintenant épater vos amis en résolvant n'importe quel sudoku !
Petit retour dans le temps avec ce script retrouvé au fond de mon disque dur, et datant de Mars 2006. C'est mes premiers pas dans l'algorithmique, et dans l'utilisation du brute-force pour résoudre un problème : on test toutes les possibilités, jusqu'à ce qu'on trouve la solution.
Bien sûr, on respecte tout le temps les règles du sudoku, ce qui nous permet de largement limiter les essais. Cependant, il arrive souvent que l'on se retrouve dans une configuration où l'on ne peut plus rajouter de chiffre sans violer une des règles; dans ce cas, le sudoku est bloqué, il faut alors revenir en arrière et essayer une autre possibilité. On peut donc assimiler la recherche de la solution au parcours d'un arbre de possibilités en profondeur.
Avec le recul, je me dis qu'il faudrait reprendre au moins la moitié de ce script, qui me semble maintenant bien compliqué et bien mal pensé (surtout au niveau de la représentation des données et de l'organisation de l'algorithme; je pense qu'il y a beaucoup de calculs redondants), mais je n'ai pas forcément le temps ni l'envie.
Vous pourrez trouver ici :
- la source php
- une démonstration du script : la grille de test proposée par défaut fait planter le script chez Free, je pense qu'il bouffe trop de mémoire. Quand je dis que ce n'est pas optimisé...
Voilà, vous pourrez maintenant épater vos amis en résolvant n'importe quel sudoku !
Pathfinding en PHP (dans Php, le 23/12/2009 à 13h 06min, édité 2 fois, dernier le 02/01/2010 à 19h 18min)
Le pathfinding, ou recherche de chemin en français, consiste grossièrement à trouver un chemin entre un point de départ et un point d'arrivé, respectant certaines contraintes (le plus court possible, par exemple).
C'est un problème qui peut se rapprocher à de la recherche opérationnelle :
Je vous présente dans la suite de l'article une implémentation en Php de l'algorithme A*
Le pathfinding, ou recherche de chemin en français, consiste grossièrement à trouver un chemin entre un point de départ et un point d'arrivé, respectant certaines contraintes (le plus court possible, par exemple).
C'est un problème qui peut se rapprocher à de la recherche opérationnelle :
Citation : Wikipédia
A la base, un problème de pathfinding peut se ramèner à un problème de recherche du meilleur chemin entre deux noeuds dans un graphe. Il existe un ensemble d'algorithmes classiques pour résoudre ce type de problème. Toutefois, le pathfinding devient un problème complexe lorsque l'on cherche à prendre en compte diverses contraintes additionnelles (exécution en temps réel, présence d'incertitudes, contrainte de ressources, environnement évolutif, etc).
Je vous présente dans la suite de l'article une implémentation en Php de l'algorithme A*
Le captcha : rebutons les robots ! (dans Php, le 17/04/2008 à 19h 16min)
Si vous avez essayé de poster un commentaire sur un des articles, vous avez sûrement vu ça :
C'est ce qu'on appelle un captcha :
Si vous voulez en savoir plus sur le processus de création que j'ai suivi pour celui là, lisez donc la suite de l'article !
Si vous avez essayé de poster un commentaire sur un des articles, vous avez sûrement vu ça :
C'est ce qu'on appelle un captcha :
Citation : Wikipédia
Ce test est utilisé sur Internet dans les formulaires pour se prémunir contre les soumissions automatisées et intensives réalisées par des robots malveillants.
Je vous laisse lire l'article sur Wikipédia, qui est bien fait, si vous êtes intéressé. Si vous voulez en savoir plus sur le processus de création que j'ai suivi pour celui là, lisez donc la suite de l'article !
Page (Php) : 1