Infinite board solution


  • 46

    For the second follow-up question, here's a solution for an infinite board. Instead of a two-dimensional array of ones and zeros, I represent the board as a set of live cell coordinates.

    def gameOfLifeInfinite(self, live):
        ctr = collections.Counter((I, J)
                                  for i, j in live
                                  for I in range(i-1, i+2)
                                  for J in range(j-1, j+2)
                                  if I != i or J != j)
        return {ij
                for ij in ctr
                if ctr[ij] == 3 or ctr[ij] == 2 and ij in live}
    

    And here's a wrapper that uses the above infinite board solution to solve the problem we have here at the OJ (submitted together, this gets accepted):

    def gameOfLife(self, board):
        live = {(i, j) for i, row in enumerate(board) for j, live in enumerate(row) if live}
        live = self.gameOfLifeInfinite(live)
        for i, row in enumerate(board):
            for j in range(len(row)):
                row[j] = int((i, j) in live)

  • 0
    C

    HI, I dont quite understand. Could you or someone rewrite to Java code? Thanks!


  • 0
    This post is deleted!

  • 10

    Not really keen on doing it in Java. What I do is I have the coordinates of all living cells in a set. Then I count the living neighbors of all cells by going through the living cells and increasing the counter of their neighbors (thus cells without living neighbor will not be in the counter). Afterwards I just collect the new set of living cells by picking those with the right amount of neighbors. Does that help?


  • 15

    I just had an idea - writing a more Java-like version:

    def gameOfLifeInfinite(self, live):
        neighbors = collections.Counter()
        for i, j in live:
            for I in (i-1, i, i+1):
                for J in (j-1, j, j+1):
                    if I != i or J != j:
                        neighbors[I, J] += 1
        new_live = set()
        for ij in neighbors.keys():
            if neighbors[ij] == 3 or neighbors[ij] == 2 and ij in live:
                new_live.add(ij)
        return new_live
    

    I think that should be understandable even if you don't know Python.


  • 0
    C

    Yeah, this is more readable for me. Thanks!


  • 1
    X

    Hello! May I ask why the dead cells are not counted? According to the rules of game, the dead cells could become live ones in the next generations (if the counter = 3).


  • 1

    @XueW22 Sorry, I don't understand. Yes, they can become live in the future, and when they do, then I will count them. But why would I count them when they're still dead?


  • 0
    X

    Thanks! Get the idea now.


  • 28
    R

    Here is (quite verbose) translation to Java:

        private Set<Coord> gameOfLife(Set<Coord> live) {
            Map<Coord,Integer> neighbours = new HashMap<>();
            for (Coord cell : live) {
                for (int i = cell.i-1; i<cell.i+2; i++) {
                    for (int j = cell.j-1; j<cell.j+2; j++) {
                        if (i==cell.i && j==cell.j) continue;
                        Coord c = new Coord(i,j);
                        if (neighbours.containsKey(c)) {
                            neighbours.put(c, neighbours.get(c) + 1);
                        } else {
                            neighbours.put(c, 1);
                        }
                    }
                }
            }
            Set<Coord> newLive = new HashSet<>();
            for (Map.Entry<Coord,Integer> cell : neighbours.entrySet())  {
                if (cell.getValue() == 3 || cell.getValue() == 2 && live.contains(cell.getKey())) {
                    newLive.add(cell.getKey());
                }
            }
            return newLive;
        }
    

    where Coord is:

        private static class Coord {
            int i;
            int j;
            private Coord(int i, int j) {
                this.i = i;
                this.j = j;
            }
            public boolean equals(Object o) {
                return o instanceof Coord && ((Coord)o).i == i && ((Coord)o).j == j;
            }
            public int hashCode() {
                int hashCode = 1;
                hashCode = 31 * hashCode + i;
                hashCode = 31 * hashCode + j;
                return hashCode;
            }
        }
    

    and the wrapper:

        public void gameOfLife(int[][] board) {
            Set<Coord> live = new HashSet<>();
            int m = board.length;
            int n = board[0].length;
            for (int i = 0; i<m; i++) {
                for (int j = 0; j<n; j++) {
                    if (board[i][j] == 1) {
                        live.add(new Coord(i,j));
                    }
                }
            };
            live = gameOfLife(live);
            for (int i = 0; i<m; i++) {
                for (int j = 0; j<n; j++) {
                    board[i][j] = live.contains(new Coord(i,j))?1:0;
                }
            };
            
        }

  • 0
    S

    The rule says that if a cell is currently 0 and it has exactly 3 live neighbours, it will relive. May be we should count the whole board instead of just living ones?


  • 2
    C

    but, is there any hint, that the number of live cells is finite, so that you can put all of them in a set? Since the board is infinite, wouldn't it be expected that live cells are also infinite?


  • 1

    @Chomolungma Supporting infinite collections of live cells is impossible (there are uncountably many, and there are only countably many inputs). So I think it's ok that I don't :-)

    I also just checked what the wikipedia page has to say about infinite boards and "vector of coordinate pairs representing live cells" is mentioned as one solution.


  • 0
    M

    @sometimescrazy
    It's covered if you look at StefanPochman's python and ruben3's java implementation carefully. The neighbors include dead cells from the previous step and some of them could be live cells after the update.


  • 0
    E

    The way it gets the count is so brilliant!
    it only calculate the count of the potential live node of next state, which is the neighbors of current live nodes. It iterate through the neighbors of current live nodes, and add 1 to their count!
    (live node without live neighbor will not be in the count)
    I learn so much from you Stefan. Thanks


  • 1
    S

    @mycscareer @StefanPochmann - What I am having trouble to understand is why we need this check in Stefan solution: "and ij in live". Neighbors will contain the number of live neighbors for each I,J. So if a dead cell has 3 live neighbors then it will become live again which i think is omitted by check above ? Can someone help me to understand here what am I missing.

    Example:
    1,0,1
    1,0,0

    then live will contain cordinates {(0,0), (0,2), (1,0)} and neighbors will contain (x_cor, y_cor, count): { (0,0,1), (0,1,3), (1,0,1), (1,1,3), (1,2,1)}

    but the final set new_live will contain zero element since 2nd and 4th element in neighbor is not in live whereas it should contain those element ?


  • 0
    A

    @sorabhit In the condition "if neighbors[ij] == 3 or neighbors[ij] == 2 and ij in live", "and" will be judged before "or". So "neighbors[ij] == 3" considers both "live cell with 3 live neighbors remain alive" and "dead cell with 3 live neighbors become alive" situations, then "neighbors[ij] == 2 and ij in live" considers "live cell with 2 live neighbors remain alive" situation, which are all the positions for a cell to be alive in the next step.


  • 4
    A

    @sorabhit You confusion was because the code was not bracketed.
    It is actually if (neighbors[ij] == 3 or (neighbors[ij] == 2 and (ij in live))): with proper brackets.


  • 0

    Got confused by the description of follow up 2. According to Stefan's answer, seems that the problem can be stated as:

    Assuming that the board is infinite while # of live cells is finite, how to proceed the state transforming process?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.