4 ms·
I figured caching the results of common patterns appearing in blocks of 2x2, 3x3, 4x4, etc. pixels which are surrounded by all 'off' pixels, you can easily skip
by alainbryden 14y ago
I figured caching the results of common patterns appearing in blocks of 2x2, 3x3, 4x4, etc. pixels which are surrounded by all 'off' pixels, you can easily skip many repetitive calculations.
---- ----
-oo- =\ -oo-
-oo- =/ -oo-
---- ----
----- ----- -----
--o-- ----- --o--
--o-- =\ -ooo- =\ --o--
--o-- =/ ----- =/ --o--
----- ----- -----
------ ------ ------
-oo--- -oo--- -oo---
-oo--- =\ -o---- =\ -oo---
---oo- =/ ----o- =/ ---oo-
---oo- ---oo- ---oo-
------ ------ ------
Since repeating patterns tend to turn up a lot on their own in CGoL they would end up cached, and large blocks of n cells could be computed in 1 move rather than requiring o(8n) time. That seems to be how Hashlife works: http://en.wikipedia.org/wiki/Hashlife http://en.wikipedia.org/wiki/Hashlife
- eranation 14y agoHere is a CoffeeScript implementation of Hashlife https://github.com/raganwald/cafeaulife https://github.com/raganwald/cafeaulife
- tisme 14y agoThat does not credit Bill Gosper. http://www-users.cs.york.ac.uk/~jowen/hashlife.html http://www-users.cs.york.ac.uk/~jowen/hashlife.html
- deleted 14y ago[deleted]
- raganwald 14y agoWhere doesn't it give appropriate credit? 1. The description line for the Github package reads "Gosper's HashLife in CoffeeScript" 2. The readme says: "Cafe au Life implements Bill Gosper's HashLife algorithm." 3. The docs say "Cafe au Life is based on Bill Gosper's brilliant <a href="http://en.wikipedia.org/wiki/Hashlife>HashLife</a> http://en.wikipedia.org/wiki/Hashlife>HashLife</a...; algorithm."
- tisme 14y agoWell, I could be wrong but I swear did an 'F3' on the page earlier to search for Gosper and it seemed like it wasn't there then. Apologies for not being able to use a browser and falsely accusing you!
- raganwald 14y agoCredit for ideas is important. I'd rather 100 people falsely accuse me than have one omission slip through. Thanks for caring.
- raganwald 14y agoFYI: It has its own home page: http://recursiveuniver.se http://recursiveuniver.se