7
$\begingroup$

First post to Math Stackexchange. Recently I was posed with a mathematically intensive computer programming challenge that I am completely at a loss for solving. To give you some info on my math background, I'm a senior physics major and computer science minor at university and have recently completed a course in linear algebra in addition to having taken calc 1, 2, multivariate calc, and diff eq. I have some small experience with discrete mathematics and number theory from an intro computer science course. I have applied linear algebra, discrete mathematics, and algebraic coding courses scheduled in the next 6 months but am not sure if I will cover the material to answer my problem. I would wait until after taking the courses to see if I can apply anything new to it but this problem has been driving me nuts.

I'm not necessarily looking for a solution but rather some areas to look into that may help me to solve it. If more info or explanation is needed, please let me know. The problem is as follows:

From the scans of the nebula, you have found that it is very flat and distributed in distinct patches, so you can model it as a 2D grid. You find that the current existence of gas in a cell of the grid is determined exactly by its 4 nearby cells, specifically, (1) that cell, (2) the cell below it, (3) the cell to the right of it, and (4) the cell below and to the right of it. If, in the current state, exactly 1 of those 4 cells in the 2x2 block has gas, then it will also have gas in the next state. Otherwise, the cell will be empty in the next state.

For example, let's say the previous state of the grid (p) was:

.O..
..O.
...O
O...

To see how this grid will change to become the current grid (c) over the next time step, consider the 2x2 blocks of cells around each cell. Of the 2x2 block of [p[0][0], p[0][1], p[1][0], p[1][1]], only p[0][1] has gas in it, which means this 2x2 block would become cell c[0][0] with gas in the next time step:

.O -> O
..

Likewise, in the next 2x2 block to the right consisting of [p[0][1], p[0][2], p[1][1], p[1][2]], two of the containing cells have gas, so in the next state of the grid, c[0][1] will NOT have gas:

O. -> .
.O

Following this pattern to its conclusion, from the previous state p, the current state of the grid c will be:

O.O
.O.
O.O

Note that the resulting output will have 1 fewer row and column, since the bottom and rightmost cells do not have a cell below and to the right of them, respectively.

Write a function answer(g) where g is an array of array of bools saying whether there is gas in each cell (the current scan of the nebula), and return an int with the number of possible previous states that could have resulted in that grid after 1 time step. For instance, if the function were given the current state c above, it would deduce that the possible previous states were p (given above) as well as its horizontal and vertical reflections, and would return 4. The width of the grid will be between 3 and 50 inclusive, and the height of the grid will be between 3 and 9 inclusive. The answer will always be less than one billion (10^9).

Inputs:
(boolean) g = [
                [true, false, true],
                [false, true, false],
                [true, false, true]
              ]
Output:
(int) 4

Inputs:
(boolean) g = [
                [true, false, true, false, false, true, true, true],
                [true, false, true, false, false, false, true, false],
                [true, true, true, false, false, false, true, false],
                [true, false, true, false, false, false, true, false],
                [true, false, true, false, false, true, true, true]
              ]
Output:
(int) 254

Inputs:
(boolean) g = [
                [true, true, false, true, false, true, false, true, true, false],
                [true, true, false, false, false, false, true, true, true, false],
                [true, true, false, false, false, false, false, false, false, true],
                [false, true, false, false, false, false, true, true, false, false]
              ]
Output:
(int) 11567

I have looked into coding theory but don't think this falls into any of those categories. I have explored options in bit masking image processing, and cellular automata. The closest I have come to a solution is in researching Margolus neighborhood 2D cellular automata. As this isn't reversible by definition, I haven't found a solution or even general method to find a solution. I'm just curious where I should look. I know this has to have an answer stemming from a field in mathematics but it doesn't resemble anything I currently know.

$\endgroup$
3
  • $\begingroup$ How is the value answer(g) supposed to be calculated? You've told us what the input is, but not what the output is supposed to tell us. The rules for evolution are a little bit like Conway's Game of Life, but at first glance it looks like this is most likely to be approached by bit-wise operations on binary strings. $\endgroup$
    – postmortes
    Jun 20, 2017 at 5:25
  • $\begingroup$ I guess that's really the heart of my problem. I'm tasked with designing the function. Nearly all of the challenges I've been posed with have dealt with combinatorics with some design problems and one difficult recursion relation. The output is the number of possible previous states that will lead to the given current state following the neighborhood rule given. I have added an edit. It looks as though the original post was missing part of the question describing the meaning of the output as well as what a solution should look like. Hopefully this helps. $\endgroup$
    – Kyle
    Jun 20, 2017 at 14:25
  • $\begingroup$ I am late to the party by few years:) This problem can be solved in several ways which is what I did. Fundamentally, I recommend writing a brute force solution. Then optimize it. And then look closely at why the brute force method doesn't complete under larger grids. $\endgroup$
    – Vortex
    Jan 10, 2021 at 3:08

1 Answer 1

Reset to default
4
$\begingroup$

this is clearly a cellular automaton (CA) question. It has to do with computing the number of preimages of a certain CA rule of size 2x2 within a finite rectangular array. Think of how you would try to construct such preimages. The input (current configuration) is an array of size NxM with values 0 and 1 (true and false if you prefer). So the preimages (i.e. configurations one time-step in the past) have size (N+1)x(M+1) also with values 0 and 1. Now what is the local rule of evolution from one configuration to the next? It has to do with the values of four adjacent cells determining the new value of one cell. Try to do a small example by hand, e.g. given the 3x3 input g from your post. Can you find all four preimage-configurations step by step? Think of what it means to specify some of the cells in the preimage (e.g. along a column or a row) to see what cells in the preimage become determined by those values and by knowing their state (0 or 1, gas or no gas) in the next step of the evolution (i.e. in the input g).

In general finding preimages of CAs (or even determining their number) is a hard problem, but in the case of finite configurations and this specific evolution rule a computer can manage. There is a brute force algorithm which should work fine for the specified input sizes, but there is also a more clever/elaborate algorithm to save a lot of time, especially if your input is a rather long but narrow rectangle.

Hope these comments give you some ideas how to attack the problem. If you need more details, let me know.

$\endgroup$
6
  • $\begingroup$ Ok, so I expanded across the top row of the 3x3 matrix given and came to some conclusions. Row (1 0 1) gives 8 preimages. (I tried to list them here but can't format them right) When expanding the next row, I noticed that the correct preimages for the second row had their top row in common with the bottom row of the first row's preimages. They "overlap" It seems fairly daunting to write an algorithm to find a row's preimages and then continue down the matrix keeping only preimages that "overlap" $\endgroup$
    – Kyle
    Jun 20, 2017 at 17:41
  • $\begingroup$ But in its core it is the right idea. $\endgroup$
    – MHS
    Jun 20, 2017 at 17:59
  • 2
    $\begingroup$ What makes things more treatable is that you could set up something which is called a transfer matrix. The idea is that given a column (take the shorter of the two sides of the rectangle) there are certain preimages possible. Those have the shape of a rectangle of width 2 (i.e. two columns) and you could store possible preimages for a given image column in an array. Now for the next column, you would take its preimages and simply compare which ones are admissible with the ones the previous column produced. $\endgroup$
    – MHS
    Jun 20, 2017 at 18:06
  • $\begingroup$ Since the height of your input rectangle is not more then 9 cells, this preimages array has not more than 512 entries and the algorithm to go through up to 50 columns should be fast enough to yield the desired answer. (There are more tricks to speed up the computation, but start with something simple, brute-force-ish.) And all steps (i.e. filling the matrix, comparing overlaps of columns etc.) can be made automatically using subroutines. $\endgroup$
    – MHS
    Jun 20, 2017 at 18:06
  • $\begingroup$ Well she isn't pretty but I have a working program to solve the test cases given to me at least. Hopefully it runs in decent enough time to solve more complex cases. Thank you for the inspiration and ideas! $\endgroup$
    – Kyle
    Jun 21, 2017 at 6:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.