This is an implementation of a simple version of the 2D Schelling model. We solve it as follows:
Then, we evolve this model using the following rules:
We evolve the board forward by randomly selecting a single unhappy polygon and moving it to an empty cell. We continue doing so until every polygon is either meh or happy. We keep track of how your segregation index evolves with each step, as well as the fraction of polygons that are meh and happy. Finally, we plot both the board and (separately), the evolution of the segregation, meh fraction, and happy fraction over time.
In [ ]:
%matplotlib inline
import matplotlib.pyplot as plt
import numpy as np
import random
import time
# USER PARAMETERS
square_frac = 1./3. # fraction of cells that are squares
triangle_frac = 1./3. # fraction of cells that are triangles
happy_min_frac = 1./3. # unhappy if less than this fraction
happy_max_frac = 1.0 # unhappy if more than this fraction
board_size = 20 # size of board (NxN). Board assumed to be a square.
random_seed = 8675309 # random seed for the simulation
In [ ]:
# put your code here. Add additional cells as necessary!
def generate_board(tri_frac=1./3., square_frac=1./3., board_size=20, random_seed=8675309):
'''
Generates a game board. Optionally takes in a fraction of cells that are triangles,
fraction that are squares, a board size (board assumed to be square), and a random seed.
Returns a games board.
Note: in the returned game board, empty spaces have a value of zero, triangles are 1,
and squares are 2.
'''
random.seed(random_seed)
# create a board that's entirely empty.
game_board = np.zeros([board_size,board_size],dtype='int64')
# loop over game board and fill it in.
for i in range(game_board.shape[0]):
for j in range(game_board.shape[1]):
val = random.uniform(0.0,1.0)
if val <= square_frac:
game_board[i,j] = 2
elif val > square_frac and val <= tri_frac+square_frac:
game_board[i,j] = 1
else:
game_board[i,j] = 0 # empty is zero
return game_board
In [ ]:
def is_happy_or_meh(game_board, happy_min_frac, happy_max_frac):
'''
This function takes in the game board and the bounds for happiness (i.e., at least
a fraction happy_min_frac of your neighbors must be like you, and at most happy_max_frac
must be like you in order for you to be happy.) The happy_max_frac is not necessary for the
baseline version of the game, but I put it in b/c it's necessary for the later versions.
The function returns 'True' if the cell is either (1) happy, (2) meh, or (3) empty - in other words,
the only cells marked 'False' are truly unhappy.
'''
# create an empty array
happy_board = np.zeros_like(game_board)
# loop over board
for i in range(game_board.shape[0]):
for j in range(game_board.shape[1]):
happy = False
# guess at bounds of neighborhood (this cell +/- in each direction)
xstart=i-1
xend=i+2
ystart=j-1
yend=j+2
# do some bounds-checking to ensure that we don't overrun the ends of the array
if xstart < 0:
xstart = 0
if xend > game_board.shape[0]:
xend = game_board.shape[0]
if ystart < 0:
ystart = 0
if yend > game_board.shape[1]:
yend = game_board.shape[1]
# calculate the number of neighbors (not counting me, hence the -1)
num_neighbors = game_board[xstart:xend,ystart:yend].size - 1
# how many of my neighbors are like me? (subtract 1 b/c I'm always like me)
like_me = (game_board[xstart:xend,ystart:yend]==game_board[i,j]).sum()-1
# how many of my neighbors are empty cells?
empty = (game_board[xstart:xend,ystart:yend]==0).sum()
frac_like_me = like_me/num_neighbors
frac_empty = empty/num_neighbors
# start off assuming each cell is 'happy', which really means empty, meh, or happy
# (in other words, assume that each cell is "not unhappy")
happy = True
# not happy if too many neighbors are like me (not important for baseline version)
if frac_like_me > happy_max_frac:
happy=False
# not happy if too many neighbors are *unlike* me
if frac_like_me < happy_min_frac:
happy=False
# assign values to the board
happy_board[i,j] = happy
return happy_board
In [ ]:
def find_unhappy(happy_board):
'''
Takes in the game board and finds a random unhappy cell, and returns the indices
of that unhappy cell.
'''
not_done=True
counter=0
# loop until we find an unhappy cell or until we iterate for too long
# In this case, "too long" is 10x the size of the board, and if we reach
# that we probably don't have any unhappy cells.
while not_done and counter < 10*happy_board.size:
# pick random x and y indices
i = random.randint(0,happy_board.shape[0]-1)
j = random.randint(0,happy_board.shape[0]-1)
# if this cell happens to be unhappy, return its indices (which means
# that we exit the function)
if happy_board[i,j]==False:
return i,j
counter+=1
# if we can't find any unhappy cells, return an invalid value.
print("can't find an unhappy cell!",counter)
return -1, -1
In [ ]:
def find_empty(game_board):
'''
Takes in the game board and finds a random empty cell, and returns the indices
of that empty cell.
'''
not_done=True
counter=0
# loop until we find an empty cell or until we iterate for too long
# In this case, "too long" is 10x the size of the board
while not_done and counter < 10*game_board.size:
# pick random x and y indices
i = random.randint(0,game_board.shape[0]-1)
j = random.randint(0,game_board.shape[0]-1)
# if this cell happens to be empty, return its indices (which means
# that we exit the function)
if game_board[i,j]==0:
return i,j
counter+=1
# if we can't find any empty cells, return an invalid value.
print("Can't find an empty cell!",counter)
return -1, -1
pass
In [ ]:
def move(game_board, unhappy_cell, empty_cell):
'''
Move an unhappy polygon to an empty cell.
Takes in the game board, the indices for the unhappy cell, and the
indices for the empty cell. We do not return anything because
python directly modifies the game_board array.
'''
val = game_board[unhappy_cell[0],unhappy_cell[1]]
game_board[unhappy_cell[0],unhappy_cell[1]] = 0
game_board[empty_cell[0],empty_cell[1]] = val
In [ ]:
def calc_segregation_metric(game_board):
'''
Calculates the segregation metric for the game board. Takes in
the game board, returns a fraction that corresponds to the fraction
of segregated polygons. (Note that "segregated" corresponds to polygons that
are surrounded entirely by some combination of polygons like them and empty
cells - polygons that are adjacent to unlike polygons are not segregated.)
'''
num_filled_cells = 0
num_segregated = 0
# loop over the entire game board
for i in range(game_board.shape[0]):
for j in range(game_board.shape[1]):
# only look at non-empty cells
if game_board[i,j] > 0:
num_filled_cells += 1
# calculate neighborhood
xstart=i-1
xend=i+2
ystart=j-1
yend=j+2
# check to make sure bounds are sensible
if xstart < 0:
xstart = 0
if xend > game_board.shape[0]:
xend = game_board.shape[0]
if ystart < 0:
ystart = 0
if yend > game_board.shape[1]:
yend = game_board.shape[1]
# calculate number of cells in this polygon's neighborhood
num_total = game_board[xstart:xend,ystart:yend].size
# how many adjacent cells are like me? (including me)
num_like_me = (game_board[xstart:xend,ystart:yend]==game_board[i,j]).sum()
# how many adjacent cells are empty?
num_zeros = (game_board[xstart:xend,ystart:yend]<1).sum()
#print("zeros,like me, total:", num_zeros,num_like_me,num_total,i,j)
#print(game_board[xstart:xend,ystart:yend])
#if (num_zeros+num_like_me) == num_total:
# print("SEGREGATED")
#print("\n\n")
# if all adjacent cells are either filled with polygons like me or
# empty cells, this cell is segregated
if (num_zeros+num_like_me) == num_total:
num_segregated += 1
# return the fraction of polygons that are 'segregated'
return num_segregated/num_filled_cells
In [ ]:
def plot_board(myarray):
'''
This function takes in a 2D array and uses pyplot to make a matplotlib
plot. It returns no value.
'''
# first create two vectors based on the x and y sizes of the grid
x_range = np.linspace(0, myarray.shape[0], myarray.shape[0])
y_range = np.linspace(0, myarray.shape[1], myarray.shape[1])
# use the numpy meshgrid function to create two matrices
# of the same size as myarray with x and y indexes
x_indexes, y_indexes = np.meshgrid(x_range, y_range)
# make a list of all the x and y indexes that are either squares or triangles.
# the notation below is relatively new to us; it means that when myarray==(value),
# only record those values.
sq_x = x_indexes[myarray == 1];
sq_y = y_indexes[myarray == 1];
tr_x = x_indexes[myarray == 2];
tr_y = y_indexes[myarray == 2];
# plot the squares and triangles. make the size of the polygons
# larger than the default so they're easy to see!
plt.plot(sq_x,sq_y, 'bs',markersize=10)
plt.plot(tr_x,tr_y, '^g',markersize=10)
#Set the x and y limits to include half a space overlap so we don't cut off the shapes
plt.ylim([-0.5,myarray.shape[1]+0.5])
plt.xlim([-0.5,myarray.shape[0]+0.5])
In [ ]:
# This cell runs the entire program, calling the functions defined above.
# generate game board
gb = generate_board(triangle_frac, square_frac, board_size)
# plot initial configuration
plot_board(gb)
step_counter = 0
# create empty lists to keep track of steps and segregation metric
segregation = []
step = []
# this is a timer so that I know how long the loop runs.
start_time = time.time()
max_steps = 10000
# move polygons until everybody's happy/meh or we reach max_steps
for i in range(max_steps):
# for this step, find out who is unhappy
happy_or_meh = is_happy_or_meh(gb,happy_min_frac,happy_max_frac)
# get the indices of an unhappy polygon
uhx,uhy = find_unhappy(happy_or_meh)
# break if there are no unhappy polygons
if uhx<0:
break
# get the indices of an empty cell
emptyx,emptyy = find_empty(gb)
# break if there are no empty cells (should never happy)
if emptyx<0:
break
# move unhappy polygon to empty cell
move(gb,[uhx,uhy],[emptyx,emptyy])
step_counter += 1
# keep track of segregation metric and number of steps
step.append(step_counter)
segregation.append(calc_segregation_metric(gb))
stop_time = time.time()
print("time elapsed:", stop_time-start_time,"seconds. Steps:", step_counter,
"time/step:", (stop_time-start_time)/step_counter,"seconds.")
In [ ]:
# plot the final state of the game board
plot_board(gb)
In [ ]:
# plot the evolution of the segregation metric
plt.plot(step,segregation)