GOL via set clear solution for Life Counter by hanpari - python coding challenges

Enable Javascript in your browser and then refresh this page, for a much enhanced experience.

GOL via set solution in Clear category for Life Counter by hanpari

# Check description of steps below the code :)
AROUND = ((-1, -1), (-1, 0), (-1, 1),(0, -1),
          (0, 1), (1, -1), (1, 0), (1, 1))
CELLS = AROUND + ((0,0),)

def life_counter(seed, ticks):
    life = {(x,y) for x in range(len(seed[0])) for
            y in range(len(seed)) if seed[y][x] == 1}
    locate = lambda pos1, pos2:(pos1[0]+pos2[0],
                                  pos1[1]+pos2[1])
    for __ in range(ticks):
        new_life = set()
        for living in life:
            for pos in (locate(living, cell) for
                        cell in CELLS):
                count = sum((locate(pos, cell) in life) for
                            cell in AROUND)
                if count == 2:
                    if pos in life: new_life.add(pos)
                elif count == 3:
                    new_life.add(pos)
                else:
                    pass
        life = new_life         
    return len(life)

"""
STEPS DESCRIPTION
1. Convert data to set of positions of living cells
2. Evaluating every living cell + all its neighbours (9 cells together)
3. All 9 cells (CELLS) are checked for count of surrounding living cells(AROUND).
4. Based of evaluation, still living or newly born cells are added to new set.
5. New set is switched for the old one.
6. Next iterations starts at point 2
7. Desired number is returned as length of set life.

AROUND - surrounding of cell
CELLS - The same as AROUND including cell itself
locate - helper function to calculate desired position

"""
    







if __name__ == '__main__':
    #These "asserts" using only for self-checking and not necessary for auto-testing
    assert life_counter(((0, 1, 0, 0, 0, 0, 0),
                         (0, 0, 1, 0, 0, 0, 0),
                         (1, 1, 1, 0, 0, 0, 0),
                         (0, 0, 0, 0, 0, 1, 1),
                         (0, 0, 0, 0, 0, 1, 1),
                         (0, 0, 0, 0, 0, 0, 0),
                         (1, 1, 1, 0, 0, 0, 0)), 4) == 15, "Example"
    assert life_counter(((0, 1, 0, 0, 0, 0, 0),
                         (0, 0, 1, 0, 0, 0, 0),
                         (1, 1, 1, 0, 0, 0, 0),
                         (0, 0, 0, 0, 0, 1, 1),
                         (0, 0, 0, 0, 0, 1, 1),
                         (0, 0, 0, 0, 0, 0, 0),
                         (1, 1, 1, 0, 0, 0, 0)), 15) == 14, "Little later"
    assert life_counter(((0, 1, 0),
                         (0, 0, 1),
                         (1, 1, 1)), 50) == 5, "Glider"
    assert life_counter(((1, 1, 0, 1, 1),
                         (1, 1, 0, 1, 1),
                         (0, 0, 0, 0, 0),
                         (1, 1, 0, 1, 1),
                         (1, 1, 0, 1, 1)), 100) == 16, "Stones"

Nov. 6, 2014

Comments:

bukebuer on Nov. 7, 2014, 8:23 a.m.
Based on your solution, if (0,0) is a living cell, then (-1,-1) is its neighbor and will be checked for evaluation. It seems not to raise any error, but won't it lead to some wrong answer?

hanpari on Nov. 7, 2014, 11:32 a.m.
Negative coordinates as (-1,-1) are perfectly valid because the grid is infinite. In set life are only living cells and set new_life contains new living cells for next tick. Remember, life can grow every directions. Thats why, my very first step was to get rid of tuple of tuples which is pretty inconvenient for working with. In my first solution I tried to use dict type with 0 and 1. After I run off the memory I realized it is useless to store zero values because they are not necessary. I only evaluate 3x3 area around living cell. And living cell is every coordinate tuple in the set. This means I have onl few values in every tick and I he life can continue ad infinitum (at least in theory). And I dont need dict as well because i know the living cell is only of value 1. Using dict (or set) is based on Guido comments on checkio. In that comment he wonders why are all inputs given in list of list or tuple of tuples. I believe he was right because with the dictionaries are easier to work with. For example in searching patterns task, data[-2][1] wont give you any exception because it is valid negative index. But in dict you receive for data[(-2,1)] IndexException which is for grid 10x10 without negative values much more reasonable. However, in this very case I dont need to care for negative values because they are OK for me. You can check more info here: <a href="http://www.checkio.org/mission/calculate-islands/publications/hanpari/python-3/readability-counts/share/f06121dd1339a4669d3d0e6e82a6264b/">http://www.checkio.org/mission/calculate-islands/publications/hanpari/python-3/readability-counts/share/f06121dd1339a4669d3d0e6e82a6264b/</a>

bukebuer on Nov. 7, 2014, 2:57 p.m.
After run in detail at local computer, I finally get your point. The line <pre class='brush: python'>count = sum((locate(pos, cell) in life) for cell in AROUND) </pre> is really excellent idea. My thought should be more flexible. Good job.

hanpari on Nov. 7, 2014, 6:50 p.m.
Thank you very much. I am using this quite often but it is used a lot across checkio. I have probably learnt it here from clever girls and guys :)

xtofl on Dec. 31, 2014, 12:42 p.m.
Quite a find, to represent the sparse matrix as a series of living-cell-coordinates. It matches the problem greatly! It reads like a fairy tale. Or a poem if you prefer. Am I mistaken if I say that the runtime complexity is quite big, however? Take a grid <pre class='brush: python'>xxx x.x xxx </pre> -> the center will be calculated 8 times. Wonder if this can be improved by e.g. keeping a cache of `done` positions.

hanpari on Dec. 31, 2014, 7:10 p.m.
Thank you. You are first one who noticed my fairy-tale algorithm explanation :) It is really nice from you. Gradually, sets became my favourite datatype :) I believe they are making code more readable and shorter when they replace many not necessary ifs. If I am not mistaken 8 times anything is still linear O(n) so it should be fine. As I mentioned in my previous comment this is pretty fast. When I used dict with 0 and 1 I run out dedicated memory and the time was for bigger number of ticks really horrible. This one was evaluated immediately. PS: Happy New Year 2015.

l2032 on Jan. 14, 2015, 9:28 p.m.
excellent solution, I ran into much the same problems as you (I tried creating a 'worst case scenario' grid), and came to a similar solution after reading the comments; store only the live cells. I did approach the problem slightly different though; looping over cells alive in the last iteration I add neighbouring dead cells to a list of possible new life, then loop over that list. In xtofl's example that means the middle cell is only evaluated once, however I do have to check 8 times if it already occurs in the 'possible' or 'alive in last iteration' set. I wonder what is quicker in the end. On a side note, I actually use a list instead of a set, is a set much quicker?

xtofl on Jan. 15, 2015, 6:47 a.m.
As a reply to your side note: a `list` may contain a cell more than once. So either your algorithm 'makes sure' there are no doubles, or it does extra work. On the other hand, the `set` insertion is more expensive since it has to check for doubles itself. But the problem is really expressed as a `set` of living cells, so that's the more natural choice. And apparently this runs fast enough :)

hanpari on Jan. 15, 2015, 3:13 p.m.
I am using sets because "something in set" is O(1) though "something in list" is O(n) where n is length of list. Not to speak about great operators available for sets | & - ^. Try them by yourself :) They are great!

hanpari on Jan. 15, 2015, 4:46 p.m.
This is few examples why is find sets or frozensets so useful :) <pre class='brush: python'>>>> first = {1,2,3,4,5,6} >>> second = {5,6,7,8,9} >>> third = {1,2,3} >>> third <= first True >>> third == first False >>> first & second {5, 6} >>> first | second {1, 2, 3, 4, 5, 6, 7, 8, 9} >>> first ^ second {1, 2, 3, 4, 7, 8, 9} >>> third |= second >>> third {1, 2, 3, 5, 6, 7, 8, 9} >>> third - first {8, 9, 7} >>> third.add(1) >>> third.add(1) >>> third.add(1) >>> third {1, 2, 3, 5, 6, 7, 8, 9} // using list is not so fun and safe >>> second = [] >>> second.append(1) >>> second.append(1) >>> if 1 in second: second.append(1) >>>Second [1,1,1] </pre>

The Game is Worth it!

0 %

You ClassRoom Demo is Ready With the new tool CheckiO ClassRoom, you will be able to analyze your students' progress, have your own leaderboard, change missions order on the map, and so on.