CODEWITHSUNDEEP
arraysalgorithmiterationconways-game-of-life
Henricus V.
Henricus V.

Reputation: 948

Non-iterative algorithm for 1D game of life

Consider a Boolean array a[n], where each element is a cell. A cell becomes alive (set to true) in the next generation if one and only one adjacent cell is alive, otherwise it becomes dead (set to false). The first and last cell are considered neighbours.

Given a[n], the array size n, and a positive integer t, I wish to compute the a[n] after t'th generation of evolution, but without using any iterative algorithm on t, which can be potentially very large.

What I have observed: if we define S_k(a[n]) be a circular shift of a[n] to the right by k elements. That is, a[0] becomes a[k] after one shift if 0 <= k < n. Define a[n] ^ b[n] to be the element-wise xor operation between two boolean arrays. If w[n] is a Boolean array, the next generation can be expressed by

r(w[n]) = S_{-1}(w[n]) ^ S_1(w[n])

The xor operator ^ is associative and commutative. Using this property, the next few generations of w[n] can be computed by

r^2(w[n]) = ( S_{-2}(w[n]) ^ S_0(w[n]) ) ^ ( S_0(w[n]) ^ S_2(w[n]) )
          = S_{-2}(w[n]) ^ S_2(w[n])

If we let s_j = S_{-j}(w[n]) ^ S_j(w[n]), there is a pattern

r(w[n]) = s_1
r^2(w[n]) = s_2
r^3(w[n]) = s_3 ^ s_1
r^4(w[n]) = s_4
...
r(s_m) = s_{m-1} ^ s_{m+1}

Moreover, s_n = 0 (the array of zeroes) since a full circular shift is the original array. How do I use this to derive a non-iterative expression of r^t(w[n])?

Edit: The pattern is

[1]
[2]
[1,3]
[4]
[3,5]
[2,6]
[1,3,5,7]
[8]

Upvotes: 5

Views: 365

Answers (3)

fjardon
fjardon

Reputation: 7996

Let's represent your input as a column vector a_0 of size n of elements of Z/2Z.

You can compute the next generation vector, a_1 by using a matrix multiplication:

a_1 = M.a_0 = |0 1 0 0 ... 0 0 0|  |a_01|
              |1 0 1 0 ... 0 0 0|  |a_02|
              |0 1 0 1 ... 0 0 0|  |a_03|
              ....
              |0 0 0 0 ... 0 1 0|  |... |
              |0 0 0 0 ... 1 0 1|  |... |
              |0 0 0 0 ... 0 1 0|  |a_0n|

Given this recurrence relation, you can compute the generation at time t using the formula:

a_t = M^t . a_0

And you can easily compute M^t in O(n^3.log(t)) using repeated squaring.

Upvotes: 1

Stefan Haustein
Stefan Haustein

Reputation: 18803

I think you need to uncover more of the pattern...

Does it go on like this:

1
 2 
1 3
   4
  3 5
 2   6
1 3 5 7
       8
      7 9
     6   a
    5     b
   4       c
  3   ???   d
 2           e
1 3 5 7 9 b d f
               g

If so, the simplest way seems to be to calculate r for the closest power of two <= t, then do the same for the remainder (t' = t-2^n) etc, so you'd be down to O(log(t)). If the ??? area is actually empty, you should be able to limit the steps to 3 (avoid 2^n-1 by calculating the value before, then go a single step).

Upvotes: 0

Tony
Tony

Reputation: 6158

As far as I know, there is no non-iteration way to solve this game as here stated. Even the 'Hashlife' algorithm is also iterative but with many assisted memory.

But you can use some ways to opt plain iteration algo:

  • Use bits rather than int array: This way can save much memory and accelerate speed in some cases.
  • Store generations of bits: You can easily compare bits from different generation to find out whether there exists some repeated patterns between generations, in which cases, no more calculation is needed any more. Considering you only have one dimension, the chance might be very high.

Upvotes: 0

Related Questions