Calculate the highest possible period oscillator in Conway's Game of Life

Question

Input: a whole positive number greater than 4

Output: A whole positive number that describes the highest possible period an oscillator could have inside a square space of size (input)x(input) in a "life" grid that follows the rules of Conway's Game of Life. The oscillator never leaves this area throughout its cycles. It may not interact with any outside cells. There is no wall, cells outside this area are just dead by default.

Your program should be able to theoretically calculate as high of a number as the 32 bit Integer Limit.

Winner: this is code-golf, so shortest code in bytes wins!

Answer 1

Rust + rlifesrc-lib, 114 bytes

When I wrote this lib I never thought one day I would use it in codegolf.

use rlifesrc_lib::*;
|n|(1..1<<n*n).rev().find(|&p|Config::new(n,n,p).world().unwrap().search(None)!=Status::None)

Very inefficient. Only works for \$n=2\$. It tries every period from \$p=2^{n^2}-1\$ to \$1\$. It would be faster if there is a better upper bound for the period.

Answer 2

Python, 368 bytes

Let’s get the elephant out of the room: This thing has runtime \$n^2(2^{n^2})^2\$. But hey, you said short, not efficient.

from numpy import *
from itertools import *
P=lambda x,n:product(x,repeat=n)
n=int(input())
s=lambda x,i,j:sum(x[max(0,i-1):i+2,max(0,j-1):j+2])
def c(x):
 y=copy(x)
 for i,j in P(range(n),2):x[i,j]=2<s(y,i,j)<4+y[i,j]
def r(x):
 x=array(x);x.shape=(n,n);y=copy(x);a=0
 while a<2**(n**2):
  c(x);a+=1
  if all(x==y):return a
 return 0
print(max(map(r,P((0,1),n**2))))

This solution basically tries all \$2^{n^2}\$ possible variants for periodicity. That is, if after \$k\$ iterations we reach the starting point for the first time. Since only \$2^{n^2}\$ possible combinations exist we know that we can stop after this many iterations.

Also note that the memory footprint of this solution is not too bad. Our memory complexity should be around \$n^2\$, so this code will handle fairly large input numbers, but it will take a decent amount of time.