[Tutor] Re: Implementation Help Request on Game of Life

Thu Jan 2 17:15:03 2003

This is a multi-part message in MIME format.

------=_NextPart_000_0052_01C2B269.BE8B36E0
Content-Type: text/plain;
	charset="iso-8859-1"
Content-Transfer-Encoding: 7bit

Hi,
I'm not normally subscribed to python-tutor, but since I just implemented
Conway's life in December for PythonCard this is a fresh subject for me.
Please cc me on all replies as I will probably remain subscribed to the
tutor list, but disable list delivery.

There is more about the PytonCard life sample program at:

http://pythoncard.sourceforge.net/samples/life.html

The source is at:

http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/pythoncard/PythonCardPrototyp
e/samples/life/

You won't be able to run it without having Python 2.2.x or higher and
wxPython 2.3.3.1 or higher and checking PythonCard out of cvs

http://sourceforge.net/cvs/?group_id=19015

However, it will be part of release 0.7 of PythonCard sometime later this
month.

I've attached a zip file with the core generation calculation along with the
util.py module that can read .LIF files and LIF style patterns in the
clipboard (this is the same util.py that is in cvs). The cmdLife.py script
runs the rpento pattern for 1103 generations (when it stabilizes); I put it
together, so Bill Bumgarner could port the code to PyObjC for Mac OS X and
to use as a simple benchmark comparison. The same base could be used for a
tkinter app, curses, or any other GUI; PythonCard uses wxPython.

The algorithm I use is pretty elegant and is more readable (but slower) than
the fastest algorithms used by some of the C++ and Java programs. They all
use bit shifting and "blobbing" to calculate sections of a generation all at
once. My method is real simple and doesn't put any limits on universe size
except for +/-maxint since an (x, y) tuple is used as the key in the
dictionary for each cell. The grid is a dictionary of each live cell and its
neighbors. The values of each cell is either 1 or 0. Each generation, you
simply loop through all the grid cells, sum the neighbors and apply the test

if sum == 3 or (grid[cell] and sum == 2)

to determine whether a given cell lives in the next generation. Then you
make sure all its neighbors exist. Using get and setdefault really
simplifies using the dictionary and avoids try/except blocks.

I am interested in further optimizations such as used by the fastest Java
and C Life programs which use bit shifting and "blobbing" to calculate areas
of the grid all at once.

Note that I've also implemented other cellular automata and visualizations,
but not all are included as PythonCard samples.

ka
---
Kevin Altis
altis@semi-retired.com
http://radio.weblogs.com/0102677/
http://www.pythoncard.org/

------=_NextPart_000_0052_01C2B269.BE8B36E0
Content-Type: application/x-zip-compressed;
	name="bill_life.zip"
Content-Transfer-Encoding: base64
Content-Disposition: attachment;
	filename="bill_life.zip"

UEsDBBQAAAAIAAORIS5TSMYRPQkAAMcbAAAUAAAAYmlsbF9saWZlL2NtZExpZmUucHm9WG1v2zgS
/m7A/4Fno7CcOjrLTnpIgHzY694WBYrdINvF4RAUBi1RNjeyKIhUHG/R/34zfJGoF3fbw90JsWOK
w+G8PjPkeMQPhSgVqRTPxqPxKM6olOS3nD+zUrLb8YjAk7CUbDY852qzCSTL0rmdwAfHIc69K3kS
zDsTT4wVP5b0yPMduSNL3MJxrNd0OU4JJYUoqowqlpAdkJA9lSR4WZDTnKiqyJgkqSjJEztJf9mR
qz2JSEAzEH9OgGJJgoTRZK7J1Z6RZ5pVjIiUMBrvkUFHXr3bHfn8pfue5aykiou8q0YiHqr8A0+Z
1mNBpGKFvLuMfI2Oe56xvkFonhhy8hdg6tHjYyWppWrP5uw4ICo+qGnMsgzsq3l02OIjq4PRojsx
zRnf7beilDBf//6IFg+Q5+Py00Izf4w+zQeWE64Il+C+LfxIKegGVhcgScZzBvaHOTDiHt/uaT7E
IKZZpk1D0iqP0d59qlhkC1KKI8iIsvQJipI9P+h5pLokUZ8kZy+qIXk9RIJc3ooMd4Hvs1wakkEu
vkWDwPJcOBHnCxLEnbFl6r3rc/WfhmnZYVB+z2JrkVoib1wzdO/mLgH8Z0reE1VySFlKED0wV47g
a6YTL+Ham7Q8QdYVCmhiUZwwE3G2sZJO7yHm20ppUgG895DTGN9SiRKjRW9AFYVsYQcQAGJOVOqI
TPVcLKQa4gm7Q8DFiDSOTSMJZueBJjZu6RY4kuvlKyIzcWTlEDuaSUEqiax2TAVzA0gUYYJWGehc
FIyijoJsmeW4Wl6url/ZZBliiplimVKw7+mv7CVGA24zET+BBU6ALDSOGcA2qIOp/fpOJ/6jU+VT
ny2ChJtGQ9ZaD6AFPh7bEFVz9AuyHMKBAryiyASzc2IAY2FEwp8D4tgFtRRnKUCO/hw3at/dkTVi
ftDsZBDWzK3mZ3SbGrg8cvhCt2Dx0JFOGtAfXmlB2O51N5T++HyvsfGxrEPJlI2eP7G5e6ZgjVyo
mgFUzg2UuXr1OSvotfjllKqjxy947unWxNc95U1du+y/96qs3apNMJ1qkoTLIqOnd/UewbxLd3wJ
jy+/0pT9i7PMthGtytxj0es0pjHNn6l0dTYW0A3lLFcy3FbpL2nqkx55AtlsKSXgBoOiYAYFjSE/
+3xDWinxwNKSyX274tYUcQaQ4OvWr/veKkJLKK0loqgWB5IL4GFnMMqnS1jB8gRBA7yzhxJ3EhU5
UkghAB9rGJ9eY9yBqb1IsIKLPDuRndCgKDRGanC0XVkrITxzQAI27525Vm0FoKqLw4EZQQCuNV/J
/2CuFHiFIoDg3c9b6gPs8fwJGohgTXSiYu5JzCqqy51J4z2FGUqia9hE0cwQ+XyAvrOXaxDXliMi
B46jFQBIWYrKWHMAohzaZSzX0DMHyKt/+8o31uvEApbLE5EH6H2IKBQ/8D86RjblD5oq+ix4gtJp
1FPQIWtbovRMc+GqB1lAaZ0B2dhJ/wJ8rDD+Hzuw/A1tJPBt4O8MrHg69zGiIUIhQiyPeRK4TpNc
eLFVt52tt/MeJtiswg77Hrl+4FIFhr9Hy7L6bOOe/6e+vpQPLFaQwU2D/Q1qL1zy63+tGKstUBrU
8ZHFIitGTSX/TstQYZG7I5MGIW/JqwRJ72s18M2EvCJBB/IXnqreHjYX/oscz2CpZ1rUfzKZjEdT
PIaRKFxew+8fSXkJ8aTEgedCj38wKbYgz3wnIKMlWBewCFxVUAVpk4dIpkn/uWcGId7Rg0YmzfkI
lSLlJfaSQAOKliKpYmx4NT6Q6OZvy4WBUiDVREUpCiGRRBqkQwmYVG5LTYSxB0fE2DSr0BWCWGa3
Kn/KxVEL9jN87gGeAGLDi4vxCD/hhdV8POJ4RM9B2s0G83y22RwozzebmQ1Ue84XsjUstL9arwB+
mIuoyt4DgL3dlYALKCgZqAa03LAOsN/isplMmIxLXlivGk3B2koUH1iqFgbv7/SlQwjVLJd41H+b
8WIraJncmwXB7OLiYma3s3HleE0atq15u8Ok3qs1i9tOzO5OiS0eQVLosuoDgOVLjsyALUD+DmIS
e8LqsGUO+ad1xahLwsI6MRFM5jNFSga+PsEZAhkS07bXxttTRd7PDkY0Xaft+UbXf31w8J2jTQVF
O2bOOs43uklYkJX+c0YBHHmcQT2UM3dON8xC86+9uPYohBopKyyl3c63pm/f50Sd2eYuJPqmbbsb
R9Fy7e2tTzSlTmJHaSyMCeYy1PkLYG3LM3Bt7SBtzYwnsCOWzhj8ATFrOoTfKwjencDuCPyIpdNf
5XimeG3DdXthuxZ9EHxuwqfSXKg+kGLLUEnT0cBeCRriJ+TgrjLMro0yB/rEsLtgKN5RlE8yDMOO
Sbs3a9+TWr4QgZAhkO/D36EYBjO3crYgs4f7f/z88Zfww/ufZvP/cbqhefB2aLdjeBSCvDM20bd5
PH6qfXc4QXsHkAv4uSvpQV8AAshCpjB9fo7BF8CC1q6yHV1zngDnUAReYSZiaOKwU6oLaJ5A0Jm+
CLDTtcduLc2gREASHqTNc1pPyYLFPOWxTm5kjS76IU/uveyse2l9JZAAENSa6dQ+QMxhSBUZ8MFb
Tmfe5sYEvil+oO6XvAlqyAi8B7WoZfrUJgwwHvVSQC9tWN0Jw5HmG1Hkamk+53HEJAj0t0TuRZUl
eGReRS2/Y/PbznTbEQ+hzp/j0texB9K+VB+hZsErLF0hfgXdpR4wAcS0gxyBBxdBX5LqvsRjgyc8
t0GP57kT6pCJrm5u/jMbNc0NVogC/EtTjHzwqYZMCG/Ilfu3SFcH0ePnGXQdHIWa3ZJgiVcGkOja
kbfkURfWT/ACUxMJ1gsSzb/ACcCmsV0yHmk0MdPj0ecgwh+3ZImXijhY+YN1PVj5ZCtDFrlBQ7b2
ydY+2donu/LJrnyyK5/s2ie79mW7tmRfUIUVKvY1QetBS58rX9ClP4h8qXsq1IOGwZXPYEi5etCy
wZVV4ZyT9Ya+k6FLRHQ332HP4euvOPzNgryBQT8edap/DtY3CBONFXAYtYeeIsB6fdMaemv1sLGh
HrbXXnlmiNqsIssqaoZRe7hqDz1WqzarVZvVqqWRHq7aQ4/Vus1q3VZw7ViB8xqsid6ENzfXy+Vy
PPIPS7oDIu3jUhS9GfSFxhSNDf8GUEsDBAoAAAAAAFOOIS4AAAAAAAAAAAAAAAATAAAAYmlsbF9s
aWZlL3BhdHRlcm5zL1BLAwQUAAAACAAdW40tgG9RGqoAAAD1AAAAHQAAAGJpbGxfbGlmZS9wYXR0
ZXJucy9SUEVOVE8uTElGNc4/C8IwEAXwvdDvcNCt1NBSRBwFwUXEzTm0iQmau5A/9uubnDi8IfDL
u9ddrVYwiXHfNt0Zws4rTOQsEr9PEJ18vwf42CcFynGAhZwjBC9TUgFFZUwfRiEko+AinQLSwM2b
jKBtiImNxRRozYtaQZY2XGE6HsahfLOxUkY+kKdYSeQ+XqBi+p9kpCnAZuximFBOZdbvWsYX0sbD
biV3mGFuG9H3bVMjSr5QSwMEFAAAAAgAdLiTLbxF7EjFBgAAcRYAABEAAABiaWxsX2xpZmUvdXRp
bC5webVYbW/bNhD+HiD/4Wp/sOw6QrJiG1AsA/oKFMiSoO2HAVk+UBJtc2VIgaTieMP+++5I0Xqx
7LodpiKJfXzueHc83j3V6ckY3v3+6rfbq3dw9eE9vP9w9e70ZDQanZ6Mr8SCw0V6/iN+fguvcm2U
//R5xeFBWwePYqmNrqzcwNLotVBL+Pks51J62OiBu1VluWSrEZTMOW5UCvCJc2DSavj46vXrD58/
pQi+xp9bOHsBZxenJ+kMf1L6PZvhn9ms9of+FXwRTb0VD1xZoZVNaomdvjw9AXzGsBDLynDQlQOH
3hZbLOiFl3DlBAIWQvKgI/nCwSWch29Ol80XI5ar1lqmndMPzfeFNtEnECp+tLUv3vYcSL9euZuU
2gqH3kzuG8xaFG41hxWvN9uCrfiLt4EGFyU8DwqNOEOxQ3Ew0MjFAtG/+PBaHtFTRyw7WIdYDL4H
DenoWjXwa8hMDxuzZTroDNEhcT34NptZnWzuKkwkOTenfefB4LwGxiIwnBVUn+/xAOn8V83Zu5Ww
kOtKFpBxyFdMLXmBpoABVqM5Q3WhUFIIE1Use0QBHh5DRYXFExYKbnMjSjoqdHAyiXDO8tX2yNdC
StKyAm8EVhdT8DSHTcTqxcLyOnOxNNDY3X1HhJK//6lLz2xaKVpQ4nXJVQiyWSiYY7i0KFNKhcSI
bDJt66W51JaTrHMQpHd3fp9ah5ElU3iGgTU3fdI/zHAa11rxth0qedqSUuYNXry872lSkASJG3VX
0REEUE57avSUzNqulEtSQFPMOLsWbpVMxteTKaAbPenHyXTA4hjQZPXA4Y1Wa7aB5FqbByanYCrJ
rQ9H6fX3evJ2cE/Kdbt+9gRLT7fO7N2Ll/fDaaOHS8uPsPP8EkZ/qBF2hAP2hqK53ZPBjC+FUtTj
qciB2jxkUudfBkOPdf2MCnuPu70Wh6EnnS44EHxLzaasxHtRxO6f5rrcJNMBJbqOTV5LKVwygckA
0O/eNPb2s+3LA2u7d3hgtd31KVKhXPI0nQP93Qx5vdXDyWq9zt19F7WnEnqKMU12YA8aDtha7BS7
sw9+z0nFxATw3uxgzV10ms2hKvjG0//qqTfwfbOjmapD3KHRH5cGTwVGma5UYUfzA8Oor0KxoALL
bBLm4JlXngZR7cYZmWrtVzfZ1u2db8OdQ7LdHa0kx1iuTfOnnJft6dxr5p5UOY5Ty1U4KDOW0dAi
zkWsC5LyBzI0S4mEERuDNHxM+x9TrxNZIw1dlklOE5cOBwdiQY3UIdsy6COxryWOJsvMhuCl0Tm3
NgxVmhgk9N2KZidqbzBQVlDjIUvOMCHpiy0Z6hFYKySgfgKiceZCpwJqZ9inUhoSM2DG2y2x0UUK
WKfYuyyZ+lKbQCSIpdKGF944Qk1riRVFYBOeVzZHRlgGvrsA8o8Ck4yOeVTtmsYDeNCP3g/kKGpp
ceULx0T/dD5tctNyyzMZzy+UdoBEppDbdVRmZslNwDGiLr4bY/Q5Q55DtigSi7pgq7LUxhGWZl1C
HXFaUxMbCBXmVVnJHH8jRZlpZorbsFFCAz6OhFbAn2hoYCq2LXGYLR3Fefp8InTpmtS0Kng/qdhL
KLoj3A88SqZFDkS7JZN0MofJjH7d7Ey+MR138GzoxLvQbBPzTOVJ4JyVwjEJNztWLdXK5iHTEtaE
U7Dkro9yK+zgyt8CtM1ihnZhHbfCHQgjPVyCne3pdqwEXrechULpkNk+Gj3Di2xMVTq6Et1FvEtI
tQ2awbpfR9KtRF5nTOC98qmIVdU34Mv7z8rSHsoxz8Ebb9B7LN8DScfC8cpU8alvELMu5Ega1qNg
XcCeQbuHbrWrbUevy+7jg22ejNHOBwnK8I4k7Tncb/3x2SW0RxO71ji/3EPqvpM/jZsjPJ/D+X46
Hv83hbPKYufBJNC8BepaZijWQeJFW3wX3TqSVx3DqQ7xqR0udYBHfQOHOpI//Rfu9I286bs50//A
l+JrBUVpy7Sxn6tS8iTXEl3X6+blQr03Q86EALoxUSVIbAT62Y29S2qFUxrWhpU2vGFw2lQ1rDT8
8aNeY3JxE/SmPnHFn1wjfh7FhH6DE+MSW6XsohvxFl17miS12jzuRmnJe99rGy1ZtygbI6anYA6B
60C2O7a+bw1E2XT7fk8isYvkY2lEMafAbvzN9/vFj/WZx8MxMWM3rVcu4+3dEdaP0PCShvgDErCA
abOPGt26Y3lMbdtsVMtJh3R7lxzvbB7oxR5mQQ/FdtfUGF3fi12U74axxtDkV0p0aJMU/cbMskq6
JKrvdsE9U27Ay14P92XX8d2X7WWvEsnQ6cm/UEsDBAoAAAAAACORIS4AAAAAAAAAAAAAAAAKAAAA
YmlsbF9saWZlL1BLAQIUABQAAAAIAAORIS5TSMYRPQkAAMcbAAAUAAAAAAAAAAEAIAC2gQAAAABi
aWxsX2xpZmUvY21kTGlmZS5weVBLAQIUAAoAAAAAAFOOIS4AAAAAAAAAAAAAAAATAAAAAAAAAAAA
EAD/QW8JAABiaWxsX2xpZmUvcGF0dGVybnMvUEsBAhQAFAAAAAgAHVuNLYBvURqqAAAA9QAAAB0A
AAAAAAAAAQAgALaBoAkAAGJpbGxfbGlmZS9wYXR0ZXJucy9SUEVOVE8uTElGUEsBAhQAFAAAAAgA
dLiTLbxF7EjFBgAAcRYAABEAAAAAAAAAAQAgALaBhQoAAGJpbGxfbGlmZS91dGlsLnB5UEsBAhQA
CgAAAAAAI5EhLgAAAAAAAAAAAAAAAAoAAAAAAAAAAAAQAP9BeREAAGJpbGxfbGlmZS9QSwUGAAAA
AAUABQBFAQAAoREAAAAA

------=_NextPart_000_0052_01C2B269.BE8B36E0--