skip to Main Content

Game of Life Strings

The universe of the Game of Life is an infinite two-dimensional orthogonal grid of square cells, each of
which is in one of two possible states, alive or dead. Every cell
interacts with its eight neighbours, which are the cells that are
horizontally, vertically, or diagonally adjacent. At each step in
time, the following transitions occur:

  • Any live cell with fewer than two live neighbours dies, as if caused by under-population.
  • Any live cell with two or three live neighbours lives on to the next generation.
  • Any live cell with more than three live neighbours dies, as if by overcrowding.
  • Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

Implement the method that calculates new generation of game of life.
The method receives a string in the format "000_000_000" that
represents the matrix NxM of 0’s (dead cell) and 1’s (living cell).

And returns a string in the same format "000_000_000" that represents
equally sized array representing the next generation. Cells outside
the array must be considered dead. Cells that would born out of the
array boundaries should be ignored (universe never grows beyond the
initial NxM grid).

Examples

  • Input: "000_111_000"
  • Output: "010_010_010"

PS. I am not asking for any implementation just help to understand this. Once I understand the implementation is just a detail.

2

Answers


  1. Chosen as BEST ANSWER

    After the help here to understand it, this is one possible solution using javascript

    const getNewString = (str) => {
        const cells = str.replace(/_/ig, '').split('').map(num => parseInt(num));
        
        const result = []
    
        // Considering a 3x3 matrix
        for(let cellIndex=0; cellIndex < cells.length; cellIndex++){
          
           const position = Math.floor((cellIndex/3) % 1 * 100);
           const isFirst = position === 0
           const isLast = position === 66
           
           if(cellIndex > 2 && isFirst){
             result.push('_')
           }
    
          let sum = 0
          
          const backBreakIndex = isFirst ? 3 : 4
    
          for(let back = cellIndex-1; back >= cellIndex-backBreakIndex; back--){
            const isNeighbour = ((!isFirst && (back < cellIndex-1)) || (!isLast && (back!==cellIndex-2)))
            
            if(cells[back] && isNeighbour){
              sum++
            }
          }
          
          const forwardBreakIndex = cellIndex + (isLast ? 3 : 4)
      
          for(let forward= cellIndex+1; forward <= forwardBreakIndex; forward++){
            const isNeighbour = (!isLast && forward!==cellIndex+1 ) || (!isFirst && forward!==cellIndex+2)
            
            if(cells[forward] && isNeighbour){
              sum++
            }
          }
    
          if(cells[cellIndex]){ // is alive
             result.push(sum > 1 && sum < 4 ? 1 : 0); 
          }else{
            result.push(sum === 3 ? 1 : 0); 
          }
    
        }
        return result.join('')
    }
     console.log(getNewString('000_111_000'))
     console.log(getNewString('000_000_000'))
     console.log(getNewString('111_111_111'))
     console.log(getNewString('11'))
    

  2. Simply follow the rules.

    The string represents a 2D grid

    "000_111_000"
    

    is

    A B C
    1 0 / dead 0 / dead 0 / dead
    2 1 / live 1 / live 1 / live
    3 0 / dead 0 / dead 0 / dead

    (added coordinates for clarity: A1 is top-left with value 0/dead and B2 is in the middle with value 1)

    Going down the list of rules and each cell:

    • A1 (dead) has three neighbours: B1 (dead), B2 (live), A2 (live)
      • no rule applies, the value 0 remains
    • A2 (live) has five neighbours: A1 (dead), B1 (dead), B2 (live), B3 (dead), A3 (dead)
      • First rule applies: fewer than two live neighbours, therefore the value changes to 0
    • A3 (dead) has three neighbours: A2 (live), B2 (live), B3 (dead)
      • no rule applies, the value 0 remains
    • B1 (dead) has five neighbours: C1 (dead), C2 (live), B2 (live), A2 (live), A1 (dead)
      • Fourth rule applies: exactly three live neighbours, therefore the value changes to 1
    • B2 (live) has eight neighbours: B1 (dead), C1 (dead), C2 (live), C3 (dead), B3 (dead), A3 (dead), A2 (live), A1 (dead)
      • Second rule applies: two live neighbours, therefore the value changes remains 1
    • B3 (dead) has five neighbours: B2 (live), C2 (live), C3 (dead), A3 (dead), A2 (live)
      • Fourth rule applies: exactly three live neighbours, therefore the value changes to 1
    • C1 (dead) has three neighbours: C2 (live), B2 (live), B1 (dead)
      • no rule applies, the value 0 remains
    • C2 (live) has five neighbours: C1 (dead), C3 (dead), B3 (dead), B2 (live), B1 (dead)
      • First rule applies: fewer than two live neighbours, therefore the value changes to 0
    • C3 (dead) has three neighbours: C2 (live), B3 (dead), B2 (live)
      • no rule applies, the value 0 remains

    This results in

    A B C
    1 0 / dead 1 / live 0 / dead
    2 0 / dead 1 / live 0 / dead
    3 0 / dead 1 / live 0 / dead

    Which in turn when encoded back to a string matches the putput

    "010_010_010"
    
    Login or Signup to reply.
Please signup or login to give your own answer.
Back To Top
Search