# File: TestBinaryTree.py

# Description: Creates binary trees and runs several tests on them.

import sys

class Node (object):

def __init__(self, data = None, level = 1):

self.data = data

self.left = None

self.right = None

self.level = level

def __str__(self):

return ("DATA:" + str(self.data), "LEVEL:", self.level)

class Tree (object):

def __init__(self, data_list):

self.root = None

# Insert each item in the data list into the tree

for i in data_list:

self.insert(i)

def insert(self, data):

# Make the data the root if the root is empty

if (self.root == None):

self.root = Node(data)

return

# Find a place for this piece of data

level = 1

current = self.root

while (current != None):

level += 1

# If the data is less than the current node, go left

if (data < current.data):

#print(data, "is less than", current.data)

if (current.left == None):

#print("Found a spot to the left of", current.data)

current.left = Node(data, level)

return

current = current.left

# If the data is greater than or equal to the current node,

# go right

elif (data >= current.data):

#print(data, "is greater than or equal to", current.data)

if (current.right == None):

#print("Found a spot to the right of", current.data)

current.right = Node(data, level)

return

current = current.right

# Returns true if two binary trees are similar

def is_similar (self, pNode):

# First check if they have the same height

if (self.get_height() != pNode.get_height()):

return False

# Check if each level has the same values

for level in range(1, self.get_height() + 1):

self_nodes = self.get_level(level)

other_nodes = pNode.get_level(level)

if (self_nodes != other_nodes):

return False

return True

# Prints out all nodes at the given level

def print_level (self, level):

# Return a blank string if the level doesn't exist

if (level < 1) or (level > self.get_height()):

return ''

tree_queue = [self.root]

# Using a Breadth First Search, print all the nodes with a given

# level value

while(len(tree_queue) != 0):

current = tree_queue.pop()

if (current != None):

if (current.level == level):

print(current.data)

tree_queue.append(current.left)

tree_queue.append(current.right)

# Returns a list of all nodes at the given level. Same idea as

# print_level() except you are adding the nodes into a list

def get_level (self, level):

# Return a blank string if the level doesn't exist

if (level < 1) or (level > self.get_height()):

return ''

tree_queue = [self.root]

nodes = []

while(len(tree_queue) != 0):

current = tree_queue.pop()

if (current != None):

if (current.level == level):

nodes.insert(0, current.data)

tree_queue.append(current.left)

tree_queue.append(current.right)

return nodes

# Returns the height of the tree

def get_height (self):

# Check if the tree is empty

if (self.root == None):

return -1

height = 0

tree_stack = [self.root]

# Using a Depth First Search, find the node with the largest

# height.

while(len(tree_stack) != 0):

current = tree_stack.pop(0)

if (current != None):

#print(current.data, "is at level", current.level)

if (current.level > height):

height = current.level

tree_stack.insert(0, current.right)

tree_stack.insert(0, current.left)

return height

# Returns the number of nodes in the left subtree and

# the number of nodes in the right subtree and the root

def num_nodes (self):

# Check if the tree is empty

if (self.root == None):

return 0

left_count = self.count_nodes(self.root.left)

right_count = self.count_nodes(self.root.right)

print("Root has 1 node")

print("Left subtree has", left_count, "and right subtree has", right_count)

return (left_count + right_count + 1)

# Helper function that counts the nodes starting from a given node

def count_nodes(self, start):

node_count = 0

nodes_queue = [start]

while(len(nodes_queue) != 0):

current = nodes_queue.pop()

if (current != None):

node_count += 1

nodes_queue.append(current.left)

nodes_queue.append(current.right)

return node_count

def main():

# Create three trees - two are the same and the third is different

line = sys.stdin.readline()

line = line.strip()

line = line.split()

tree1_input = list (map (int, line)) # converts elements into ints

line = sys.stdin.readline()

line = line.strip()

line = line.split()

tree2_input = list (map (int, line)) # converts elements into ints

line = sys.stdin.readline()

line = line.strip()

line = line.split()

tree3_input = list (map (int, line)) # converts elements into ints

treeA = Tree(tree1_input)

treeB = Tree(tree2_input)

treeC = Tree(tree3_input)

print()

# Test your method is_similar()

print("----- is_similar() -----")

print("Tree A is similar to Tree B:", treeA.is_similar(treeB))

print("Tree A is similar to Tree C:", treeA.is_similar(treeC))

print("Tree B is similar to Tree C:", treeB.is_similar(treeC))

print()

# Print the various levels of two of the trees that are different

print("----- print_level() -----")

print("-- Tree A --")

for i in range(1, treeA.get_height() + 1):

print("Level " + str(i) + ": ")

print(treeA.get_level(i))

print()

print("-- Tree C --")

for i in range(1, treeC.get_height() + 1):

print("Level " + str(i) + ": ")

print(treeC.get_level(i))

print()

# Get the height of the two trees that are different

print("----- get_height -----")

print("Height of Tree A:", treeA.get_height() - 1)

print("Height of Tree C:", treeC.get_height() - 1)

print()

# Get the total number of nodes a binary search tree

print("----- num_nodes() -----")

print("-- Tree A --")

print("That makes", treeA.num_nodes(), "nodes total.")

print()

print("-- Tree C --")

print("That makes", treeC.num_nodes(), "nodes total.")

if __name__ == "__main__":

main()

# File: RadixSort.py

# Description: Performs a radix sort on a given list of letters and

# numbers.

import sys

class Queue (object):

def __init__ (self):

self.queue = []

# add an item to the end of the queue

def enqueue (self, item):

self.queue.append (item)

# remove an item from the beginning of the queue

def dequeue (self):

return (self.queue.pop(0))

# check if the queue if empty

def is_empty (self):

return (len(self.queue) == 0)

# return the size of the queue

def size (self):

return (len(self.queue))

# Input: a is a list of strings that have either lower case

# letters or digits

# Output: returns a sorted list of strings

def radix_sort (a):

# a list will store all of our queue objects

queues = []

big_queue = Queue()

# find the length of the longest string. This will be how many passes

# we will perform.

num_passes = 0

for item in a:

if len(item) > num_passes:

num_passes = len(item)

#print("we will perform", num_passes, "passes")

# populate the list with queues

for i in range(37):

queues.append(Queue())

# enqueue items to the big queue

for i in range(len(a)):

while len(a[i]) < num_passes: #review this

a[i] += '#'

big_queue.enqueue(a[i])

# sort items

for i in range(1, num_passes + 1):

for j in range(big_queue.size()):

item = big_queue.dequeue()

index = get_index(item, i)

#print(item, "goes into index", index)

queues[index].enqueue(item)

#print_queues(queues, big_queue)

# return items in queues to the Big Queue

for k in range(len(queues)):

while queues[k].size() > 0:

item = queues[k].dequeue()

big_queue.enqueue(item)

# Remove '#' padding from each of the strings

results = []

for i in range(big_queue.size()):

item = big_queue.dequeue()

new_item = ''

for j in range(len(item)):

if item[j] != '#':

new_item += item[j]

results.append(new_item)

return results

# Prints how many items are in a queue

def print_queues(queues, big_queue):

for i in range(len(queues)):

print("Q" + str(i) + ":", queues[i].size())

print("Big Queue:", big_queue.size())

# Gets which queue the string will go into

def get_index(item, i):

if item[-i] == '#':

return 0

if item[-i].isdigit():

return eval(str(item)[-i])

if item[-i].isalpha():

return ord(item[-i]) - 86

def main():

# read the number of words in file

line = sys.stdin.readline()

line = line.strip()

num_words = int (line)

# create a word list

word_list = []

for i in range (num_words):

line = sys.stdin.readline()

word = line.strip()

word_list.append (word)

# print word_list

#print (word_list)

# use radix sort to sort the word_list

sorted_list = radix_sort (word_list)

# print the sorted_list

print (sorted_list)

if __name__ == "__main__":

main()

# File: Chess.py

# Description: Given the size of a chess board, return the number of

# solutions in which 8 queens can stand without threatening each other.

import sys

class Queens (object):

def __init__ (self, n = 8):

self.board = []

self.n = n

self.solutions = 0

for i in range (self.n):

row = []

for j in range (self.n):

row.append ('*')

self.board.append (row)

# print the board

def print_board (self):

for i in range (self.n):

for j in range (self.n):

print (self.board[i][j], end = ' ')

print ()

print ()

# check if a position on the board is valid

def is_valid (self, row, col):

for i in range (self.n):

if (self.board[row][i] == 'Q') or (self.board[i][col] == 'Q'):

return False

for i in range (self.n):

for j in range (self.n):

row_diff = abs (row - i)

col_diff = abs (col - j)

if (row_diff == col_diff) and (self.board[i][j] == 'Q'):

return False

return True

def solve(self, col):

if (col == self.n):

self.solutions += 1

#self.print_board()

return

for i in range(self.n):

if self.is_valid(i, col):

self.board[i][col] = 'Q'

self.solve(col + 1)

self.board[i][col] = '*'

def main():

# read the size of the board

line = sys.stdin.readline()

line = line.strip()

n = int (line)

# create a chess board

game = Queens (n)

# place the queens on the board and count the solutions

game.solve(0)

# print the number of solutions

print(game.solutions)

if __name__ == "__main__":

main()