Question 1: Obstacle Course Revisited:¶
On the first day, we did an obstacle course. Now that we've learned more... we can take it to the next level! No pun intended.
- Do not change the print statements
- Do not change or over-write the message function
- Do not have Errors
- Pass all the levels
Change the value of player before statement to pass the level
In [ ]:
def message(level_number, passed):
"""
Input: level_number (int, str), passed (bool) [True if the level is passed]
Output: (None)
"""
if passed:
print(f'Level {level_number} is passed :) yay!')
else:
print(f'Level {level_number} is... failed :( oh no!')
In [ ]:
# Make all the statements print True.
# Do not change or delete the message statements
# You can do anything else that you'd like
# For example, you can change the value of player in between each print statement
player = None
message(1, type(player) == int)
message(2, type(player) == str and int(player) % 5 == 2 and len(player) > 4)
message(3, player[ : 3] == player[2 : 5] and player[0] == 2 * player[1])
message(4, player[0][1:] == 'secret_passcode')
message(5, type(player[0]) == list and type(player[1]) == str and player[0][1] == player[1][1])
message(6, (player.append('yo!') is None) and player[-1] == player[0] and len(player) == 1)
message(7, (player[0]) and (not player[1]) and (player[2] != player[0] or player[1]))
message(8, len(str(int(player))) < len(player))
message(9, player[0][0] + player[1][1] + player[2][2] == 6 and (player[0][0] > player[1][1] > player[2][2]))
message(10, player == [int(x % 2 ** 5 * 125 / 6) for x in range(100)] * 7)
message('bonus', type(player[0]) == int and write_this(player) and player[0] == 'yay! jamcoders!')
Question 2: Maze:¶
Get from the start to the goal without going through spikes or obstacles.
You are in a maze. You can call:
move(maze, DIR_RIGHT)move(maze, DIR_DOWN)move(maze, DIR_LEFT)move(maze, DIR_UP)
The tiles are:
'P'is the player. This is your current position'#'are obstacles. If you run into one, you will not move.'!'is the goal. If you run into this, you will win'x'are spikes. If you run into this, you will lose' 'is empty. If you run into this, you will win
Write code to reach the goal, using the functions provided.
Helpers¶
Run the helpers. They are long, so ignore them.
In [2]:
% pip install termcolor
In [3]:
# Please run this. You should not read or understand this code.
# (unless you really want to, but it's not particularly well written)
# There are no objects or dictionaries in the code since we have not learned them yet
from IPython.display import clear_output
from time import sleep as wait
TILE_OBSTACLE = '#'
TILE_SPIKES = 'x'
TILE_GOAL = '!'
TILE_EMPTY = ' '
TILE_PLAYER = 'P'
STATE_ALIVE = 1
STATE_LOSE = 2
STATE_WIN = 3
DIR_UP = 1
DIR_DOWN = 2
DIR_LEFT = 3
DIR_RIGHT = 4
global_pos = None
global_state = None
def get_square(maze, pos):
return maze[pos[0]][pos[1]]
def set_square(maze, pos, tile):
maze[pos[0]][pos[1]] = tile
def set_current_state(maze):
global global_state
if global_state == STATE_ALIVE:
if get_square(maze, global_pos) == TILE_SPIKES:
global_state = STATE_LOSE
return
if get_square(maze, global_pos) == TILE_GOAL:
global_state = STATE_WIN
return
def print_maze(maze):
def print_m(maze):
for row_index in range(len(maze)):
for col_index in range(len(maze[row_index])):
if global_pos == [row_index, col_index]:
print(TILE_PLAYER + ' ', end='')
else:
print(maze[row_index][col_index] + ' ', end='')
print()
def print_status():
if global_state == STATE_ALIVE:
print(f'You are at {global_pos} and are ALIVE!')
if global_state == STATE_LOSE:
print(f'You are at {global_pos} and LOST!')
if global_state == STATE_WIN:
print(f'You are at {global_pos} and WON!')
def show(t = 0.3):
wait(t)
clear_output(wait=True)
print_m(maze)
print_status()
show()
def move(maze, dir):
global global_pos
def can_move():
if global_state == STATE_LOSE or global_state == STATE_WIN:
return False
return True
def get_new_pos(pos, dir):
new_pos = list(pos)
if dir == DIR_UP:
new_pos = [global_pos[0] - 1, global_pos[1]]
if dir == DIR_DOWN:
new_pos = [global_pos[0] + 1, global_pos[1]]
if dir == DIR_LEFT:
new_pos = [global_pos[0], global_pos[1] - 1]
if dir == DIR_RIGHT:
new_pos = [global_pos[0], global_pos[1] + 1]
return new_pos
if not can_move(): # You can't move because alr won/lost
return
new_pos = get_new_pos(global_pos, dir) # Get new position
if get_square(maze, new_pos) == TILE_OBSTACLE: # You hit an obstacle
return
if (new_pos[0] < 0 or # You are out of bounds
new_pos[0] >= len(maze) or
new_pos[1] < 0 or
new_pos[1] >= len(maze[new_pos[0]])):
return
global_pos = new_pos # Go to new position
set_current_state(maze) # Get new state
print_maze(maze) # Print board again
from random import randrange
def get_random_maze():
"""
returns (maze, start, goal):
maze: (list of lists) [the maze]
start: (list) [maze start in the format [row_index, col_index]]
goal: (list) [maze goal in the format [row_index, col_index]]
"""
def make_sizes(row_min=5, row_max=30, col_min=5, col_max=30):
return randrange(row_min, row_max), randrange(col_min, col_max), randrange(0, row_max * col_max)
def make_maze(rows, cols, num_obs):
# Make empty maze
maze = []
for r in range(rows):
row = []
for c in range(cols):
row.append(TILE_EMPTY)
maze.append(row)
# Make border
maze.insert(0, [TILE_OBSTACLE] * cols)
maze.append([TILE_OBSTACLE] * cols)
for row in maze:
row.insert(0, TILE_OBSTACLE)
row.append(TILE_OBSTACLE)
# Add obstacles
for obs in range(num_obs):
set_square(maze, (randrange(1, rows + 1), randrange(1, cols + 1)), TILE_OBSTACLE)
# Set goal
goal = (randrange(1, rows + 1), randrange(1, cols + 1))
set_square(maze, goal, TILE_GOAL)
# Set start
start = (randrange(1, rows + 1), randrange(1, cols + 1))
set_square(maze, start, TILE_EMPTY)
return maze, start, goal
def is_possible(maze, start, goal):
"""
returns True if maze from start to goal is possible, False otherwise
"""
if start[0] == goal[0] and start[1] == goal[1]:
return False
def get_neighbors(pos):
# Lazy slow way instead of generating adj list from the start
neighbors = []
for diff in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
new_pos = (pos[0] + diff[0], pos[1] + diff[1])
if (new_pos[0] < 0 or
new_pos[0] >= len(maze) or
new_pos[1] < 0 or
new_pos[1] >= len(maze[new_pos[0]])):
continue
if get_square(maze, new_pos) == TILE_OBSTACLE:
continue
neighbors.append(new_pos)
return neighbors
visited = set()
def dfs(visited, maze, pos):
if pos not in visited:
if pos[0] == goal[0] and pos[1] == goal[1]:
return True
visited.add(pos)
for neighbour in get_neighbors(pos):
if dfs(visited, maze, neighbour):
return True
return False
return dfs(visited, maze, start)
rows, cols, obs = make_sizes() # Get random sizes
maze, start, goal = make_maze(rows, cols, obs) # Make maze
if not is_possible(maze, start, goal): # If not possible
return get_random_maze() # ...then make another maze
else: # Otherwise
return (maze, list(start), list(goal)) # ...return the maze
# Alter the global variables and print the maze
def set_globals(new_pos, new_state, maze):
global global_pos
global global_state
global_pos = new_pos
global_state = new_state
set_current_state(maze)
print_maze(maze)
MAZE_1 = ['#####',
'# #',
'# #',
'# !#',
'#####']
MAZE_2 = ['#####',
'# x!#',
'# x #',
'# #',
'#####']
MAZE_3 = ['##########',
'# x #',
'# x ##x #',
'# x #',
'# x! ###',
'# # #',
'# xx ## #',
'# x#',
'##########']
MAZE_4 = []
num_hashes = 0
# Kinda ugly
for row_index in range(8):
num_spaces = 8 - row_index
line = '#' + 'x' * num_hashes + ' ' * num_spaces
remaining = 31 - len(line)
MAZE_4.append(line + 'x' * remaining + '#')
num_hashes += num_spaces - 1
MAZE_4.insert(0, '#' * 32)
MAZE_4.append('#' * 32)
MAZE_4[-2] = MAZE_4[-2][:-3] + TILE_GOAL + MAZE_4[-2][-2:]
Maze 1:¶
In [4]:
# === MAZE 1 ===
maze = MAZE_1
set_globals([1, 1], STATE_ALIVE, maze)
print_maze(maze)
# === DO NOT CHANGE THE ABOVE ===
# Your code here. For example:
for i in range(5):
move(maze, DIR_RIGHT)
move(maze, DIR_DOWN)
move(maze, DIR_LEFT)
move(maze, DIR_UP)
Maze 2:¶
In [ ]:
# === MAZE 2 ===
maze = MAZE_2
set_globals([1, 1], STATE_ALIVE, maze)
print_maze(maze)
# === DO NOT CHANGE THE ABOVE ===
# Your code here!
Maze 3:¶
In [ ]:
# === MAZE 3 ===
maze = MAZE_3
set_globals([1, 1], STATE_ALIVE, maze)
print_maze(maze)
# === DO NOT CHANGE THE ABOVE ===
# Your code here!
Maze 4:¶
Hint for the following problem
Can you see a pattern? We go 7 across then down, then 6 across then down, then 5 across then down... and so on.
In [ ]:
# === MAZE 4: Part 1 ===
maze = MAZE_4
set_globals([1, 1], STATE_ALIVE, maze)
print_maze(maze)
# === DO NOT CHANGE THE ABOVE ===
# Can you write a for loop to reach the goal?
# Can you write a while loop to reach the goal?
In [ ]:
# === MAZE 4: Part 2 ===
maze = MAZE_4
set_globals([1, 1], STATE_ALIVE, maze)
print_maze(maze)
# === DO NOT CHANGE THE ABOVE ===
# Can you write a recursive function to reach the goal?
def complete_maze(n):
# This is a base case to stop if you hit a spike or the goal
if global_state != STATE_ALIVE:
return
# Your base case here!
# Your recursive case here!
return
complete_maze(7)
Maze 5 CHALLENGE - OPTIONAL¶
For this question there will be no spikes on the board
How can you win if you do not know what the maze looks like before hand?
Can you write an algorithm to win?
We recommend the following algorithm:
- Choose a random direction
- Move in that direction
- Repeat until you win (choose another random direction)
# The directions are:
DIR_UP = 1
DIR_DOWN = 2
DIR_LEFT = 3
DIR_RIGHT = 4
Even more optional:
- If you would like reach the goal more efficiently than the random algorithm, you can use
get_square(maze, pos)and the variablesmaze,start, andgoal. You can try printing these out to see what they look like. - You can also read
global_posandglobal_state(although try not to write over them like settingglobal_pos = goal). - The above can get complicated and is not recommended. That being said, here are the relevant variables and functions:
TILE_OBSTACLE = '#'
TILE_GOAL = '!'
TILE_EMPTY = ' '
def get_square(maze, pos):
"""
Input: maze (list of lists) [the maze], pos (list) [position = [row, col]]
Output: (int) [one of the TILE_s listed above]
"""
return maze[pos[0]][pos[1]]
global_pos = None # The player's current position in the form [row, col]
global_state = None # The player's current state = one of the following:
STATE_ALIVE = 1 # The player can move
STATE_LOSE = 2 # The player has lost and cannot move
STATE_WIN = 3 # The player has won and cannot move
In [7]:
# === MAZE 5 ===
maze, start, goal = get_random_maze()
set_globals(start, STATE_ALIVE, maze)
# === DO NOT CHANGE THE ABOVE ===
# Your code here!
Question 3: Time:¶
How can you tell if code is fast or slow? One way is to time it. Run the following example code:
In [9]:
from timeit import default_timer as get_time
for n in range(0, 5000, 500):
start_time = get_time()
for i in range(n):
for j in range(n):
pass
end_time = get_time()
print(f'Time elapsed for n = {n}: {end_time - start_time}s')
In [ ]:
# What does the above code seem to do?
# Explain why we subtract the end_time from the start_time
We've seen different ways to add an element to the end of a list:
lst = lst + [element]lst.append(element)Which method is faster? Can you use thetimeitmodule to find out?
In [ ]:
# Explore here!
Elijah wrote some slow code. Can you find out what his functions do, and write faster code that does the same thing?
Note: x and n are positive integers.
Run the following helper function
In [16]:
# A helper function to check the time of two functions
def check_time(func_1, func_2, inputs):
""" Prints the timing of running the functions on the input
Input: func_1, func_2, inputs (list)
Output: (None)
"""
res_1 = []
res_2 = []
t_1 = 0
t_2 = 0
start_time = get_time()
for args in inputs:
res_1.append(func_1(*args))
t_1 = get_time() - start_time
start_time = get_time()
for args in inputs:
res_2.append(func_2(*args))
t_2 = get_time() - start_time
if res_1 == res_2:
print('The function outputs match!')
else:
print('The function outputs do not match!')
return
print(f'{func_1.__name__} ran in: {t_1}s and {func_2.__name__} ran in: {t_2}s ')
Fill in mult_fast() so that it better than mult_slow() and does less steps. The outputs should still be the same though.
In [17]:
def mult_slow(x, n):
if n <= 0:
return 0
return x + mult_slow(x, n - 1)
def mult_fast(x, n):
# Your code
pass
check_time(mult_slow, mult_fast, [[x, x] for x in range(100, 500)])
Fill out foo_fast(). Try different values for x and n for foo_slow() to see what is going on.
In [19]:
def foo_slow(x, n):
if n <= 0:
return x
if x % 2 == 0:
return foo_slow(x - 1, n - 1)
else:
return foo_slow(x, n - 1) - 1
def foo_fast(x, n):
# Your code
pass
check_time(foo_slow, foo_fast, [[x + 5, x] for x in range(100, 500)])
print(foo_slow(10, 3))
print(foo_slow(7, 2))
Same thing, try to guess what the function does!
In [24]:
def baz_slow(n):
if n <= 0:
return 1
else:
return 2 * baz_slow(n - 1)
def baz_fast(n):
# Your code
pass
check_time(baz_slow, baz_fast, [[x] for x in range(100, 500)])
In [21]:
def bar_slow(x, n):
if x < n :
return x
else:
return bar_slow(x - n, n)
def bar_fast(x, n):
# Your code
pass
print(bar_slow(10, 4))
print(bar_slow(7, 2))
check_time(bar_slow, bar_fast, [[x, 2] for x in range(100, 500)])
In [ ]: