Algorithms
  • Introduction
  • Analysis of Algorithms
  • Numbers
    • Reverse Integer
    • Palindroms
      • Valid Palindrome
    • Prime factor
    • Prime Number
    • Roman to Integer
    • Happy Number
    • p^k
  • Searching
    • Union-Find Algorithms
    • Finding Peak
    • Find Sum in Array
    • Binary Search
      • Find Index Binary Search
      • Sqrt(x)
      • Search in Rotated Sorted Array
      • Guess Number Higher or Lower
      • First Bad Version
      • Find Peak Element
      • Find Minimum in Rotated Sorted Array
      • Find Minimum in Rotated Sorted Array II
      • Search for a Range
      • Closest Binary Search Tree Value
      • Find K Closest Elements
      • Search in a Sorted Array of Unknown Size
      • Pow(x, n)
      • Valid Perfect Square
      • Find Minimum in Rotated Sorted Array II
      • Intersection of Two Arrays
      • Intersection of Two Arrays II
      • Two Sum II - Input array is sorted
      • Find the Duplicate Number
    • Longest Common Prefix
  • Sorting
    • Elementary Sorts
    • Insertion Sort
    • Bubble Sort
    • Mergesort
    • Quicksort
    • Radix Sort
    • Heap Sort
  • Data Structures
    • Array & List
      • Find Pivot Index
      • Largest Number At Least Twice of Others
      • Plus One
      • Diagonal Traverse
      • Spiral Matrix
      • Pascal's Triangle
      • Implement strStr()
      • Add Binary
      • Duplicate Counts
      • Find Duplicates
      • Reverse String
      • Array Partition I
      • Two Sum II - Input array is sorted
      • Remove Element
      • Max Consecutive Ones
      • Minimum Size Subarray Sum
      • Reverse Words in a String
      • Reverse Words in a String III
      • Remove Duplicates from Sorted Array
      • Move Zeroes
      • Rotate Array
      • Rotate Image
      • Best Time to Buy and Sell Stock
      • Best Time to Buy and Sell Stock II
      • Valid Anagram
      • 3Sum
      • String to Integer (atoi)
      • Count and Say
      • Merge Sorted Array
      • Shuffle an Array
      • Max Area of Island
    • Matrix
    • Stack
      • Valid Parentheses
      • Min Stack
    • Queue
    • Linked List
      • Design Linked List
      • Design Doubly Linked List
      • Find Middle Element
      • Doubly Linked List
      • Cyclic Linked List
      • Linked List Cycle II
      • Find Nth Element from End
      • Remove Nth Node From End of List
      • Add Two Numbers
      • Merge Two Sorted Lists
      • Remove Nth Node From End of List
      • Reverse Linked List
      • Remove Linked List Elements
      • Odd Even Linked List
      • Design Doubly Linked List
      • Flatten a Multilevel Doubly Linked List
      • Rotate List
      • Copy List with Random Pointer
      • Insert into a Cyclic Sorted List
      • Delete Node in a Linked List
      • Palindrome Linked List
    • Set
      • Intersection of Two Arrays
      • Single Number
      • Contains Duplicate
      • Contains Duplicate II
      • Jewels and Stones
      • Longest Substring Without Repeating Characters
      • Two Sum III - Data structure design
      • Valid Sudoku
      • Missing Number
    • Map
      • Two Sum
      • Isomorphic Strings
      • Minimum Index Sum of Two Lists
      • First Unique Character in a String
      • Intersection of Two Arrays II
      • Logger Rate Limiter
      • Group Anagrams
      • Group Shifted Strings
      • Find Duplicate Subtrees
      • 4Sum II
      • Top K Frequent Elements
      • Unique Word Abbreviation
      • Insert Delete GetRandom O(1)
    • Binary Tree
      • Binary Tree Preorder Traversal
      • Binary Tree Inorder Traversal
      • Binary Tree Postorder Traversal
      • Binary Tree Level Order Traversal
      • Maximum Depth of Binary Tree
      • Symmetric Tree
      • Path Sum
      • Balanced Binary Tree
      • Count Univalue Subtrees
      • Construct Binary Tree from Inorder and Postorder Traversal
      • Construct Binary Tree from Preorder and Inorder Traversal
      • Populating Next Right Pointers in Each Node
      • Lowest Common Ancestor of a Binary Tree
      • Serialize and Deserialize Binary Tree
      • Median of Two Sorted Arrays
      • Invert Binary Tree
      • Find K-th Smallest Pair Distance
      • Split Array Largest Sum
    • Heap
    • Binary Search Tree
      • Validate Binary Search Tree
      • Inorder Successor in BST
      • Binary Search Tree Iterator
      • Search in a Binary Search Tree
      • Insert into a Binary Search Tree
      • Delete Node in a BST
      • Kth Largest Element in a Stream
      • Lowest Common Ancestor of a Binary Search Tree
      • Contains Duplicate III
      • Height-Balanced BST
        • Balanced Binary Tree
        • Convert Sorted Array to Binary Search Tree
    • Map
    • N-ary Tree
      • N-ary Tree Preorder Traversal
      • N-ary Tree Postorder Traversal
      • N-ary Tree Level Order Traversal
      • Maximum Depth of N-ary Tree
      • Encode N-ary Tree to Binary Tree
      • Serialize and Deserialize N-ary Tree
    • Trie
      • Implement Trie (Prefix Tree)
      • Map Sum Pairs
      • Replace Words
      • Design Search Autocomplete System
      • Maximum XOR of Two Numbers in an Array
      • Add and Search Word - Data structure design
      • Word Search II
      • Word Squares
      • Longest Common Prefix
      • Palindrome Pairs
    • Balanced Tree
      • B-Tree
      • Red-black Tree
      • AVL Tree
    • Graph
      • A* Search
      • Breadth First Search
      • Depth First Search
      • Dijkstra Algorithm
  • Sequences
    • Fibonacci Sequence
  • Dynamic Programming
    • Knapsack problem
    • Climbing Stairs
    • Best Time to Buy and Sell Stock
    • Maximum Subarray
    • House Robber
  • Interviews
    • Google Leetcode
      • Repeated String Match
      • K Empty Slots
      • Next Closest Time
      • Longest Univalue Path
      • License Key Formatting
      • Spiral Matrix
      • Plus One
      • Trapping Rain Water
      • Longest Substring with At Most K Distinct Characters
      • Add Bold Tag in String
      • Game of Life
      • Read N Characters Given Read4
      • Read N Characters Given Read4 II - Call multiple times
      • One Edit Distance
      • Valid Palindrome
      • Valid Number
      • Valid Parentheses
      • Image Smoother
      • Intersection of Two Arrays
      • Max Consecutive Ones
      • Max Consecutive Ones II
      • Shortest Palindrome
      • First Missing Positive
      • First Unique Character in a String
      • Move Zeroes
      • Remove Duplicates from Sorted Array
      • Merge k Sorted Lists
      • Insert into a Cyclic Sorted List
      • Evaluate Division
      • Inorder Successor in BST
      • Robot Room Cleaner
      • Redundant Connection II
      • Course Schedule
      • Validate Binary Search Tree
      • Closest Binary Search Tree Value
      • Word Squares
      • Strobogrammatic Number II
      • Word Search II
      • Android Unlock Patterns
      • Minimum Window Substring
      • Kth Largest Element in an Array
      • Shortest Distance from All Buildings
      • Find K-th Smallest Pair Distance
      • Find K Pairs with Smallest Sums
      • Range Module
      • Insert Interval
      • Sort Transformed Array
      • Merge Intervals
      • Longest Palindromic Substring
      • Next Greater Element I
      • Pacific Atlantic Water Flow
      • Evaluate Reverse Polish Notation
      • Decode Ways
      • Word Break
      • Sentence Screen Fitting
      • Maximum Vacation Days
      • Edit Distance
      • Minimum Path Sum
      • House Robber II
      • Moving Average from Data Stream
      • Peeking Iterator
      • Binary Search Tree Iterator
      • Zigzag Iterator
      • Design Tic-Tac-Toe
      • Range Sum Query 2D - Mutable
      • UTF-8 Validation
      • Maximum Product of Word Lengths
  • Other
    • Game of Life
Powered by GitBook
On this page

Was this helpful?

  1. Other

Game of Life

PreviousOther

Last updated 5 years ago

Was this helpful?

[Game of Life]() is a system where cells can die, live or become alive based on surrounding cells.

Here is an implementation that is using library (inspired by ).

let resolution;
let cols;
let rows;
let grid;

function setup() {
  frameRate(20);
  resolution = 5;
  createCanvas(400, 400);
  cols = width / resolution;
  rows = height / resolution;
  grid = createGrid(cols, rows);
}

let generationCount = 0;

function draw() {
  background(255);
  let next = createGrid(cols, rows);
  for (let i = 0; i < cols; i++) {
    for (let j = 0; j < rows; j++) {
      if (grid[i][j] === 1) { 
        fill(255, 90, generationCount);
        stroke(255, 90, generationCount);
        rect(i * resolution, j * resolution, resolution - 1, resolution - 1);
      }
      let sum = countNeighbors(grid, i, j);
      let current = grid[i][j];
      // Any live cell with fewer than two live neighbors dies, as if by underpopulation.
            // Any live cell with two or three live neighbors lives on to the next generation.
            // Any live cell with more than three live neighbors dies, as if by overpopulation.
            // Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
      if (current === 1 && sum < 2) {
         next[i][j] = 0;
      } else if (current === 1 && (sum === 2 || sum === 3)) {
         next[i][j] = 1;
      } else if (current === 1 && sum > 3) {
         next[i][j] = 0;
      } else if (current === 0 && sum == 3) {
         next[i][j] = 1;
      } else {
        // next[i][j] = current; // this should be there in order to keep the original algorithm design
        // just an experiment - any other will become 1 with 1% probability
        // try to lower this number and see how little 
        // probability is enough to keep cells alive or dead
        next[i][j] = random(1) < 0.01 ? 1 : 0;
      }
    }
  }
  generationCount++;
  grid = next;
}

function countNeighbors(grid, i, j) {
  let sum = 0;
  if (i > 0) sum += grid[i - 1][j];
  if (i < cols - 1) sum += grid[i + 1][j];
  if (j > 0) sum += grid[i][j - 1]; 
  if (j < rows - 1) sum += grid[i][j + 1];
  if (i > 0 && j > 0) sum += grid[i - 1][j - 1];  
  if (i < cols - 1 && j > 0) sum += grid[i + 1][j - 1];  
  if (i > 0 && j < rows - 1) sum += grid[i - 1][j + 1];  
  if (i < cols - 1 && j < rows - 1) sum += grid[i + 1][j + 1];  
  return sum;
}

function createGrid(cols, rows) {
  const grid = new Array(cols);
  for (let i = 0; i < cols; i++) {
    grid[i] = new Array(rows);
    for (let j = 0; j < rows; j++) {
      grid[i][j] = floor(random(0, 2));
    }
  }
  return grid;
}
https://en.wikipedia.org/wiki/Conway's_Game_of_Life]%28https://en.wikipedia.org/wiki/Conway's_Game_of_Life
p5
Game of Life video