codeholic / gencols Goto Github PK
View Code? Open in Web Editor NEWThis project forked from conwaylife/gencols
Program to search for collisions in Conway's Life
Home Page: http://www.radicaleye.com/lifepage/gencols.txt
This project forked from conwaylife/gencols
Program to search for collisions in Conway's Life
Home Page: http://www.radicaleye.com/lifepage/gencols.txt
Overview: -------- The following directory contains the source and related files for "gencols" a program that searches for pattern interactions in Conway's Game of Life by generating interactions between pairs of patterns within a range of user-determined parameters, and which filters the output for "interesting" objects (those with special properties). This includes, but is by no means limited to, collisions occurring between pairs of gliders. The result of a successful search will be a list of patterns, one on each line. Each pattern is encoded as a string in the first field of the line, and additional fields give some extra information about the collision. The encoding is quite simple: '.' denotes a dead cell, '*' denotes a live cell, and '!' denotes the action "move to beginning of next row" (assumed to have the same x coordinate as the first cell in the string). Also, a program "makematrix" is provided to convert such a list into a Life pattern suitable for viewing with Xlife 3.0, in which collisions are positioned in a regular array. Installing: see the file "Installing" ---------- What's included? --------------- Three C programs: gencols <big complicated list of arguments> gencols is a Life collision generator that is the main program provided in this distribution. See the file "Arguments.Explanation" to see how to use it. Sample invocations are given in the C-shell script "Examples". I realize this is not a good user interface, but it is adequate for my purposes, and has been used successfully over a period of about five months as an aid in complex pattern construction. The program does not really need human interacton, so the command line approach is not entirely inappropriate. Improvements are encouraged, if anyone wants to put the work into it. One idea I had was to integrate it with Xlife, so that parts of the current pattern being viewed could be collided with other objects. However, I'm more interested in getting search results than improving the user interface, so this will have to do for now. makematrix [-space #space] [-maxcol #col] makematrix takes a list of patterns (usually generated as output by gencols) from standard input and prints to standard output a single Xlife pattern in which each pattern from the input is placed in a position on a regular grid. The optional parameter "-space" changes the spacing, while the optional parameter "-maxcol" changes the width of the grid. makepatlist file1 file2 ... filen makepatlist reads the patterns given in the list of files provided and prints a list of patterns, one per line, to standard output. This is useful for making lists of patterns for which gencols can attempt collisions. A directory containing objects for collisions: Successful installation will create a directory called "obj" containing patterns and lists of patterns for collision. These will be necessary for trying out the file "Examples." A shell script of sample invocations: The shell script "Examples" can be run in Unix by typing "Examples" after installation has finished. It demonstrates gencols by using it to find many collisions that are well-known, but remarkable nonetheless. Included are sample runs that "rediscover" both the p30 glider gun and the interaction that results in the p20 puffer train. The parameters given on the input line are such that a human being can easily rule other possible collisions simply by observing the behavior of the patterns to be collided. Many of these runs are quite fast, and all should finish in a realistic amount of time on any desktop machine (though the last two may take over an hour to finish on slower systems). In X-windows, it is recommended that you run "Examples" in one xterm and Xlife in another with the same current directory. This will allow you to look at the patterns as they are generated by loading in the file that is produced. Note on spurious results: Any search with gencols will filter the output to fit some specific set of constraints, but there may be solutions that satisfy the given constraints and yet do not behave in the manner that was truly intended by the user. A good example is provided in the run that searches for p30 glider guns. Two of its results (equivalent by symmetry to each other) do not succeed as guns because the glider that is produced collides with the gun several steps later. This can be eliminated by increasing the generation time before testing, but it is not really necessary, because the total number of solutions produced (4) is small enough to allow convenient selection by a human observer. In fact, it is often worthwhile to look at all instances of a given set of collisions by displaying the resulting grid in a program such as Xlife. This is because it is not clear from the beginning what kinds of collisions are interesting. It is not necessary that the output filters perfectly characterize the object being sought, but only that they reduce the possibilities to a manageable level. Thus, if you are looking for a specific object containing a certain number of cells, an efficient approach may be to generate all collision products that contain that number of cellls, and refine the choice by observing them using Xlife. Speed of the program: -------------------- While I make no claims that this is the fastest way to enumerate collisions, I have spent considerable effort at increasing the efficiency of this code. There are two main refinements to an easy brute-force approach of trying all relative positions between patterns. First, the only collisions that are tested are those such that the patterns do not share any neighbors for a certain number (call it k) of generations but must share neighbors at generation k+1. These interactions are enumerated fairly rapidly for any choice of k by exploiting pattern sparsity using a hashed list of cells. Second, the code to generate patterns after the collisions is performed using a variant of the strategy used in many of the fastest Life programs available, including Xlife. The strategy exploits both bit parallelism and pattern sparsity by representing the pattern as a sparse list of 32x32 boxes and using bit manipulation within the boxes. While the code is several times slower than that used in Xlife, it allows multiple patterns to exist simultaneously, and is (in my opinion) somewhat simpler to understand.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.