On Mon, 3 Jan 2005, Brian van den Broek wrote:
Seconded. (Thanks for offering, Danny.)(Aside: one nonobvious example where copying can be avoided is in Conway's Game of Life: when we calculate what cells live and die in the next generation, we can actually use the 'Command' design pattern to avoid making a temporary copy of the world. We can talk about this in more detail if anyone is interested.)
[Long post up ahead.]
Just as a warning, none of what I'm going to code here is original at all: I'm rehashing a main idea off of a paper called "Using the Game of Life to Introduce Freshman Students to the Power and Elegance of Design Patterns":
http://portal.acm.org/citation.cfm?id=1035292.1028706
Hi Danny and all,
Thanks for doing this, Danny. (And sorry to have taken a bit to get to it.)
<tangents>
As an aside, Daniel Dennett, a philosopher who seems popular amongst the hacker-types, wrote some about Life some time in the 80's, I believe in the first instance in a paper called "Real Patterns". One of the neat things he toys with there is the (needless to say, abstract) possibility of instantiating a Turing-Complete computer out of the Life cells.
Similarly, Wolfram's recent tome _A New Kind of Science_, from reviews and the skimming I've done, seems largely devoted to the idea that such cellular automata are a rich and untapped source of insight and scientific modelling. Wolfram's book is on my list, but, sadly, 1000'ish page books have a tendency to remain on that list ;-)
</tangents>
OK, Danny, I get that you were quickly (and kindly) adapting an approach from somewhere else. So, this is all by way of query rather than criticism.
I am having a hard time figuring out how to efficiently snip and comment, so please bear with any organizational issues. I think I will just preserve the parts relevant to what I want to talk/ask about and write at the end.
Ok, let's start hacking. The Game of Life involves a 2-D matrix of cells, where any cell can be 'LIVE' or 'DEAD'.
### LIVE, DEAD = '*', '.' ###
<SNIP>
<SNIP>def make_random_world(M, N): """Constructs a new random game world of size MxN.""" world = {} for j in range(N): for i in range(M): world[i, j] = random.choice([LIVE, DEAD]) world['dimensions'] = (M, N) return world
def print_world(world): """Prints out a string representation of a world.""" M, N = world['dimensions'] for j in range(N): for i in range(M): print world[i, j], print ###
(If I had more space, I'd rather do this as a real data structure instead of hacking up a dictionary.)
<SNIP>
So now we have something that shows a single generation of a game world. How does the world run? Well, between each generation, each cell can either live or die according to the rule:
A dead cell with exactly 3 live neighbors becomes alive (or is "born").
A live cell with 2 or 3 live neighbors stays alive; otherwise it dies (from "loneliness").
### def get_state(world, i, j): """Returns the state of the cell at position (i, j). If we're out of bounds, just returns DEAD to make calculations easier.""" return world.get((i, j), DEAD)
def count_live_neighbors(world, i, j): """Returns the number of live neighbors to this one.""" live_count = 0 for i_delta in [-1, 0, 1]: for j_delta in [-1, 0, 1]: if (i_delta, j_delta) == (0, 0): continue if get_state(world, i+i_delta, j+j_delta) == LIVE: live_count += 1 return live_count
def is_born(world, i, j): """Returns True if the cell at (i, j) is currently dead, but will be born in the next generation.""" return (get_state(world, i, j) == DEAD and count_live_neighbors(world, i ,j) == 3)
def is_deceased(world, i, j): """Returns True if the cell at (i, j) is currently alive, but will die in the next generation.""" return (get_state(world, i, j) == LIVE and not (2 <= count_live_neighbors(world, i ,j) <= 3)) ###
<SNIP>
Now the problem is: given the current state of the world, how do we calculate the next state of the world? One way is to make a temporary copy of the world, and apply changes to it, consulting the original world for the rules:
<SNIP'ed a version that involved making a copy of the world>
<SNIP>The unsatisfying thing, though, is that we use an explicit copying step and the temporary scratch space. But we can actually get away from making temporary scratch space by using this cute idea: instead of directly applying status changes immediately, we store a list of "Commands" that we can execute after we figure out who lives and who dies:
### def make_rise_command(world, i, j): """Produces a callable function that, when called, will apply a change to the world to make the cell at (i, j) live.""" def cmd(): world[i, j] = LIVE return cmd
def make_die_command(world, i, j): """Produces a callable function that, when called, will apply a change to the world to make the cell at (i, j) die.""" def cmd(): world[i, j] = DEAD return cmd ###
<SNIP>Notice that the change to our world does not take place until we execute the some_cmd command. This is, conceptually, an example of a "Command": it's a callable that applies a state change when we finally call it. Stripped of all the OOP/Class baggage, that's pretty much all it is.
Punchline time!
### def apply_next_generation_revised(world): """Destructively mutate the world so it reflect the next generation.""" M, N = world['dimensions'] commands = [] for j in range(N): for i in range(M): if is_born(world, i, j): commands.append(make_rise_command(world, i, j)) if is_deceased(world, i, j): commands.append(make_die_command(world, i, j)) for cmd in commands: cmd() ###
I know I rushed the heck out of this program. *grin* If you have any questions on it, please feel free to ask. Talk to you later!
OK, I've read you and Kent discussing whether the design pattern is really appropriate here. I'm pretty sure my queries are independent, but then I'm the tutee, so grain of salt, and all that. Anyway:
To summarize what you code does:
1) Define world dict by filling an M by N matrix with representations of live cells and dead cells, and using the (M,N) tuples as dict keys for the representations, together with 'dimensions' as a key for (M,N).
2) Defines a print function which prints each cell's contents.
3) Defines a "count a cell's neighbours" function.
4) Defines a function for determining if a live cell is doomed.
5) Defines a function for determining if a dead cell will flourish.
6) Runs through the matrix, storing a list of alterations to apply, and then applies them en mass once the entire matrix is scanned (thereby obviating the need for a scratch copy of the matrix).
I gave some thought (though produced no code) to the question of how to do a life game before you posted your code. My naive approach differs a bit, and it seems to me better. I'd like to know why I am wrong ;-)
So, relying on your code unless differences specified (and, like you, not making it OOP, so having more passing of the world than I'd like, but I'm only just now groking the OOP way), I would have done something like the following. (Please be tolerant of any syntactic slips; I think and hope my aim is clear, if not the execution.):
1) Define world by filling an M by N matrix with True and False. Otherwise, as your step (1).
2) Define a print function which goes through the matrix, printing one thing for each True cell and another for each False cell.
3) Define the count_live_neighbours() roughly as you did. (The actual code below assumes your count function, modulo the change to it that you define a LIVE name and I am just using True.)
4) Define a "will be changed function" roughly as the untested code:
def cell_will_change(cell):
'''Returns True if a cell will change, False otherwise. (I'd actually structure it with a single exit point, but that
doesn't seem a popular way to go here ;-)
'''
i, j = cell
if world[cell] and not (2 <=
count_live_neighbors(world, i ,j) <= 3)):
return True
if not world[cell] and count_live_neighbors(world, i ,j) == 3):
return True
return False5) Define a get_changed_cells_list function (again, untested):
def get_changed_cells_list(world):
'''Returns a list of cells that will change in the next generation.''' changed_cells_list = []
for c in world:
if c = 'dimensions':
continue
if cell_will_change(c):
changed_cells_list.append(c)
return changed_cells_list6) Define update_world function (again, untested):
def update_world(world):
'''Produces the next generation world.''' changed_cells_list = get_changed_cells_list(world)
for c in changed_cells_list:
if c = 'dimensions':
continue
world[c] = not world[c]
return worldFinally,
def create_and_print_new_generation(world):
world = update_world(world)
print_world(world)
return worldI hope the fragmentary nature of this makes my intent clear.
Anyway, as I see it, this has the following advantages over your posted code:
1) Cell representations done with built-ins seems likely to be quicker. (A minor point, though.)
2) Use of booleans for cell contents makes the change cell procedure simply saying not
.> cell_contents # as in for loop of my update_world().
3) Neither a copy of the world nor the design pattern is needed. Instead, I make a list of the cells to be changed. In the limit, where ever cell will change, this is no better than a copy of the world, but i) it often is better, and ii) I'm not sure the Life rules can create a world where every cell will change in the next generation, anyway.
I don't see any disadvantages, but then I don't see too well ;-)
Again, I get that your code was quick, adapting another source, and designed to showcase a pattern. But, all that aside, am I wrong in thinking that my approach has the listed advantages over your posted code? Any problems with it I am not seeing?
Oh, also, when you said:
> (If I had more space, I'd rather do this as a real data structure > instead of hacking up a dictionary.)
did you mean make the world a class (and thus avoid the sort of passing the world dict up and down as I did here?) Either way, a quick word or two will be great; I'm not asking for you to take the time to code it up for me :-)
Thanks for taking the time. Best to all,
Brian vdB
_______________________________________________ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
