1. deque()

deque虽然使用时很像list，但是两者截然不同。deque是一个doubly linked list而list是一个array，所以处理两端数据的时候deque的复杂度是O(1)，而list是O(n)。但deque处理中部数据的效率低，是O(n)。因此，当处理随机状态时，使用list更好。

from collections import deque
D = deque()
D.append(5)
print(D)
print(D.popleft())
print(D)

D.append(6)
print(D[0])
print(D)
>>>
deque([5])
5
deque([])
6
deque([6])

2. Card Shuffling Simulator

洗牌的流程是先将一副牌分成尽量均匀的A和B两部分，之后选择A或者B的第一张作为洗牌之后的第一张，然后A和B各自的顺序保持不变，但是彼此交叉在一起形成新顺序。A和B未洗的牌越多，就越容易被优先选中。

2.1 将牌分成两部分

为了保证尽量均匀，每张牌用掷筛子的方式（randint(0, 1)）选择分到哪一部分。

from random import randint

nb_of_heads = 0
for _ in range(52):
#总共52张牌，没有大小王
    outcome = randint(0, 1)
    if outcome == 1:
        nb_of_heads += 1

print(nb_of_heads)

简化后的写法

from random import randint

sum(randint(0, 1) for _ in range(52))

2.2 洗牌

根据分成两个部分的牌数量将牌切成两部分，记录数量为i2（第二部分牌开始的index），第一部分牌开始的index为i1（初始值为0），洗后的牌index为i（初始值为0），剩余未洗卡牌数量为nb_of_cards_left（初始值为52）。
在洗牌过程中会出现一部分的牌全部洗完的状况，这时讲剩余部分的牌直接放入洗过的牌的后边。

deck = list(range(52))
cut = sum(randint(0, 1) for _ in range(52))

new_deck = [None] * 52
i1 = 0
i2 = cut 
i = 0
nb_of_cards_left = 52

while i1 < cut and i2 < 52:
    if randint(0, nb_of_cards_left - 1) < cut - i1:
    #rand(0, nb_of_cards_left - 1) 能够根据两部分剩余厚度等概率选择下一张洗的牌
        new_deck[i] = deck[i1]
        i1 += 1
    else:
        new_deck[i] = deck[i2]
        i2 += 1
    i += 1
    nb_of_cards_left -= 1
    
if i1 == cut:
    new_deck[i: ] = deck[i2: ]
else:
    new_deck[i: ] = deck[i1: cut]
print(new_deck)

3. Identity

首先明确概念，计算机程序中的各种数字并不是真正的值。比如3，3.14，这些数实际上由两部分构成：一部分是name--"3", "3,14"，另一部分是storage，存储的binary bits。这两个部分分别叫做v-name和v-storage，计算机中并不存在值这个概念，它是一个抽象概念，大体可以理解为v-name指向v-storage。
v-name可以出现多次，比如可以有N个"2"作为v-name，2 + 2中，v-name2出现了两次。在v-name中有两种形式，constant expressions和variable expressions。
constant expression：例如2和1+1。如下面程序所示，2和1+1都指向相同的binary bits。所以，1+1的过程实际上是先做运算1+1，根据值2的v-storage再分配一个v-name。等号实际上是把v-name指向了v-storage，所以下面程序x=2的时候是把2所在的v-storage再加上一个新的v-name x。

>>> id(2)
4297636928
>>> id(1 + 1)
4297636928
>>> x = 2
>>> id(x)
4297636928

对于基础类型，都和上述的int类型一致，例如下面列举的bool类型和str类型。

>>> id(False)
4297244992
>>> a = False
>>> id(a)
4297244992
>>> b = False
>>> id(b)
4297244992

>>> id('abc')
4314648336
>>> a = 'abc'
>>> id(a)
4314648336
>>> b = 'abc'
>>> id(b)
4314648336

对于非基础类型，比如List, tuple, set, dictionary，要根据实际情况分析。比如由于list可修改，所以他的分配都是动态的，x = [2]和y = [2]两者的存储位置不同；而tuple是不可修改的，所以他的分配是静态的，x = (2)和y = (2)两者的存储位置相同；set和dictionary是经过hash的，所以不仅x = {2}和y = {2}不同，他们也都和{2}不同。

>>> id([2])
4316726600
>>> x = [2]
>>> id(x)
4316726600
>>> y = [2]
>>> id(y)
4316726664

>>> id((2))
4297636928
>>> x = (2)
>>> id(x)
4297636928
>>> y = (2)
>>> id(y)
4297636928

>>> id({2})
4316700456
>>> x = {2}
>>> id(x)
4316700232
>>> y = {2}
>>> id(y)
4316700456

is的判断是判别v-storage地址是否一样，而==的判别是判断v-storage的binary bits是否一样。
由于binary是8位的，2^8 =256，所以如果一个数大于256，v-storage的地址会变化，小于的时候不变化，这样用上文说的is判断就会出现下述情况

>>> x = 257
>>> x is 257
False
>>> x = 256
>>> x is 256
True

programming的时候如果遇到可修改的非基础类型数据，一定要小心generate的方式。如下：

>>> X = [0] * 3; X
[0, 0, 0]
>>> id(X), id(X[0]), id(X[1]), id(X[2])
(4521957128, 4481604640, 4481604640, 4481604640)
>>> X[0] = 1; X
[1, 0, 0]
>>> id(X), id(X[0]), id(X[1]), id(X[2])
(4521957128, 4481604672, 4481604640, 4481604640)

[0] * 3，由于0是基本数据类型，实际上产生3次0，地址改变，所以如果对其中任何一个进行修改，三者不会全部变化。

>>> X = [[0]] * 3; X
[[0], [0], [0]]
>>> id(X), id(X[0]), id(X[1]), id(X[2])
(4521981960, 4511587784, 4511587784, 4511587784)
>>> X[0][0] = 1; X
[[1], [1], [1]]
>>> id(X), id(X[0]), id(X[1]), id(X[2])
(4521981960, 4511587784, 4511587784, 4511587784)

[[0]] * 3，由于[0]是可修改的非基础数据类型，实际上并没有产生3次[0]，而是给了3个v-name而已，地址未变，所以如果对其中任何一个进行修改，三者全部变化。如果想要产生3个[0]，用下面的方法。

>>> X = [[0] for i in range(3)]; X
[[0], [0], [0]]
>>> id(X), id(X[0]), id(X[1]), id(X[2])
(4521980424, 4521980104, 4521981832, 4521980680)
>>> X[0][0] = 1; X
[[1], [0], [0]]
>>> id(X), id(X[0]), id(X[1]), id(X[2])
(4521980424, 4521980104, 4521981832, 4521980680)

4. Game of Life

游戏规则：A cell comes into existence at an empty spot when that spot is surrounded by exactly 3 cells. A cell survives if and only if it is surrounded by exactly 2 or 3 cells.

4.1 显示数据

0代表死，1代表生，有以下两种方法显示数据。

Method 1:
def print_grid():
    for i in range(20):
        for j in range(20):
            print(grid[i][j], end = ' ')
        print()

grid = [[0] * 20] * 20

Method 2:
def print_grid():
    for i in range(20):
        print(' '.join(str(e) for e in grid[i]))

grid = [[0] * 20] * 20

注意，这里生成grid用到grid = [[0] * 20] * 20是没有问题的，因为[0]中的0是基础数据类型int。如果改成grid = [[[0]] * 20] * 20则会出问题，因为[[0]]中的[0]是非基础数据类型list且可修改。如果grid = [[(0)] * 20] * 20则不会出问题，因为[(0)]]中的(0)是非基础数据类型tuple，但不可修改。

4.2 生成生死规则

注意全局变量使用和bondary的巧妙处理方式（在原数据外层加一圈符合规则的数据）

from random import randrange

dim = 20

def print_grid():
    for i in range(1, dim + 1):
        print(' '.join(str(e) for e in grid[i]))

def initialise_grid():
    for i in range(1, dim + 1):
        for j in range(1, dim + 1):
            if not randrange(0, density):
                grid[i][j] = 1

def update_grid():
    global grid
    #因为最后grid =，赋值了，grid是local；如果只是改变grid的值，那么不用global
    for i in range(1, dim + 1):
        for j in range(1, dim + 1):
            nb_of_neighbours = sum((grid[i - 1][j - 1], grid[i - 1][j], grid[i - 1][j + 1],
                                  grid[i][j - 1], grid[i][j + 1],
                                  grid[i + 1][j - 1], grid[i + 1][j], grid[i + 1][j + 1]))
            if grid[i][j] and nb_of_neighbours in {2, 3} or\
                    not grid[i][j] and nb_of_neighbours == 3:
                new_grid[i][j] = 1
    grid = new_grid
    
density = 2
grid = [[0] * (dim + 2) for _ in range(dim + 2)]
initialise_grid()
print_grid()
print()

update_grid()
print_grid()
new_grid = [[0] * (dim + 2) for _ in range(dim + 2)]
#周围加一圈0，方便check周围多少neighbor是1