Game of Life and Fatigue

10

1

Stewie's Game of Life and Fatigue is quite similar to the more famous Conway's Game of Life.


The universe of the Stewie's Game of Life and Fatigue (GoLF) is an infinite two-dimensional orthogonal grid of square cells, each of which is in one of three possible states, alive, dead or tired. Every cell interacts with its eight neighbors, 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 underpopulation.
  • 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 overpopulation.
  • Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.
  • Any cell that has been alive for two consecutive generations dies, as if by fatigue. It can't wake to life again until next generation
  • Any cell that is outside the boundary of the input grid are dead, as if it's fallen off a cliff.

Challenge:

Your challenge is to take a grid of dimensions n-by-m representing the initial state of a GoLF, and an integer p, and output the state of the Game after p generations.

Rules:

  • Input and output formats are optional, but the input/output grids should have the same representation
  • You may choose any printable symbols to represent live and dead cells (I'll use 1 for live cells and 0 for dead cells).
  • You may choose if you have 0 or 1-indexed. In the examples, p=1 means the state after one step.
  • Shortest code in each language wins
  • Built-in function for cellular automation are allowed

Test cases:

In the examples, I've only included the input grid in the input, not p. I've provided outputs for various p-values. You shall only output the grid that goes with a given input p.

Input:
0   0   0   0   0
0   0   1   0   0
0   0   1   0   0
0   0   1   0   0
0   0   0   0   0

--- Output ---
p = 1
0   0   0   0   0
0   0   0   0   0
0   1   1   1   0
0   0   0   0   0
0   0   0   0   0

p = 2
0   0   0   0   0
0   0   1   0   0
0   0   0   0   0
0   0   1   0   0
0   0   0   0   0

p = 3 -> All dead
---

Input:
0   1   0   0   0   0
0   0   1   0   0   0
1   1   1   0   0   0
0   0   0   0   0   0
0   0   0   0   0   0
0   0   0   0   0   0
0   0   0   0   0   0

--- Output ---
p = 1
0   0   0   0   0   0
1   0   1   0   0   0
0   1   1   0   0   0
0   1   0   0   0   0
0   0   0   0   0   0
0   0   0   0   0   0
0   0   0   0   0   0

p = 2
0   0   0   0   0   0
0   0   0   0   0   0
1   0   0   0   0   0
0   1   1   0   0   0
0   0   0   0   0   0
0   0   0   0   0   0
0   0   0   0   0   0

p = 3
0   0   0   0   0   0
0   0   0   0   0   0
0   1   0   0   0   0
0   0   0   0   0   0
0   0   0   0   0   0
0   0   0   0   0   0
0   0   0   0   0   0

p = 4 -> All dead
Input
0   1   1   0   1   1   0
1   1   0   1   1   1   1
0   1   0   0   0   1   0
0   0   0   1   1   0   1
1   0   0   1   0   1   1
0   0   1   1   0   1   1
1   1   0   0   0   0   1

--- Output ---
p = 1
1   1   1   0   0   0   1
1   0   0   1   0   0   1
1   1   0   0   0   0   0
0   0   1   1   0   0   1
0   0   0   0   0   0   0
1   0   1   1   0   0   0
0   1   1   0   0   1   1

p = 2
1   0   0   0   0   0   0
0   0   0   0   0   0   0
1   0   0   1   0   0   0
0   1   1   0   0   0   0
0   1   0   0   0   0   0
0   0   0   0   0   0   0
0   0   1   1   0   0   0   

p = 3
0   0   0   0   0   0   0
0   0   0   0   0   0   0
0   1   1   0   0   0   0
1   1   0   0   0   0   0
0   1   1   0   0   0   0
0   0   1   0   0   0   0
0   0   0   0   0   0   0

p = 4
0   0   0   0   0   0   0
0   0   0   0   0   0   0
1   1   1   0   0   0   0
1   0   0   0   0   0   0
1   0   1   0   0   0   0
0   1   1   0   0   0   0
0   0   0   0   0   0   0

p = 5
0   0   0   0   0   0   0
0   1   0   0   0   0   0
1   0   0   0   0   0   0
0   0   1   0   0   0   0
1   0   0   0   0   0   0
0   1   0   0   0   0   0
0   0   0   0   0   0   0

p = 6
0   0   0   0   0   0   0
0   0   0   0   0   0   0
0   1   0   0   0   0   0
0   1   0   0   0   0   0
0   1   0   0   0   0   0
0   0   0   0   0   0   0
0   0   0   0   0   0   0

p = 7
0   0   0   0   0   0   0
0   0   0   0   0   0   0
0   0   0   0   0   0   0
1   1   1   0   0   0   0
0   0   0   0   0   0   0
0   0   0   0   0   0   0
0   0   0   0   0   0   0

p = 8
0   0   0   0   0   0   0
0   0   0   0   0   0   0
0   1   0   0   0   0   0
0   0   0   0   0   0   0
0   1   0   0   0   0   0
0   0   0   0   0   0   0
0   0   0   0   0   0   0

p = 9 -> All dead

Yes, I'm aware that all initial seeds won't end in all cells being dead.

Stewie Griffin

Posted 2017-06-21T09:53:56.540

Reputation: 43 471

You should perhaps clarify that transition item 5 is applied "at the same time" as items 1--4, that is, it is based on the state before having applied 1--4 – Luis Mendo – 2017-06-21T11:48:33.100

2"cells, each of which is in one of two possible states, alive or dead" seems like a deliberately perverse definition given that the later fatigue rule can only be expressed in a standard finite automaton by making each cell have three states (dead, newly alive, alive for two consecutive generations) – Peter Taylor – 2017-06-21T17:18:48.910

1I have a Golly rule for this if anyone wants it. – CalculatorFeline – 2017-06-21T21:38:35.740

6Playing GoD, eh? – Adám – 2017-06-21T22:16:02.310

Answers

3

MATL, 34 30 25 bytes

5 bytes removed thanks to a suggestion by @CalculatorFeline!

0ii:"wy*~wt3Y6QZ+5:7mb*]&

Try it online!

Inputs are a matrix and a number. The matrix uses ; as row separator. The matrices for the three test cases are entered as

[0 0 0 0 0; 0 0 1 0 0; 0 0 1 0 0; 0 0 1 0 0;0 0 0 0 0]
[0 1 0 0 0 0; 0 0 1 0 0 0; 1 1 1 0 0 0; 0 0 0 0 0 0; 0 0 0 0 0 0; 0 0 0 0 0 0; 0 0 0 0 0 0]
[0 1 1 0 1 1 0; 1 1 0 1 1 1 1; 0 1 0 0 0 1 0; 0 0 0 1 1 0 1; 1 0 0 1 0 1 1; 0 0 1 1 0 1 1; 1 1 0 0 0 0 1]

Explanation

0     % Push 0. This represents the generation previous to the input one. Actually
      % This should be an array of zeros, but thanks to broadcasting it is
      % equivalent (and saves bytes)
i     % Input: array with starting generation
i     % Input: number of iterations, p.
      % STACK (bottom to top): 0, array with initial generation, p
:"    % Do the following p times
      %   STACK: previous gen, current gen
  wy  %   Swap, duplicate from below
      %   STACK: current gen, previous gen, current gen
  *~  %   Multiply element-wise, negate. This creates a mask of cells that do not 
      %   die of fatigue (they were 0 in the current or in the previous generation)
      %   STACK: current gen, fatigue mask
  wt  %   Swap, duplicate
      %   STACK: Fatigue mask, current gen, current gen
  3Y6 %   Push predefined literal: 8-neighbourhood: [1 1 1; 1 0 1; 1 1 1]
      %   STACK: Fatigue mask, current gen, current gen, 8-neighbourhood
  Q   %   Add 1 element-wise. This gives [2 2 2; 2 1 2; 2 2 2], which will be
      %   used as convolution kernel. Active cells with 2 neighbours will give 5;
      %   inactive cells with 3 neighbours will give 6; and active cells with 3
      %   neighbours will give 7
      %   STACK: Fatigue mask, current gen, current gen, convolution kernel
  Z+  %   2D convolution, keeping size
      %   STACK: Fatigue mask, current gen, convolution result
  5:7 %   Push array [5 6 7]
  m   %   Ismember, element-wise. Cells that give true will survive, unless fatigued
      %   STACK: Fatigue mask, current gen, cells that can survive
  b   %   Bubble up
      %   STACK: Current gen, cells that can survive, fatigue mask
  *   %   Multiply element-wise. This tells which cells survive considering fatigue.
      %   The result is the new generation
      %   STACK: "Current" gen which now becomes old, "new" gen which now becomes
      %   current
]     % End 
&     % Specify that implicit display will show only top of the stack

Luis Mendo

Posted 2017-06-21T09:53:56.540

Reputation: 87 464

1Can you explain 3Y6 in more detail? Also, if the middle element of the kernel was .5, you could check CGOL with just 2<value<4. Might help. – CalculatorFeline – 2017-06-21T19:44:07.140

@CalculatorFeline That's a very good suggestion, thanks! It led to saving 5 bytes, using twice the mask and then testing that 5<=value<=7. As for 3Y6, it's just a predefined literal. There's also 1Y6, which is the 4-neighbourhood – Luis Mendo – 2017-06-21T21:28:30.367

1Huh. That actually worked. Neat. – CalculatorFeline – 2017-06-21T21:37:10.833

3

APL (Dyalog Classic 16.0), 59 bytes

⌊{((3∊⌊{⍵,⍵-c}+/,⍵)∧.1>1|c)×(.1×c)+1⌈c←2 2⌷⍵}⎕U233A 3 3⍣⎕⊢⎕

Try it online! (emulated on Classic 15.0)


APL (Dyalog Unicode 16.0), 85 bytes

⌊{((3∊⌊{⍵,⍵-c}+/,⍵)∧.1>1|c)×(.1×c)+1⌈c←2 2⌷⍵}⌺3 3⍣⎕⊢⎕

Try it online! (emulated on Unicode 15.0)


Prompts for grid and then for p. Prints the new grid after p generations.

Note that this uses the new (Stencil) primitive which is not included in the Classic character set, hence a shorter version and a less-bytes version.

Explanation to follow…

Adám

Posted 2017-06-21T09:53:56.540

Reputation: 37 779

APL's display format is nice :-) – Luis Mendo – 2017-06-21T22:47:55.613

@LuisMendo Actually, it isn't "APL's" but rather the interpreter does a callback to this APL function when it wants to output. The function then analyzes what we want to output and modifies it accordingly. Explanation for the display function is here.

– Adám – 2017-06-21T22:55:18.120

3

Golly RuleLoader, 295 bytes

@RULE Y
@TABLE
n_states:3
neighborhood:Moore
symmetries:permute
var z={1,2}
var y=z
var x=z
var w=z
var u=z
var a={0,z}
var b=a
var c=a
var d=a 
var e=a
var f=a
var g=a 
var h=a
0,z,y,x,0,0,0,0,0,1
z,a,0,0,0,0,0,0,0,0
z,y,x,w,u,a,b,c,d,0
2,a,b,c,d,e,f,g,h,0
1,a,b,c,d,e,f,g,h,2
@COLORS
2 255 0 0

Input grid should be pasted in, boundaries are in the rulename (eg 5*3 is Y:P5,3), press space to advance.

CalculatorFeline

Posted 2017-06-21T09:53:56.540

Reputation: 2 608

2

Java 8, 333 bytes

int[][]G(int p,int[][]s){for(int h=s.length,w=s[0].length,y,x,n,a,b,t[][]=new int[h][w],i=0;i++<2*p;)for(y=0;y<h;++y)for(x=0;x<w;++x)if(i%2>0){for(n=0,a=y-2;++a<y+2;)for(b=x-2;++b<x+2;)n+=a>=0&a<h&b>=0&b<w&(a!=y|b!=x)&&s[a][b]>0?1:0;t[y][x]=s[y][x]<1?n==3?1:0:n<2|n>3|s[y][x]>1?0:2;}else s[y][x]=i==2*p&t[y][x]>1?1:t[y][x];return s;}

Explanation:

int[][]G(int p,int[][]s){
    for(int h=s.length,w=s[0].length,y,x,n,a,b,t[][]=new int[h][w],       //height, width, vars, temp array
            i=0;i++<2*p;)                                                 //for 2*generations: 1. calculate in temporary t, 2. copying to s
        for(y=0;y<h;++y)                                                  //for each row
            for(x=0;x<w;++x)                                              //for each column
                if(i%2>0){                                                //1. calculate
                    for(n=0,a=y-2;++a<y+2;)                               //n = number of alive cells around [y][x]. row above, at and below y
                        for(b=y-2;++b<y+2;)                               //column left, at and right of x
                            n+=a>=0&a<h&b>=0&b<w&(a!=y|b!=x)&&s[a][b]>0?1:0;    //if within bounds and not the cell itself, add 1 if alive.
                    t[y][x]=s[y][x]<1?n==3?1:0:n<2|n>3|s[y][x]>1?0:2;     //save next state in temporary, depending on rules. alive cells become 2.
                }
                else                                                      //2. copy temporary t to s
                    s[y][x]=i==2*p&t[y][x]>1?1:t[y][x];                   //if last generation, replace 2 by 1
    return s;
}

Sebastian Matschke

Posted 2017-06-21T09:53:56.540

Reputation: 41