3
\$\begingroup\$

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!

\$\endgroup\$
6
  • 2
    \$\begingroup\$ Probably won't be easy to generate, but some test cases would be nice. \$\endgroup\$ Mar 21 at 17:42
  • 12
    \$\begingroup\$ Test cases/some explanation of the theory behind calculating the maximum period are a must for this problem honestly \$\endgroup\$
    – des54321
    Mar 21 at 17:45
  • 7
    \$\begingroup\$ Why does the input start at 5? The block has period 1 and fits in a 2x2 box, and the blinker has period 2 and fits in a 3x3 box. They would make for good test cases. \$\endgroup\$
    – Zgarb
    Mar 21 at 18:33
  • 1
    \$\begingroup\$ Related sequence? oeis.org/A231427 \$\endgroup\$
    – friddo
    Mar 21 at 22:17
  • 5
    \$\begingroup\$ For code golf, the obvious (and likely optimal) approach would be brute force enumeration of all possible n by n cell patterns. The problem is that the runtime of such a brute force search will be proportional to exp(n²). It should work fine for n = 5, and probably OK for n = 6. It's unlikely that anyone will ever finish such a search for n = 9. (A far more efficient approach could be to use a SAT solver e.g. via LLS. But it will not golf well, unless you're willing to accept "shell + LLS" as a language. And probably not even then.) \$\endgroup\$ Mar 22 at 1:23

2 Answers 2

6
\$\begingroup\$

Rust + rlifesrc-lib, 114 bytes

When I wrote this lib I never thought ony 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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ I really like this answer because it's basic Python without extra libraries! So good! \$\endgroup\$
    – Squareoot
    Mar 22 at 20:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.