To put it as short as possible: I want to create algorithm to generate every single possible combination of alive cells in John Conway's Game of Life starting with a single cell and then going bigger and bigger but without generating combinations that could be considered equal to any previously generated ones.
This task seemed so overwhelming that I made a decision to first try and generate only 1-dimensional combinations and if I succeed then try and see how I can apply similiar approach for 2-dimensional ones. So to do that I first wrote down the rules that my 1-dimensional combination should follow and those go like this:
- combinations will be represented as an array of bits
- 1 means cell is alive, 0 means it is dead
- combinations like 000011001 and 11001 and 1100100 should all be considered the same and only the shortest 11001 should be generated
- combinations that are a mirror of each other should also be considered the same and only one version should be generated, example: 10011 and 11001
- generation should start with the shortest possible combination and a longer one should only generate after all possible shorter combinations were generated
example output:
0, 1, 11, 101, 111, 1001, 1101, 1111, 10001, 11001, 10101, 11101, 11011, 11111, 100001, ...
So I started writing code. To store a single combination I chose the long type and I decided that I will store the result of the generating process in an array of those long types: long[] myArrays. I wrote a simple method printArray(int i) to print a combination in console and then, to help me visualize the process, I wrote a code that prints the first 5 combinations that should be generated:
What I noticed at this point was that once the length of combination goes above 2 eg (101, 1001, 10001) I can fill the zeros inside with what was generated previously. With that in mind I first wrote private void generate(int m, int n) method that would generate arrays that start at m and end at n with 1s and have 0s everywhere in between. Then I wrote a loop that calls this method with m equal to 0 and n incrementing by 1 with every iteration. And then for the cases where the array is long enough to have 0s inside I added a loop in the method that would recursively call the method with every possible combination of m and n in ranges where there are 0s such that m <= n. If it is not clear what I mean I put the code I had at that moment below:
But here I forgot that the combination generated inside ijloop must be made on top of combination already generated inside generate(int m, int n) so I came up with a way to pass this previously generated combination to the method. I added new parameter int origin in which I would pass the index of myArray that contains the combination on top of which new one needs to be built:
Now the only problem was that it also generated mirrored arrays and I needed to get rid of them. My first idea was that if you look at those generated arrays: (11001, 10101, 10011) you can notice that mirrored array got generated after inner 1 crossed the middle ground. Thus I should limit i inside ijloop to only go as far as middle of the length of array. I also noticed similiar problem with j. Let's have a look at those generated arrays:
The 1 that travels from index 5 to 4 to 3 to 2 is generated by j and array x is a mirror of array 2. So here I concluded that j needs to only go as far as n - (i - m). But there is yet another thing to consider. Think about array like this: 11000101. When it comes to 000 subarray inside it we want to generate every possible combination without any limit to i or j and the condition for that is symmetry. So my guess is I should add another parameter to the method. It will be boolean isSymetric. If that parameter is true I should generate only arrays with limited i and j and then pass true if the new array to be generated will still be symmetric. And the condition for that is i - m == n - j. Otherwise I should pass false. Now code looks like this:
It seems like so far I done well but I feel that there is a better/more simple/faster way to do this. Is there?
Also how do I google for something like this? Because my efforts in that area didn't bear any fruit and only led to frustration.
Is there a name/term for something like this?
But that's not all. The next thing I wanted to do is to be able to turn a number into one of those combinations with the same rules. And I commited something like this:
The code basically uses my solution to generate every combination starting from 0 and stoping when it reaches the ID passed to the method. How can I do this one better/more simple/faster?
And finally and most importantly how can I do a similiar thing in 2-dimensional array made of 0s and 1s?
And with rules excluding from generation any array that is a mirror/rotation/translation (or any combination of those) of previously generated array.
Because with 2-dimensional arrays I don't even know what place would be good to start with. I tried googling, I thought about
starting with array of size (1, 1) and then going to size (2, 2), (3, 3), ... and so on or
(1, 1), (2, 1), (2, 2), (3, 1), (3, 2) ... or
[1], [2], [3], [2][1], [4], [3][1], [2][2], [5], [4][1], [3][2], [3][1][1] ... in case that is not clear [6][5][2][2] would stand for an array of size like this:
but thinking about all of that only serves to make me confused. I thought doing the 1-d array first would help me with wrapping my head around all of that but 2-d arrays don't have any cells that would be beginning and an end that has to be 1 and have a lot of transformations that can make multiple different combinations equivalent and in need of exclusion like
and
and
So I am pretty stuck with this at the moment.