Well, HashLife isn't complicated at it's core. It's complicated at it's interface and practical application.
Code: Select all
from __future__ import division, print_function
import itertools as it
from PyQt4 import QtCore as qtc
from PyQt4 import QtGui as qtg
import numpy
def b3s23(*cells):
cnt = sum(cells)-cells[4]
if cnt == 3:
return True
elif cnt == 2 and cells[4]:
return True
else:
return False
class Cell(object):
__slots__ = ['t']
def __init__(self, *args):
self.t = args
def __getitem__(self, item):
return self.t[item]
class Hashlife(object):
__slots__ = ['dic', 'top', 'zero', 'level', 'rule']
def __init__(self, rulef):
self.reset()
self.rule = tuple(rulef(*cells)\
for cells in it.product((False, True), repeat=9))
def reset(self):
self.dic = {}
self.top = None
self.zero = None
self.level = 0
for c in it.product((False, True), repeat=4):
cell = Cell(*c)
self[c] = cell
def __setitem__(self, key, value):
if key in self.dic:
raise ValueError("key already exists")
self.dic[key] = value
def __getitem__(self, key):
try:
return self.dic[key]
except KeyError:
try:
c0 = key[0][4]
c1 = self[key[0][1], key[1][0], key[0][3], key[1][2]][4]
c2 = key[1][4]
c3 = self[key[0][2], key[0][3], key[2][0], key[2][1]][4]
c4 = self[key[0][3], key[1][2], key[2][1], key[3][0]][4]
c5 = self[key[1][2], key[1][3], key[3][0], key[3][1]][4]
c6 = key[2][4]
c7 = self[key[2][1], key[3][0], key[2][3], key[3][2]][4]
c8 = key[3][4]
d0 = self[c0, c1, c3, c4][4]
d1 = self[c1, c2, c4, c5][4]
d2 = self[c3, c4, c6, c7][4]
d3 = self[c4, c5, c7, c8][4]
rs = self[d0, d1, d2, d3]
cell = Cell(key[0], key[1], key[2], key[3], rs)
self[key] = cell
return cell
except IndexError:
celltup = (
(key[0][0], key[0][1], key[1][0], key[1][1]),
(key[0][2], key[0][3], key[1][2], key[1][3]),
(key[2][0], key[2][1], key[3][0], key[3][1]),
(key[2][2], key[2][3], key[3][2], key[3][3])
)
res = tuple(self.rule[sum(2**(8-ii)*jj\
for ii, jj in enumerate(celltup[i+di][j+dj]\
for di in (-1,0,1) for dj in (-1,0,1)))]\
for i in (1, 2) for j in (1, 2))
cr = self[res]
cell = Cell(key[0], key[1], key[2], key[3], cr)
self[key] = cell
return cell
def toarr(self):
dic = self.dic
darr = list(dic.values())
cellarr = [False, True]
tuparr = [self.rule]
start = 0
while start < len(darr)+2:
d = {j:i+start for i,j in enumerate(cellarr[start:])}
if self.zero in d:
zero = d[self.zero]
if self.top in d:
top = d[self.top]
newcells = [i for i in darr if i[0] in d]
newtups = [tuple(d[x] for x in i) for i in newcells]
perm = sorted(range(len(newcells)), key=lambda x: newtups[x])
if start > 0:
tuparr += [newtups[i] for i in perm]
start = len(cellarr)
cellarr += [newcells[i] for i in perm]
tuparr += [zero, top]
return tuparr
def fromarr(self, arr):
self.rule = arr.pop(0)
self.reset()
arr = [False, True]\
+ [self[c] for c in it.product((False, True), repeat=4)]\
+ arr
for i in range(18,len(arr)-2):
arr[i] = Cell(*(arr[x] for x in arr[i]))
self.zero = arr[arr[-2]]
self.top = arr[arr[-1]]
level = 0
cur = self.top
while type(cur) != bool:
cur = cur[0]
level += 1
self.level = level
d = {x[:4]:x for x in arr[2:-2]}
self.dic = d
def expand(self):
c0 = self[self.zero, self.zero, self.zero, self.top[0]]
c1 = self[self.zero, self.zero, self.top[1], self.zero]
c2 = self[self.zero, self.top[2], self.zero, self.zero]
c3 = self[self.top[3], self.zero, self.zero, self.zero]
self.top = self[c0, c1, c2, c3]
self.zero = self[self.zero, self.zero, self.zero, self.zero]
self.level += 1
def _compress(self, arr, start, stop, fromr=False, fromb=False):
n, m = stop[0] - start[0], stop[1] - start[1]
arr2 = [[None]*m for i in range(n)]
for i in range(n):
for j in range(m):
arr2[i][j] = arr[i+start[0]][j+start[1]]
arr = arr2
level = 1
zero = False
while n > 1 or m > 1:
n2m, m2m = n&1, m&1
n2, m2 = (n+1)>>1, (m+1)>>1
arr2 = [[None]*m2 for i in range(n2)]
for i in range(n2):
for j in range(m2):
c0 = arr[i*2-n2m*fromb][j*2-m2m*fromr] if\
i*2-n2m*fromb >= 0 and j*2-m2m*fromr >= 0 else zero
c1 = arr[i*2-n2m*fromb][j*2+1-m2m*fromr] if\
i*2-n2m*fromb >= 0 and j*2+1-m2m*fromr < m else zero
c2 = arr[i*2+1-n2m*fromb][j*2-m2m*fromr] if\
i*2+1-n2m*fromb < n and j*2-m2m*fromr >= 0 else zero
c3 = arr[i*2+1-n2m*fromb][j*2+1-m2m*fromr] if\
i*2+1-n2m*fromb < n and j*2+1-m2m*fromr < m else zero
arr2[i][j] = self[c0,c1,c2,c3]
zero = self[zero, zero, zero, zero]
n, m, arr = n2, m2, arr2
level += 1
return arr[0][0], level, zero
def populate(self, arr):
n, m = len(arr), len(arr[0])
midn, midm = (n+1)>>1, m>>1
c0, l0, z0 = self._compress(arr, (0, 0), (midn, midm), True, True)
c1, l1, z1 = self._compress(arr, (0, midm), (midn, m), False, True)
c2, l2, z2 = self._compress(arr, (midn, 0), (n, midm), True, False)
c3, l3, z3 = self._compress(arr, (midn, midm), (n, m), False, False)
level = l1
zero = z1
if l0 < level:
c0 = self[z0, z0, z0, c0]
if l2 < level:
c2 = self[z2, c2, z2, z2]
if l3 < level:
c3 = self[c3, z3, z3, z3]
self.level = level
self.zero = zero
self.top = self[c0, c1, c2, c3]
def show(self, l, r, t, b, s, z):
req = max(abs(x) for x in (l, r+1, t+1, b)) + s
while req > 1<<(self.level-1):
self.expand()
if l > r:
l, r = r, l
if t < b:
t, b = b, t
s -= s%(1<<z)
l -= s
r += s
t += s
b -= s
arr = [[self.top]]
zero = [self.zero]
n, m = 1, 1
level = self.level
cl = cb = -1<<(level-1)
cr = ct = (1<<(level-1))-1
cs = 0
while level > z:
ts = 1<<(level-1)
cutl = l >= cl + ts
cutr = r <= cr - ts
cutt = t <= ct - ts
cutb = b >= cb + ts
cl += cutl*ts
cr -= cutr*ts
ct -= cutt*ts
cb += cutb*ts
n2 = n*2 - cutt - cutb
m2 = m*2 - cutl - cutr
arr2 = [[None]*m2 for i in range(n2)]
for i in range(n2):
for j in range(m2):
i2, di = divmod(i+cutt, 2)
j2, dj = divmod(j+cutl, 2)
arr2[i][j] = arr[i2][j2][2*di+dj]
arr = arr2
n, m = n2, m2
ts = 1<<(level-2) if level > 1 else 1
if s >= cs + ts:
for i in range(n-1):
for j in range(m-1):
c0 = arr[i][j]
c1 = arr[i][j+1]
c2 = arr[i+1][j]
c3 = arr[i+1][j+1]
arr[i][j] = self[c0, c1, c2, c3][4]
arr[i].pop()
arr.pop()
n -= 1
m -= 1
cs += ts
level -= 1
zero = zero[0]
if z > 0:
for i in range(n):
for j in range(m):
arr[i][j] = arr[i][j] != zero
return arr
def pprint(self, l, r, t, b, s, z):
print('\n'.join(''.join([' ', '*'][x] for x in i)\
for i in self.show(l, r, t, b, s, z)))
class MyWidget(qtg.QWidget):
def __init__(self, hl):
super(MyWidget, self).__init__()
self.hl = hl
self.pic = qtg.QLabel(self)
self.size = qtc.QSize(400,400)
self.pic.resize(self.size)
self.timer = qtc.QTimer()
self.cur = 0
def render(self, l, r, t, b, s, z):
arr = self.hl.show(l, r, t, b, s, z)
w, h = len(arr[0]), len(arr)
arr = numpy.packbits(numpy.array(arr, dtype=numpy.uint8), axis=1)
img = qtg.QBitmap.fromData(
qtc.QSize(w, h),
arr.data, qtg.QImage.Format_Mono)
self.pic.setPixmap(img.scaled(self.size))
self.show()
def start(self, l, r, t, b, start, step, z, tstep):
self.cur = start
def tick():
self.render(l, r, t, b, self.cur, z)
self.cur += step
self.timer.timeout.connect(tick)
self.timer.start(tstep)
def stop(self):
self.timer.timeout.disconnect()
self.timer.stop()
hl=Hashlife(b3s23)
rpent = [[False,True,True],[True,True,False],[False,True,False]]
acorn = [
[False]+[True]+[False]*5,
[False]*3+[True]+[False]*3,
[True]*2+[False]*2+[True]*3
]
gg = [
[False]*11+[True]*2+[False]*23,
[False]*11+[True]*2+[False]*23,
[True]*2+[False]*6+[True]*2+[False]*12+[True]*2+[False]*12,
[True]*2+[False]*5+[True]*3+[False]*14+[True]+[False]*11,
[False]*8+[True]*2+[False]*15+[True]+[False]*8+[True]*2,
[False]*11+[True]*2+[False]*12+[True]+[False]*8+[True]*2,
[False]*11+[True]*2+[False]*12+[True]+[False]*10,
[False]*24+[True]+[False]*11,
[False]*22+[True]*2+[False]*12
]
infgrow = [
[False]*6+[True]+[False],
[False]*4+[True]+[False]+[True]*2,
[False]*4+[True]+[False]+[True]+[False],
[False]*4+[True]+[False]*3,
[False]*2+[True]+[False]*5,
[True]+[False]+[True]+[False]*5
]
hl.populate(rpent)
a = qtg.QApplication([])
w = MyWidget(hl)
Core HashLife implementation is about 60 lines of code, and I've found that it was much simpler to write it than to write the function that extracted an arbitrary rectangle of the grid at arbitrary time step and zoom level (function show in the code above). And I've sidestepped issues of keeping memory bounded, rehashing, etc. Although I've wrote an interface between internal representation and an array (that could be dumped to a file, for example). And that also was not quite simple.
Oh, and I don't think that your implementation of the core is complete in the sense that you handle empty tiles and universe expansion explicitly from outside. I think that work has to be done by the core itself, not by the interface or an external part.