8 ms·

Solar Powered Conways Game of Life

15 points by signa11 3y ago

westurner 3y ago
Conway's Game of Life: https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life Solar power: https://en.wikipedia.org/wiki/Solar_power https://en.wikipedia.org/wiki/Solar_power E Ink: https://en.wikipedia.org/wiki/E_Ink https://en.wikipedia.org/wiki/E_Ink
- lproven 3y ago
  I am just curious, but what do you feel defining these three common terms, surely all well known to anyone who'd read HN, adds to the discussion?
  - westurner 3y ago
    Links are edges. When there are URL links, there are better edges that cost less to find than NLP tasks like conceptual entity recognition. Because I've added edges from hn_uri to wikipedia_uris; I, others, and search engines could discover the hn_uris relevant to the concept URIs (by graph pattern search) W3C SPARQL is a graph pattern query language. Some triple graph patterns enabled by there being links in the comments here in HN: ?s ?p ?o. ?s linksTo ?o. ?s linksTo <wikipedia_uri> . Also, recently, for example, because I linked to "methane" on Wikipedia unnecessarily, and then checked the "See also" section, and then saw the "Global Methane Initiative" page, I realized that there was an opportunity to forward the latest methane emissions tech to GMI (which I learned about by reading comparatively mundane background information from Wikipedia, which has Concept URIs which are reused by DBpedia which contributes to the Linked Open Data cloud for indeed what returns)
    - westurner 3y ago
      (I haven't even yet written a "parse into RDF and load into triplestore/quadstore" probably because just full text search over teh hnlog with Ctrl-F is usually good enough to find the citation I'm trying to recall; but search engines do index URL edges with some magnitude)
westurner 3y ago
Neat. Can it zoom out instead of wrapping around? From "Building arbitrary Life patterns in 15 gliders" (2022) https://news.ycombinator.com/item?id=33799981 https://news.ycombinator.com/item?id=33799981 : > From "Convolution Is Fancy Multiplication" https://news.ycombinator.com/item?id=25194658 https://news.ycombinator.com/item?id=25194658 : >> FWIW, (bounded) Conway's Game of Life can be efficiently implemented as a convolution of the board state: https://gist.github.com/mikelane/89c580b7764f04cf73b32bf4e94fd3a3#file-game_of_life-py-L113 https://gist.github.com/mikelane/89c580b7764f04cf73b32bf4e94... ; scipy.ndimage.convolve > Conway's Game is a 2D convolution > Convolution theorem: https://en.wikipedia.org/wiki/Convolution_theorem https://en.wikipedia.org/wiki/Convolution_theorem Conway's Game of Life > Algorithms: https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life#Algorithms https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life#Algori... Rosetta Code > Conway's Game of Life: http://rosettacode.org/wiki/Conway%27s_Game_of_Life http://rosettacode.org/wiki/Conway%27s_Game_of_Life
- westurner 3y ago
  scipy.ndimage.convolve / scipy.fftpack.dct* From https://github.com/thearn/game-of-life https://github.com/thearn/game-of-life : > How it's written > The game grid is encoded as a simple m by n array (default 100x100 in the code) of zeros and ones. In each program, a state transition is determined for each pixel by looking at the 8 pixel values all around it, and counting how many of them are "alive", then applying some rules based that number. Since the "alive" or "dead" states are just encoded as 1 or 0, this is equivalent to summing up the values of all 8 neighbors. > If you want to do this for all pixels in a single shot, this is equivalent to computing the 2D convolution between the game state array and the matrix [[1,1,1],[1,0,1],[1,1,1]]. Convolution is an operation that basically applies that matrix as a "stencil" at every position around the game grid array, and sums up the values according to the values in that stencil. And convolution can be very efficiently computed using the FFT, thanks to the Fourier Convolution Theorem. > One side effect: the convolution using FFT implicitly involves periodic boundary conditions, so the game grid is "wrapped" around itself (like in Pacman, or Mario Bros. 2). If you wanted to change this, you would just have to modify the 2D convolution function to use an orthogonal form of the DCT instead of the FFT. This would correspond to "hard" (i.e. Dirichlet) boundary conditions on the convolution operator. > I think you could do this with scipy using the 1D orthogonal dct provided: from scipy import fftpack fftpack.dct(data, norm='ortho') > but I haven't tried that yet. You'd have to define a dct2() method using fftpack.dct and separability (ie. the 1D transform matrix is rank-one, and the 2D transform operator is the Kronecker product of two 1D transforms) The (Inverse) Quantum Fourier Transform is also applied in QC; https://en.wikipedia.org/wiki/Quantum_Fourier_transform#Definition https://en.wikipedia.org/wiki/Quantum_Fourier_transform#Defi...
deleted 3y ago
[deleted]

15 points by signa11 3y ago

Conway's Game of Life: https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life Solar power: https://en.wikipedia.org/wiki/Solar_power https://en.wikipedia.org/wiki/Solar_power E Ink: https://en.wikipedia.org/wiki/E_Ink https://en.wikipedia.org/wiki/E_Ink

lproven 3y ago
I am just curious, but what do you feel defining these three common terms, surely all well known to anyone who'd read HN, adds to the discussion?
- westurner 3y ago
  Links are edges. When there are URL links, there are better edges that cost less to find than NLP tasks like conceptual entity recognition. Because I've added edges from hn_uri to wikipedia_uris; I, others, and search engines could discover the hn_uris relevant to the concept URIs (by graph pattern search) W3C SPARQL is a graph pattern query language. Some triple graph patterns enabled by there being links in the comments here in HN: ?s ?p ?o. ?s linksTo ?o. ?s linksTo <wikipedia_uri> . Also, recently, for example, because I linked to "methane" on Wikipedia unnecessarily, and then checked the "See also" section, and then saw the "Global Methane Initiative" page, I realized that there was an opportunity to forward the latest methane emissions tech to GMI (which I learned about by reading comparatively mundane background information from Wikipedia, which has Concept URIs which are reused by DBpedia which contributes to the Linked Open Data cloud for indeed what returns)
  - westurner 3y ago
    (I haven't even yet written a "parse into RDF and load into triplestore/quadstore" probably because just full text search over teh hnlog with Ctrl-F is usually good enough to find the citation I'm trying to recall; but search engines do index URL edges with some magnitude)

westurner 3y ago

Neat. Can it zoom out instead of wrapping around? From "Building arbitrary Life patterns in 15 gliders" (2022) https://news.ycombinator.com/item?id=33799981 https://news.ycombinator.com/item?id=33799981 : > From "Convolution Is Fancy Multiplication" https://news.ycombinator.com/item?id=25194658 https://news.ycombinator.com/item?id=25194658 : >> FWIW, (bounded) Conway's Game of Life can be efficiently implemented as a convolution of the board state: https://gist.github.com/mikelane/89c580b7764f04cf73b32bf4e94fd3a3#file-game_of_life-py-L113 https://gist.github.com/mikelane/89c580b7764f04cf73b32bf4e94... ; scipy.ndimage.convolve > Conway's Game is a 2D convolution > Convolution theorem: https://en.wikipedia.org/wiki/Convolution_theorem https://en.wikipedia.org/wiki/Convolution_theorem Conway's Game of Life > Algorithms: https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life#Algorithms https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life#Algori... Rosetta Code > Conway's Game of Life: http://rosettacode.org/wiki/Conway%27s_Game_of_Life http://rosettacode.org/wiki/Conway%27s_Game_of_Life

westurner 3y ago
scipy.ndimage.convolve / scipy.fftpack.dct* From https://github.com/thearn/game-of-life https://github.com/thearn/game-of-life : > How it's written > The game grid is encoded as a simple m by n array (default 100x100 in the code) of zeros and ones. In each program, a state transition is determined for each pixel by looking at the 8 pixel values all around it, and counting how many of them are "alive", then applying some rules based that number. Since the "alive" or "dead" states are just encoded as 1 or 0, this is equivalent to summing up the values of all 8 neighbors. > If you want to do this for all pixels in a single shot, this is equivalent to computing the 2D convolution between the game state array and the matrix [[1,1,1],[1,0,1],[1,1,1]]. Convolution is an operation that basically applies that matrix as a "stencil" at every position around the game grid array, and sums up the values according to the values in that stencil. And convolution can be very efficiently computed using the FFT, thanks to the Fourier Convolution Theorem. > One side effect: the convolution using FFT implicitly involves periodic boundary conditions, so the game grid is "wrapped" around itself (like in Pacman, or Mario Bros. 2). If you wanted to change this, you would just have to modify the 2D convolution function to use an orthogonal form of the DCT instead of the FFT. This would correspond to "hard" (i.e. Dirichlet) boundary conditions on the convolution operator. > I think you could do this with scipy using the 1D orthogonal dct provided: from scipy import fftpack fftpack.dct(data, norm='ortho') > but I haven't tried that yet. You'd have to define a dct2() method using fftpack.dct and separability (ie. the 1D transform matrix is rank-one, and the 2D transform operator is the Kronecker product of two 1D transforms) The (Inverse) Quantum Fourier Transform is also applied in QC; https://en.wikipedia.org/wiki/Quantum_Fourier_transform#Definition https://en.wikipedia.org/wiki/Quantum_Fourier_transform#Defi...

deleted 3y ago

[deleted]