# Towers of Hanoi game to demonstrate use of the stack linear data structure
#The game follows three rules:
#1. Only one disk can be moved at a time.
#2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack #or on an empty rod.
#3. No disk may be placed on top of a smaller disk.
#Rebuild the stack of disks on the opposite rod.
# TowersOfHanoi.py
from stack import Stack
print("\nLet's play Towers of Hanoi!!")
#Create the Stacks
stacks = []
left_stack = Stack("Left")
middle_stack = Stack("Middle")
right_stack = Stack("Right")
stacks.append(left_stack)
stacks.append(middle_stack)
stacks.append(right_stack)
#Set up the Game
num_disks = int(input("\nHow many disks do you want to play with\n"))
while(num_disks < 3):
num_disks = int(input("\nEnter a number greater than or equal to 3\n"))
for i in range(num_disks, 0, -1):
left_stack.push(i)
num_optimal_moves = 2**num_disks-1
print("\nThe fastest you can solve this game is in {} moves".format(num_optimal_moves))
#Get User Input
def get_input():
choices = [stack.get_name()[0] for stack in stacks]
while True:
for num in range(len(stacks)):
name = stacks[num].get_name()
letter = choices[num]
print("Enter {0} for {1}".format(letter,name))
user_input = input("")
if user_input in choices:
for i in range(len(stacks)):
if choices[i] == user_input:
return stacks[i]
#Play the Game
num_user_moves = 0
while right_stack.get_size() != num_disks:
print("\n\n\n...Current Stacks...")
for stack in stacks:
stack.print_items()
while True:
print("\nWhich stack do you want to move from?\n")
from_stack = get_input()
print("\nWhich stack do you want to move to?\n")
#get_input must be flushed first - returning the previous input
to_stack = get_input()
if from_stack.get_size() == 0:
print("\n\nInvalid move, try again.")
elif to_stack.get_size() == 0 or from_stack.peek() < to_stack.peek():
disk = from_stack.pop()
to_stack.push(disk)
num_user_moves += 1
break
else:
print("\n\nInvalid move, try again.")
print("You completed the game in {0} moves, and the optimal number of moves is {1}".format(num_user_moves, num_optimal_moves))
#stack.py
from node import Node
class Stack:
def __init__(self, name):
self.size = 0
self.top_item = None
self.limit = 1000
self.name = name
def push(self, value):
if self.has_space():
item = Node(value)
item.set_next_node(self.top_item)
self.top_item = item
self.size += 1
else:
print("No more room!")
def pop(self):
if self.size > 0:
item_to_remove = self.top_item
self.top_item = item_to_remove.get_next_node()
self.size -= 1
return item_to_remove.get_value()
print("This stack is totally empty.")
def peek(self):
if self.size > 0:
return self.top_item.get_value()
print("Nothing to see here!")
def has_space(self):
return self.limit > self.size
def is_empty(self):
return self.size == 0
def get_size(self):
return self.size
def get_name(self):
return self.name
def print_items(self):
pointer = self.top_item
print_list = []
while(pointer):
print_list.append(pointer.get_value())
pointer = pointer.get_next_node()
print_list.reverse()
print("{0} Stack: {1}".format(self.get_name(), print_list))
# node.py
class Node:
def __init__(self, value, link_node=None):
self.value = value
self.link_node = link_node
def set_next_node(self, link_node):
self.link_node = link_node
def get_next_node(self):
return self.link_node
def get_value(self):
return self.value
#The game follows three rules:
#1. Only one disk can be moved at a time.
#2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack #or on an empty rod.
#3. No disk may be placed on top of a smaller disk.
#Rebuild the stack of disks on the opposite rod.
# TowersOfHanoi.py
from stack import Stack
print("\nLet's play Towers of Hanoi!!")
#Create the Stacks
stacks = []
left_stack = Stack("Left")
middle_stack = Stack("Middle")
right_stack = Stack("Right")
stacks.append(left_stack)
stacks.append(middle_stack)
stacks.append(right_stack)
#Set up the Game
num_disks = int(input("\nHow many disks do you want to play with\n"))
while(num_disks < 3):
num_disks = int(input("\nEnter a number greater than or equal to 3\n"))
for i in range(num_disks, 0, -1):
left_stack.push(i)
num_optimal_moves = 2**num_disks-1
print("\nThe fastest you can solve this game is in {} moves".format(num_optimal_moves))
#Get User Input
def get_input():
choices = [stack.get_name()[0] for stack in stacks]
while True:
for num in range(len(stacks)):
name = stacks[num].get_name()
letter = choices[num]
print("Enter {0} for {1}".format(letter,name))
user_input = input("")
if user_input in choices:
for i in range(len(stacks)):
if choices[i] == user_input:
return stacks[i]
#Play the Game
num_user_moves = 0
while right_stack.get_size() != num_disks:
print("\n\n\n...Current Stacks...")
for stack in stacks:
stack.print_items()
while True:
print("\nWhich stack do you want to move from?\n")
from_stack = get_input()
print("\nWhich stack do you want to move to?\n")
#get_input must be flushed first - returning the previous input
to_stack = get_input()
if from_stack.get_size() == 0:
print("\n\nInvalid move, try again.")
elif to_stack.get_size() == 0 or from_stack.peek() < to_stack.peek():
disk = from_stack.pop()
to_stack.push(disk)
num_user_moves += 1
break
else:
print("\n\nInvalid move, try again.")
print("You completed the game in {0} moves, and the optimal number of moves is {1}".format(num_user_moves, num_optimal_moves))
#stack.py
from node import Node
class Stack:
def __init__(self, name):
self.size = 0
self.top_item = None
self.limit = 1000
self.name = name
def push(self, value):
if self.has_space():
item = Node(value)
item.set_next_node(self.top_item)
self.top_item = item
self.size += 1
else:
print("No more room!")
def pop(self):
if self.size > 0:
item_to_remove = self.top_item
self.top_item = item_to_remove.get_next_node()
self.size -= 1
return item_to_remove.get_value()
print("This stack is totally empty.")
def peek(self):
if self.size > 0:
return self.top_item.get_value()
print("Nothing to see here!")
def has_space(self):
return self.limit > self.size
def is_empty(self):
return self.size == 0
def get_size(self):
return self.size
def get_name(self):
return self.name
def print_items(self):
pointer = self.top_item
print_list = []
while(pointer):
print_list.append(pointer.get_value())
pointer = pointer.get_next_node()
print_list.reverse()
print("{0} Stack: {1}".format(self.get_name(), print_list))
# node.py
class Node:
def __init__(self, value, link_node=None):
self.value = value
self.link_node = link_node
def set_next_node(self, link_node):
self.link_node = link_node
def get_next_node(self):
return self.link_node
def get_value(self):
return self.value
#Tomb Explorer game - traverse vertices (rooms) in a graph data structure (tomb)
#vertex.PY
class Vertex:
#function to initialise
def __init__(self, value):
self.value = value
self.edges = {}
#function to add an edge to the vertex
def add_edge(self, adjacent_value, weight = 0):
self.edges[adjacent_value] = weight
#function to return the number of edges
def get_edges(self):
return self.edges.keys()
#graph.PY
from vertex import Vertex
class Graph:
#function to initialise
def __init__(self):
self.graph_dict = {}
#function to add a vertex to the graph
def add_vertex(self, node):
self.graph_dict[node.value] = node
#function to add an edge to a node
def add_edge(self, from_node, to_node, weight = 0):
self.graph_dict[from_node.value].add_edge(to_node.value, weight)
self.graph_dict[to_node.value].add_edge(from_node.value, weight)
#function to run through the exploration process of the graph
def explore(self):
print("=================\n")
print("Welcome to Tomb Explorer, intrepid adventurer! Having made your way through the Amazonian rainforest, you stumble upon the ancient Aztec ruins of El Dorado." +
" However, upon entering the ruins, you find yourself stricken with a curse! You must find the treasure room before the timer expires, or you will succumb to the curse and die. Good luck!\n")
print("================\n")
current_room = 'entrance'
path_total = 0
print("\nStarting off at the {0}\n".format(current_room))
#loop to run while user is not in the treasure room
while current_room != 'treasure room':
node = self.graph_dict[current_room]
for connected_room, weight in node.edges.items():
key = connected_room[:1]
print("enter {0} for {1}: {2} steps".format(key, connected_room, weight))
valid_choices = [room[:1] for room in node.edges.keys()]
print("\nYou have accumulated: {0} steps".format(path_total))
print("Do not exceed 9 steps!")
choice = input("\nWhich room do you move to? ")
if choice not in valid_choices:
print("please select from these letters: {0}".format(valid_choices))
else:
for room in node.edges.keys():
if room.startswith(choice):
current_room = room
path_total += node.edges[room]
print("\n*** You have chosen: {0} ***\n".format(current_room))
if path_total > 9:
print("You succumb to the curse! \n \nYOU LOSE\n")
break
if current_room == 'treasure room':
print("Made it to the treasure room with {0} steps".format(path_total))
#function to print the map out
def print_map(self):
print("\n=====TOMB EXPLORER=====\n\n")
print("\nTOMB LAYOUT\n")
for node_key in self.graph_dict:
print("{0} connected to...".format(node_key))
node = self.graph_dict[node_key]
for adjacent_node, weight in node.edges.items():
print("=> {0}: steps are {1}".format(adjacent_node, weight))
print("")
print("")
#function to build the graph
def build_graph():
graph = Graph()
# MAKE ROOMS INTO VERTICES
entrance = Vertex("entrance")
ante_chamber = Vertex("ante-chamber")
shrine_room = Vertex("shrine room")
great_hall = Vertex("great hall")
treasure_room = Vertex("treasure room")
# ADD ROOMS TO GRAPH
graph.add_vertex(entrance)
graph.add_vertex(ante_chamber)
graph.add_vertex(shrine_room)
graph.add_vertex(great_hall)
graph.add_vertex(treasure_room)
# ADD EDGES BETWEEN ROOMS
graph.add_edge(entrance, ante_chamber, 7)
graph.add_edge(entrance, shrine_room, 3)
graph.add_edge(ante_chamber, shrine_room, 1)
graph.add_edge(ante_chamber, great_hall, 2)
graph.add_edge(shrine_room, great_hall, 2)
graph.add_edge(treasure_room, great_hall, 4)
graph.add_edge(treasure_room, ante_chamber, 6)
# print the map and return the graph
graph.print_map()
return graph
#tomb-explorer.py
#import classes
from graph import Graph, build_graph
from vertex import Vertex
excavation_site = build_graph()
excavation_site.explore()
#vertex.PY
class Vertex:
#function to initialise
def __init__(self, value):
self.value = value
self.edges = {}
#function to add an edge to the vertex
def add_edge(self, adjacent_value, weight = 0):
self.edges[adjacent_value] = weight
#function to return the number of edges
def get_edges(self):
return self.edges.keys()
#graph.PY
from vertex import Vertex
class Graph:
#function to initialise
def __init__(self):
self.graph_dict = {}
#function to add a vertex to the graph
def add_vertex(self, node):
self.graph_dict[node.value] = node
#function to add an edge to a node
def add_edge(self, from_node, to_node, weight = 0):
self.graph_dict[from_node.value].add_edge(to_node.value, weight)
self.graph_dict[to_node.value].add_edge(from_node.value, weight)
#function to run through the exploration process of the graph
def explore(self):
print("=================\n")
print("Welcome to Tomb Explorer, intrepid adventurer! Having made your way through the Amazonian rainforest, you stumble upon the ancient Aztec ruins of El Dorado." +
" However, upon entering the ruins, you find yourself stricken with a curse! You must find the treasure room before the timer expires, or you will succumb to the curse and die. Good luck!\n")
print("================\n")
current_room = 'entrance'
path_total = 0
print("\nStarting off at the {0}\n".format(current_room))
#loop to run while user is not in the treasure room
while current_room != 'treasure room':
node = self.graph_dict[current_room]
for connected_room, weight in node.edges.items():
key = connected_room[:1]
print("enter {0} for {1}: {2} steps".format(key, connected_room, weight))
valid_choices = [room[:1] for room in node.edges.keys()]
print("\nYou have accumulated: {0} steps".format(path_total))
print("Do not exceed 9 steps!")
choice = input("\nWhich room do you move to? ")
if choice not in valid_choices:
print("please select from these letters: {0}".format(valid_choices))
else:
for room in node.edges.keys():
if room.startswith(choice):
current_room = room
path_total += node.edges[room]
print("\n*** You have chosen: {0} ***\n".format(current_room))
if path_total > 9:
print("You succumb to the curse! \n \nYOU LOSE\n")
break
if current_room == 'treasure room':
print("Made it to the treasure room with {0} steps".format(path_total))
#function to print the map out
def print_map(self):
print("\n=====TOMB EXPLORER=====\n\n")
print("\nTOMB LAYOUT\n")
for node_key in self.graph_dict:
print("{0} connected to...".format(node_key))
node = self.graph_dict[node_key]
for adjacent_node, weight in node.edges.items():
print("=> {0}: steps are {1}".format(adjacent_node, weight))
print("")
print("")
#function to build the graph
def build_graph():
graph = Graph()
# MAKE ROOMS INTO VERTICES
entrance = Vertex("entrance")
ante_chamber = Vertex("ante-chamber")
shrine_room = Vertex("shrine room")
great_hall = Vertex("great hall")
treasure_room = Vertex("treasure room")
# ADD ROOMS TO GRAPH
graph.add_vertex(entrance)
graph.add_vertex(ante_chamber)
graph.add_vertex(shrine_room)
graph.add_vertex(great_hall)
graph.add_vertex(treasure_room)
# ADD EDGES BETWEEN ROOMS
graph.add_edge(entrance, ante_chamber, 7)
graph.add_edge(entrance, shrine_room, 3)
graph.add_edge(ante_chamber, shrine_room, 1)
graph.add_edge(ante_chamber, great_hall, 2)
graph.add_edge(shrine_room, great_hall, 2)
graph.add_edge(treasure_room, great_hall, 4)
graph.add_edge(treasure_room, ante_chamber, 6)
# print the map and return the graph
graph.print_map()
return graph
#tomb-explorer.py
#import classes
from graph import Graph, build_graph
from vertex import Vertex
excavation_site = build_graph()
excavation_site.explore()
#This is an "Escape The Haunted Forest" game. You get a unique story experience by making decisions. A tree #data structure is used to keep track of the different paths a user may choose.
class TreeNode:
def __init__(self, story_piece):
self.story_piece = story_piece
self.choices = []
def add_child(self, node):
self.choices.append(node)
def traverse(self):
story_node = self
print(story_node.story_piece)
while story_node.choices != []:
choice = input("Enter 1 or 2 to continue the story: ")
if choice not in ["1", "2"]:
print("invalid choice")
else:
chosen_index = int(choice)
chosen_index -= 1
chosen_child = story_node.choices[chosen_index]
print(chosen_child.story_piece)
story_node = chosen_child
######
# VARIABLES FOR TREE
######
story_root = TreeNode("""
You are travelling to another town, when you become lost in a forest. You stop in a forest clearing. There is a path to the left.
A strange woman emerges from the trees and and beckons you to follow her...
Do you:
1 ) Shout at her!
2 ) Follow her
""")
choice_a = TreeNode("""
The strange woman is frightened and hides behind a tree.
Do you:
1 ) Shout 'Sorry!'
2 ) Yell 'Hooray!'
""")
choice_b = TreeNode("""
You come across a clearing full of flowers. You realise the strange woman is a ghost.
The ghost calls after you 'Why have you chosen to follow me? You do not know me'
Do you:
1 ) Gasp 'Youre a ghost!'
2 ) Explain that she startled you, but you thought she may be able to help.
""")
choice_a_1 = TreeNode("""
The strange woman returns and tells you she is a ghost who helps weary travellers. After making peace with
the ghost, she shows you the way out of the forest.
YOU HAVE ESCAPED THE HAUNTED FOREST.
""")
choice_a_2 = TreeNode("""
The strange woman returns and tells you that bullying is not okay before leaving you alone
in the wilderness.
YOU REMAIN LOST.
""")
choice_b_1 = TreeNode ("""
The ghost is unamused. It turns around and leaves you alone.
YOU REMAIN LOST.
""")
choice_b_2 = TreeNode("""
The ghost understands and apologizes for startling you. Your new friend shows you a
path leading out of the forest.
YOU HAVE ESCAPED THE HAUNTED FOREST.
""")
#user_choice = input("What is your name?")
#print(user_choice)
######
# TESTING AREA
######
print("#########################")
print("ESCAPE THE HAUNTED FOREST")
print("#########################\n")
print("Once upon a time, in a land far away...")
story_root.add_child(choice_a)
story_root.add_child(choice_b)
choice_a.add_child(choice_a_1)
choice_a.add_child(choice_a_2)
choice_b.add_child(choice_b_1)
choice_b.add_child(choice_b_2)
story_root.traverse()
class TreeNode:
def __init__(self, story_piece):
self.story_piece = story_piece
self.choices = []
def add_child(self, node):
self.choices.append(node)
def traverse(self):
story_node = self
print(story_node.story_piece)
while story_node.choices != []:
choice = input("Enter 1 or 2 to continue the story: ")
if choice not in ["1", "2"]:
print("invalid choice")
else:
chosen_index = int(choice)
chosen_index -= 1
chosen_child = story_node.choices[chosen_index]
print(chosen_child.story_piece)
story_node = chosen_child
######
# VARIABLES FOR TREE
######
story_root = TreeNode("""
You are travelling to another town, when you become lost in a forest. You stop in a forest clearing. There is a path to the left.
A strange woman emerges from the trees and and beckons you to follow her...
Do you:
1 ) Shout at her!
2 ) Follow her
""")
choice_a = TreeNode("""
The strange woman is frightened and hides behind a tree.
Do you:
1 ) Shout 'Sorry!'
2 ) Yell 'Hooray!'
""")
choice_b = TreeNode("""
You come across a clearing full of flowers. You realise the strange woman is a ghost.
The ghost calls after you 'Why have you chosen to follow me? You do not know me'
Do you:
1 ) Gasp 'Youre a ghost!'
2 ) Explain that she startled you, but you thought she may be able to help.
""")
choice_a_1 = TreeNode("""
The strange woman returns and tells you she is a ghost who helps weary travellers. After making peace with
the ghost, she shows you the way out of the forest.
YOU HAVE ESCAPED THE HAUNTED FOREST.
""")
choice_a_2 = TreeNode("""
The strange woman returns and tells you that bullying is not okay before leaving you alone
in the wilderness.
YOU REMAIN LOST.
""")
choice_b_1 = TreeNode ("""
The ghost is unamused. It turns around and leaves you alone.
YOU REMAIN LOST.
""")
choice_b_2 = TreeNode("""
The ghost understands and apologizes for startling you. Your new friend shows you a
path leading out of the forest.
YOU HAVE ESCAPED THE HAUNTED FOREST.
""")
#user_choice = input("What is your name?")
#print(user_choice)
######
# TESTING AREA
######
print("#########################")
print("ESCAPE THE HAUNTED FOREST")
print("#########################\n")
print("Once upon a time, in a land far away...")
story_root.add_child(choice_a)
story_root.add_child(choice_b)
choice_a.add_child(choice_a_1)
choice_a.add_child(choice_a_2)
choice_b.add_child(choice_b_1)
choice_b.add_child(choice_b_2)
story_root.traverse()
#Program to relate the names of crystals to their meanings in a hash-map data structure.
#Chains of linked lists are stored at each index.
#Separate chains will avoid collisions in the hashing function.
#Key-value pairs store the common crystal name as the key and the colour & meaning as the value.
#script.py
from linked_list import Node, LinkedList
from crystals_lib import crystal_definitions
class HashMap:
def __init__(self, size):
self.array_size = size
self.array = [LinkedList() for number in range(size)]
def hash(self, key):
return sum(key.encode())
def compress(self, hash_code):
return hash_code % self.array_size
#method to assign a value to the linked list stored at a specified key
def assign(self, key, value):
array_index = self.compress(self.hash(key))
payload = Node([key, value])
list_at_array = self.array[array_index]
for item in list_at_array:
list_at_array.insert(payload)
#method to find hash code for a key and retrieve value stored there
def retrieve(self, key):
array_index = self.compress(self.hash(key))
list_at_index = self.array[array_index]
for item in list_at_index:
if key == item[0]:
return item[1]
return None
jewellery = HashMap(len(crystal_definitions))
for crystal in crystal_definitions:
jewellery.assign(crystal[0], crystal[1])
print('CRYSTALS: ')
print('')
print('clear quartz')
print('ruby')
print('rose quartz')
print('sunstone')
print('citrine')
print('jade')
print('azurite')
print('amethyst')
print('obsidian')
print('jet')
print('aquamarine')
print('malachite')
print('garnet')
print('selenite')
print('')
choice = input("Enter a crystal name to find the colour and meaning: ")
if choice not in ['clear quartz','ruby','rose quartz','sunstone','citrine',
'jade','azurite','amethyst','obsidian',
'jet','aquamarine','malachite','garnet','selenite']:
print("invalid choice, please enter a valid crystal name")
else:
print(jewellery.retrieve(choice))
#crystals_lib.py
crystal_definitions = [['clear quartz', 'clear - cleansing, purity'], ['ruby', 'red - intensity, high energy'], ['rose quartz', 'pink - love and kindness'], ['sunstone', 'orange - creativity and confidence'], ['citrine', 'yellow - willpower & optimism'], ['jade', 'green - wealth & prosperity'], ['azurite', 'blue - clarity & communication'], ['amethyst', 'purple - spirituality & intuition'], ['obsidian', 'black - banishing negativity'], ['jet', 'black - focus & effort'], ['aquamarine', 'blue - expression of ideas, calmness'], ['malachite', 'green - abundance & growth'], ['garnet', 'red - determination & courage'], ['selenite', 'white - peace & serenity']]
#linked_list.py
class Node:
def __init__(self, value):
self.value = value
self.next_node = None
def get_value(self):
return self.value
def get_next_node(self):
return self.next_node
def set_next_node(self, next_node):
self.next_node = next_node
class LinkedList:
def __init__(self, head_node=None):
self.head_node = head_node
def insert(self, new_node):
current_node = self.head_node
if not current_node:
self.head_node = new_node
while(current_node):
next_node = current_node.get_next_node()
if not next_node:
current_node.set_next_node(new_node)
current_node = next_node
def __iter__(self):
current_node = self.head_node
while(current_node):
yield current_node.get_value()
current_node = current_node.get_next_node()
#Chains of linked lists are stored at each index.
#Separate chains will avoid collisions in the hashing function.
#Key-value pairs store the common crystal name as the key and the colour & meaning as the value.
#script.py
from linked_list import Node, LinkedList
from crystals_lib import crystal_definitions
class HashMap:
def __init__(self, size):
self.array_size = size
self.array = [LinkedList() for number in range(size)]
def hash(self, key):
return sum(key.encode())
def compress(self, hash_code):
return hash_code % self.array_size
#method to assign a value to the linked list stored at a specified key
def assign(self, key, value):
array_index = self.compress(self.hash(key))
payload = Node([key, value])
list_at_array = self.array[array_index]
for item in list_at_array:
list_at_array.insert(payload)
#method to find hash code for a key and retrieve value stored there
def retrieve(self, key):
array_index = self.compress(self.hash(key))
list_at_index = self.array[array_index]
for item in list_at_index:
if key == item[0]:
return item[1]
return None
jewellery = HashMap(len(crystal_definitions))
for crystal in crystal_definitions:
jewellery.assign(crystal[0], crystal[1])
print('CRYSTALS: ')
print('')
print('clear quartz')
print('ruby')
print('rose quartz')
print('sunstone')
print('citrine')
print('jade')
print('azurite')
print('amethyst')
print('obsidian')
print('jet')
print('aquamarine')
print('malachite')
print('garnet')
print('selenite')
print('')
choice = input("Enter a crystal name to find the colour and meaning: ")
if choice not in ['clear quartz','ruby','rose quartz','sunstone','citrine',
'jade','azurite','amethyst','obsidian',
'jet','aquamarine','malachite','garnet','selenite']:
print("invalid choice, please enter a valid crystal name")
else:
print(jewellery.retrieve(choice))
#crystals_lib.py
crystal_definitions = [['clear quartz', 'clear - cleansing, purity'], ['ruby', 'red - intensity, high energy'], ['rose quartz', 'pink - love and kindness'], ['sunstone', 'orange - creativity and confidence'], ['citrine', 'yellow - willpower & optimism'], ['jade', 'green - wealth & prosperity'], ['azurite', 'blue - clarity & communication'], ['amethyst', 'purple - spirituality & intuition'], ['obsidian', 'black - banishing negativity'], ['jet', 'black - focus & effort'], ['aquamarine', 'blue - expression of ideas, calmness'], ['malachite', 'green - abundance & growth'], ['garnet', 'red - determination & courage'], ['selenite', 'white - peace & serenity']]
#linked_list.py
class Node:
def __init__(self, value):
self.value = value
self.next_node = None
def get_value(self):
return self.value
def get_next_node(self):
return self.next_node
def set_next_node(self, next_node):
self.next_node = next_node
class LinkedList:
def __init__(self, head_node=None):
self.head_node = head_node
def insert(self, new_node):
current_node = self.head_node
if not current_node:
self.head_node = new_node
while(current_node):
next_node = current_node.get_next_node()
if not next_node:
current_node.set_next_node(new_node)
current_node = next_node
def __iter__(self):
current_node = self.head_node
while(current_node):
yield current_node.get_value()
current_node = current_node.get_next_node()
#Python program to sort two data files using the quicksort and bubble sort algorithms.
#The data files are two lists of books, books_small.csv and books_large.csv
#a_sorted_tale.py
import utils
import sorts
bookshelf = utils.load_books('Modules/books_small.csv')
long_bookshelf = utils.load_books('Modules/books_large.csv')
print("")
print("Original short list:")
print("")
for book in bookshelf:
print(book['title'] + " - " + book['author'])
print("")
#comparison functions
def by_title_ascending(book_a, book_b):
if len(book_a['title']) > len(book_b['title_lower']):
return True
else:
return False
def by_author_ascending(book_a, book_b):
if book_a['author_lower'] > book_b['author_lower']:
return True
else:
return False
def by_total_length(book_a, book_b):
if len(book_a['author_lower']) + len(book_a['title_lower']) > len(book_b['author_lower']) + len(book_b['title_lower']):
return True
else:
return False
bookshelf_v1 = bookshelf.copy()
bookshelf_v2 = bookshelf.copy()
sort_1 = sorts.bubble_sort(bookshelf, by_title_ascending)
print("")
print("Sorted by title length ascending - bubble sort:")
print("")
for book in sort_1:
print(book['title'] + " - " + book['author'])
print("")
sort_2 = sorts.bubble_sort(bookshelf, by_author_ascending)
print("")
print("Sorted by author descending - bubble sort:")
print("")
for book in sort_2:
print(book['author'] + " - " + book['title'])
print("")
sorts.quicksort(long_bookshelf,0,len(long_bookshelf)-1, by_total_length)
sorts.quicksort(bookshelf_v2, 0, len(bookshelf_v2)-1, by_author_ascending)
print("")
print("Sorted by author descending - quicksort:")
print("")
for book in bookshelf_v2:
print(book['author'] + " - " + book['title'])
print("")
print("")
print("Sorted long list by total length - quicksort:")
print("")
for book in long_bookshelf:
print(book['author'] + " - " + book['title'])
print("")
#sorts.py
import random
def bubble_sort(arr, comparison_function):
swaps = 0
sorted = False
while not sorted:
sorted = True
for idx in range(len(arr) - 1):
if comparison_function(arr[idx], arr[idx + 1]):
sorted = False
arr[idx], arr[idx + 1] = arr[idx + 1], arr[idx]
swaps += 1
print("Bubble sort: There were {0} swaps".format(swaps))
return arr
def quicksort(list, start, end, comparison_function):
if start >= end:
return
pivot_idx = random.randrange(start, end + 1)
pivot_element = list[pivot_idx]
list[end], list[pivot_idx] = list[pivot_idx], list[end]
less_than_pointer = start
for i in range(start, end):
if comparison_function(pivot_element, list[i]):
list[i], list[less_than_pointer] = list[less_than_pointer], list[i]
less_than_pointer += 1
list[end], list[less_than_pointer] = list[less_than_pointer], list[end]
quicksort(list, start, less_than_pointer - 1, comparison_function)
quicksort(list, less_than_pointer + 1, end, comparison_function)
#utils.py
import csv
# This code loads the current book
# shelf data from the csv file
def load_books(filename):
bookshelf = []
with open(filename) as file:
shelf = csv.DictReader(file)
for book in shelf:
book['author_lower'] = book['author'].lower()
book['title_lower'] = book['title'].lower()
bookshelf.append(book)
return bookshelf
#The data files are two lists of books, books_small.csv and books_large.csv
#a_sorted_tale.py
import utils
import sorts
bookshelf = utils.load_books('Modules/books_small.csv')
long_bookshelf = utils.load_books('Modules/books_large.csv')
print("")
print("Original short list:")
print("")
for book in bookshelf:
print(book['title'] + " - " + book['author'])
print("")
#comparison functions
def by_title_ascending(book_a, book_b):
if len(book_a['title']) > len(book_b['title_lower']):
return True
else:
return False
def by_author_ascending(book_a, book_b):
if book_a['author_lower'] > book_b['author_lower']:
return True
else:
return False
def by_total_length(book_a, book_b):
if len(book_a['author_lower']) + len(book_a['title_lower']) > len(book_b['author_lower']) + len(book_b['title_lower']):
return True
else:
return False
bookshelf_v1 = bookshelf.copy()
bookshelf_v2 = bookshelf.copy()
sort_1 = sorts.bubble_sort(bookshelf, by_title_ascending)
print("")
print("Sorted by title length ascending - bubble sort:")
print("")
for book in sort_1:
print(book['title'] + " - " + book['author'])
print("")
sort_2 = sorts.bubble_sort(bookshelf, by_author_ascending)
print("")
print("Sorted by author descending - bubble sort:")
print("")
for book in sort_2:
print(book['author'] + " - " + book['title'])
print("")
sorts.quicksort(long_bookshelf,0,len(long_bookshelf)-1, by_total_length)
sorts.quicksort(bookshelf_v2, 0, len(bookshelf_v2)-1, by_author_ascending)
print("")
print("Sorted by author descending - quicksort:")
print("")
for book in bookshelf_v2:
print(book['author'] + " - " + book['title'])
print("")
print("")
print("Sorted long list by total length - quicksort:")
print("")
for book in long_bookshelf:
print(book['author'] + " - " + book['title'])
print("")
#sorts.py
import random
def bubble_sort(arr, comparison_function):
swaps = 0
sorted = False
while not sorted:
sorted = True
for idx in range(len(arr) - 1):
if comparison_function(arr[idx], arr[idx + 1]):
sorted = False
arr[idx], arr[idx + 1] = arr[idx + 1], arr[idx]
swaps += 1
print("Bubble sort: There were {0} swaps".format(swaps))
return arr
def quicksort(list, start, end, comparison_function):
if start >= end:
return
pivot_idx = random.randrange(start, end + 1)
pivot_element = list[pivot_idx]
list[end], list[pivot_idx] = list[pivot_idx], list[end]
less_than_pointer = start
for i in range(start, end):
if comparison_function(pivot_element, list[i]):
list[i], list[less_than_pointer] = list[less_than_pointer], list[i]
less_than_pointer += 1
list[end], list[less_than_pointer] = list[less_than_pointer], list[end]
quicksort(list, start, less_than_pointer - 1, comparison_function)
quicksort(list, less_than_pointer + 1, end, comparison_function)
#utils.py
import csv
# This code loads the current book
# shelf data from the csv file
def load_books(filename):
bookshelf = []
with open(filename) as file:
shelf = csv.DictReader(file)
for book in shelf:
book['author_lower'] = book['author'].lower()
book['title_lower'] = book['title'].lower()
bookshelf.append(book)
return bookshelf
#binary search algorithm
def sparse_search(data, search_val):
print("Data: " + str(data))
print("Search Value: " + str(search_val))
first = 0
last = len(data)-1
while first <= last:
mid = (first+last)//2
if not data[mid]:
left = mid-1
right = mid+1
while True:
if (left < first) and (right > last):
print("{0} is not in the dataset".format(search_val))
return
elif (right <= last) and (data[right]):
mid = right
break
elif (left >= first and data[left]):
mid = left
break
right += 1
left -= 1
if data[mid] == search_val:
print("{0} found at position {1}".format(search_val, mid))
return
elif search_val < data[mid]:
last = mid - 1
elif search_val > data[mid]:
first = mid + 1
print('{0} is not in the dataset'.format(search_val))
#test the algorithm with data
from searchcademy import sparse_search
print("")
print("Iterative binary search algorithm")
print("")
data_one = ["Arthur", "", "", "", "", "", "Elise", "", "", "", "Gary", "", "Mimi", "", "", "", "Zachary"]
search_one = "Zachary"
print("Calling sparse_search.....")
ret = sparse_search(data_one, search_one)
#print("Return Value: " + str(ret))
data_two = ["1", "", "", "2", "", "", "3", "", "5", "", "", "", "9", "12"]
search_two = "2"
print("\n\nCalling sparse_search.....")
ret = sparse_search(data_two, search_two)
#print("Return Value: " + str(ret))
data_three = ["Alex", "", "", "", "", "Devan", "", "", "Elise", "", "", "", "Gary", "", "", "Mimi", "", "", "Parth", "", "", "", "Zachary"]
search_three = "Parth"
print("\n\nCalling sparse_search.....")
ret = sparse_search(data_three, search_three)
data_four = ["Apple", "", "Banana", "", "", "", "", "Cow"]
search_four = "Banana"
print("\n\nCalling sparse_search.....")
ret = sparse_search(data_four, search_four)
data_five = ["A", "", "", "", "B", "", "", "", "C"]
search_five = "D"
print("\n\nCalling sparse_search.....")
ret = sparse_search(data_five, search_five)
def sparse_search(data, search_val):
print("Data: " + str(data))
print("Search Value: " + str(search_val))
first = 0
last = len(data)-1
while first <= last:
mid = (first+last)//2
if not data[mid]:
left = mid-1
right = mid+1
while True:
if (left < first) and (right > last):
print("{0} is not in the dataset".format(search_val))
return
elif (right <= last) and (data[right]):
mid = right
break
elif (left >= first and data[left]):
mid = left
break
right += 1
left -= 1
if data[mid] == search_val:
print("{0} found at position {1}".format(search_val, mid))
return
elif search_val < data[mid]:
last = mid - 1
elif search_val > data[mid]:
first = mid + 1
print('{0} is not in the dataset'.format(search_val))
#test the algorithm with data
from searchcademy import sparse_search
print("")
print("Iterative binary search algorithm")
print("")
data_one = ["Arthur", "", "", "", "", "", "Elise", "", "", "", "Gary", "", "Mimi", "", "", "", "Zachary"]
search_one = "Zachary"
print("Calling sparse_search.....")
ret = sparse_search(data_one, search_one)
#print("Return Value: " + str(ret))
data_two = ["1", "", "", "2", "", "", "3", "", "5", "", "", "", "9", "12"]
search_two = "2"
print("\n\nCalling sparse_search.....")
ret = sparse_search(data_two, search_two)
#print("Return Value: " + str(ret))
data_three = ["Alex", "", "", "", "", "Devan", "", "", "Elise", "", "", "", "Gary", "", "", "Mimi", "", "", "Parth", "", "", "", "Zachary"]
search_three = "Parth"
print("\n\nCalling sparse_search.....")
ret = sparse_search(data_three, search_three)
data_four = ["Apple", "", "Banana", "", "", "", "", "Cow"]
search_four = "Banana"
print("\n\nCalling sparse_search.....")
ret = sparse_search(data_four, search_four)
data_five = ["A", "", "", "", "B", "", "", "", "C"]
search_five = "D"
print("\n\nCalling sparse_search.....")
ret = sparse_search(data_five, search_five)
#SkyRoute is a routing tool that uses breadth-first search, depth-first search, and Python dictionaries to accomplish #this feat.
#Assumes that it takes the same amount of time to get from each station to each of its connected neighboring #stations.
#Ideas for further development:
#Can deal with situation where same station for origin and destination
#Maybe Vancouver’s system wants a user interface for employees to update the stations under construction
from graph_search import bfs, dfs
from vc_metro import vc_metro
from vc_landmarks import vc_landmarks
from landmark_choices import landmark_choices
landmark_string = ""
stations_under_construction = ['Richmond-Brighouse']
for letter, landmark in landmark_choices.items():
landmark_string += "{0} - {1}\n".format(letter, landmark)
def get_active_stations():
updated_metro = vc_metro
for station_under_construction in stations_under_construction:
for current_station, neighbouring_stations in vc_metro.items():
if current_station != station_under_construction:
updated_metro[current_station] -= set(stations_under_construction)
else:
updated_metro[current_station] = set([])
return updated_metro
def new_route(start_point=None, end_point=None):
start_point, end_point = set_start_and_end(start_point, end_point)
shortest_route = get_route(start_point, end_point)
if shortest_route:
shortest_route_string = '\n'.join(shortest_route)
print("The shortest metro route from {0} to {1} is:\n{2}".format(start_point,end_point,shortest_route_string))
else:
print("Unfortunately, there is currently no path between {0} and {1} due to maintenance.".format(start_point, end_point))
again = input("Would you like to see another route? Enter y/n: ")
if again == "y":
show_landmarks()
new_route(start_point,end_point)
def show_landmarks():
see_landmarks = input("Would you like to see the list of landmarks again> Enter y/n: ")
if see_landmarks == "y":
print(landmark_string)
def goodbye():
print("Thanks for using SkyRoute!")
def get_route(start_point, end_point):
start_stations = vc_landmarks[start_point]
end_stations = vc_landmarks[end_point]
routes = []
for start_station in start_stations:
for end_station in end_stations:
metro_system = get_active_stations() if stations_under_construction else vc_macro
if len(stations_under_construction) > 0:
possible_route = dfs(metro_system, start_station, end_station)
if not possible_route:
return None
route = bfs(metro_system, start_station, end_station)
if route:
routes.append(route)
shortest_route = min(routes)
return shortest_route
def greet():
print("Hi there and welcome to SkyRoute!")
print("We'll help you find the shortest route between the following Vancouver landmarks:\n" + landmark_string)
def skyroute():
greet()
new_route()
goodbye()
def set_start_and_end(start_point, end_point):
if start_point != None:
change_point = input("What would you like to change? You can enter 'o' for 'origin', 'd' for 'destination', or 'b' for 'both': ")
if change_point == "b":
start_point = get_start()
end_point = get_end()
elif change_point == "o":
get_start()
elif change_point == "d":
end_point = get_end()
else:
print("Oops, that isn't 'o', 'd', or 'b'...")
set_start_and_end(start_point,end_point)
return start_point, end_point
else:
start_point = get_start()
end_point = get_end()
return start_point, end_point
def get_start():
start_point_letter = input("Where are you coming from? Type in the corresponding letter: ")
if start_point_letter in landmark_choices.keys():
start_point = landmark_choices[start_point_letter]
return start_point
else:
print("Sorry, that's not a landmark we have data on. Let's try this again...")
return get_start()
def get_end():
end_point_letter = input("Ok, where are you headed? Type in the corresponding letter: ")
if end_point_letter in landmark_choices.keys():
end_point = landmark_choices[end_point_letter]
return end_point
else:
print("Sorry, that's not a landmark we have data on. Let's try this again...")
return get_start()
print(skyroute())
#graph_search.py
def bfs(graph, start_vertex, target_value):
path = [start_vertex]
vertex_and_path = [start_vertex, path]
bfs_queue = [vertex_and_path]
visited = set()
while bfs_queue:
current_vertex, path = bfs_queue.pop(0)
visited.add(current_vertex)
for neighbor in graph[current_vertex]:
if neighbor not in visited:
if neighbor == target_value:
return path + [neighbor]
else:
bfs_queue.append([neighbor, path + [neighbor]])
def dfs(graph, current_vertex, target_value, visited = None):
if visited is None:
visited = []
visited.append(current_vertex)
if current_vertex == target_value:
return visited
for neighbor in graph[current_vertex]:
if neighbor not in visited:
path = dfs(graph, neighbor, target_value, visited)
if path:
return path
#landmark_choices.py
landmark_choices = {
'a': 'Marine Building',
'b': 'Scotiabank Field at Nat Bailey Stadium',
'c': 'Vancouver Aquarium',
'd': 'Vancouver Lookout',
'e': 'Canada Place',
'f': 'Cathedral of Our Lady of the Holy Rosary',
'g': 'Library Square',
'h': 'B.C. Place Stadium',
'i': 'Lions Gate Bridge',
'j': 'Gastown Steam Clock',
'k': 'Waterfront Station',
'l': 'Granville Street',
'm': 'Pacific Central Station',
'n': 'Prospect Point Lighthouse',
'o': 'Queen Elizabeth Theatre',
'p': 'Stanley Park',
'q': 'Granville Island Public Market',
'r': 'Kitsilano Beach',
's': 'Dr. Sun Yat-Sen Classical Chinese Garden',
't': 'Museum of Vancouver',
'u': 'Science World',
'v': 'Robson Square',
'w': 'Samson V Maritime Museum',
'x': 'Burnaby Lake',
'y': 'Nikkei National Museum & Cultural Centre',
'z': 'Central Park'
}
#vc_landmarks.py
vc_landmarks = {
'Marine Building': set(['Burrard', 'Waterfront']),
'Scotiabank Field at Nat Bailey Stadium': set(['King Edward']),
'Vancouver Aquarium': set(['Burrard']),
'Vancouver Lookout': set(['Waterfront']),
'Canada Place': set(['Burrard', 'Waterfront']),
'Cathedral of Our Lady of the Holy Rosary': set(['Vancouver City Centre', 'Granville']),
'Library Square': set(['Vancouver City Centre', 'Stadium-Chinatown']),
'B.C. Place Stadium': set(['Stadium-Chinatown']),
'Lions Gate Bridge': set(['Burrard']),
'Gastown Steam Clock': set(['Waterfront']),
'Waterfront Station': set(['Waterfront']),
'Granville Street': set(['Granville', 'Vancouver City Centre']),
'Pacific Central Station': set(['Main Street-Science World']),
'Prospect Point Lighthouse': set(['Burrard']),
'Queen Elizabeth Theatre': set(['Stadium-Chinatown']),
'Stanley Park': set(['Burrard']),
'Granville Island Public Market': set(['Yaletown-Roundhouse']),
'Kitsilano Beach': set(['Olympic Village']),
'Dr. Sun Yat-Sen Classical Chinese Garden': set(['Stadium-Chinatown']),
'Museum of Vancouver': set(['Yaletown-Roundhouse']),
'Science World': set(['Main Street-Science World']),
'Robson Square': set(['Vancouver City Centre']),
'Samson V Maritime Museum': set(['Columbia']),
'Burnaby Lake': set(['Sperling / Burnaby Lake', 'Lake City Way', 'Production Way / University']),
'Nikkei National Museum & Cultural Centre': set(['Edmonds']),
'Central Park': set(['Patterson', 'Metrotown'])
}
#vc_metro.py
vc_metro = {
'Richmond-Brighouse': set(['Lansdowne']),
'Lansdowne': set(['Richmond-Brighouse', 'Aberdeen']),
'Aberdeen': set(['Lansdowne', 'Bridgeport']),
'Bridgeport': set(['Aberdeen', 'Templeton', 'Marine Drive']),
'YVR-Airport': set(['Sea Island Centre']),
'Sea Island Centre': set(['YVR-Airport', 'Templeton']),
'Templeton': set(['Sea Island Centre', 'Bridgeport']),
'Marine Drive': set(['Bridgeport', 'Langara-49th Avenue']),
'Langara-49th Avenue': set(['Marine Drive', 'Oakbridge-41st Avenue']),
'Oakbridge-41st Avenue': set(['Langara-49th Avenue', 'King Edward']),
'King Edward': set(['Oakbridge-41st Avenue', 'Broadway-City Hall']),
'Broadway-City Hall': set(['King Edward', 'Olympic Village']),
'Olympic Village': set(['Broadway-City Hall', 'Yaletown-Roundhouse']),
'Yaletown-Roundhouse': set(['Olympic Village', 'Vancouver City Centre']),
'Vancouver City Centre': set(['Yaletown-Roundhouse', 'Waterfront']),
'Waterfront': set(['Vancouver City Centre', 'Burrard']),
'Burrard': set(['Waterfront', 'Granville']),
'Granville': set(['Burrard', 'Stadium-Chinatown']),
'Stadium-Chinatown': set(['Granville', 'Main Street-Science World']),
'Main Street-Science World': set(['Stadium-Chinatown', 'Commercial-Broadway']),
'Commercial-Broadway': set(['VCC-Clark', 'Main Street-Science World', 'Renfrew', 'Nanaimo']),
'VCC-Clark': set(['Commercial-Broadway']),
'Nanaimo': set(['Commercial-Broadway', '29th Avenue']),
'29th Avenue': set(['Nanaimo', 'Joyce-Collingwood']),
'Joyce-Collingwood': set(['29th Avenue', 'Patterson']),
'Patterson': set(['Joyce-Collingwood', 'Metrotown']),
'Metrotown': set(['Patterson', 'Royal Oak']),
'Royal Oak': set(['Metrotown', 'Edmonds']),
'Edmonds': set(['Royal Oak', '22nd Street']),
'22nd Street': set(['Edmonds', 'New Westminster']),
'New Westminster': set(['22nd Street', 'Columbia']),
'Columbia': set(['New Westminster', 'Sapperton', 'Scott Road']),
'Scott Road': set(['Columbia', 'Gateway']),
'Gateway': set(['Scott Road', 'Surrey Central']),
'Surrey Central': set(['Gateway', 'King George']),
'King George': set(['Surrey Central']),
'Sapperton': set(['Columbia', 'Braid']),
'Braid': set(['Sapperton', 'Lougheed Town Centre']),
'Lougheed Town Centre': set(['Braid', 'Production Way / University', 'Burquitlam']),
'Burquitlam': set(['Lougheed Town Centre', 'Moody Centre']),
'Moody Centre': set(['Burquitlam', 'Inlet Centre']),
'Inlet Centre': set(['Moody Centre', 'Coquitlam Central']),
'Coquitlam Central': set(['Inlet Centre', 'Lincoln']),
'Lincoln': set(['Coquitlam Central', 'Lafarge Lake-Douglas']),
'Lafarge Lake-Douglas': set(['Lincoln']),
'Production Way / University': set(['Lougheed Town Centre', 'Lake City Way']),
'Lake City Way': set(['Production Way / University', 'Sperling / Burnaby Lake']),
'Sperling / Burnaby Lake': set(['Lake City Way', 'Holdom']),
'Holdom': set(['Sperling / Burnaby Lake', 'Brentwood Town Centre']),
'Brentwood Town Centre': set(['Holdom', 'Gilmore']),
'Gilmore': set(['Brentwood Town Centre', 'Rupert']),
'Rupert': set(['Gilmore', 'Renfrew']),
'Renfrew': set(['Rupert', 'Commercial-Broadway'])
}
#Assumes that it takes the same amount of time to get from each station to each of its connected neighboring #stations.
#Ideas for further development:
#Can deal with situation where same station for origin and destination
#Maybe Vancouver’s system wants a user interface for employees to update the stations under construction
from graph_search import bfs, dfs
from vc_metro import vc_metro
from vc_landmarks import vc_landmarks
from landmark_choices import landmark_choices
landmark_string = ""
stations_under_construction = ['Richmond-Brighouse']
for letter, landmark in landmark_choices.items():
landmark_string += "{0} - {1}\n".format(letter, landmark)
def get_active_stations():
updated_metro = vc_metro
for station_under_construction in stations_under_construction:
for current_station, neighbouring_stations in vc_metro.items():
if current_station != station_under_construction:
updated_metro[current_station] -= set(stations_under_construction)
else:
updated_metro[current_station] = set([])
return updated_metro
def new_route(start_point=None, end_point=None):
start_point, end_point = set_start_and_end(start_point, end_point)
shortest_route = get_route(start_point, end_point)
if shortest_route:
shortest_route_string = '\n'.join(shortest_route)
print("The shortest metro route from {0} to {1} is:\n{2}".format(start_point,end_point,shortest_route_string))
else:
print("Unfortunately, there is currently no path between {0} and {1} due to maintenance.".format(start_point, end_point))
again = input("Would you like to see another route? Enter y/n: ")
if again == "y":
show_landmarks()
new_route(start_point,end_point)
def show_landmarks():
see_landmarks = input("Would you like to see the list of landmarks again> Enter y/n: ")
if see_landmarks == "y":
print(landmark_string)
def goodbye():
print("Thanks for using SkyRoute!")
def get_route(start_point, end_point):
start_stations = vc_landmarks[start_point]
end_stations = vc_landmarks[end_point]
routes = []
for start_station in start_stations:
for end_station in end_stations:
metro_system = get_active_stations() if stations_under_construction else vc_macro
if len(stations_under_construction) > 0:
possible_route = dfs(metro_system, start_station, end_station)
if not possible_route:
return None
route = bfs(metro_system, start_station, end_station)
if route:
routes.append(route)
shortest_route = min(routes)
return shortest_route
def greet():
print("Hi there and welcome to SkyRoute!")
print("We'll help you find the shortest route between the following Vancouver landmarks:\n" + landmark_string)
def skyroute():
greet()
new_route()
goodbye()
def set_start_and_end(start_point, end_point):
if start_point != None:
change_point = input("What would you like to change? You can enter 'o' for 'origin', 'd' for 'destination', or 'b' for 'both': ")
if change_point == "b":
start_point = get_start()
end_point = get_end()
elif change_point == "o":
get_start()
elif change_point == "d":
end_point = get_end()
else:
print("Oops, that isn't 'o', 'd', or 'b'...")
set_start_and_end(start_point,end_point)
return start_point, end_point
else:
start_point = get_start()
end_point = get_end()
return start_point, end_point
def get_start():
start_point_letter = input("Where are you coming from? Type in the corresponding letter: ")
if start_point_letter in landmark_choices.keys():
start_point = landmark_choices[start_point_letter]
return start_point
else:
print("Sorry, that's not a landmark we have data on. Let's try this again...")
return get_start()
def get_end():
end_point_letter = input("Ok, where are you headed? Type in the corresponding letter: ")
if end_point_letter in landmark_choices.keys():
end_point = landmark_choices[end_point_letter]
return end_point
else:
print("Sorry, that's not a landmark we have data on. Let's try this again...")
return get_start()
print(skyroute())
#graph_search.py
def bfs(graph, start_vertex, target_value):
path = [start_vertex]
vertex_and_path = [start_vertex, path]
bfs_queue = [vertex_and_path]
visited = set()
while bfs_queue:
current_vertex, path = bfs_queue.pop(0)
visited.add(current_vertex)
for neighbor in graph[current_vertex]:
if neighbor not in visited:
if neighbor == target_value:
return path + [neighbor]
else:
bfs_queue.append([neighbor, path + [neighbor]])
def dfs(graph, current_vertex, target_value, visited = None):
if visited is None:
visited = []
visited.append(current_vertex)
if current_vertex == target_value:
return visited
for neighbor in graph[current_vertex]:
if neighbor not in visited:
path = dfs(graph, neighbor, target_value, visited)
if path:
return path
#landmark_choices.py
landmark_choices = {
'a': 'Marine Building',
'b': 'Scotiabank Field at Nat Bailey Stadium',
'c': 'Vancouver Aquarium',
'd': 'Vancouver Lookout',
'e': 'Canada Place',
'f': 'Cathedral of Our Lady of the Holy Rosary',
'g': 'Library Square',
'h': 'B.C. Place Stadium',
'i': 'Lions Gate Bridge',
'j': 'Gastown Steam Clock',
'k': 'Waterfront Station',
'l': 'Granville Street',
'm': 'Pacific Central Station',
'n': 'Prospect Point Lighthouse',
'o': 'Queen Elizabeth Theatre',
'p': 'Stanley Park',
'q': 'Granville Island Public Market',
'r': 'Kitsilano Beach',
's': 'Dr. Sun Yat-Sen Classical Chinese Garden',
't': 'Museum of Vancouver',
'u': 'Science World',
'v': 'Robson Square',
'w': 'Samson V Maritime Museum',
'x': 'Burnaby Lake',
'y': 'Nikkei National Museum & Cultural Centre',
'z': 'Central Park'
}
#vc_landmarks.py
vc_landmarks = {
'Marine Building': set(['Burrard', 'Waterfront']),
'Scotiabank Field at Nat Bailey Stadium': set(['King Edward']),
'Vancouver Aquarium': set(['Burrard']),
'Vancouver Lookout': set(['Waterfront']),
'Canada Place': set(['Burrard', 'Waterfront']),
'Cathedral of Our Lady of the Holy Rosary': set(['Vancouver City Centre', 'Granville']),
'Library Square': set(['Vancouver City Centre', 'Stadium-Chinatown']),
'B.C. Place Stadium': set(['Stadium-Chinatown']),
'Lions Gate Bridge': set(['Burrard']),
'Gastown Steam Clock': set(['Waterfront']),
'Waterfront Station': set(['Waterfront']),
'Granville Street': set(['Granville', 'Vancouver City Centre']),
'Pacific Central Station': set(['Main Street-Science World']),
'Prospect Point Lighthouse': set(['Burrard']),
'Queen Elizabeth Theatre': set(['Stadium-Chinatown']),
'Stanley Park': set(['Burrard']),
'Granville Island Public Market': set(['Yaletown-Roundhouse']),
'Kitsilano Beach': set(['Olympic Village']),
'Dr. Sun Yat-Sen Classical Chinese Garden': set(['Stadium-Chinatown']),
'Museum of Vancouver': set(['Yaletown-Roundhouse']),
'Science World': set(['Main Street-Science World']),
'Robson Square': set(['Vancouver City Centre']),
'Samson V Maritime Museum': set(['Columbia']),
'Burnaby Lake': set(['Sperling / Burnaby Lake', 'Lake City Way', 'Production Way / University']),
'Nikkei National Museum & Cultural Centre': set(['Edmonds']),
'Central Park': set(['Patterson', 'Metrotown'])
}
#vc_metro.py
vc_metro = {
'Richmond-Brighouse': set(['Lansdowne']),
'Lansdowne': set(['Richmond-Brighouse', 'Aberdeen']),
'Aberdeen': set(['Lansdowne', 'Bridgeport']),
'Bridgeport': set(['Aberdeen', 'Templeton', 'Marine Drive']),
'YVR-Airport': set(['Sea Island Centre']),
'Sea Island Centre': set(['YVR-Airport', 'Templeton']),
'Templeton': set(['Sea Island Centre', 'Bridgeport']),
'Marine Drive': set(['Bridgeport', 'Langara-49th Avenue']),
'Langara-49th Avenue': set(['Marine Drive', 'Oakbridge-41st Avenue']),
'Oakbridge-41st Avenue': set(['Langara-49th Avenue', 'King Edward']),
'King Edward': set(['Oakbridge-41st Avenue', 'Broadway-City Hall']),
'Broadway-City Hall': set(['King Edward', 'Olympic Village']),
'Olympic Village': set(['Broadway-City Hall', 'Yaletown-Roundhouse']),
'Yaletown-Roundhouse': set(['Olympic Village', 'Vancouver City Centre']),
'Vancouver City Centre': set(['Yaletown-Roundhouse', 'Waterfront']),
'Waterfront': set(['Vancouver City Centre', 'Burrard']),
'Burrard': set(['Waterfront', 'Granville']),
'Granville': set(['Burrard', 'Stadium-Chinatown']),
'Stadium-Chinatown': set(['Granville', 'Main Street-Science World']),
'Main Street-Science World': set(['Stadium-Chinatown', 'Commercial-Broadway']),
'Commercial-Broadway': set(['VCC-Clark', 'Main Street-Science World', 'Renfrew', 'Nanaimo']),
'VCC-Clark': set(['Commercial-Broadway']),
'Nanaimo': set(['Commercial-Broadway', '29th Avenue']),
'29th Avenue': set(['Nanaimo', 'Joyce-Collingwood']),
'Joyce-Collingwood': set(['29th Avenue', 'Patterson']),
'Patterson': set(['Joyce-Collingwood', 'Metrotown']),
'Metrotown': set(['Patterson', 'Royal Oak']),
'Royal Oak': set(['Metrotown', 'Edmonds']),
'Edmonds': set(['Royal Oak', '22nd Street']),
'22nd Street': set(['Edmonds', 'New Westminster']),
'New Westminster': set(['22nd Street', 'Columbia']),
'Columbia': set(['New Westminster', 'Sapperton', 'Scott Road']),
'Scott Road': set(['Columbia', 'Gateway']),
'Gateway': set(['Scott Road', 'Surrey Central']),
'Surrey Central': set(['Gateway', 'King George']),
'King George': set(['Surrey Central']),
'Sapperton': set(['Columbia', 'Braid']),
'Braid': set(['Sapperton', 'Lougheed Town Centre']),
'Lougheed Town Centre': set(['Braid', 'Production Way / University', 'Burquitlam']),
'Burquitlam': set(['Lougheed Town Centre', 'Moody Centre']),
'Moody Centre': set(['Burquitlam', 'Inlet Centre']),
'Inlet Centre': set(['Moody Centre', 'Coquitlam Central']),
'Coquitlam Central': set(['Inlet Centre', 'Lincoln']),
'Lincoln': set(['Coquitlam Central', 'Lafarge Lake-Douglas']),
'Lafarge Lake-Douglas': set(['Lincoln']),
'Production Way / University': set(['Lougheed Town Centre', 'Lake City Way']),
'Lake City Way': set(['Production Way / University', 'Sperling / Burnaby Lake']),
'Sperling / Burnaby Lake': set(['Lake City Way', 'Holdom']),
'Holdom': set(['Sperling / Burnaby Lake', 'Brentwood Town Centre']),
'Brentwood Town Centre': set(['Holdom', 'Gilmore']),
'Gilmore': set(['Brentwood Town Centre', 'Rupert']),
'Rupert': set(['Gilmore', 'Renfrew']),
'Renfrew': set(['Rupert', 'Commercial-Broadway'])
}