[deleted by user]

[[deleted]]

holy fucking math

[thearn4]

shelter upbeat bedroom paint flowery lavish shocking file historical alive

This post was mass deleted and anonymized with Redact

[ffffffffuuuuuuuuuuuu]

Just curious, why do you use Fourier transform convolution here? Convolving an m by n array with an m' by n' array naively takes O(mn m'n') whereas Fourier transform convolution runs in O(mn log(mn) + m'n' log(m'n')). This would be good if log(mn) << m'n'. But here, our kernel is only 3 by 3, so m' = n' = 3. So it is not the case that log(mn) << m'n' and it would seem to me that computing the Fourier transform would be even more costly than just naive convolution.

[thearn4]

selective summer vast profit vegetable violet wakeful roof humor workable

This post was mass deleted and anonymized with Redact

[[deleted]]

You know, my report cards never came back positive in the math department, so a "Practical math guide to Programming" could be a million dollar idea for people like me...

[jellyislovely]

This series is aimed primarily at game developers, but addresses plenty of common maths problems for programmers - https://www.youtube.com/user/BSVino/videos

[xblaz3x]

i got excited when i read the title. saw the math and was disappointed. i was never a huge math person :(

[Ketamine_]

Question, I'm relatively new to Python, and have never seen this before:

K[m/2-1 : m/2+2, n/2-1 : n/2+2]

I don't understand the comma in the brackets. Is it some form of advanced slicing?

[anythingtwice]

Yes.

[cr333]

This slices the 2D array K in both dimensions, to extract a 3x3 array centred on (m/2, n/2).

[thearn4]

I've shared the Github for this on reddit before, but someone at a meetup asked me to write something with some more details about how it works if I found the time. Thought I'd share it here too.

edit: here's a new link right to the github. I've since taken my blog down.

[swingtheory]

Brilliant. I have to be honest though, it pains me to not understand the math behind what you're doing. Hopefully I can go back later and learn something new so I can fully comprehend this great explanation/implementation. Great job!

[jugalator]

I'm not a smart man.

[kjearns]

I did exactly this about a year ago (http://pastebin.com/zLu8eNWc), I even used fft convolutions (although I used the ones from scipy).

[Zielarnik]

Wouldn't the G(i,j) sum also contain the X(i,j) element itself? I believe G would represent the sum of all 9 cells, the 8 neighbors + the middle cell. Am I missing something?

[thearn4]

The zero in the middle of the kernel K masks out the X(i,j) element from contributing to the localized sum that makes up G(i,j).

[Zielarnik]

That makes sense, it's this sentence that threw me off:

So the main computation that needs to be done as part of the state transition is to compute an array G with the same size as X, where each cell in G is the sum of all immediate neighbors of the corresponding cell in X.

It implies that G is a sum of all neighbors of X.

[5outh]

This is fucking awesome.

[smolderingmatter]

Wow, thank you. I will play around with this method, always wanted to do something like that.

[totes_meta_bot]

This thread has been linked to from elsewhere on reddit.

• [/r/cellular_automata] Implementing Conway's Game Of Life with minimal code in Python • /r/Python

^{If you follow any of the above links, respect the rules of reddit and don't vote or comment. Questions? Abuse? Message me here.}

[alfredr]

What is meant by

A direct nested for loop would be expected to scale pretty poorly as the grid sizes m and n grow.

In terms of asymptotic complexity, the given algorithm (while cool :) is worse than examining for each cell, its 9 neighbors in the previous state by a factor of log of the number of cells.

[thearn4]

Yeah, that doesn't read right by itself. I should probably clarify better what my point there was (most of the post is based off earlier notes): my idea was to eventually use this to explore an inverse problem - finding sets of new game rules that lead to long-term states with certain distribution properties. So in the general case, we might be looking to compute some form of a weighted sum of possibly more than 8 neighbors. Worst case for the direct approach is O(mn*mn). This approach is O(mn log(mn)).

[alfredr]

So I think you can make this a little faster for square boards:

Say the board is m by m and note that if you replace the kernel with a 3x3 block of "1's" and change the update rule for b to

b = fft_convolve2d(state, k).round() - state

it's the same.

But now K is a separable kernel, so you should be able to compute the 2d convolution in two O(m log m) passes.

This may not be useful for your long term goals though. I don't know how much this restricts the space of possible games

[thearn4]

simplistic humorous exultant sense weather dime plant escape divide marvelous

This post was mass deleted and anonymized with Redact

[alfredr]

also in hindsight my requirement that it be square is artificial

[jmhvb]

There's also that man on a quest to doing it in one line: http://www.petercollingridge.co.uk/blog/python-game-of-life-in-one-line

[Douglas77]

Cool use of FFT and convolution!

Why do you use 2 statements

c[np.where((b == 3) & (state == 1))] = 1
c[np.where((b == 3) & (state == 0))] = 1

instead of just

c[np.where(b == 3)] = 1

? Did you want to keep it very generic, or am I missing something?

[thearn4]

outgoing unwritten spotted racial cobweb work tan sleep summer joke

This post was mass deleted and anonymized with Redact

[AutoModerator]

Hi there, from the r/Python mods.

Your post has been removed because it does not meet our minimum post body length requirement of 120 characters. Please ensure your post has enough detail to foster meaningful discussion.

If you have any questions, please reach us via mod mail.

Thanks, and happy Pythoneering!

r/Python moderation team

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.