It is alive! Alive!!
Cette semaine, c'est Thomas qui vous propose un #KataOfTheWeek : The Conway's game of life
Briefing du Kata : Si vous ne le connaissez pas, le jeu de la vie prend la forme d'un tableau bidimentionnel théoriquement infini, dans lequel chaque case est une cellule. Une cellule est soit morte, soit vivante et a donc exactement 8 voisines. Ce qui rend le jeu intéressant ce sont les règles de naissance et de mort des cellules. À chaque tour les cellules naissent ou meurent suivant ces règles :
- Une cellule morte qui a exactement 3 voisines en vie naît
- Une cellule vivante qui a 2 ou 3 voisines reste en vie
- Dans tous les autres cas elle meurt d'isolement ou d'étouffement.
Pour tester si votre jeu marche pour la configuration tour n suivante :
*
* *
* *
*
Une *représente une cellule en vie. Au tour suivant vous aurez cette configuration :
***
***
Et au tour suivant vous retrouverez la configuration du tour n.
Puisque ce Kata est un grand classique de programmation, il n'est pas improbable que vous l'ayez déjà fait. Si tel été le cas, il pourrait être intéressant que vous le fassiez dans un langage de programmation que vous auriez envie d'apprendre. Ou bien encore faire une version web en utilisant un framework comme React ou en essayant de mettre en place le pattern MVC avec du webassembly ! Et pour tout ceux qui le finisse une première fois, n'hésitez pas à expérimenter les variantes de programmation ou bien encore à changer les règles de naissance / décès des cellules.
Saurez-vous résoudre le problème ?
Bon courage !
Et voici plusieurs solutions proposées par l'auteur :
Pour ce challenge je vous propose plusieurs solutions. La première est une solution entièrement web. Sur cette approche là, l'objectif était d'avoir une interface graphique qui permettrait à l'utilisateur de mettre le programme en pause et d'ajouter des cellules quand il souhaite. Tout est dans le même fichier index.html pour faciliter l'implémentation. Le but n'était pas forcément de faire un code propre, mais fonctionnel et qui permettrait de s'amuser avec plein de cellules dans des couleurs un peu douteuses :
<!DOCTYPE html>
<html>
<head>
<title>Game of Life</title>
<meta charset="utf-8"/>
<style>
.container {
display: grid;
grid-template-columns: repeat(4, 1fr);
grid-auto-rows: 25px;
gap: 1px;
}
.item {
background-color: blue;
}
.dead {
background-color: darkviolet;
}
.alive {
background-color: gold;
}
</style>
</head>
<body>
<input id="pause" type="checkbox" onclick="pauseGeneration(this)"/>
<label for="pause">Pause</label>
<div class="container"></div>
</body>
<script>
let pause = false;
function pauseGeneration(elem) {
pause = elem.checked;
}
document.body.onkeydown = (event) => {
if (event.keyCode === 32 || event.keyCode === 80) {
pause = !pause;
document.getElementById("pause").checked = pause;
}
};
const HEIGHT = 64;
const WIDTH = 64;
const CELLS = [];
function createDivCell(x, y) {
let div = document.createElement("div");
div.state = 0;
div.setAttribute("class", div.state === 1 ? "alive" : "dead");
div.nextState = 0;
div.onclick = () => {
div.state = (div.state + 1) % 2;
div.classList.remove("dead", "alive");
if (div.state === 1) {
div.classList.add("alive");
} else {
div.classList.add("dead");
}
}
return div;
}
const container = document.getElementsByClassName("container")[0];
container.style["grid-template-columns"] = `repeat(${WIDTH}, 1fr)`;
for (let y = 0; y < HEIGHT; ++y) {
for (let x = 0; x < WIDTH; ++x) {
const div = createDivCell(x, y);
container.appendChild(div);
CELLS.push(div);
}
}
for (let y = 0; y < HEIGHT; ++y) {
for (let x = 0; x < WIDTH; ++x) {
const neighboors = [
getNeighboor(CELLS, x - 1, y + 1),
getNeighboor(CELLS, x, y + 1),
getNeighboor(CELLS, x + 1, y + 1),
getNeighboor(CELLS, x - 1, y),
getNeighboor(CELLS, x + 1, y),
getNeighboor(CELLS, x - 1, y - 1),
getNeighboor(CELLS, x , y - 1),
getNeighboor(CELLS, x + 1, y - 1)
];
CELLS[y * WIDTH + x].neighboors = neighboors.filter(elem => elem !== undefined);
}
}
setInterval(() => {
if (pause) {
return;
}
for (let cell of CELLS) {
const neighboorsSum = cell.neighboors.reduce((acc, elem) => acc + elem.state, 0);
if (neighboorsSum === 3) {
cell.nextState = 1;
} else if (neighboorsSum !== 2) {
cell.nextState = 0;
} else {
cell.nextState = cell.state;
}
}
nextGeneration(CELLS);
}, 1000);
function getNeighboor(cells, x, y) {
if (x < 0 || x >= WIDTH || y < 0 || y >= HEIGHT) {
return undefined;
}
return cells[y * WIDTH + x]
}
function nextGeneration(cells) {
for (let cell of cells) {
cell.state = cell.nextState;
cell.setAttribute("class", cell.state === 1 ? "alive" : "dead");
}
}
</script>
</html>Dans cette première version les div contiennent à la fois l'état courant de la cellule et celle de la prochaine génération. On maintient un tableau avec toutes les cellules. Lorsqu'on calcule la génération suivante de cellule on se base sur la génération actuelle, on stock le résultat, et lorsque le calcul est terminé on transforme la génération actuelle avec l'état de la suivante.
Dans la seconde version, l'idée est de maintenir un tableau avec les cellules vivantes uniquement. Du coup une cellule contient un état (morte ou vivante) ainsi qu'une coordonné sur la grille à 2 dimensions. Pour la seconde version, j'ai également pris le partie de l'implémenter en Rust afin d'expérimenter quelque possibilité de macro que nous offre le langage. Voici l'implémentation :
range.rs
#[macro_use]
macro_rules! range {
($e:expr; $v:ident in $range:expr) => {{
let mut vec = vec![];
for $v in $range {
vec.push($e)
}
vec
}};
($e:expr; $v1:ident in $range1:expr, $($v:ident in $range:expr),*) => {{
let mut res = vec![];
for $v1 in $range1 {
__range!($e; $($v in $range),* => res)
}
res
}};
($e:expr; $v1:ident in $range1:expr, $($v:ident in $range:expr),*; $cond:expr) => {{
let mut res = vec![];
for $v1 in $range1 {
__range!($e; $($v in $range),*; $cond => res)
}
res
}}
}
macro_rules! __range {
($exp:expr; $i:ident in $r:expr => $res:ident) => {{
for $i in $r {
$res.push($exp);
}
}};
($exp:expr; $i:ident in $r:expr, $($i1:ident in $r1:expr),+ => $res:ident) => {{
for $i in $r {
__range!($exp; $($i1 in $r1),* => $res)
}
}};
($exp:expr; $i:ident in $r:expr; $cond:expr => $res:ident) => {{
for $i in $r {
if $cond {
$res.push($exp);
}
}
}};
($exp:expr; $i:ident in $r:expr, $($i1:ident in $r1:expr),+; $cond:expr => $res:ident) => {{
for $i in $r {
__range!($exp; $($i1 in $r1),*; $cond => $res)
}
}}
}
Ce fichier contient l'ensemble des macros pour pouvoir générer des listes avec une syntaxe par compréhension comme en python ou en haskell par exemple.
Et voici le fichier principale :
#[macro_use]
mod range;
use std::{thread, time, fmt};
use std::collections::{HashMap, HashSet};
const HEIGHT: usize = 4;
const WIDTH: usize = 4;
#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
enum CellState {
DEAD,
ALIVE,
}
type Coord = (i32, i32);
#[derive(PartialEq, Debug, Clone, Copy, Eq, Hash)]
pub struct Cell {
coord: Coord,
state: CellState,
}
impl Cell {
fn dead(coord: Coord) -> Cell {
Cell {
coord,
state: CellState::DEAD,
}
}
fn alive(coord: Coord) -> Cell {
Cell {
coord,
state: CellState::ALIVE,
}
}
fn from(cell: &Cell) -> Cell {
Cell { ..*cell }
}
pub fn is_alive(&self) -> bool {
self.state == CellState::ALIVE
}
}
impl fmt::Display for Cell {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
if self.state == CellState::DEAD {
write!(f, "-")
} else {
write!(f, "*")
}
}
}
pub fn compute_new_generation(cells: &[Cell]) -> Vec<Cell> {
let alive_cells: HashMap<Coord, Cell> = cells
.iter()
.filter(|cell| cell.is_alive())
.map(|&cell| (cell.coord, cell))
.collect();
let neighboors = neighboors_set(&alive_cells);
alive_cells
.values()
.chain(dead_neighboors(&alive_cells, &neighboors).iter())
.filter_map(|cell| compute_next_cell_state(cell, &alive_cells))
.filter(|cell| cell.is_alive())
.collect()
}
fn neighboors_set(cells: &HashMap<Coord, Cell>) -> HashSet<Coord> {
cells
.values()
.flat_map(|cell| {
let (x, y) = cell.coord;
range![(x + i, y + j); i in -1..=1, j in -1..=1; i != 0 || j != 0].into_iter()
})
.collect()
}
fn dead_neighboors(cells: &HashMap<Coord, Cell>, neighboors: &HashSet<Coord>) -> Vec<Cell> {
neighboors
.into_iter()
.filter(|coord| !cells.contains_key(coord))
.map(|&cell| Cell::dead(cell))
.collect()
}
fn compute_next_cell_state(cell: &Cell, alive_cells: &HashMap<Coord, Cell>) -> Option<Cell> {
let (x, y) = cell.coord;
let nb_of_alive_neighboor = range![(x + i, y + j); i in -1..=1, j in -1..=1; i != 0 || j != 0]
.iter()
.fold(0, |acc, elem| {
acc + alive_cells.get(&elem).map(|_| 1).unwrap_or(0)
});
if nb_of_alive_neighboor == 3 {
Some(Cell::alive(cell.coord))
} else if nb_of_alive_neighboor != 2 {
None
} else {
Some(Cell::from(&cell))
}
}
fn display_grid(grid: &[Cell]) {
let mut i = 0;
let dead = Cell::dead((0, 0));
for y in 0..HEIGHT {
for x in 0..WIDTH {
if i < grid.len() {
let cell = grid[i];
if cell.coord.0 == x as i32 && cell.coord.1 == y as i32 {
i += 1;
print!("{} ", cell);
} else {
print!("{} ", dead);
}
} else {
print!("{} ", dead);
}
}
println!("");
}
}
fn main() {
println!("Hello, world!");
let mut grid = vec![
Cell::alive((2, 0)), Cell::alive((0, 1)), Cell::alive((3, 1)),
Cell::alive((0, 2)), Cell::alive((3, 2)), Cell::alive((1, 3)),
];
let waiting_time = time::Duration::from_millis(500);
loop {
grid.sort_by_key(|&cell| (cell.coord.1, cell.coord.0));
display_grid(&grid);
grid = compute_new_generation(&grid);
println!("");
thread::sleep(waiting_time);
}
}
Ici contrairement à la première solution, le programme est un programme console et l'utilisateur ne peut pas définir le placement des cellules sur la grille, il faut définir dans les sources les coordonnées des cellules vivantes ainsi que la taille de la grille.
En espérant vous avoir donné envie de tester votre propre version du jeu de la vie avec votre langage favori et vos propres règles ! Longue vie au jeu
Votre équipe TakiVeille