Skip to content

Instantly share code, notes, and snippets.

@jackhftang
Created February 16, 2019 04:51
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jackhftang/b66394570ce1cd820c0bfd376899b516 to your computer and use it in GitHub Desktop.
Save jackhftang/b66394570ce1cd820c0bfd376899b516 to your computer and use it in GitHub Desktop.
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
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.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment