Si ça intéresse des gens, j'ai récemment écrit une implémentation de HashLife, un algorithme sophistiqué pour calculer l'état d'un jeu de la vie un grand nombre de générations dans le futur. Le code, en OCaml, est documenté à but pédagogique : c'était avant tout pour moi, pour bien comprendre l'algorithme, mais aussi pour pouvoir l'expliquer aux autres.
(En deux mots, l'idée de Hashlife est de compresser à la fois le temps et l'espace: au lieu de calculer seulement une géneŕation dans le futur, on calcule l'état dans 2N générations, et au lieu de recalculer à chaque endroit on essaie de reconnaître et partager les motifs spatiaux répétés.)
# Une implémentation documentée de HashLife en OCaml
Posté par gasche . En réponse au journal Le jeu de la vie: conférence de Jean-Paul Delahaye. Évalué à 5.
Si ça intéresse des gens, j'ai récemment écrit une implémentation de HashLife, un algorithme sophistiqué pour calculer l'état d'un jeu de la vie un grand nombre de générations dans le futur. Le code, en OCaml, est documenté à but pédagogique : c'était avant tout pour moi, pour bien comprendre l'algorithme, mais aussi pour pouvoir l'expliquer aux autres.
La discussion autour du programme est là :
http://progmod.org/forum/sujet/310/hashlife-explique-en-ocaml/
Le code source directement:
https://gitorious.org/hashlife-in-literate-ocaml/hashlife-in-literate-ocaml/blobs/master/hashlife.ml
(En deux mots, l'idée de Hashlife est de compresser à la fois le temps et l'espace: au lieu de calculer seulement une géneŕation dans le futur, on calcule l'état dans 2N générations, et au lieu de recalculer à chaque endroit on essaie de reconnaître et partager les motifs spatiaux répétés.)