Principle of Computting(Python)学習ノート(5)BFS Searching+Zombie Aporaypes

1 Generators 
Generatorとlist coprehensionは似ています.
Generators are a kind of iterator that are defined like functions. 
http://www.codeskulptor.org/#examples_generators.py
https://wiki.python.org/moin/Generators
generanter functionの関数体にはyieldを書かなくてはいけません.returnを書いたり書いたりしません.
Generators function allow you to declare a function that behaves like an iterator,i.e.it can be used in a for loop.
Each time the next()は、method s isappinind to the rerererererererererestgenerator、the code is run until the nexxyieldexpression、and the ininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininststststststststststststststststststststststststststststststststststststststststrererererererererererenumber of elements.

# A list comprehension
print "max in list:", max([num * 2 - 3 for num in range(7)])

# A generator expression
print "max in gen:", max(num * 2 - 3 for num in range(7))

# A generator function
def genfunc(limit):
    num = 0
    while num < limit:
        yield num  #generator function   iteration    。yield        ，    ，        ，      ，       yield    。
        num = num + 1

print genfunc(7)
# Iteration using a generator function
print "Iterate over generator:"
for number in genfunc(7):
    print number

2 stack and queue
ロック http://www.codeskulptor.org/#user36_ZHLkI 0 d 7 kb_2.py
queue http://www.codeskulptor.org/#user35_AtoP 6 ttM 6 w_0.py
3 inherityance
http://www.codeskulptor.org/#examples_inheitance.py
http://www.codeskulptor.org/#examples_inheitance 2.py
4 grid collision
http://www.codeskulptor.org/#poc_physics_quadratic.py
https://class.coursera.org/principlescomputing-001/wiki/view?page=fun_growth
https://class.coursera.org/principlescomputing-001/wiki/view?page=grids

5 grid類の実現  http://www.codeskulptor.org/#poc_grid.py  その中の「def get_」に注意してください.indexの転化方法は、実際のscreen positionをindex 6 Conway'sに変換します. game of lifeシミュレーションgame of life概要 http://en.wikipedia.org/wiki/Conway‘s’.ゲームof_Life game of lifeでgrid操作の練習をします. http://www.codeskulptor.org/#poc_golstudent.py 7 BFS BFSアニメーション野火焼ききれない春风吹いてまた生みます.  http://www.codeskulptor.org/#poc_wildfire_student.pyhttp://www.codeskulptor.org/#poc_wildfire_gi.pyhttp://www.codeskulptor.org/#poc_grid.py BFSの原理 https://class.coursera.org/principlescomputing-001/wiki/view?page=bfs 8 gridの用途はbucket sortingを使ってstring sortingを行います.https://class.coursera.org/principlescomputing-001/wiki/view?page=strings http://www.codeskulptor.org/#poc_stringsort.py葃生26文字構成のlist list=[chr(ord)+char num]for char num in range(26)]print list 9 stack and queue先生が実現したqueue http://www.codeskulptor.org/#poc_queue.pyは自分で実現しました.stackhttp://www.codeskulptor.org/#user36_ZHLkI 0 d 7 kb_2.py 10 Zombie Aocalypehttp://www.codeskulptor.org/#poc_zombie_template.py 1) Passable cels in the grid coresond to EMPTY cels while Full cell are impassable 2) However、several hmans and zombies may inhabit the same grid cell. 
3)for each in list 1でlist 1の要素しか読み取れないので注意してください.list 1の要素は修正できません.修正するなら、下付き操作を使います.
4)zombieとhman移動の原理はこうです.まずzombieに対してdistanceを計算します.grid、このdistance.gridの各セルは現在のセルから一番近いzombieまでの距離を表します.シューマンの時は、シューマンの周りのエクセルの中から、distanceを一つ選びます.gridの対応値が一番大きいセルは、hmanが一番安全な点に移動します.
同様に、hmanに対してdistanceを計算します.grid、の各セルは現在のセルから一番近いhumanまでの距離を表します.zombieの時は、zombieの周りのcellからdistanceを一つ選びます.gridの対応値が一番小さいセルは、hmanがhmanに一番近いところに移動します.
5)テーマを多く簡略化しました.
例えばdistanceを計算します.gridの場合、zombieでもhmanでも、現在のセルの隣のセルは4つで、8つではないと仮定します.
zombieがhmanに追いついた時、gridだけが色を変えました.もし次のステップがhman moveを続けるなら、hmanはまだ生きています.

for idx in range(len(list1)): 
    list1[idx] += 1 

私の宿題

"""
Student portion of Zombie Apocalypse mini-project
"""

import random
import poc_grid
import poc_queue
import poc_zombie_gui

# global constants
EMPTY = 0 
FULL = 1
FOUR_WAY = 0
EIGHT_WAY = 1
OBSTACLE = "obstacle"
HUMAN = "human"
ZOMBIE = "zombie"


class Zombie(poc_grid.Grid):
    """
    Class for simulating zombie pursuit of human on grid with
    obstacles
    """

    def __init__(self, grid_height, grid_width, obstacle_list = None, 
                 zombie_list = None, human_list = None):
        """
        Create a simulation of given size with given obstacles,
        humans, and zombies
        """
        poc_grid.Grid.__init__(self, grid_height, grid_width)
        if obstacle_list != None:
            for cell in obstacle_list:
                self.set_full(cell[0], cell[1])
        if zombie_list != None:
            self._zombie_list = list(zombie_list)
        else:
            self._zombie_list = []
        if human_list != None:
            self._human_list = list(human_list)  
        else:
            self._human_list = []
        
    def clear(self):
        """
        Set cells in obstacle grid to be empty
        Reset zombie and human lists to be empty
        """
        poc_grid.Grid.clear(self)
        self._zombie_list = []
        self._human_list = []
        
    def add_zombie(self, row, col):
        """
        Add zombie to the zombie list
        """
        self._zombie_list.append((row,col))
                
    def num_zombies(self):
        """
        Return number of zombies
        """
        return len(self._zombie_list)
          
    def zombies(self):
        """
        Generator that yields the zombies in the order they were
        added.
        """
        num = 0
        while num < self.num_zombies():
            yield self._zombie_list[num]
            num += 1 
        return

    def add_human(self, row, col):
        """
        Add human to the human list
        """
        self._human_list.append((row,col))
        
    def num_humans(self):
        """
        Return number of humans
        """
        return len(self._human_list)
    
    def humans(self):
        """
        Generator that yields the humans in the order they were added.
        """
        num = 0
        while num<self.num_humans():
            yield self._human_list[num]
            num += 1
        return
        
    def compute_distance_field(self, entity_type):
        """
        Function computes a 2D distance field
        Distance at member of entity_queue is zero
        Shortest paths avoid obstacles and use distance_type distances
        """
        visited = poc_grid.Grid(self._grid_height, self._grid_width)
        distance_field = [[ self._grid_width * self._grid_height for dummy_col in range(self._grid_width)]
                       for dummy_row in range(self._grid_height)]
        if entity_type == HUMAN:  
            boundary = poc_queue.Queue()              
            for each in self._human_list:
                visited.set_full(each[0],each[1])
                distance_field[each[0]][each[1]] = 0
                boundary.enqueue(each)
            while len(boundary)>0:
                cur_cell = boundary.dequeue()
                four_neighbors = poc_grid.Grid.four_neighbors(self,cur_cell[0],cur_cell[1])
                for each_neighbor in four_neighbors:
                    if  visited.is_empty(each_neighbor[0],each_neighbor[1]) and poc_grid.Grid.is_empty(self, each_neighbor[0], each_neighbor[1]) :
                        visited.set_full(each_neighbor[0],each_neighbor[1])
                        if distance_field[cur_cell[0]][cur_cell[1]]+1 < distance_field[each_neighbor[0]][ each_neighbor[1]]:
                            distance_field[each_neighbor[0]][ each_neighbor[1]] = distance_field[cur_cell[0]][cur_cell[1]]+1
                        boundary.enqueue(each_neighbor)                
        elif  entity_type == ZOMBIE:
            boundary = poc_queue.Queue()                          
            for each in self._zombie_list:
                visited.set_full(each[0],each[1])
                distance_field[each[0]][each[1]] = 0
                boundary.enqueue(each)
            while len(boundary)>0:               
                cur_cell = boundary.dequeue()
                four_neighbors = poc_grid.Grid.four_neighbors(self,cur_cell[0],cur_cell[1])                
                for each_neighbor in four_neighbors:
                    if  visited.is_empty(each_neighbor[0],each_neighbor[1]) and poc_grid.Grid.is_empty(self, each_neighbor[0], each_neighbor[1]):
                        visited.set_full(each_neighbor[0],each_neighbor[1])                        
                        if distance_field[cur_cell[0]][cur_cell[1]]+1 < distance_field[each_neighbor[0]][ each_neighbor[1]]:
                            distance_field[each_neighbor[0]][ each_neighbor[1]] = distance_field[cur_cell[0]][cur_cell[1]]+1
                        boundary.enqueue(each_neighbor)                
        return   distance_field          
                    
    def move_humans(self, zombie_distance):
        """
        Function that moves humans away from zombies, diagonal moves
        are allowed
        """
        for idx in range(len(self._human_list)):
            eight_neighbor_human = poc_grid.Grid.eight_neighbors(self, self._human_list[idx][0],self._human_list[idx][1])    
            max_distance = zombie_distance[self._human_list[idx][0]][self._human_list[idx][1]]
            max_pos =(self._human_list[idx][0],self._human_list[idx][1]) 
            for eight_neighbor in eight_neighbor_human:
                if zombie_distance[eight_neighbor[0]][eight_neighbor[1]]> max_distance:
                    max_distance = zombie_distance[eight_neighbor[0]][eight_neighbor[1]]
                    max_pos =(eight_neighbor[0],eight_neighbor[1])
            self._human_list[idx]=(max_pos[0],max_pos[1])
    
    def move_zombies(self, human_distance):
        """
        Function that moves zombies towards humans, no diagonal moves
        are allowed
        """
        for idx in range(len(self._zombie_list)):
            four_neighbor_zombie = poc_grid.Grid.four_neighbors(self, self._zombie_list[idx][0],self._zombie_list[idx][1])    
            min_distance = human_distance[self._zombie_list[idx][0]][self._zombie_list[idx][1]]
            min_pos =(self._zombie_list[idx][0],self._zombie_list[idx][1]) 
            for four_neighbor in four_neighbor_zombie:
                if human_distance[four_neighbor[0]][four_neighbor[1]]< min_distance:
                    min_distance = human_distance[four_neighbor[0]][four_neighbor[1]]
                    min_pos =(four_neighbor[0],four_neighbor[1])
            self._zombie_list[idx]=(min_pos[0],min_pos[1])

# Start up gui for simulation - You will need to write some code above
# before this will work without errors
#test_zombie =  Zombie(3, 3, [], [], [(2, 2)])
#print test_zombie.compute_distance_field('human')
poc_zombie_gui.run_gui(Zombie(20, 15))