cellCompete.nim

proc next(state : int): int =
  # shift one bit left for convenience 
  var s = state shl 1
  for i in 0..7:
    let mask = (s and (5 shl i)) shr i
    if mask == 5 or mask == 0:
      result = result or (1 shl i) 

proc encode(cells : array[8,int]): int = 
  for i in 0..7:
    result = result or (cells[i] shl i)

proc decode(state : int): array[8,int] = 
  for i in 0..7:
    if (state and (1 shl i)) != 0:
      result[i] = 1

proc precompute() : auto = 
  var 
    groups : array[256, int]
    offsets : array[256, int]
    cycles : seq[seq[int]]

  for i in 0..255:
    groups[i] = -1 
    offsets[i] = -1 

  for i in 0..255:
    if groups[i] == -1: 
      var 
        j = i 
        cycle : seq[int] 
      while groups[j] == -1: 
        groups[j] = cycles.len
        offsets[j] = cycle.len 
        cycle.add j 
        j = next(j) 
      cycles.add cycle

  return (groups, offsets, cycles)
      
# compile time constants
const 
  t = precompute()
  groups = t[0] 
  offsets = t[1] 
  cycles = t[2]

proc cellComplete(cells : array[8,int], days : int) : array[8, int] = 
  let 
    s = encode(cells)
    g = groups[s]
    o = offsets[s]
    c = (o + days) mod cycles[g].len 
    ans = cycles[g][c] 
  result = decode(ans)
  
proc cellCompleteNaive(cells : array[8,int], days : int) : array[8, int] = 
  var state = encode(cells)
  for i in 1..days:
    state = next(state)
  result = decode(state)

when isMainModule:
  for state in 0..255: 
    for days in [0,10,100]: 
      let cells = decode(state)
      let a = cellCompleteNaive(cells, days)
      let b = cellComplete(cells, days)
      assert a == b

Problem.txt

There is a colony of 8 cells arranged in a straight line where each day every cell competes with its adjacent cells(neighbour). Each day, for each cell, if its neighbours are both active or both inactive, the cell becomes inactive the next day,. otherwise itbecomes active the next day.

Assumptions: The two cells on the ends have single adjacent cell, so the other adjacent cell can be assumsed to be always inactive. Even after updating the cell state. consider its pervious state for updating the state of other cells. Update the cell informationof allcells simultaneously.

Write a fuction cellCompete which takes takes one 8 element array of integers cells representing the current state of 8 cells and one integer days representing te number of days to simulate. An integer value of 1 represents an active cell and value of 0 represents an inactive cell.