Coding: Fleeting Thoughts

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

User avatar
My HERO!!!
Posts: 5258
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex

Re: Coding: Fleeting Thoughts

Postby Xanthir » Thu Feb 15, 2018 1:05 am UTC

Yeah, a dict just connects keys to values. Values can be anything, keys are anything "hashable" (strings, numbers, tuples of those, and some other things).

An array is basically just a dict that only accept integer keys, and only in a certain range - it just connects the numbers 0, 1, 2, etc to values.

You just use different syntax to define/refer to them. Previous posts already went into detail about what sort of dict you'd want to use - probably with keys that are 3-tuples for the coordinates, like `{(0,0,0): 0, (0,0,1): 0, ...}`; I won't repeat the previous posts here. To get/set them you can still use the `a[foo]` syntax, but it'll look like `a[0,0,1] = 2` (set the key (0,0,1) to the value 2), instead of your current drilling down into a multidimensional array like `a[0][0][1] = 2` (look up the value at index 0, then the value at index 0 of the subarray, then the value at index 1 of the sub-subarray, and set it to 2).
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Yes Man
Posts: 1983
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Coding: Fleeting Thoughts

Postby Flumble » Thu Feb 15, 2018 2:45 am UTC

Assuming that cells are either alive or dead, I'd go with sets. Sets are simple things that hold a bunch of items. For example, a set in which each item is the coordinate of a live cell. So the question "is the cell at (x,y,z) alive or dead?" becomes "does the coordinate (x,y,z) exist in the set of alive cells or not?". And birthing/killing cells becomes a matter of adding/deleting coordinates to/from the set.

The example below also adds some functional programming to the mix leading to only a few (>5) lines of code:

Code: Select all

# in haskell typology: getNeighbours :: Coordinate -> Set Coordinate
def getNeighbours(coordinate):
    (x,y,z) = coordinate # python 3 doesn't allow deconstructing a tuple in the parameter definition, so it needs its own line
    return frozenset({(x+dx,y+dy,z+dz) for dx in [-1,0,1] for dy in [-1,0,1] for dz in [-1,0,1] if not dx == dy == dz == 0}) # butifel
    # also, if you want a wrapping field or dead boundaries or whatever, this is the place to go

# in haskell typology: evolveState :: Set Coordinate -> Set Coordinate
def evolveState(oldAlive):
    newAlive = set() # starting with a blank slate (practice may show that copying the old state and adding/deleting some elements performs better)
    activeCells = oldAlive.union(*map(getNeighbours, oldAlive)) # such ugly notation to take the union of a couple of sets (also simply assuming that all live cells and their neighbours may change; this may be optimized)

    for cell in activeCells:
        aliveNeighbours = sum(1 for neighbour in getNeighbours(cell) if neighbour in oldAlive)
        if aliveNeighbours == 5 or (cell in oldAlive and 1 < aliveNeighbours < 8): # copied a rule from the blogosphere
            newAlive.add(cell) # I would've gone for `newAlive = newAlive.union({cell})` if it weren't both less readable and significantly slower because python won't realize that it can reuse the set instead of making a modified copy

    return frozenset(newAlive) # just pretend it was a frozen set all along

def __main__():
    alive = someInitialLiveCells # like `frozenset({(-1, 0, 0), (0, -1, 0), (0, 0, 0), (0, 1, 0), (1, -1, 0), (1, 1, 0)})`

    for generation in range(1, 1001):
        alive = evolveState(alive)
        somehowShowThisState(generation, alive) # like... I dunno, I avoid graphics libraries, and 3D data doesn't translate to text output nicely

It becomes more readable if you remove the comments, except for the oldAlive.union(*map(getNeighbours, oldAlive)), which is alive ∪ { N | N ∈ getNeighbours(A), A ∈ alive } or "grab all the alive cells and all their surrounding cells".
I have no idea about the performance of this thing, though I expect something of an O(n²) time per iteration because of the way the active cells are decided.

Return to “Coding”

Who is online

Users browsing this forum: No registered users and 6 guests